跳到正文

键值存储系统设计:分区、复制与 Quorum

一步步设计 Dynamo 风格的键值存储:哈希环、复制、R + W > N 的 quorum、冲突解决、hinted handoff、gossip 和 LSM 引擎。

· 创始人兼开发者

发布于

A 到 F 六台服务器位于一个环上;键 k 哈希到 A 之前。购物车服务向 A 发送 put(k, ctx, v),A 复制到 B(ack)和 C(宕机)。虚线的 hinted write 发往 D,D 稍后交给 C。面板列出 N = 3、W = 2、R = 2 以及 LSM 写入路径。

购物车服务每次点击都要写入,到了 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)树:

  1. 把写入追加到 commit log。默认情况下(periodic),Cassandra 立即确认,并每 10 秒同步一次,所以崩溃可能丢失这段时间的数据。
  2. 把它插入 memtable,这是内存中的有序结构。
  3. 把写满的 memtable 刷新为磁盘上不可变的有序 SSTable。
  4. 在后台压缩 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 风格键值存储图

A 到 F 六台服务器位于一个环上;键 k 哈希到 A 之前。购物车服务向 A 发送 put(k, ctx, v),A 复制到 B(ack)和 C(宕机)。虚线的 hinted write 发往 D,D 稍后交给 C。面板列出 N = 3、W = 2、R = 2 以及 LSM 写入路径。

21 个组件 · 8 个连接

在 Archboard 中打开
图表内容
  • 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
键 k 哈希到六节点环上的一个点。Node A 协调 put 并复制到 B 和 C。C 已宕机,所以 D 保存带提示的副本并在之后交还。侧边面板列出 N、R、W 以及每个节点内的写入路径。

这张图的读法如下:

  • 环。 从圆点所示的 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 中构建

  1. 用 Google 或 GitHub 登录并创建一个图表。
  2. 从基础包添加一个大的灰色椭圆,作为 token 环。
  3. 从网络包把六个服务器节点放在环上,按顺时针从 Node A 到 Node F。把 A 和 B 涂成绿色,C 涂成红色,D 涂成琥珀色,并用基础包的文本注释标出它们的角色。
  4. 在环上 Node A 之前添加一个小的椭圆表示 hash(k),并加一个文本标签。
  5. 从 C4 模型包添加一个容器表示购物车服务,并画一条 put(k, ctx, v) 边指向 Node A。
  6. 画出各条边:A 到 B 为绿色实线,A 到 C 为带叉形箭头的红色虚线,A 到 D 和 D 到 C 为琥珀色虚线(hinted write,然后 handoff),F 和 E 之间为点线 gossip 边,并加一个文本注释。
  7. 从基础包添加一个 Markdown 块,写入 N、R、W 和场景说明。
  8. 从基础包添加一个框架,放入 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。

免费开始 — 1 个席位,无需信用卡。

相关文章

← 返回博客

一分钟打开画布

使用 Google 或 GitHub 登录。单席位免费,团队加入后再升级。