购物车服务每次点击都要写入,到了 12 月,它连一次加入购物车的请求都不能拒绝。高峰期间会有磁盘损坏,机架交换机会抖动,也许还有数据中心断网。单一主数据库会把其中每一种情况都变成故障。
Amazon 2007 年的 Dynamo 论文描述了一种在这些情况下依然持续接受写入的存储;Cassandra 和 Riak KV 借鉴了它大部分的集群设计思路。本文从 API 到存储引擎设计一个 Dynamo 风格的存储,比较真实系统,并把结果画出来。
需求与 API
Dynamo 的接口只有两个操作:
get(key) -> [value, ...], context
put(key, context, value) -> ok
get 可能返回相互冲突的版本,外加一个不透明的 context;下一次 put 把它传回去,说明自己替换了哪些版本。需求如下:
- 始终可写,即使有节点或链路宕机。
- 可预测的尾延迟。 论文中的 SLA 示例是:在每秒 500 个请求的峰值下,99.9% 的请求在 300 ms 内完成。
- 小值、单键:对象通常小于 1 MB,不支持多键操作。
- 增量扩展,一次增加一个节点。
容量估算假设值为 1 KB,磁盘半满以便为压缩留出空间:10 亿个键是 1 TB,三副本是 3 TB,所以需要六个 1 TB 的节点,和图中的环一致。每秒 30,000 次写入时,三副本意味着 90,000 次副本写入,即每个节点 15,000 次。
CAP 与 PACELC 简述
CAP 指出,网络分区期间,存储必须拒绝部分请求,或者承担读到过期数据的风险;Dynamo 选择保持可用。Daniel Abadi 的 PACELC(2012)补充说,即使没有分区,你仍然要在延迟和一致性之间取舍;他把 Dynamo、Cassandra 和 Riak 的默认配置归为 PA/EL。
用哈希环和虚拟节点分区
Dynamo 用 MD5 把每个键哈希到环上的一个 128 位位置,键属于顺时针方向的第一个节点。节点加入或离开时,只有相邻的范围会移动,而不是像 hash(key) % N 那样几乎所有键都要移动;一致性哈希图展示了其原理。
每个节点只占一个位置会让数据分布不均,所以每个节点占据许多位置,称为虚拟节点或 token。Cassandra 5.0 默认每个节点 16 个 token;Riak 的环默认有 64 个分区。你会失去范围扫描:相邻的键会落在不同节点上,数据库分片图对此有说明。
复制与偏好列表
每个键存放在 N 个节点上:协调者(顺时针方向的第一个节点)和随后 N − 1 个不同的物理节点。键的偏好列表会延伸到它们之后,这样副本宕机时有替补可用。要把副本分散到不同的故障域:Dynamo 把每个列表分散到多个数据中心,Cassandra 的 NetworkTopologyStrategy 则分散到多个机架。与数据库复制图中基于 leader 的方案不同,每个副本都接受写入。
Quorum:R + W > N
协调者把每次写入发给全部 N 个副本,收到 W 个确认后返回;读取在收到 R 个响应后返回。如果 R + W > N,任意读集合与任意已确认的写集合至少共享一个节点。
| N, R, W | R + W > N | 你得到什么 | 你付出什么 |
|---|---|---|---|
| 3, 2, 2 | 是 | 读取能看到最新的已确认写入;可容忍一个副本故障 | 每个请求等待第二快的响应 |
| 3, 1, 3 | 是 | 从任意副本快速读取 | 写入要等待全部三个副本 |
| 3, 1, 1 | 否 | 延迟最低,可用性最高 | 读取可能过期 |
| 5, 3, 3 | 是 | 可容忍两个副本故障 | 每个值有五份副本 |
Dynamo 论文中常见的配置是 (3, 2, 2),产品目录这类读多的服务使用 R = 1、W = N。Cassandra 为每个请求设置一致性级别,从 ONE 到 ALL;读写都用 QUORUM 即可得到 R + W > N。
重叠并不等于线性一致性。一次写入到达一个副本后失败,可能出现在某次读取中,又在下一次读取中消失;Cassandra 默认的阻塞式 read repair 可以在 quorum 读取时防止这种情况。Compare-and-set 需要共识,例如 Cassandra 的轻量级事务,或基于 Raft 的存储。
冲突:Last Write Wins、向量时钟还是 CRDT
经由不同副本的并发写入会留下两个版本。有三种解决办法:
| 策略 | 解决方式 | 会丢失更新吗 | 使用者 |
|---|---|---|---|
| Last Write Wins | 时间戳最大者胜出 | 会,而且是悄无声息的;时钟偏差决定胜者 | Cassandra、DynamoDB 全局表、配置后的 Riak |
| 向量时钟 | 保留并发版本,由客户端合并 | 不会,但每个客户端都必须合并 | Dynamo、Riak(dotted version vector) |
| CRDT | 合并结果总会收敛的数据类型 | 不会(对受支持的类型) | Riak 的计数器、集合和映射 |
向量时钟是一组(节点,计数器)对。如果一个版本的所有计数器都小于或等于另一个版本,它就是祖先,可以丢弃;否则两个版本都保留。购物车服务会合并冲突的购物车,所以添加的商品不会丢失,但已删除的商品可能会重新出现。冲突很少见:在 24 小时内,99.94% 的购物车请求只看到一个版本。CRDT 则把合并交给数据类型本身;基于 CRDT 的协同编辑器把同样的思路用在共享文本上。
故障处理:hinted handoff、repair 与 gossip
Sloppy quorum 与 hinted handoff。 Dynamo 使用偏好列表中前 N 个健康的节点:如果 C 宕机,D 带着提示接管 C 的副本,并在 C 恢复后交还。写入继续可用,但从 B 和已恢复的 C 读取时,可能漏掉只有 A 和 D 确认过的写入。Cassandra 保持严格的 quorum:hint 只在 ANY 级别才计入一致性级别,并且在节点宕机 3 小时后停止(max_hint_window)。
Read repair 与 anti-entropy。 当响应不一致时,协调者会把最新版本写回过期的副本。对于冷数据,副本按键范围比较 Merkle 树,只同步有差异的范围。Cassandra 文档建议每个节点至少每 7 天运行一次 nodetool repair:tombstone 在 gc_grace_seconds(默认 10 天)之后被清除,未修复的副本可能让已删除的数据重新出现。
Gossip 与故障检测。 每个节点每秒与一个随机对等节点交换成员关系和 token 状态;所有节点都知道的 seed 节点可以防止环分裂。Cassandra 的 phi accrual 检测器在怀疑值超过 phi_convict_threshold(默认 8)时,把对等节点标记为宕机。
写入路径:commit log、memtable、SSTable
Cassandra 的存储引擎是针对写入优化的日志结构合并(LSM)树:
- 把写入追加到 commit log。默认情况下(
periodic),Cassandra 立即确认,并每 10 秒同步一次,所以崩溃可能丢失这段时间的数据。 - 把它插入 memtable,这是内存中的有序结构。
- 把写满的 memtable 刷新为磁盘上不可变的有序 SSTable。
- 在后台压缩 SSTable,保留最新版本并丢弃已过期的 tombstone。
读取先查 memtable,再查 SSTable,每个 SSTable 的 Bloom filter 会跳过不可能包含该键的文件:每个键 10 位、7 个哈希函数时,误报率是 (1 − e^(−0.7))^7,约 0.8%。Size-tiered compaction 是默认策略;Cassandra 5.0 建议新的工作负载使用其 unified 策略。
真实系统与论文对比
| Dynamo (2007) | Amazon DynamoDB | Cassandra 5.0 | Riak KV | |
|---|---|---|---|---|
| 分区 | MD5 环,等大分区 | 按大小或流量拆分的范围 | Murmur3 环,每节点 16 个 token | 160 位环,64 个分区 |
| 复制 | 无 leader,每个键 N 份 | 跨 AZ 的 3 个副本,Multi-Paxos leader | 无 leader,按数据中心 | 无 leader,n_val 3 |
| 一致性 | Sloppy quorum | 默认最终一致;强一致读取走 leader | 每个请求设置一致性级别 | Sloppy quorum、pr 和 pw |
| 冲突 | 向量时钟 | Leader 为写入排序;跨 Region 为 last writer wins | Last Write Wins | Sibling 或 CRDT |
| 存储 | Berkeley DB、MySQL | B 树加 write-ahead log | LSM 树 | Bitcask、LevelDB |
DynamoDB 只是名字相同,设计并不相同:根据其 2022 年 USENIX 论文,分区 leader 在三个副本中有两个记录日志后就确认写入。全局表默认在 Region 之间采用 last writer wins;截至本文撰写时(2026 年 11 月),它们还在恰好三个 Region 中提供多 Region 强一致性。
Dynamo 风格键值存储图
图表内容
- Node B
- Node A
- Node C
- Node F
- Node D
- Node E
- Cart service
- Inside every node: LSM write path
- Commit log
- Memtable
- SSTables
- put(k, ctx, v)
- replica 2: ack
- replica 3: no reply
- hinted write for C: ack
- hand off when C recovers
- then insert
- flush when full
- gossip
这张图的读法如下:
- 环。 从圆点所示的 hash(k) 顺时针走,得到 A 到 F 的偏好列表。
- 写入。 购物车服务把 put(k, ctx, v) 发给协调者 A,A 复制到 B 和 C。
- 故障。 C 宕机,所以 D 带着提示接管 C 的副本(虚线琥珀色),并在之后交还。W = 2 时,A 和 B 写入后 put 就返回。
- Gossip(点线)在随机的节点对之间进行。
- 面板列出 N、R、W 以及每个节点的写入路径。
把键值存储图画清楚
- 跟踪一个键。 标出它的哈希,写出它的偏好列表,并把 N、R 和 W 放在旁边;没有键的环什么也解释不了。
- 画出故障。 红色节点加一条虚线的后备边,比文字更快地解释 sloppy quorum。
- 展示故障域: 按机架或可用区给副本着色,让评审者能检查没有两个副本处于同一个故障域。
- 把节点内部留给一个内嵌图。 先画集群。
一个常见错误:从客户端向每个副本画箭头,却没有协调者,这会掩盖由谁决定写入成功。循序渐进的系统设计方法介绍了布局和数字。
在 Archboard 中构建
- 用 Google 或 GitHub 登录并创建一个图表。
- 从基础包添加一个大的灰色椭圆,作为 token 环。
- 从网络包把六个服务器节点放在环上,按顺时针从 Node A 到 Node F。把 A 和 B 涂成绿色,C 涂成红色,D 涂成琥珀色,并用基础包的文本注释标出它们的角色。
- 在环上 Node A 之前添加一个小的椭圆表示 hash(k),并加一个文本标签。
- 从 C4 模型包添加一个容器表示购物车服务,并画一条 put(k, ctx, v) 边指向 Node A。
- 画出各条边:A 到 B 为绿色实线,A 到 C 为带叉形箭头的红色虚线,A 到 D 和 D 到 C 为琥珀色虚线(hinted write,然后 handoff),F 和 E 之间为点线 gossip 边,并加一个文本注释。
- 从基础包添加一个 Markdown 块,写入 N、R、W 和场景说明。
- 从基础包添加一个框架,放入 C4 模型包的三个组件节点:Commit log、Memtable 和 SSTables,自上而下连接,并加一个关于 Bloom filter 的文本注释。
这个示例共用 14 个图表节点,在 Free 套餐的限制之内。
常见问题
如何设计分布式键值存储? 用一致性哈希分区,把每个键复制到 N 个节点,调整 R 和 W,选择冲突策略,加入 hinted handoff 和 anti-entropy repair,并在每个节点上运行 LSM 树。
R + W > N 是什么意思? 在 N 个副本中,写入等待 W 个,读取等待 R 个。如果 R + W 大于 N,每次读取都至少会到达一个持有最新已确认写入的副本。
DynamoDB 基于 Dynamo 论文吗? 只是部分如此:每个分区有三个副本,带 Multi-Paxos leader 和 B 树存储,而不是 sloppy quorum 和向量时钟。
什么是 hinted handoff? 由另一个节点带着提示保存无法访问的副本的写入,并在副本恢复后送达。Cassandra 默认在节点宕机 3 小时后停止为它保存 hint。
应该用 Last Write Wins 还是向量时钟? Last Write Wins 适合可以接受丢失并发更新的数据,例如会话。当每次更新都重要时,比如购物车和计数器,请使用向量时钟或 CRDT。