Dynamo

原文是2007年SOSP上Amazon发布的分布式存储经典论文《Dynamo: Amazon’s Highly Available Key-value Store》。这是一个高可用的分布式KV存储——Dynamo，Amazon的一些核心服务就是依赖Dynamo提供持续可用的服务，为了达到这种可用级别，Dynamo牺牲了几种特定场景下的一致性。并且，Dynamo大量地使用了对象版本化和应用层面的冲突解决机制。

INTRODUCTION

支撑着Amazon电商发展的是建立在分布于全球数据中心成千上万的服务器基础上的，因此对性能、可靠性和效率都有很高的要求。同时为了支撑业务的持续增长和避免因故障导致的经济损失，平台需要有足够好的可扩展性、可靠性。

Amazon使用的是去中心化的、松耦合的、面向服务的架构，这种服务架构对持续可用的存储技术有着强烈的诉求。例如，即便是磁盘故障、路由抖动、数据中心被摧毁，用户仍然能够向购物车添加和查看商品。因此Amazon推出了一款高可用的kv存储组件——Dynamo。Dynamo用于管理对可靠性要求非常高的服务，这些服务还要求对一致性、成本效率和性能有很强的控制能力。

Dynamo使用了一些常见的技术来实现了可扩展性和高可用性：

数据通过一致性哈希来分区和复制；
通过对象版本化来实现一致性；
副本之间的一致性使用了类似quorum的技术和一个去中心化的副本同步协议；
gossip-based分布式故障检测和成员检测协议；

Dynamo是一个极少需要人工管理的、完全去中心化的系统，向Dynamo添加或者删除节点不需要人工调整哈希节点和重分布节点间数据。

BACKGROUND

传统上生产系统会使用关系型数据库来存储状态，但这并不是一种理想的方式，大多数服务并不需要RDBMS提供的复杂查询和管理功能，这些额外的支持带来的硬件成本并不经济，并且这类数据库的复制功能有局限，往往是通过牺牲可用性来换取一致性。

System Assumptions and Requirements

Dynamo对于使用它的服务有几点假设：

Query Model：通过唯一的key对数据进行读写，存储状态是binary objects。没有relational schema需求，无跨data items的操作。存储对象较小，往往小于1MB；
ACID Properties：Dynamo的设计目标是使用部分一致性来换取更高的可用性；
Efficiency：存储系统必须满足那些严格的SLA；
Other Assumptions：内部使用，假设环境足够安全；

Service Level Agreements (SLA)

在Amazon去中心化的基础设施中，SLA会扮演着重要的角色，客户端和服务端会定义一个 SLA协议。Amazon不是使用传统的平均值、中位数和方差来描述面向性能的SLA，而是更多使用了P99.9分布，来确定性能的长尾结果。

Design Considerations

前面提过，很多系统中数据复制算法一般是同步的，为了提供一个强一致性的数据访问结果，往往会牺牲掉某些场景下的可用性。考虑到这一点，Dynamo最终被设计为最终一致的数据存储系统。

在分布式系统中，需要关注的是机器或者网络故障时可能会导致数据冲突，需要检测和解决冲突。一些传统的数据库可能会在写的时候解决冲突，牺牲一点可用性。但Dynamo的目标是提供一个持续可写的存储，因此将解决冲突的逻辑放到了读操作，从而避免写操作被拒绝。同时Dynamo可以配置是存储系统来解决冲突还是应用选择自行实现冲突解决操作。

SYSTEM ARCHITECTURE

本文主要介绍了Dynamo用到的部分分布式系统技术：包括partitioning, replication, versioning, membership, failure handling 和 scaling。

System Interface

Dynamo的存储接口非常简单，只有两个：

get()：会返回存储key对应的所有对象副本，以及一个context；
put()：确定对象的存储位置，写入到相应的磁盘。

Dynamo将调用方提供的key和对象都视作是opaque array of bytes，其对key应用MD5哈希得到一个128bit的ID，并根据ID计算应该存储到哪个存储节点。

Partitioning Algorithm

Dynamo的设计有一个核心诉求：支持增量扩展。这就要求有一种机制能够将数据分散到系统的不同节点中，Dynamo的方案是基于一致性哈希，其哈希函数的输出是一个固定范围，作为一个循环空间环，每个节点会随机分配一个循环空间内的值，代表着节点在环上的节点。

Dynamo寻找item对应节点的方法：

首先对key做哈希得到哈希值；
然后在环上沿着顺时针方向找到第一个多带值被这个哈希值更大的节点；

这种方法有一个缺陷，就是每个节点随机分配的位置可能会导致数据不均匀分布负载，也没有考虑到节点的异构因素。为了解决这些问题，Dynamo做了优化，每个节点不是映射到环上的一个点，而是多个点。Dynamo使用了虚拟节点的概念，一个新节点加入到系统后，会在环上分配多个位置（对应多个token）。

虚拟节点的好处就是：

当一个节点不可用离开时，会将该节点管理的虚拟节点平均分配给其他真实节点均衡管理；
同理，新节点加入时，会从现有虚拟节点中拿出虚拟节点分配给新节点；
一个节点负责的虚拟节点数量可以根据节点容量来决定，充分利用机器的异构性信息；

Replication

为了实现高可用性和持久性，Dynamo会将数据复制到N台机器上，N可配置。

具体的做法是，每个Key都会分配一个coordinator节点，coordinator负责落到它管理范围内的复制，除了自己存储一份之外，还会沿着顺时针方向的其他N-1个节点存储一份副本。

如下图，B除了自己存储一份之外，还会将数据存储到C和D节点。D实际存储的数据，其key范围包括了(A, B]、(B, C] 和 (C, D]。

存储某个特定key的所有节点会组成一个preference list，为了防止节点的failure，整这个preference list可能多于N个节点，另外由于引入了虚拟节点机制，preference list会保证N个节点不落在相同的物理机上。

Data Versioning

Dynamo提供最终一致性，所有更新操作会异步地传递给所有的副本。put()操作返回时，更新可能还没有应用到所有的副本，后续的get操作可能去不到最新数据。Amazon有些应用是可以容忍这种不一致性的，应用在这种情况下能继续运行。以操作购物车威力，如果购物车的最新状态不可用，用户对一个老版本的购物车状态做了修改，这种修改是需要保留的，由后续的步骤来解决冲突。

为了解决冲突，Dynamo将每次修改结果都作为一个全新的版本，允许系统多个版本共存。使得冲突一致化的两种方式：syntactic reconciliation和semantic reconciliation。在大多数情况下，新版本都包含了老版本的数据，而且系统可以判断哪个是权威版本，这就是syntactic reconciliation。

但是在发生故障并且并发更新的情况下，版本可能发生分叉，系统无法处理这种情况，需要客户端介入，从而将多个版本分支合并成一个，这就是semantic reconciliation。这种操作的好处是写操作永远可用，但会导致业务应用上一些奇怪现象，比如已经删除的商品偶尔又在购物车中冒出来。

Dynamo使用向量时钟（vector clock）来追踪同一个对象不同版本之间的因果关系，一个向量时钟就是一个 (node, counter) 列表。一个向量时钟关联了一个对象的所有版本，可以用来判断对象两个版本是并行分支还是具备因果关系。如果对象的第一个时钟上的所有 counter 都小于它的第二个时钟上的 counter，那第一时钟就是第二个的祖先，可以安全的删除。否则需要进行reconciliation。

在Dynamo中，客户端更新一个对象需要指明基于哪个版本进行更新。流程是先读拿到context，context带有vector clock，写的时候把context带下去。在读的时候如果发现了多个版本，并且系统无法reconcile这些版本，就会返回所有的版本，待解决了冲突将多个版本分支合并起来。

以下图为例

客户端写入一个对象。处理这个key的写请求节点Sx增加key的counter，系统有了一个对象D1和它的时钟[(Sx, 1)]；
客户端更新这个对象。假设还是Sx处理这个请求。此时，系统有了对象D2和它的时钟 [(Sx, 2)]，但可能D1在其他节点的副本还没有看到这个更新；
假设这个客户端，再次更新了对象，并且这次是由另外的一个节点Sy处理请求。此时，系统有了D3和它的时钟[(Sx, 2), (Sy, 1)]。假设另一个客户端读取D2，并尝试更新它，写请求由另一个节点Sz处理。现在，系统有D4（D2的后代），版本clock是[(Sx, 2), (Sz, 1)]。
此时，D3和D4各自的改动都没有反映在对方之中。因此这两个版本都应当被保留，然后交给客户端，由客户端在下次读取的时候执行semantic reconciliation；
假设某个客户端读到了D3和D4，即[(Sx, 2), (Sy, 1), (Sz, 1)]。如果客户端执行 reconciliation，并且节点Sx执行协调写，Sx会更新自己在clock中的序列号。最终新生成的数据D5的clock格式如下：[(Sx, 3), (Sy, 1), (Sz, 1)]。

vector clock的一个潜在问题是，如果有多个节点先后协调同一个对象的写操作，那这个对象的clock vector会变得很长。这种情况发生的可能性不大，只有在网络分裂或多台服务器挂掉的情况下，写操作才可能由非preference list前N个节点来执行，导致vector clock变长。

为了避免这个问题，Dynamo采用的方法是clock truncation scheme，另外保存一个和(node, counter) 对应的时间戳，记录最后一次更新该记录的时间，当vector clock达到阈值时就删掉最老的一个。这种方案可能会导致无法精确判断部分后代的因果关系，但论文说生产环境没遇到过这个问题。

Execution of get () and put () operations

Dynamo中所有存储节点都可以接受key的读写操作。

读写操作由Amazon基础设施相关的请求处理框架发起HTTP请求。客户端有两种选择：

将请求路由到负载均衡器，由后者根据负载信息选择后端节点；
使用能感知partition的客户端，直接路由到coordinator节点；

前者是负载均衡器转发到环上任意一个节点，如果收到请求的节点不是preference list前N个节点中的一个，那它就不会处理这个请求，而是转发到preference list第一个节点。

读写操作需要preference list中有不可用节点，就跳过。优先访问preference list中编号较小的节点。

为了保证副本的一致性，Dynamo使用了一种类似quorum的一致性协议。这个协议有两个配置参数：R 和 W：

R：允许执行一次读操作所需的最少节点数；
W：允许执行一次写操作所需的最少节点数；

设置R + W > N，就得到了一个quorum系统。在这种模型下，读写请求由R/W副本中最慢的一个决定。

当收到写请求后，coordinator 会为新版本生成 vector clock，并将其保存到节点本地。然后将新版本（和对应的vector clock）发送给N个排在最前面的、可用的节点，只要有至少W-1个节点返回成功，就认为写操作成功。

读操作类似，如果coordinator收集到多个版本，它会将所有系统判断没有因果关系的版本返回给客户端。客户端需要对版本进行reconcile，合并成一个最新版本，然后将结果写回 Dynamo。

Handling Failures: Hinted Handoff

如果使用传统的quorum算法，Dynamo无法在节点不可用时保持可用。Dynamo采用了一种更为宽松quorum：所有读和写操作在preference list的前N个健康节点上执行，遇到不可用节点，会沿着哈希环的顺时针方向顺延。

以下图为例，如果A临时不可用，正常情况下发到A的请求会发送到D，发到D副本的元数据中会提示这个副本数据应该发到A，然后这个数据会被D保存到本地的一个独立数据库中，并且有一个定期任务不断扫描，一旦A可用了，就将这个数据发送回 A，然后D就可以从本地数据库中将其删除了。

Handling permanent failures: Replica synchronization

如果出现了在hinted副本移交给原副本节点之前就变的不可用，就会威胁到持久性。Dynamo基于Merkle trees实现了一种逆熵（副本同步）协议来保证副本是同步的。

Membership and Failure Detection

Ring Membership

Amazon使用显式机制来向Dynamo环增删节点，管理员通过命令行或web方式连接到 Dynamo node，然后下发一个成员变更命令增删节点。负责处理这个请求的 node 将成员变动信息和对应的时间写入持久存储。成员变动会形成历史记录。Dynamo使用一个gossip-based的算法传播成员变更信息。

External Discovery

上面的逻辑会有个问题，假设管理员同时添加两个节点，那么它们不会立即感知到对方，导致临时的逻辑分裂。为了避免这个问题，论文将部分Dynamo节点作为种子节点，所有节点都知道种子节点的存在，因为所有节点最终都会和种子节点reconcile成员信息，所以逻辑分裂就几乎不可能发生了。种子是从静态配置文件或者配置中心获取的。

Failure Detection

故障检测在Dynamo中的读写操作或者partition和hinted replica时移跳过不可用的节点。其做法是，节点B只要没有应答节点A的消息，A就认为B不可达。在有持续的client请求时，Dynamo Ring上的节点会有持续的交互，能定期检查及诶但是否恢复。使用简单的gossip协议就可以感知到节点的增删。

Adding/Removing Storage Nodes

当新节点加入系统后，会获得一些随机分散到Ring上的token，此时原本负责某些key range的节点会将此时负责的key转移到新节点。

IMPLEMENTATION

Dynamo支持选择不同的本地存储组件来作为存储引擎，其实以插件的方式引入的，包括了BDB、Mysql、in-memory buffer with persistent backing store等。应用能够为不同的访问类型选择最合适的存储引擎。

coordinator会代替客户端执行读写请求，每个客户端请求都会在收到这个请求的节点上创建一个状态机，包括了所有相关的逻辑。

对于写请求，前面提到过由preference list前N个节点中任一个coordinate，总是由第一个来coordinate的好处是使得在同一个地方完成写操作的顺序化，但可能会导致复杂不均匀。为了解决这个问题，preference list内的所有N个节点都可以coordinate写操作，另外由于写操作前面都带有读操作，写操作的coordinator会选择前一次读操作返回最快的节点（这个信息会被存在返回的上下文中）。由于这项优化使得前一次读操作选中的存储节点更容易被选中，提高了read-your-writes的概率。

CONCLUSIONS

本文介绍了Dynamo作为一个高可用、高可扩展性的数据存储系统，在Amazon的诸多核心系统中都有应用。Dynamo提供了期望的可用性与性能，能够很好处理节点不可用、网络分裂的情况。Dynamo最大的意义是证明了：一些去中心化的技术结合起来能够提供一个高可用的系统，并且在很多应用环境中投产了。