这篇论文叙述的是 Amazon 研发的高可用 Key-Value 存储系统，Dynamo。很多 Amazon 的核心服务依赖于它，它通过牺牲在某些特定失效情况下的数据一致性来保证高度可用。它采用一致性哈希来获得可伸缩性和提高可用性，并且通过对象版本（Object Versioning）来保证一致性。在更新数据过程中，副本之间的一致性通过一种 quorum-like 技术和去中心化的同步复制协议保证。Dynamo 采用基于 gossip 的失效探测和成员协议。Dynamo 是完全去中心化的系统，节点增加和删除不需要人工操作。
设计思考
这里作者指出 Dynamo 两个设计权衡点，一个是什么时候解决更新数据的冲突，一个是谁来解决冲突。前者 Dynamo 决定在 read 的时候解决为了保证 wirte 一直可用提供良好的用户体验；后者觉得由应用来解决而不是 data store 已获得灵活性。
比较讨论
这部分作者提到了一些中心化的存储系统，指出 Dynamo 由于特殊需求从而设计也与这些系统不同。主要的特殊需求体现在：（一）永远可写，不能拒绝写请求；（二）建立在所有节点均可信任的基础设施上；（三）使用 Dynamo 的应用不依赖层次结构的命名服务；（四）低延迟和高性能决定了不能将请求进行过多的路由转发
系统架构
论文聚焦于系统的数据分区、复制、版本、成员、容错和伸缩。
系统接口
Dynamo 提供 get 和 put 两个接口。get(key) 操作定位到数据的副本且返回一个单独对象或者版本不同的对象列表和 context。put(key, context, object) 操作决定数据存到哪个副本且将副本刷回磁盘持久化。context 包含了对象的元数据例如版本信息，对 caller 不透明。Dynamo将 caller 提供的 key 和对象当成一个不透明的字节数组。它使用 MD5 对 key 进行 Hash 以产生一个 128 位的标识符，它是用来确定负责那个 key 的存储节点。
分区算法
Dynamo 对 key 的设计要求是必须可以增量扩张，这就要求一种机制来动态在系统中的一系列节点上进行数据分区。采用一致性哈希算法来在不同的存储宿主机上进行负载均衡，一致性哈希算法此处不再赘述，可以看其他介绍性的文章。Dynamo 中的一致性哈希加入了虚拟节点层已达到更好的均衡效果。
复制
为了实现高可用性和耐用性，Dynamo 将数据复制到多台主机上，其中每个数据项被复制到 N 台主机，N 的值可配。每个键，K，被分配到一个 coordinator 节点。coordinator 节点掌控其负责范围内的复制数据项。除了在本地存储其范围内的每个 key 外，协调器节点复制这些 key 到环上顺时针方向的 N-1 后继节点。这样的结果是，系统中每个节点负责环上的从其自己到第N个前继节点间的一段区域。在 Figure 2 中，节点 B 除了在本地存储键 K 外，在节点 C 和 D 处复制键 K。节点 D 将存储落在范围 (A,B], (B,C] 和 (C,D] 上的所有键。
数据版本
Dynamo 保证数据的最终一致性，从而允许 update 操作可以异步地传播到所有副本。Dynamo 给客户端返回结果时，所有副本可能还没有都更新完毕，这会导致 get 操作拿到不同的数据，在一些故障情况下，更新操作可能无法传播到每个副本导致系统环境中存在不一致。
而作者指出在 Amazon 的应用下，有些需求例如添加购物车等可以容许这种不一致的产生，所以 Dynamo 会为每个变更操作记录一个新的且不可变的版本。Dynamo 使用 vector clock 来协调某个对象的不同版本间的因果关系。矢量时钟实际上是一个 [node,counter] 对组成的列表。矢量时钟是与每个对象的每个版本相关联。通过查看其向量时钟，我们可以判断一个对象的两个版本是平行分枝或者有因果关系。如果第一个时钟对象上的计数器在第二个时钟对象上小于或等于其他所有节点的计数器，那么第一个是第二个的祖先，可以被人忽略。否则，这两个变化被认为是冲突，并要求协调。put 操作要求用户必须指定更新哪个版本，这个版本信息可以由 get 操作返回的 context 得到。
仲裁协议
为了保持副本的一致性，Dynamo 使用 quorum-like 的一致性协议。该协议有两个关键配置值：R 和 W。
- R 是必须参与一个成功的读取操作的最少数节点数目。
- W 是必须参加一个成功的写操作的最少节点数。
设定 R 和 W，使得 R + W > N 产生类似仲裁的系统。在此模型中，一个get/put 操作延时是由最慢的 R/W 副本决定的。基于这个原因，R 和 W 配置通常小于 Ｎ，为客户提供更小的延时。
当收到对 key 的 put 操作时，协调员生成新版本向量时钟并在本地写入新版本。协调员然后将新版本与新的向量时钟一起，发送给首选列表中排名前 Ｎ 个的可达节点。如果至少 Ｗ-1 个节点返回了响应，那么这个写操作被认为是成功的。
同样，对于一个 get 请求，协调员为 key 从首选列表中排名前 Ｎ 个可达节点处，请求所有现有版本的数据。然后等待 Ｒ 个响应，然后返回结果给客户端。如果最终协调员收集的数据的多个版本，它返回所有它认为没有因果关系的版本。不同版本将被协调，并且取代当前的版本，最后写回。
暂时性故障处理
图 2 举例，配置 N = 3。如果写操作过程中节点 A 无法连接，本来在 A 上的一个副本现在将发送到节点 D 为了保持可用性和耐用性。发送到 D 的副本在其原数据中将有一个 hint，表明哪个节点才是在副本预期的接收者即Ａ。接收暗示副本的节点将数据保存在一个单独的本地存储中，它们被定期扫描。在检测到了 A 复苏后，D 会尝试发送副本给 A。一旦传送成功，D 将数据从本地存储中删除，且不会降低系统中的副本总数。
永久性故障处理
Dynamo 采用 MerkleTree 更快地检测副本之间的不一致性，并且减少传输的数据量。
结论
论文介绍了 Dynamo，一个高度可用和可扩展的数据存储系统，被 Amazon 电子商务平台用来存储许多核心服务的状态。Dynamo 已经提供了所需的可用性和性能水平，并已成功处理服务器故障，数据中心故障和网络分区。Dynamo是增量扩展，并允许服务的拥有者根据请求负载按比例增加或减少。Dynamo让服务的所有者通过调整参数 N、R 和 W 来达到他们渴求的性能，耐用性和一致性的 SLA。
License
- 本文遵守创作共享 CC BY-NC-SA 3.0协议
Comment