Dynamo：亚马逊的高可用键值存储

一句话

Dynamo 是亚马逊为购物车等核心业务打造的高可用键值存储：它把「永远可写（always-writeable）」置于「强一致」之上，用一致性哈希（consistent hashing）决定数据分布、用可调的 N/R/W 法定人数做多副本读写、用向量时钟（vector clock）追踪版本因果并把冲突交给应用合并、用宽松法定人数 + 暗示移交（hinted handoff）扛住临时故障——由此把 CAP 三选二里的取舍明明白白摆到台面上，成了「最终一致」NoSQL 的开山之作。

Glossary · 术语表

坐标

作者是亚马逊的 Giuseppe DeCandia、Deniz Hastorun、Werner Vogels（时任 Amazon CTO）等，论文发在 SOSP 2007。它站在 Chord（2001，一致性哈希与 DHT）、Lamport 的向量/逻辑时钟（1978）等分布式经典的肩上，把这些学术构件拼装成一个真在生产环境跑的系统；下启 Cassandra、Riak、Voldemort 乃至日后的 DynamoDB，是「最终一致 NoSQL」这一整条路线的思想母本。

问题与动机

亚马逊的电商平台由数百个服务拼成，规模巨大、常年有机器和网络在出故障——「故障是常态，不是意外」。在这种环境里，很多核心服务（购物车、会话、卖家榜单）对存储只有一个近乎苛刻的要求：永远别拒绝我。尤其是「加入购物车」这类写操作，哪怕机房半瘫、网络分区，也绝不能失败——一次加购失败就是一笔流失的订单。

可传统关系数据库和多数强一致存储，走的是相反的哲学：为了保证「任何时候读到的都是唯一最新值」，它们在故障或分区时宁可阻塞甚至拒绝写入。按 CAP 定理，网络一旦分区，一致性 C 和可用性 A 只能保一个。亚马逊的业务判断是：这里可用性远比即时一致重要。购物车短暂出现两个版本、事后合并，用户几乎无感；而加购失败，用户立刻就走了。Dynamo 就是把这个取舍反过来做的产物：牺牲即时强一致，换「永远可写」。

核心思想 / 方法

Dynamo 不是单一新算法，而是把几件已知技术围绕「高可用」这个目标组装起来，每一件都服务于「别拒绝用户、故障能自愈、扩容不停机」。逐个拆开。

① 一致性哈希：数据放哪，加减机器不用大搬家

成千上万台机器，一个键该落到哪台？最朴素的办法是「机器数取模」，但那样一加一减机器，几乎所有键的归属都变，得全体大搬家。Dynamo 用一致性哈希：把哈希值的整个取值范围首尾相接，想象成一个环；每台机器也哈希到环上一个位置。一个键的归属，就是从它的哈希点顺时针走，遇到的第一台机器——称为该键的协调者（coordinator）。

为了负载均衡，Dynamo 让每台物理机在环上占多个位置（称虚拟节点，virtual node），这样数据摊得更匀，机器性能不一（异构）时也好按能力分配。

② 多副本 + preference list：存 N 份，谁都能顶上

协调者不独吞数据——它连同环上其后 N−1 台机器各存一份，共 N 份（典型 N=3）。这 N 台构成该键的preference list（副本清单）。任何一台坏了，清单里别的机器都能顶上继续服务。

③ R + W > N：一把可调的「一致性旋钮」

N 份副本，写要写几份、读要读几份才算成功？Dynamo 给出两个可调参数：写操作要至少 W 份副本确认、读操作要至少收 R 份副本回应。关键的设计是让 R + W > N：因为「写过的那 W 份」和「读到的那 R 份」在 N 份里必定至少重叠一份，于是任何一次读至少能碰到一份含最新写的副本——用数量上的重叠，换来「读不会完全错过最新写」。

这把旋钮是可调的：(N,R,W)=(3,2,2) 是常用均衡；把 W=1 调低，写只要一份确认就返回、写极快且极难失败（更偏可用）；把 R 调高则读更可能拿到最新。业务可按「读多写多、能容忍多旧」自行拧。

④ 宽松法定人数 + 暗示移交：故障时也别拒绝写

可万一 preference list 前几台正好宕机，凑不齐 W 份怎么办？严格法定人数此时会拒绝写——这正是 Dynamo 不能接受的。它改用宽松法定人数（sloppy quorum）：写请求顺着环往下找到接下来还活着的机器凑够 W 份，其中「替别人代收」的那台会额外记一张暗示（hint），写明「这份数据本属于宕机的那台」。等原主机恢复，代收方就把数据连同暗示移交（handoff）回去，然后删掉本地副本。这套暗示移交（hinted handoff）让写入几乎永不失败，故障过后又能自动把数据归位。

⑤ 向量时钟：允许分歧，但记清「谁源自谁」

放弃即时强一致的代价，是同一个键可能同时存在多个版本（比如网络分区时两边各写了一次）。麻烦在于：读到两个版本，怎么判断是「一个是另一个的更新版（覆盖即可）」还是「两个真冲突（各自独立改过，需合并）」？Dynamo 用向量时钟解决——每个版本带一串 (节点, 计数) 记号，记录它先后被哪些节点改过、各改了几次。比较两个版本的向量时钟：若 A 的每一项都 ≥ B 且至少一项更大，说明 A 是 B 的后代，直接用 A（这叫语法级调和 syntactic reconciliation）；若互不覆盖（各有对方没有的更新），说明二者真冲突。

Dynamo 自己不擅自解决真冲突——它把冲突的多个版本一并返回给应用，让应用按业务语义做语义级调和（semantic reconciliation）。购物车的规则出奇简单：两个版本取并集，两边加过的商品都保留。最坏情况是一件已删的商品「复活」，但相比丢失订单，这是划算的取舍。

⑥ 反熵与 gossip：让副本悄悄自愈、成员自治

暗示移交只治临时故障；机器彻底损坏时，副本会长期不同步。Dynamo 用 Merkle 树（默克尔树）做反熵（anti-entropy）：两个副本各把自己的数据算成一棵哈希树，逐层比对哈希、只在不一致的子树里下钻，从而用极少的数据传输就定位出差异、只补该补的那部分。成员管理则用 gossip 协议：没有中心节点，每台机器周期性和随机的同伴交换「我知道谁在、环长啥样」，故障检测和成员变更就这样在集群里扩散开——彻底去中心、人人对等。

关键结果

Dynamo 是一篇工程系统论文而非跑分论文——它的「结果」是它真在亚马逊生产环境撑起了核心业务：购物车、会话管理、卖家榜单、S3 的部分等数十个服务。论文以 99.9 分位延迟为核心指标（而非平均值），报告了在严苛 SLA（如高分位数百毫秒内）下的实测表现，并展示 (N,R,W) 不同取值如何在延迟、持久性与一致性之间移动权衡点：把 W 调到 1 写几乎从不失败，把 R/W 都调高则更一致但更慢。最有说服力的结论是：一个明确牺牲即时一致的系统，可以在真实大规模生产中做到近乎永不拒绝写入。

为什么重要 / 影响

Dynamo 把「可用性 vs 一致性」这个抽象取舍，第一次做成了一整套可落地、可调、能自愈的工程范式，并把 CAP 的选择权明确交到业务手里。它几乎以一己之力点燃了 NoSQL 与「最终一致性」运动：Cassandra（Facebook，直接承袭 Dynamo 的一致性哈希 + 可调法定人数）、Riak、Voldemort 都是它的直系后代；它的许多机制——一致性哈希、preference list、R+W 法定人数、向量时钟/版本冲突、hinted handoff、Merkle 反熵、gossip 成员——如今是分布式存储的通用词汇表。多年后亚马逊推出的托管服务 DynamoDB 借了它的名字（虽是另起炉灶的重写）。可以说，今天谈「高可用分布式数据库」，绕不开这篇。

局限与批评

• 把复杂度甩给了应用：最终一致意味着应用必须自己处理「读到多个版本」的合并逻辑。购物车能靠取并集轻松搞定，但很多业务没有这么干净的合并规则，写起来既难又易错。
• 向量时钟会膨胀：参与写的节点一多，向量时钟串就变长；Dynamo 用「截断最老项」压缩，但截断可能误判因果、带来罕见的异常。
• 宽松法定人数不是真法定人数：sloppy quorum 下，某些故障与恢复的时序里仍可能短暂读到旧值、甚至丢写——它保的是可用性，一致性只是「最终」的。后来 Riak 等提供了更严格的模式作为补充。
• 运维与调参有门槛：N/R/W、虚拟节点数、反熵频率等都要按业务细调，用不好会踩坑。
• 亚马逊自己后来换了路：面向外部客户的 DynamoDB 是重写，提供了强一致读选项与托管化——侧面说明「纯最终一致 + 应用自合并」并非对所有场景都最友好。

要点