Dynamo：最终一致的键值存储

破除误解#

最终一致是一种有条件的承诺：在没有新更新、并且失败节点最终回到集群的前提下，所有副本会收敛到同一份值。它放弃的是“任意时刻读到最新写入”，不是“永远各写各的”。Dynamo 用仲裁读写、Merkle 树和 hinted handoff 去推高收敛速度，用向量时钟把并发版本留下来而不是悄悄丢掉。没有这些机制，最终一致只是一句空话。

误解二：只要 W + R > N，读就一定看见最新写。

教科书里的多数派条件，前提是每次读写都打到同一组健康节点。Dynamo 为了在失败时仍能写，引入了松散仲裁：协调者可以把副本临时写到偏好列表之外的节点，并留下 hint。此时“那 N 个位置”已经漂移。R 和 W 的交集在纸面上成立，在故障窗口里并不自动成立。论文把这称为 sloppy quorum，并坦白：可用性换来的就是这段窗口里的额外版本。

误解三：向量时钟会替你合并购物车。

向量时钟只告诉你两份版本是因果相继还是并发。相继则留新的；并发则把两份都交给应用。亚马逊购物车的合并策略是并集——两个版本里出现过的商品都留下——这是业务规则，不是存储引擎的定理。邮箱、库存扣减、唯一券码若也做并集，会得到荒谬的结果。Dynamo 把冲突检测做成了基础设施，把冲突语义留给了写这张表的人。

环、虚拟节点与偏好列表#

数据项的键经哈希落到一个环形空间上。每个物理节点在环上占据多个位置，称为虚拟节点。加入或删除一台机器时，只有落在相邻弧上的那些键需要搬家，而不是整张表重洗。这是 David Karger 等人 1997 年一致性哈希的工程版：用虚拟节点把负载摊平，避免“一台大机器和一台小机器占同样弧长”的可笑分配。

每个键有一份偏好列表：沿环顺时针走，跳过同一台物理机上的虚拟节点，取出 N 个互异的物理节点。协调者通常是列表里的第一个健康节点。写操作把请求发向这 N 个位置，等 W 个成功应答；读等 R 个。论文里常见的配置是 N = 3、R = 2、W = 2。于是单机失败时写仍可能凑齐 W，读仍可能凑齐 R，而“所有节点都应答”并不是成功的条件。

虚拟节点还有一层运维含义。机器容量不同，就给大机器更多虚拟节点；某台机器变慢，不必立刻改哈希函数，只要在成员信息里把它的虚拟节点标为不可用，偏好列表会滑向下一个。成员信息本身靠 gossip 传播：每个节点定期和随机同伴交换自己见到的环视图。这不是 Demers 等 1987 那三类谣言/反熵装置的再版；本页写的是购物车系统怎样用 gossip 传成员视图。没有中心目录，也就没有中心目录那种单点。代价是：在传播尚未完成的短暂窗口里，两台协调者可能对“谁在偏好列表里”看法不一致。这正是后面那些修复机制要收拾的残局。

松散仲裁、Hinted Handoff 与 Merkle 树#

严格仲裁在节点失败时会把写堵住。Dynamo 选择把写临时放到偏好列表之后的健康节点上，并在报文里附一份 hint：这份数据其实属于谁。接收方把它放进本地的 hint 空间，等原主恢复后再交还。这就是 hinted handoff。它让“加入购物车”在磁盘损坏的下午仍然成功，也让集群在修复完成后多了一件必须做完的家务。

Hint 不是永恒保证。接收方自己也可能挂。所以还需要一条不依赖 hint 的慢路径：反熵。每个节点为持有的数据建 Merkle 树，与同伴交换树根，发现分歧就沿着哈希树往下走，直到定位到不一致的键再同步。Merkle 树的好处是：比较的通信量跟差异的位置有关，而不是跟数据总量有关。坏处是：它修复的是“已经写进去但尚未对齐”的状态，修复延迟以秒到分钟计，不能拿来当读路径上的线性一致。

把三条路径叠在一起，才能看清 Dynamo 的时间尺度。写路径以毫秒计，靠 W 个应答交差；hint 交还以秒到分钟计，靠原主复活；反熵以更长的周期扫尾，靠哈希树。论文给出的业务背景是：99.9% 的读写要在 300 毫秒内完成。那条 SLA 约束的是第一条路径。后两条是为了让“最终”两个字有限，而不是为了让每一次读都看见刚刚那次写。

协调者还可以做读时修复：读到多个版本时，把合并结果写回落后的副本。这把部分反熵提前到了读路径上，用一次客户请求顺便做了家务。它仍然不是事务。它只是承认：读是发现分歧的好时机。

向量时钟与“永远可写”#

Dynamo 用向量时钟给每个版本打因果标签。时钟是一组 (node, counter) 对。协调者在写入时递增自己的计数。比较两个版本时，若一方的每个计数都大于等于另一方，则前者因果上更新；否则两者并发，都要保留。客户端读到多个并发版本后，必须提供一个合并后的值再写回去，否则并发分支会一直分叉。

“永远可写”是论文里几乎不加掩饰的产品决策。购物车的写入不能因为仲裁凑不齐就对用户返回失败。于是系统宁愿产生多个版本，也不愿在写路径上阻塞。这和传统数据库的“先锁再写”刚好反过来：锁是把冲突提前变成等待，向量时钟是把冲突推迟变成合并。两种策略都诚实，诚实的位置不同。前者诚实在写的那一刻，后者诚实在下一次读。

这篇论文对后来的系统影响很大，也被误读得很深。Cassandra 吸收了 Dynamo 的分区和复制，又吸收了 Bigtable 的列模型和 LSM 树，默认的冲突处理却常常是“最后写入获胜”——用墙钟代替向量时钟。那是另一种取舍：实现简单，但在时钟漂移和并发写面前会丢掉一方的更新。Riak 更忠实地保留了向量时钟，也把合并的痛苦更完整地交给了用户。读 Dynamo，最有用的不是去复述环的画法，而是看清楚：可用性数字是用哪一类语义债务买来的。

Dynamo 自己并不是对外出售的数据库。它是亚马逊内部的存储引擎，论文是一份允许同行复用思路的设计备忘。后来云上的 DynamoDB 名字相近，模型并不相同：DynamoDB 提供了按表可选的强一致读，以及用时间戳和事务 API 补上的另一套承诺。把 2007 年那篇 SOSP 论文当成 DynamoDB 的说明书，会把两代产品的约束混在一起。

代价与运维账单#

冲突合并是产品工作。存储引擎不替你定义两个购物车哪个对。没有合并函数的团队，最后会退化成最后写入获胜，于是向量时钟白付了存储和比较成本。Riak 后来把 siblings 做成公开 API，也因此更早撞上兄弟版本把磁盘写满。

提示移交会悄悄改变故障域。提示节点若自己也挂了，hint 还在路上，反熵必须能独立把洞补上。运维要盯的不是“W 是否成功”，而是 hint 堆积、Merkle 同步落后、以及某台机器是否长期替太多邻居收数据。读修复把部分家务提前到读路径，热键会自己痊愈，冷键仍要等反熵周期。

成员变更不是免费的。虚拟节点减轻了抖动，数据仍要搬。环上的最终一致同样适用于成员表：脑裂式的暂时分歧，会让两个协调者各自写下互不包含的版本。跨键事务不存在。购物车能工作，是因为它被设计成单键对象。想在这套引擎上做扣库存且写订单，必须自己做补偿，或者换系统。

这套设计故意不走共识那条路。共识能给线性一致，但故障时写入要排队或失败。GFS 用单主与租约管元数据，仍承认应用必须看见某些不一致；Dynamo 的判断是：购物车的业务语义允许分支，加购失败不允许。是否仍适用于银行账本，答案在论文之外——那些负载后来走了完全不同的系统，其中就包括用时钟买外部一致性的 Spanner。

把 Dynamo 当对象而不是当算法#

一致性哈希的环可以在算法课上画完。系统对象要回答的是另一组问题：成员视图用 gossip 传到多快、虚拟节点的令牌密度如何表达异构硬件、一次迁移在高峰期搬多少热键、hint 空间满了怎么办。论文把这些写成生产迭代，而不是一张永远正确的图。

客户端必须带着 context 写回，否则因果枝接错。运维若把 API 收成无状态的 put(key, value)，等于把向量时钟丢掉，冲突策略会悄悄退化成覆盖。这是产品接口对存储语义的背叛，比调错 N 更常见。

读修复让热键收敛快，也让读路径的尾延迟绑上了写回。R 调大，看见最新版本的机会上升，合并次数和尾部一起上升。99.9 分位才是论文的语言：平均值好看，救不了那千分之一的加购失败。把 Dynamo 抄成“三个副本就高可用”，会把分位数从句子里删掉。

向量时钟截断是另一笔显式的遗忘。节点来来去去，时钟里的项会越来越多，元数据不能无限长。丢掉足够老的项，换来空间，冒的是极小的误判风险：两个本不可比的版本被当成可比较。购物车并集对这种误判相对宽容，余额扣减不能。于是同一套存储引擎，换一张表就可能从“可接受的遗忘”变成“静默错账”。系统对象的边界在这里再次出现：Dynamo 卖的是可调的收敛，不是一张对所有语义都安全的合并代数。

故障相关时，三个整数不再是定理#

机架断电、一次错误的滚动升级、一块共享的网络设备，会让偏好列表上的相邻节点一起消失。这时松散仲裁仍然可以在分区的某一侧凑齐写入次数，于是两侧各自收下互不包含的版本。反熵在分区愈合之后才会开始工作，愈合前的读可能长期看见分叉。运维手册必须把“分区两侧都在写”当成一等事故，而不是当成提示移交的日常家务。

购物车能活下来，是因为并集对分叉相对宽容：多一件商品通常比少一件更可接受。库存扣减、唯一券码、余额，对分叉不宽容。把 Dynamo 的词汇表套到这些表上，是用错了对象。论文从来没有承诺一张通用合并代数。它承诺的是：在写不能失败的前提下，把分歧显式留下来，让那个理解业务的人去合并。协调者、hint 与反熵只保证分叉可被看见，不保证分叉可被某种普适规则自动消掉。看见与消掉之间的那一步，始终是业务代码。

跨域连接#

• 概率论：N、R、W 把可用性写成了失败事件上的组合概率。单机独立故障时，W 个应答凑不齐的概率随 N 上升而下降，但节点失败并不独立——机架断电、部署错误会让偏好列表上的相邻节点一起消失。松散仲裁是在条件概率恶化时仍强行给出写成功，于是把“失败”从写路径搬到了版本集合的随机膨胀上。最终一致的“最终”，其实是反熵过程的期望收敛时间，不是一个确定性时刻。
• 信息不对称：副本在故障窗口里持有不同的信息，协调者、hint 接收方和原主各自只看见局部。向量时钟正是把不对称变成可比较的标签：谁也不需要一个全知的第三人来宣布真相，只要能判断“我的信息是否因果覆盖你的”。购物车并集则是一种特定的披露规则——把双方私有的商品列表公开合并。换一种业务，同样的不对称可能要求取最小库存而不是取并集，存储引擎无法替你选择。
• 图论：一致性哈希把键和节点放在同一张环上，偏好列表是沿环的一条有向路径。Gossip 把成员视图当成另一张稀疏随机图上的流言传播。两条图结构的直径决定了“看法不一致”能持续多久：环上的邻居关系决定数据怎么走，流言图的连通速度决定谁还算活着。Merkle 树则是第三张图——哈希树上的分叉路径——专门用来定位那条环上已经走歪的弧。
• 组合数学：N 个位置、R 次读、W 次写，表面上是三个整数，实际上是在副本组合上做截断。严格仲裁要求读写集合相交；松散仲裁允许相交关系在故障时被临时替换成另一组组合。向量时钟的并发版本数没有内建上限，最坏情况下版本集合随并发写入组合爆炸。Dynamo 能在购物车上工作，是因为那张表的合并函数对组合封闭；换一个不封闭的合并，组合爆炸会直接变成业务错误。

参考文献#

• DeCandia, G. et al. Dynamo: Amazon's Highly Available Key-value Store. ACM SOSP, 2007.
• Karger, D. et al. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. ACM STOC, 1997.
• Lamport, L. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7), 1978.（向量时钟的因果序前身）
• Merkle, R. A Digital Signature Based on a Conventional Encryption Function. CRYPTO, 1987.（Merkle 树）
• Lakshman, A. & Malik, P. Cassandra: A Decentralized Structured Storage System. ACM SIGOPS Operating Systems Review 44(2), 2010.

延伸阅读#

• Vogels, W. Eventually Consistent. Communications of the ACM 52(1), 2009.
• Bailis, P. & Ghodsi, A. Eventual Consistency Today: Limitations, Extensions, and Beyond. ACM Queue 11(3), 2013.
• Sivasubramanian, S. Amazon DynamoDB: A Seamlessly Scalable Non-relational Database Service. ACM SIGMOD, 2012.（同名云服务，模型已不同于 2007 年的 Dynamo）