原文  中文翻译  参考：Kai – An Open Source Implementation of Amazon’s Dynamo

本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇，个人觉得有两个原因：

1. 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如：DHT（分布式哈希表）、consistent hashing（一致性哈希）、多版本、副本策略和Merkle tree 等。
2. 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法，并总结了Dynamo 在实现、配置等方面的经验与教训，对后来者非常有借鉴意义。

下面文章将就Dynamo 实现特点和具有的特性逐一分析：

一、名词解释

文章中使用了一些常用的或者不常用的一些专业名词：

1. (N,R,W)：这三个面向上层应用的参数是Dynamo 特色之一。N 指的是读取或者写入的节点个数；R 指的是读取至少R 个副本才算读成功；W 指的是写入至少W 个副本才算成功。
2. 松散仲裁：sloppy quorum。在文中松散仲裁解决的是某些副本暂时性不可读取或者写入的情况。指的是当进行读写操作时，并不需要所涉及的N 个节点都成功，满足对应的R、W 即可。
3. 提交转移：Hinted handoff。这个是和松散仲裁相辅相成的，当某个节点因暂时性节点失效发生写操作失败时，会将操作转移到其他节点，并在其他节点有一个暗示，表示这个副本应该是保存在哪个节点，自己只是代替保存。
4. 一致性哈希：consistent hashing。简单而言，一致性哈希指的是将key 哈希的结果头尾（0 和 ）相连，形成一个环（Ring），那么所有的key-value 对都响应的映射到这个环上。所有的存储节点也采取相同的哈希函数，从而也映射到同一个环上，每个存储节点负责保存从环上的前续节点到该节点区间（Range）的key-value 对。实现程序可以参考这里。
5. Merkle tree。一种树状哈希的数据结构，每个叶子节点保存的是对应数据的哈希结果，每个父节点是所有子节点的哈希结果，这样每个叶子节点数据在发生变化时，其所有直接、间接父节点都可以察觉，且每次变化的节点个数为log(N)。这样减少了节点间一致性检查的通信流量。
6. 耐久性：durability。我的理解就是数据持久化存储从而保证数据不丢失的性质。比如直接写到硬盘就比先写缓存再定时flush 到磁盘的耐久性要好。
7. 服务水平协议：SLA。即QS，即向应用程序保证规定时间内交付完成的任务。文中特别强调在99.9%的服务需在300 ms 内响应。
8. 首选列表：perference list。负责存储某个特点key 的节点列表称为首选列表，这也是对应的key-value 可能保存的节点位置的列表。考虑到节点失效，首选列表可能超过N 个节点。并且key 之后N 个节点对应的物理节点可能少于N 个，所以需要跳过这些重复的物理节点。最后辨别首选列表和N 的区别：首选列表是每次可以负责写入或者读取节点的列表，N 是实际上应该读取或者写入的节点的个数。
9. (key,object,context)：Dynamo 保存key-value 对的格式，上下文context 是该key-value 数据的元数据信息。

二、性能上的取舍

考虑到实际应用的环境和需求，Dynamo 进行了以下取舍：

1. 去中心化的设计避免集中控制带来瓶颈问题。每个节点保存有所有节点的路由信息，并都可以单独接受、调节客户端请求，因此规模限制在上百台节点。
2. 牺牲强一致性提供高可用性和“永远可写”。系统尽全力不向客户端反馈写失败，在出现版本不一致时也采用先写入后仲裁的方式
3. 上层不同应用根据需求在一致性、延时和可用性上进行协调。Dynamo 采用(N,R,W) 三个参数控制读写操作涉及到首选清单节点个数，参与成功读最少节点数，参与成功写最少节点数。较大的N 会在多个节点上产生副本，较小的R 可能会返回不一致的数据，较小的W 延时也小，但存在安全性问题
4. 不考虑安全因素。因为Dynamo 是内部使用的一个key-value 存储系统，所以没有考虑安全因素
5. 异构性。节点虽然都是普通的主机，但在性能上还是有差异的，Dynamo 可以根据节点负载情况调整请求。

三、Dynamo 分区划分方案

策略一：每个节点T 个随机Token 和基于Token 值进行划分。这种方法类似于consistent hashing 中加入虚拟节点（这里对应Token ）。两个连续的Token 之间为一个区域（Range），因为哈希空间是组成环形的，所以最后的Token 和第一个Token 也组成一个区域。这个方案存在几个问题：

1. 节点加入时需要从附近节点“偷”数据，所以其他节点需要扫描自身需要交付给新节点的数据，这个过程是资源消耗型的过程，因此最低优先级，从而会使加入过程变得会很长。
2. 节点Merkle tree 也要重新计算，同样也非常消耗资源。
3. 无法key 空间的快照。（暂时还不明白为什么要建立key 空间的快照）
4. 最后也是最重要的原因就是这个策略将数据分区和数据分配交织在一起了，数据的分区会随着节点的加入而变化。

策略二：每个节点T 个随机Token 和等大分区。既然分区会随节点加入删除动态变化，那么我们就把环形空间划分为Q 个等大的分区。S 代表系统中节点个数，Q>>N 且 Q>>S*T ，即分区个数远大于每次读写涉及的节点个数以及虚拟节点个数。这样虚拟节点实际上是和策略一一样的，每个节点负责区域的就是自己所在分区到前一节点的所在分区之间所有分区的key-value 对。（这里我都假设副本为一）

策略三：每个节点Q/S 个Token 和等大分区。每个Token 对应着一个分区（这个怎么实现的？如果是哈希不可能分的这么平均）。新加入节点和删除节点如何保留这种性质也没有谈。

上图对应的是三种划分方案（A、B、C 分别是保存key k1 的三个节点，N=3 的情况。箭头对应着Token 的位置），下图是三种方案在每个节点保存不同数量元数据情况下的效率。

四、三个九

99.9% 指的是系统超过99.9% 的请求能够在规定时间内响应，文中有这段原话：

在文中多次提到了99.9%，这体现了Amazon 工程师出于用户体验考虑对性能的不断追求。（In this paper there are many references to this 99.9th percentile of distributions,  which reflects Amazon engineers’ relentless focus on performance from the perspective of the customers’experience.）

那我们看看Amazon 的工程师做了哪些工作来满足这个需求。

1. O(0) 零跳的DHT 解决方案，避免类似于Chord 和Pastry 的多跳路由。每个节点通过类似于心跳的Gossip ，了解对等节点处理的区域（Range）和路由信息，知道其他节点的加入或者离开。可以直接定位请求到指定的存储节点。
2. 协调器（coordinator）是用来负责读写操作的节点。通常是首选列表中前N 个节点中的第一个节点（这里的N 指的是N、R、W 中的N）。如果请求是通过负载均衡器的，那么协调器可能是任意随机节点，这时如果该节点是首选列表中前N 个节点，则处理请求，如果不是则该节点将请求转发到首选列表中第一个出现在前N 个节点中的节点。
3. 写一定涉及磁盘操作所以平均延时要大。通过牺牲耐久性可换取更好的性能（延时），每次写入都写到内存中，由另一个写线程定期的将这些数据写入到磁盘中。权衡耐久性可以选择N 个中的一个节点执行“耐久写”。
4. 客户端驱动的负载均衡器。客户端定期随机选择一个节点获取全部节点状态视图，客户端可以根据这些信息从首选列表中为给定的key 选定响应的节点集。

五、Put 和 Get 过程

不考虑节点失效，我们来看看一个完整的put 写数据和get 读数据的过程。通常两种请求都有两个策略来选择一个节点来响应请求。(1)通过一个负载均衡器根据负载情况路由请求；(2)使用一个分区敏感的客户端直接路由请求到合适的节点。（第一个方法优点在于简单，客户端不用保存Dynamo 系统的信息，请求可能分配到环上任意节点；第二个方法优点在于低延时，避免了一次潜在的转发过程。）

写入和读取操作会涉及到首选列表中前N 个可用节点，当前N 个节点都可用时将都被访问，如果有节点故障或者不可达则跳过这些节点，选取首选列表中排名较低的节点。每次将数据写入到N 个节点，当有超过W-1 个节点返回写入成功则写操作成功。读操作同理当返回R 个节点数据则任务读成功，如果协调器收集到多个版本则进行协调，则返回给客户端它认为没有因果关系的版本，然后再将协调后的版本写回。

应对暂时性节点失效的方法是文中4.6 提到的提交转移（hinted handoff），当无法写入到某个原始节点时，将数据暂时性的写入到其他节点（比如可以是首选列表中第N+1 个节点），然后对这个数据标记一个暗示，表示其本应该写入的原始节点。当该节点检测到原始节点恢复时，将该数据发送回给原始节点然后在本地删除该数据。

Dynamo 使用副本同步的方式应对永久性故障。通过Merkle tree 检查副本间不一致并减少传输数据量。

六、向量时钟“vector clocks”

向量时钟是（节点：计数器）即(node:counter) 的列表，保存在上下文context 中。通过向量列表可以判断两个版本是平行分支还是因果顺序（偏序关系）。

如上图，时间箭头所指的终点是起点的结果。(A:0)->(A:1)->(A:1,C:1)->(A:2,C:1)和 (A:0)->(A:1)->(A:1,C:1)->(A:1,B:1,C:1) 两条链中每两个向量时钟都是有因果顺序的，因为任意两个向量时钟都可以比较大小。而(A:2,C:1) 和(A:1,B:1,C:1) 之间是独立的，相当于两个平行的版本。同理 (A:2,C:2) 和(A:3,B:2,C:1) 也是两个无因果关系的平行版本。

七、Mrekle tree

如之前所讲，Mrekle tree 是哈希树，树叶节点是key 的哈希，父节点是孩子节点的哈希。在Dynamo 中（策略三），为每个虚拟节点的范围（Range ）建立一个Mrekle tree。这样虚拟节点和Range 与Mrekle tree 是一对N 的关系，每个节点保存N 个Mrekle tree。相关虚拟节点比对之间共有的Range 的Mrekle tree 即可进行一致性检查。

通过下图可以了解Mrekle tree 从根节点到叶子节点的一致性检查过程。