一、系统概述
1、Amazon平台概述      
Amazon平台是一个由数百服务组成的面向服务的架构，其秉承高度去中心化、松散耦合、完全分布式的原则，具体架构参考下图。

在这种环境中，尤其需要一个始终可用的存储系统，由此，Dynamo诞生了。

2、Dynamo概述
Dynamo是Amazon提供的一款高可用的分布式Key-Value存储系统，其满足可伸缩性、可用性、可靠性。
CAP原理满足：通过一致性哈希满足P，用复制满足A，用对象版本与向量时钟满足C。用牺牲C来满足高可用的A，但是最终会一致。但是，是牺牲C满足A，还是牺牲A满足C，可以根据NWR模型来调配，以达到收益成本平衡。
Dynamo内部有3个层面的概念：
Key-Value：Key唯一标识一个数据对象，Value标识数据对象实体，通过对Key来完成对数据对象的读写操作。
节点node：节点是指一个物理主机。在每个节点上，会有3个必备组件：请求协调器（request coordination）、成员与失败检测、本地持久引擎（local persistence engine），这些组件都由Java实现。本地持久引擎支持不同的存储引擎，最主要的引擎是Berkeley Database Transactional Data Store（存储数百K的对象更合适），其它还有BDB Java Edtion、MySQL以及一致性内存Cache。本地持久化引擎组件是一个可插拔的持久化组件，应用程序可以根据需要选择最合适的存储引擎，比如：如果存储对象的通常为数千字节则可以选择BDB，如果是更多尺寸则可以选择MySQL。生产中，Dynamo通常使用BDB事物数据存储。
实例instance：从应用的角度来看就是一个服务，提供IO功能。每个实例由一组节点组成，这些节点可能位于不同的IDC，这样IDC出现问题也不会导致数据丢失，这样会有更好的容灾和可靠性。

二、背景条件
1、系统假设与要求
（1）查询模型
基于Key-Value模型，而不是SQL即关系模型。存储对象比较小，通常小于1MB。

（2）ACID属性
传统的关系数据库中，用ACID（A原子性、C一致性、I隔离性、D持久性）来保证事务，在保证ACID的前提下往往有很差的可用性。Dynamo用弱一致性C来达到高可用，不提供数据隔离I，只允许单Key更新。

（3）效率
在廉价的机器上满足SLA，通过配置来满足延时和吞吐量的要求，因此，必须在性能、成本、可用性和持久性保证之间做权衡。

（4）其它假设
Dynamo仅在Amazon内部使用，因此，认为其使用环境是可信赖的。

2、服务水平协议（SLA）
        所谓服务水平协议是指客户端和服务端在某几个指标上达成一致的一个协议，通常包括客户端请求API的速率、服务端的预期延时，比如：在客户端每秒500个请求负载的高峰时，99.9%的响应时间为300毫秒。
        一般业界，对这种面向性能的SLA采用平均数（average）、中值（median）和预期变化（expected variance）。但是这些指标只能对大多数客户端有良好体验，而不是所有。为了解决这个问题，Dynamo采用99.9%百分位来代替这些指标。

3、设计考虑（复制数据）
传统的数据复制算法，在出现故障时，为了保证数据一致性被迫牺牲掉可用性，即：与其不能确定数据是否正确，不如让数据一直不可用直到数据绝对正确时。

但是，一个高度灵活的系统应该能够让用户知道在何种情况下能到达哪些属性，Dynamo就是如此。

对于故障是常态的系统来说，采用乐观复制技术可以提供系统的可用性，但带来的问题是需要检测并协调解决冲突，协调解决冲突的过程又包含两个问题，即：何时协调和由谁协调。Dynamo的设计是数据存储最终一致，即所有更新操作最终到达所有副本。

（1）何时协调
无外乎两种情况：写或者读时协调冲突。
传统数据存储在写时协调冲突，即如果给定时间内数据不能达到所要求的所有或大多数副本数，则写入可能会被拒绝。
Amazon认为拒绝客户的更新操作会导致糟糕的用户体验，典型应用是购物车服务，即使出现故障，客户仍然可以向购物车添加或者删除物品，基于此，Dynamo的目标定位为“永远可写”（always writable）即数据存储的“写”是高可用的。也就是说Dynamo为了确保“写”永远不会被拒绝，那么数据存储在读时协调冲突。

（2）由谁协调
无外乎两种情况：由数据存储本身或客户端应用程序来协调。
如果是数据存储本身协调，则只能使用简单策略来协调冲突的更新操作，比如：“最后一次写入获胜”（last write wins）。
如果是客户端应用程序协调，则应用程序可以根据业务需求来选择最适合协调冲突的方法。
Dynamo选择了后者，典型应用还是购物车服务，返回所有数据对象版本，最后选择合并完冲突的版本。

三、关键技术
Dynamo作为一类分布式系统的典型代表，其众多关键技术给其带来一系列的优势，具体参看下表：

1、数据分区
Hash算法：使用MD5对Key进行Hash以产生一个128位的标示符，以此来确定Key的存储节点。

为了达到增量可伸缩性的目地，Dynamo采用一致性哈希来完成数据分区。在一致性哈希中，哈希函数的输出范围为一个圆环，如图2所示，系统中每个节点映射到环中某个位置，而Key也被Hash到环中某个位置，Key从其被映射的位置开始沿顺时针方向找到第一个位置比其大的节点作为其存储节点，换个角度说，就是每个系统节点负责从其映射的位置起到逆时针方向的第一个系统节点间的区域。

一致性哈希最大的优点在于节点的扩容与缩容，只影响其直接的邻居节点，而对其它节点没有影响。这样看似很完美了，但是亚马逊没有因此而停止脚本，这是其伟大之处，其实还存在两个问题：节点数据分布不均匀和无视节点性能的异质性。为了解决这两个问题，Dynamo对一致性哈希进行了改进而引入了虚拟节点，即每个节点从逻辑上切分为多个虚拟节点，每个虚拟节点从逻辑上看像一个真实节点，这样每个节点就被分配到环上多个点而不是一个单点。

2、数据复制
为了实现高可用，Dynamo将每个数据复制到N台主机上，其中N是每个实例（per-instance）的配置参数，建议值为3。每个Key被分配到一个协调器（coordinator）节点，协调器节点管理其负责范围内的复制数据项，其除了在本地存储其责任范围内的每个Key外，还复制这些Key到环上顺时针方向的N-1个后继节点。这样，系统中每个节点负责环上从其自己位置开始到第N个前驱节点间的一段区域。具体逻辑见图2，图中节点B除了在本地存储键K外，还在节点C和D处复制键K，这样节点D将存储落在范围(A, B]、(B, C]和(C, D]上的所有键：

对于一个特定的键都有一个首选节点列表，由于虚拟节点的存在，为了解决节点故障的问题，构建首先节点列表时会跳过环上某些位置，让这些节点分别位于不同的物理节点上，以保证高可用。

为了保证复制时数据副本的一致性，Dynamo采用类似于Quorum系统的一致性协议实现。这里涉及到三个关键参数(N, R, W)，其中，N是指数据对象复制到N台主机，协调器负责将数据复制到N-1个节点上，亚马逊建议N配置为3，R代表一次成功的读取操作中最小参与节点数量，W代表一次成功的写操作中最小参与节点数量。R+W>N，则会产生类似于Quorum的效果。该模型中，读（写）延迟由最慢的R(W)复制副本决定，为了得到比较小的延迟，R和W通常配置为小于N。亚马逊建议(N, R, W)设置为(3, 2, 2)以兼顾性能与可用性。R和W直接影响性能、扩展性和一致性，如果W设置为1，则一个实例中只要有一个节点可用，也不影响写操作，如果R设置为1，只要有一个节点可用，也不会影响读请求，R和W值过小则影响一致性，过大则可用性，因此，需要在R和W两个值之间平衡，这也是Dynamo的一个亮点之一。

3、版本合并
由前文可知，Dynamo为了保证高可用，对每份数据都复制了多份（建议3份），在数据没有被异步复制到所有副本前，如果有get操作会取到不一致的数据，但是Dynamo提供最终一致性。在亚马逊平台中，购物车就是这种情况的典型应用，为了保证购物车永远可用，对任何一个副本的任何一次更改操作的结果都会当做一个数据版本存储起来，这样当用户get时就会取到多个版本，这样也就需要做数据版本合并了。Dynamo将合并工作推给应用程序，在这里就是购物车get时处理。

Dynamo用向量时钟来标识同一数据在不同节点上多个副本之间的因果关系。向量时钟实际上就是一个列表，列表的每个节点是一个(node, counter)对，即(节点，计数器)列表。数据版本之间的关系要么是因果关系，要么是平行关系，关系判断依赖于计数器值大小，如果第一个时钟对象的计数器小于或等于所有其它时钟对象的计数器时则是因果关系，那么因是果的祖先可以认为是旧版数据而直接忽略，否则是平行关系，那么就认为数据版本产生了冲突，需要协调并合并。

在Dynamo中，当客户端更新一个对象时，必须指定更新哪个版本数据，更新版本依赖于早期get操作时获得的向量时钟。

向量时钟的使用过程图上图3所示，具体流程解析如下：
客户端写入一个新对象。节点Sx处理了这个请求，处理对key的写：序列号递增，并创建数据的向量时钟，这样在该节点上生成对象D1和向量时钟[(Sx, 1)]。
客户端更新该对象。假设由同样的节点即Sx处理了这个请求，由于该节点有了D1和向量时钟[(Sx, 1)]，则更新该对象后在该节点上生成对象D2和向量时钟[(Sx, 2)]，D2继承自D1，即D2覆写D1，计数器增1，但其它节点此时可能是D1，也可能是D2，这取决于网络和节点状态。
假设同一客户端更新该对象但被不同的服务器处理了。节点Sy处理了这个请求，则更新该对象后在该节点上生成对象D3和向量时钟[(Sx, 2), (Sy, 1)]。
假设另一客户端读取到了D2并尝试更新它但被另一个不同的服务器处理了。节点Sz处理了这个请求，则更新该对象后在该节点上生成对象D4和向量时钟[(Sx, 2), (Sz, 1)]。
节点数据版本回收。现在有4个版本的数据存在并在各个节点之间传递了，当节点收到D3或D4时，会根据向量时钟将D1和D2回收掉，因为其是D3和D4的祖先。但是收到D3和D4的节点，根据向量时钟发现它们之间是并行关系，则保留二者，并在客户端get时将二者都提交给客户端由其来协调并合并版本。
假设客户端读取数据，则会获取到D3和D4，根据两者的向量时钟，会合并为D5和向量时钟[(Sx, 2), (Sy, 1), (Sz, 1)]，节点Sx协调写操作，并更新对象和向量时钟。
从上面的过程中可以看出，在节点比较多且情况极端时，向量时钟列表会增长，Dynamo对此采用时钟截断方案来解决此问题，即(node, counter)对带有时间戳，在数目达到阈值（比如：10）时，将最早的一对从向量时钟中删除。

4、故障检测
（1）Ring Membership
每个节点启动时存储自己在环上的映射信息并持久化到磁盘上，然后每个节点每隔一秒随机选择一个对等节点，通过Gossip协议传播节点的映射i信息，最终每个节点都知道对等节点所处理范围，即每个节点都可以直接转发一个key的读/写操作到正确的数据集节点，而不需要经过中间路由或者跳。

（2）External Discovery
如果人工分别往Dynamo环中加入节点A和B，则Ring Membership不会立即检测到这一变化，而出现暂时逻辑分裂的Dynamo环（A和B都认为自己在环中，但是互相不知道对方存在）。Dynamo用External Discovery来解决这个问题，即有些Dynamo节点充当种子节点的角色，在非种子节点中配置种子节点的IP，所有非种子节点都与种子节点协调成员关系 。

（3）Failure Detection
Dynamo采用类Gossip协议来实现去中心化的故障检测，使系统中的每个节点都可以了解其它节点的加入和likai

5、故障处理
传统的Quorum，在节点故障或者网络故障情况下，系统不可用。为了提高可用性，Dynamo采用Sloppy Quorum和Hinted Handoff，即所有读写操作由首选列表中的前N个健康节点执行，而发往故障节点的数据做好标记后被发往健康节点，故障节点重新可用时恢复副本。

如上面所示Dynamo配置N为3。如果在写过程中节点A暂时不可用（Down或无法连接），则发往A的副本将被发送到节点D，发到D的副本在其原始数据中有一个hint以表明节点A才是副本的预期接收者，D将副本数据保存在一个单独的本地存储中，在检测到A可用时，D尝试将副本发到A，如果发送成功，D会将数据从本地存储中删除而不会降低系统中的副本总数。

一个高可用的存储系统具备处理整个IDC故障（断电、自然灾害、网络故障灯）的能力是非常重要的，Dynamo就具备此能力。Dynamo可以配置成跨多个IDC复制对象，即key的首选列表由跨多个IDC的节点组成，这些IDC之间由高速专线连接，跨多个IDC的复制方案使得Dynamo能够处理整个IDC故障。

此外，为了处理在hinted副本移交会预期节点之前该副本不可用的情况，Dynamo实现了anti-entropy协议来保持副本同步，为了更快递检测副本之间的不一致性并减少传输量，Dynamo采用MerkleTree。

6、扩容/缩容
（1）扩容
当一个新节点X加入到系统中时，其得到一些随机分配到环上的token，节点X会负责处理一个key range，而这些key在节点X加入前由现有的一些节点负责，当节点X加入后，这些节点将这些key传递给节点X。以图2为例，假设节点X添加到环中A和B之间的位置，当X加入到系统中后，其负责的key范围为(F, G], (G, A], (A, X]，节点B、C和D都各自有一部分不再需要存储的key范围，即在X加入前，B负责(F, G], (G, A], (A, B]；C负责(G, A], (A, B], (B, C]；D负责(A, B], (B, C], (C, D]，而在X加入后，B负责(G, A], (A, X], (X, B]；C负责(A, X], (X, B], (B, C]；D负责(X, B], (B, C], (C, D]。节点B、C和D在收到节点X加入的确认信号后出发这一过程。
（2）缩容
当从系统中删除一个节点时，key的重新分配情况与步骤（1）正好相反。
       
7、读/写操作
读取和写入由请求协调组件执行，每个客户端请求都将导致在处理该请求的节点上创建一个状态机，每个状态机都包含以下逻辑：
标识负责一个key的节点；
发送请求；
等待回应；
可能的重试处理；
加工和包装返回客户端响应。

每个状态机实例只处理一个客户端请求，如果是一个读请求，则状态机如下：
发送读请求到相应结点；
等待所需的最低数量的响应；
如果在给定的时间内收到的响应太少，则请求失败；
否则收集所有数据的版本，并确定要返回的版本；
如果启用版本合并，则执行语法协调并生成一个对客户端不透明的写上下文，其中包含一个囊括所有版本的向量时钟。
返回读取响应给客户端后，状态机等待一段时间以接受任何悬而未决的响应，如果任何响应返回了过时的版本，则协调员用最新版本更新这些节点，以完成读修复。
写请求通常跟随在读请求之后，则协调员由读操作答复最快的节点充当，这种优化能提高读写一致性。

五、解决问题
1、可用性
完全去中心化，无单点，永远可写。

2、伸缩性
带虚拟机节点的一致性hash：一致性hash解决扩容/缩容问题，虚拟节点解决机器异质性问题。

3、可靠性
数据复制多份副本，用向量时钟解决版本合并问题。

4、可配置
平衡性可调，即根据（N,W,R）模型平衡可用性和一致性，建议模型参数为（3,2,2）。