简介
Dynamo是亚马逊的一个高可用的分布式KV数据库，其需要为用户提供一种一直在线的状态。同时由于该数据库需要适应不同的场景，因此需要允许用户通过对Dynamo进行配置来决定其高可用性与性能之间的平衡。为了保证Dynamo为达成高可用性和可扩展性使用了一系列技术，包括：使用一致性哈希来对数据进行分割和复制，使用版本来保证存储对象的一致性，使用一个大多数(quorum-like)的技术及无中心化的副本同步协议来保证副本更新时的一致性，基于Gossip的分布式错误监测及成员变更协议。
Dynamo针对如下需求：
- 查询模型：所有操作都是针对某个键值的查询与写入，所有操作都仅影响一个元素
- ACID：如果需要支持ACID的所有特性则会导致系统可用性较差，因此Dynamo仅支持较弱的一致性从而获得更高的可用性，同时也不保证隔离性
- 效率：系统能够在商用机器上运行并达到延迟、吞吐量等要求
- 系统运行在可信环境中，因此为非拜占庭容错
开发者在设计Dynamo时，为了保证系统拥有较高的可用性，使用了乐观复制技术，允许用户的变更在后台传输，但这样可能导致某些变更之间存在冲突，因此Dynamo通过允许对冲突进行解决来保证整个系统的最终一致性。为了解决不同变更之间的冲突，需要考虑两个问题，一个是由谁来解决变更之间的冲突，另一个是何时来解决这些冲突。针对第一个问题，解决冲突的可以是系统本身也可以是客户，如果让系统本身来解决这个冲突则可能仅支持少数几种策略，例如写入时间较晚的作为最终结果，而让用户来解决这个问题则可以根据实际场景选择最优的策略。针对何时解决冲突的问题，Dynamo为了保证“一直可写”将冲突解决放在了读操作时。同时Dynamo还要求能够支持扩展的递增(Incremental scalability)，即以此能够添加一个存储节点；对称性，即所有节点所提供的功能都是相同的；无中心化，尽可能的使用点对点技术而非中心化的技术；异构性，支持底层异构的节点，允许根据节点的实际处理能力给予相应的负载。
系统架构
| 问题 | 技术 | 优势 |
|---|---|---|
| 数据分割 | 一致性哈希 | 支持递增可扩展性 |
| 写的高可用性 | 向量钟以及读操作时的调节 | 版本大小与更新速度的解耦 |
| 处理短暂时间的错误 | Sloppy Quorum和带有提示的转交 | 提供高可用性及持久性 |
| 由永久错误中恢复 | 使用Merkle树的复制协议 | 在后台同步产生分歧的副本 |
| 成员变更及错误检测 | 给予Gossip协议的成员变更和错误检测 | 保证对称性以及去中性化的特性 |
系统接口
Dynamo所提供的接口仅有put与get，其中get会找到对应的键值对，然后返回一个或多个互相冲突的值，并返回一个上下文，其中包含了系统的元信息，例如多个相互冲突的值对应的向量钟。put操作需要用户指定需要修改的键、值以及对应的上下文。
分割算法
Dynamo使用一致性哈希来进行数据的分割，其将哈希空间视为一个环，每个节点会赋予一个标号将其映射到环上。通过将键进行哈希，然后在哈希环上进行顺时针查找，遇到的第一个节点会负责对应键值对的存储。因此实际上每个节点负责的键值空间是该节点的标号以及其在环上的前驱节点的标号之间的所有键值对。但是由于假设每个节点仅拥有一个标号则很容易出现节点负载不均衡的情况，因此可以给予每个物理节点多个虚拟节点，每个节点均映射到哈希环中，从而保证以下几点优势：
- 当一个节点下线后，那么其原有负载可以平均的转移到剩余节点中
- 当一个节点上线后，新的节点可以从其他节点处获得相对均衡的负载
- 可以根据每个物理节点的不同性能来选择其拥有的虚拟节点的数量
Dynamo的分割算法存在三种，第一种是每个物理节点有T个标号，使用标号来分割哈希环，该方法由于在成员变更时需要修改多个节点的键值范围从而需要重新计算Merkle树等信息；第二种是每个物理节点T个标号，哈希环被分割为很多固定大小的块；第三种是将哈希环分割为固定大小的块，每个物理节点有相同数量的标号。
复制
为了保证可用性和可持久性，Dynamo会将数据复制到多个物理节点中。每个键均会被分配到一个协调者节点上，该协调者会负责其键值范围内所有的键值对的复制。每个Dynamo集群均可配置副本数量N，协调者会在键值变更后储存到本地并将其复制到在哈希环中标号在其之后的N-1个物理节点，因此每个节点负责存储的键值范围是其前第N个节点对应的标号及自己标号之间的所有键值对。
负责存储某个键值对存储的所有节点的列表被称为偏好列表，Dynamo设计为每个节点都能确定某个键值所对应的偏好列表。为了防止节点失效，偏好列表里一般会包含多于N个节点，同时为了防止多个虚拟节点存在于同一个物理节点，因此偏好列表会跳过存在于同一个物理节点上的虚拟节点。
数据版本控制
由于Dynamo支持最终一致性，因此允许数据变更在后台异步的传播，一个put操作可能在其数据没有复制到所有的节点前就返回给调用者，因此可能导致之后的get操作无法看见最新的修改。由于Dynamo需要保证较高的写的可用性，因此其支持对数据进行版本的标号，并允许系统中在同一时间存在多个版本的数据并在以后进行数据的重新组合。在大多数时间里，Dynamo会利用新生成的数据替换掉旧的数据，这一关系由向量时钟来确定，但在一些情况下可能出现数据处于多个分支的情况，这时无法使用向量时钟来确定这写数据副本之间的关系，此时需要客户根据指定的策略来进行数据的重建。
客户希望更新一个数据时需要指定其版本，该版本可以从读取操作获得的上下文中取得。此时如果读取操作返回了多个值则客户端应当对其进行组合。
get/put执行流程
用户为了执行操作必须先选择一个节点作为协调者，选择节点有两种方式，第一钟是使用独立的负载均衡器来选择合适的节点，第二种是让客户端拥有足够的信息从而自行选择节点。针对读请求，任何节点均可作为该请求的协调者。而针对写请求，如果收到请求的节点处于对应键值的偏好列表中则处理该请求，否则将其转发给对应节点，这是因为节点为了写入新的值需要生成新的向量钟。
为了保证副本的一致性，Dynamo使用了一个类似Quorum系统的一致性协议，其有两个可配置的值R与W。R标识最少需要多少节点的相应才能够完成一个读操作，W标识最少需要多少节点才能够完成一个写操作。如果R+W>N则其是一个Quorum的系统，但一般为了保证交易的延迟会设置R+W<N。当收到一个put请求后，该请求的协调者会生成新版本的数据，并修改该数据对应的向量钟，之后将数据发送给N个节点，如果有W-1个节点响应则认为该写操作已经成功可以返回。读操作的流程类似。
处理临时错误：带有提示的转交
当出现服务器故障或者网络分割等情况，Dynamo使用sloppy quorum，其保证读操作或者写操作发生在偏好列表中的前N个可达节点。如果某个节点下线，则原本发送给其的数据会发送给偏好列表中的其他节点，这个节点收到对应的数据后会周期性的检测原有节点是否已经恢复，如果已经恢复则将数据发送给原有节点并将数据从本地删除。
处理永久错误：副本同步
每个节点针对其负责的键值空间建立Merkle树，树的叶子节点是对用的键值，当两个节点需要进行同步时，其可通过交换Merkle树来确定需要同步的数据。
成员管理
Dynamo使用一种显示的机制来让节点加入或退出哈希环，管理员会使用一工具连接到已有的一个节点并发出加入或删除节点的命令，之后该节点会将这个成员变更的信息记录在本地，之后使用一基于Gossip的协议将这个变更传播出去。每个节点会定期选择一个随机节点来获取其成员关系，从而更新自身的成员管理列表。