Dynamo是为亚马逊平台构建的一种高可用且可扩展的分布式数据存储，亚马逊的一些核心服务使用该系统提供“始终在线”的体验。根据CAP定理，Dynamo牺牲了部分一致性（但也达到了最终一致性）以实现近乎严苛的可用性要求。Dynamo允许服务所有者通过调整参数N，R和W来定制存储系统，从而在所需的性能，持久性和一致性直接达到平衡。

需求：

1. 为了支持持续增长，Dynamo需要高度可扩展。
2. 最轻微的中断也会造成重大的财务后果并影响客户信任度，平台可靠性要求极高，由此引出需要Dynamo这样高可用的存储技术。
3. 能够处理由数百万个组件组成的基础架构中的故障。Dynamo需要以一种将故障处理视为正常情况的方式构建，而不会影响可用性或性能。
4. Dynamo并不关注数据完整性和安全性问题，而是为可信赖的环境而构建的。
5. Dynamo面向仅要求键/值访问的应用程序，其主要重点是高可用性，即使网络分区或服务器出现故障，更新也不被拒绝。
6. Dynamo是为对延迟敏感的应用程序而构建的，这些应用程序需要在几百毫秒内执行至少99.9%的读写操作。（Dynamo实现时避免了多个节点路由请求，可以看作一个零跳DHT，其中每个节点在本地维护足够的路由信息，以便将请求直接路由到相应的节点）

Dynamo使用的技术并不新颖，而是将已有技术综合来实现可伸缩性和可用性：使用一致性哈希对数据进行分区和复制，并通过对象版本控制促进一致性。更新过程中副本之间的一致性通过quorum-like技术和分散的副本同步协议来维护。 Dynamo使用基于gossip的分布式故障检测和成员身份协议。 Dynamo是去中心化的系统，几乎不需要手动管理。管理员可以在Dynamo中添加和删除存储节点，而无需任何手动分区或重新分配。

背景：

亚马逊平台的数百种服务服务中的一些是无状态的（即，汇总来自其他服务的响应的服务），而另一些是有状态的（即，通过对存储在持久性存储中的状态执行业务逻辑来生成其响应的服务）。而传统使用的关系数据库并不适合持久状态的存储。持久状态服务大部分只需要通过key存储和检索数据，而不需要RDBMS提供的复杂查询和管理功能。这种过多的功能需要昂贵的硬件和熟练的技术人员来进行操作从而导致非常低效。同时关系数据库可扩展性很差且不适合采用智能分区方案。

Dynamo存储要求：

查询模型：对由键唯一标识的数据项（即kv键值对象）的简单读写操作。状态存储为由唯一键标识的二进制对象（即blob）。由于没有操作跨越多个数据项，也不需要relational schema。
ACID属性：提供ACID保证的数据存储的可用性往往很差。Dynamo的目标应用程序是一致性较弱的应用程序（ACID中的“ C”）。所以Dynamo不提供任何隔离保证，并且仅允许单键更新。
效率：满足严格的SLA（Service Level Agreements，服务水平协议，是客户端和服务签订的一项正式协商的合同，就几个与系统相关的特征达成协议，其中最突出的包括客户端对特定API的预期请求速率分布以及在某些条件下预期的服务延迟），始终达到延迟和吞吐量要求。与传统的使用平均值，中位数和预期方差来描述性能的SLA方法相比，亚马逊采用在分布的99.9％处表达和度量，这样会显著增加成本，但可以给重要客户带来更好的整体体验。
可伸缩性：Dynamo横向扩展添加节点时对系统的影响很小。
对称性：Dynamo中的每个节点应与其其他节点承担相同的责任；不应有承担特殊角色或额外职责的可区分节点。
异构性：Dynamo需要能够在其运行的基础架构中利用异构性。例如工作分配必须与各个服务器的能力成比例。

分区算法：

Dynamo使用一致性哈希来动态分区和在多个存储主机之间分配负载。

首先说明一点，哈希函数有一条性质是当输入的key种类足够多时，计算结果是很离散的。怎么理解呢？假如所有key的结果最后算出来在一个圆形区域内，在这个区域内用方框框范围，不管怎么框，框中的结果数量都是差不多的。

传统的分布式数据服务器组织方式就是哈希函数，而这种根据节点数取模的映射方式是一种非常好的负载均衡方式，假设节点数是3，业务中高频key是a个，中频key是b个，低频key是c个，根据哈希函数性质（输入的key的值哪怕很接近，哈希后的计算结果也很离散，和输入规律没有关系），取模后3个节点上均含高频key a/3个，中频key b/3个，低频key c/3个，三个节点的负载几乎一样。这种方式的前提是key的种类需要足够多，最好是身份证号这种类型；如果key的种类很少，比如以国家名作为key存储交易信息，交易频繁的国家也就是中美，属于中国的key全在一个服务器上，属于美国的key全在另一个服务器上，最后剩下的一台服务器就几乎每什么负载，负载不均衡（所以在设计分布式数据查询的hot key时不要让hot key集中在有限几个上，而要让hot key是一批）。但这种方式存在的问题在于：当节点增删，即 N 值变化时，整个哈希表（Hash Table）需要重新映射，这便意味着大部分数据需要在节点之间移动，数据迁移太繁重。

一致性哈希利用服务器自带的字符串信息（ip地址，host name，mac地址都行）用哈希函数计算后映射到环（最大的哈希值环绕到最小的哈希值形成环，例如0到2^32 - 1）上。需要处理的业务请求无非是增删查改，以增为例，存储请求的key进行哈希处理后对应在环上的某个位置，然后在环上顺时针找，将kv键值对交给遇到的第一个服务器对应的节点存储。

上图中Key K就交给B节点处理，每个每个节点都负责它和它在环上的前任节点之间的环中区域。

一致性哈希的好处是节点的离开或到达只会影响其直接邻居，而其他节点则不受影响。但它也存在缺点：

1. 环上每个节点的随机位置分配导致数据和负载分布不均衡。虽然哈希函数的计算结果具有离散性，但离散性需要key的种类足够多才能够体现。假如服务器很少，例如只有三台，是很难保证哈希计算的结果刚好是这三台服务器把环三等分的，从而导致负载不均衡。
2. 忽略了节点的异构性。不能做到任务分配与各个服务器的能力成比例。
3. 数据迁移发生在两个相邻节点之间，如果每个节点存储的数据量很大，那数据迁移带来的压力势必会影响参与迁移的节点正常的请求，导致不可用。

解决方案就是引入虚节点，所谓的虚拟节点其实就是在一个物理节点上虚拟出多个逻辑节点。当新节点添加到系统时，会在环中为其分配多个位置（也就是多个虚节点，论文中有个别的说法是tokens，令牌）原本利用服务器1个字符串信息映射，现在增加到1000个，然后再把这1000个映射到环上。哈希函数能保证这1000个结果非常的离散。从而保证三台服务器负载均衡。

论文原文中虚节点优势：

1. 如果某个节点不可用（由于故障或例行维护），则此节点处理的负载将平均分散在其余可用节点上。
2. 当某个节点再次变得可用，或将新节点添加到系统时，新可用节点从其他每个可用节点接受的负载量大致相等。
3. 一个节点负责的虚拟节点的数量可以根据其容量来确定，这要考虑物理基础架构中的异构性。

引入虚节点后，在新增或者移除节点时，会有更多的节点参与到数据迁移过程中，提升迁移效率。

数据复制：

为了实现高可用性和持久性，Dynamo将数据复制到多个节点上。每个数据项都在N个节点上复制，N的值取决于配置参数。

还是这个图，N=3的情况下，对象K根据计算应该落在虚拟节点B上，同时，会选择B的后继虚拟节点C、D作为另外两个副本。节点D将存储落入（A，B]，（B，C]和（C，D]范围内的key。但是需要注意的是B、C、D三个虚拟节点必须位于不同的物理节点。

数据版本控制：

引入副本除了提供高可用外，也可能会带来严重的后果。比如，在异步复制数据的时候，可能由于网络抖动，导致数据没来得及复制到 slave replica 上。这个时候，如果有请求去读 slave replica，就读不到最新的数据。又比如，在 multi-master 的场景下，可能两个 master 同时接收到修改同一个数据的请求。这个时候，两个写操作成功返回客户端后，再复制到对方时，就可能由于数据冲突导致更新失败。

Dynamo采用的是最终一致性模型：即虚拟节点的多个副本之间可能会存在不一致的时间窗口，但最终系统会保证多个副本之间数据达成一致。
为了保持副本之间的一致性，Dynamo 使用了类似于使用法定人数系统（quorum systems）中使用的一致性协议。该协议有两个关键的可配置值：R 和 W。R 是成功读取操作必须参与的最小节点数。W 是成功写入操作必须参与的最小节点数。设置 R 和 W，使得 R + W > N 产生一个类似群体的系统。在这个模型中，get（或 put）操作的延迟由最慢的复制决定。因此，R 和 W 通常配置为小于 N，以提供更好的延迟。

根据鸽笼原理，只要满足W+R>N，便可以保证客户端一定能读到最新版本的数据。

Dynamo 使用向量时钟来捕捉同一对象不同版本之间的因果关系。向量时钟实际上是(node, counter) 对的列表。一个向量时钟与每个对象的每个版本相关联。可以通过检查一个对象的向量时钟来确定它的两个版本是在平行的分支上还是有因果关系。如果第一个对象时钟上的计数器小于或等于第二个时钟上的所有节点，那么第一个是第二个的祖先，可以被垃圾回收。否则，这两个变化被认为是冲突的，需要和解。

现在考虑并发更新情况下的向量时钟使用

系统当前是三副本，某个partition的三个副本分别为Sx，Sy，Sz，且R=2， W=2。按照下面的顺序进行数据更新：

1. 数据在Sx节点写入，产生数据的新版本为<Sx, 1>，并同步至Sy，Sz；
2. 数据在Sx节点更新，产生数据新版本为<Sx，2>，并同步至Sy，Sz；
3. 截止目前，Sx，Sy，Sz三个节点的数据版本均为<Sx, 2>，数据处于一致状态；
4. 由于某种原因，A客户端选择了Sy节点对数据进行更新，而此时A客户端看到的数据版本为<Sx, 2>，因此，A向Sy节点发送数据更新请求，且指明本次更新的版本为<Sx, 2>，Sy节点收到更新请求后，选择更新本地数据的版本为<Sx, 2>，<Sy, 1>；
5. 在4进行的过程中，客户端B选择了Sz节点对数据进行更新，此时B客户端看到的数据版本也是<Sx, 2>，于是B给Sz发送请求更新对象的<Sx, 2>的版本数据。Sz同样更新本地的数据以及版本为<Sx, 2>, <Sz, 1>；
6. 接下来数据主从同步的过程中，无论是Sy将自己的数据同步至Sz，还是Sz将数据同步至Sy，都会发现他们之间的数据其实是存在冲突的，而且存储系统自身是无法解决这种冲突的，于是，继续保存这种冲突数据，但是在Sy(或者Sz)向Sx同步数据的时候是没问题的，因为通过向量时钟比对发现Sx的版本无论比Sy还是Sz都要更小；
7. 接下来，客户端发起对数据的读请求，因为存在冲突，冲突的版本都会被发送至客户端，于是客户端看到的数据版本是{<Sx, 2>, <Sy, 1>}和{<Sx, 2>, <Sz, 1>}。接下来应用程序根据自己的业务逻辑尝试去解决冲突，例如，最终选择了{<Sx, 2>, <Sy, 1>}作为最终的数据，那接下来会将自己的协调结果写到某个副本（假如选择Sx写入）上，需要注意的是，客户端指定更新的版本为<Sx, 2>, <Sy, 1>, <Sz, 1>，而Sx收到请求后，会将对象的版本更新为<Sx, 3>,<Sy, 1>, <Sz, 1>。如此这样，接下来Sx将新版本的数据推送到其他副本的时候，就不会在出现冲突了，因为无论是Sy节点上的<Sx, 2>, <Sy, 1>还是Sz节点上的<Sx, 2>, <Sz, 1>均落后于Sx上的当前版本，大家又达成了数据一致性

并发更新部分节选自参考2，原文中这一部分讲解没参考2简练

暂时故障处理：Hinted Handoff

Hinted Handoff 机制是为了进一步提高系统的可用性。正常情况下，客户的写入数据会被复制到ring上的N个节点。但是一旦出现异常时，写入的节点不可达，这时候可能就会出错，如下：

假如数据应该被写入至节点A并复制到B和C，但是此时假如A节点异常，可能就会导致数据不可写。

Dynamo的做法是引入Handoff节点，如上图所示，如果节点 A 在写入操作期间暂时关闭或不可访问，则通常位于节点 A 上的副本现在将被发送到节点 D。发送到 D 的副本在其元数据中将有一个提示，提示哪个节点是副本的预期接收者（在本例中为 A）。D会将这些副本保存在一个单独的本地数据库中，并定期进行扫描。一旦检测到 A 已经恢复，D 将尝试将副本传送给 A。一旦传输成功，D 可以从其本地存储中删除该对象，而不会减少系统中副本的总数。

通过使用Handoff机制，Dynamo 确保读写操作不会因临时节点或网络故障而失败。需要最高级别可用性的应用程序可以将 W 设置为 1，这可以确保只要系统中的单个节点将 key 持久写入其本地存储，写入就可以被接受。因此，只有当系统中的所有节点都不可用时，写请求才会被拒绝。但实际上，生产中的亚马逊大部分服务都设置了较高的 W，以满足期望的持久性水平。

永久故障处理：副本同步

当节点宕机不可恢复或其他情况导致永久故障时，Dynamo 实现了一个反熵（anti-entropy）（副本同步）协议来保持副本的同步。
先解释下熵，熵是用来衡量系统内部混乱程度的一个术语；一个系统如果不加干预，是会趋近于熵值最高的状态的，即内部混乱程度最高。在此处，我对反熵的理解是，在可能出现数据一致性问题的分布式系统中，采用某种方式实现最终一致性，从而避免系统达到一种很混乱的状态（同一数据的多个副本不一样就是一种混乱的状态），不一定正确，大家可以做个参考。关于反熵可以参考此链接anti-entropy。

为了更快地检测副本之间的不一致，并最大限度地减少传输的数据量，Dynamo 使用了Merkle 树。Merkle 树是一种 hash 树，叶子是各个键的值的哈希。树中较高的父节点是它们各自子节点的 hash。Merkle 树的主要优点是可以独立检查树的每个分支，而不需要节点下载整个树或整个数据集。此外，Merkle 树有助于减少需要传输的数据量，同时检查副本之间的不一致性。例如，如果两棵树的根的哈希值相等，则树中叶节点的值相等，并且节点不需要同步。如果没有，则意味着某些副本的值不同。在这种情况下，节点可以交换子节点的哈希值，并且该过程继续进行，直到到达树叶，此时主机可以识别 "不同步" 的 key。Merkle 树最大限度地减少了同步所需传输的数据量，并减少了反熵过程中执行的磁盘读取次数。

Dynamo 使用 Merkle 树进行反熵。每个节点为其托管的每个 key 范围（虚拟节点覆盖的密钥集）维护一个单独的 Merkle 树。这允许节点比较一个键范围内的键是否是最新的。在该方案中，两个节点交换对应于它们共同拥有的 key 范围的 Merkle 树的根。随后，使用上述树遍历方案，节点确定它们是否有任何差异，并执行适当的同步动作。该方案的缺点是，当节点加入或离开系统时，许多关键范围会改变，从而需要重新计算树。

有关Merkle树可以参考链接。

参考：

1. 漫谈分布式系统
2. Dynamo论文笔记