本文是Dynamo论文的阅读笔记，Dynamo是亚马逊的高可用键值数据库。在大规模集群中，各类故障是家常便饭，Dynamo的设计目标是在大规模集群中降低一致性要求，实现高性能和高可用。
背景
本文提出的数据存储技术需要满足以下要求：
- 查询模型：数据对象由键来指定；
- ACID性质：Dynamo只提供了弱一致性，而且只有单个键上的操作，并没有提供事务；
- 高效：系统延迟需要满足要求；
- 其他：Dynamo需要只在亚马逊内部使用，所以不需要考虑安全性方面的问题。
为了保证应用在限定时间内完成功能，客户端和服务需要达成一个服务标准协议（SLA），客户端和服务器需要在一些系统特征上达成一致。本文采用延迟分布的99%作为SLA，对服务的性能做出要求。
在服务器故障和网络故障是家常便饭的情况下，以及并发写入的存在，如何检测和解决冲突是个巨大的挑战。Dynamo设计成最终一致的形式，所有的更新最终会到达所有的副本。为了保证永远可以写入的特性，系统将解决冲突的任务交给读取操作。
Dynamo提供了灵活的冲突消解策略，既可以使用内置的简单策略，也可以采用程序自定义的策略。系统设计过程中还需要考虑以下准测：
- 增量扩展性：一次扩展一个节点，最小化运维工作和系统运行负担；
- 对称性：所有节点起到的功能都是相同的；
- 去中心化：不存在中心化的节点；
- 异质性：能够充分利用性能不同的机器。
系统架构
系统接口
Dynamo只提供了两种操作get()和put()：
get(key)获取键对应的数据对象，或者带有冲突版本的数据对象列表；put(key, context, object)将数据和上下文保存在键中，上下文包含了数据对象的元数据例如版本号。
分区算法
Dynamo采用一直哈希来决定键的存储位置，也就是将键和节点通过哈希函数映射到一个环上，然后将键保存在环上顺时针方向遇到的第一个节点上。
但是最基本的一致哈希存在一下问题：
- 每个节点在环上的分布不是均匀的；
- 没有考虑节点性能的差异；
解决方法是让每个节点映射在环上的多个虚拟结点，使用虚拟节点有以下好处：
- 如果节点不可用，那么它的负载可以均匀地重新分发给其他节点；
- 如果节点恢复可用，那么它可以从多个节点获取差不多量的负载；
- 并且可以根据节点的性能设置虚拟节点的数量。
副本
除了将数据对象保存在键对应的节点上之外，还需要将副本保存在顺时针方向个节点上。保存键的节点列表称为偏好列表，另外需要跳过已经保存过数据的物理节点对应的虚拟节点。
数据版本
Dynamo把每次修改的结果作为新的不可更改的新版本，客户端需要提供冲突消解机制将多个版本的数据合并。Dynamo通过向量时钟追踪不同版本的数据。
运行get()和put()
客户端每次读写的时候需要选择一个节点进行请求，可以：
- 通过负载均衡器根据负载情况选择一个节点；
- 根据分区信息选择一个节点。
响应读写操作的节点称为协调者，Dynamo使用多数投票的一致协议，提供了两个参数：
需要参与读取的最小节点数目
需要参与写入的最小节点数目
用户可以调整和
，在延迟和一致性之间取得平衡。
提示切换
某些节点会因为故障无法访问，这个时候偏好列表选择个健康节点进行读写，等到故障节点恢复之后将这些副本返还给恢复后的节点。
副本同步
Dynamo使用反熵协议进行副本同步，为了加快数据对比速度，使用Merkle树组织数据对象的哈希值。
成员关系和故障检测
- 环成员关系：Dynamo主要依赖基于流言的协议来传播成员关系更改，维护一个最终一致的成员关系；
- 外部发现：如果同时新增两个节点，那么会有一段时间它们相互不知道对方存在，所以有必要设置一些种子节点，让所以节点和它通信加快新节点发现；
- 故障检测：如果节点B不响应节点A，那么认为节点B故障。Dynamo使用基于流言协议来感知其他节点的下线。
添加/删除存储节点
当一个新的节点被添加之后，会有一些键范围分配给新节点，需要将这些键对应的数据传递给新节点。同样，当节点被删除之后，数据的存储也同样需要进行调整。
实现
每个存储节点由三个软件组件构成：请求协调、成员关系和故障检测，以及本地持久化引擎。Dynamo允许使用不同的存储引擎，例如Berkeley DB、MySQL或者带持久化内存存储。请求协调组件建立在事件驱动模型上，以流水线的方式处理消息。
请求协调组件的运行过程是一个状态机，一个读取操作的运行如下：
- 将读取请求发送给节点；
- 等待最小回复数量的回复；
- 如果给定时间之内没有收到足够数量的回复，那么请求失败；
- 那么聚合所有数据版本决定返回的数据；
- 如果启用版本，那么执行语义冲突消解，产生一个包含向量时钟的上下文。
节点之间通信过程中如果发现有过时版本，那么要进行及时更新。
参考文献
- DeCandia, Giuseppe, et al. "Dynamo: amazon's highly available key-value store." ACM SIGOPS operating systems review. Vol. 41. No. 6. ACM, 2007.
