设计分布式键值存储

分布式键值存储提供最简单可能的接口——get(key) 和 put(key, value)——但构建一个跨数千节点保持可用且快的,是个经典难题。这是 Amazon Dynamo、Cassandra 和 Riak 背后的设计。有趣的决策全关于分布:如何在集群变化时不重洗一切地把键散到节点、如何为持久性和可用性复制、如何保持副本一致(或决定不)、如何在无单一 leader 下挺过节点故障继续服务。它是我们 DDIA 复制笔记和分区里分布式数据想法最直接的应用。

⚡ 速览要点

一致性哈希把键散到一个环上,使增删节点只移动一小片键——绝不整个键空间(无 hash mod N)。
虚拟节点给每个物理节点环上许多点,平滑负载并使再平衡均匀。
复制到 N 个节点(环上接下来的 N 个 = preference list);一个协调者处理每个请求。
经 quorum 可调一致性——若 W + R > N 读集和写集重叠,所以读看到最新写。为读多/写多负载调 W/R。
无主 = 总可写——并发写造成冲突版本,用向量时钟(sibling)或最后写入胜调和。
故障是常态——hinted handoff 覆盖临时宕机、Merkle 树反熵修复永久的、gossip 传播成员关系。
它是个 AP 系统——分区下它偏好可用性而非强一致(CAP)。

tldr

用一致性哈希 + 虚拟节点分区键。把每个键复制到 N 个节点(preference list)。用 quorum(W + R > N)使一致性可调。因为无 leader,并发写用向量时钟(或 LWW)调和。用 hinted handoff(临时)和 Merkle 树反熵(永久)挺过故障,用 gossip 协议跟踪成员关系。结果是一个高可用、横向可扩展的 AP 存储。

the hash ring (N = 3 replication)

          0 / 2^160
              ▲
       NodeD  │  NodeA
          ╲   │   ╱
           ╲  │  ╱      key "user:42" 哈希到这 ─┐
            ╲ │ ╱                                ▼
   ◀─────────●─────────▶   顺时针走 → 存到
            ╱ │ ╲          NodeA, NodeB, NodeC  (N=3)
           ╱  │  ╲         = "preference list"
          ╱   │   ╲
       NodeC  │  NodeB
              ▼

第 1 步 — 澄清需求

功能:get(key)、put(key, value)、delete(key);值是适度大小(比如 ≤ 1 MB)的不透明 blob;无复杂查询或 join。非功能——这些是全部重点:高可用性("总可写",即便故障期间)、低延迟(个位数 ms)、横向可扩展(加节点增长)、可调一致性(让调用方用一致性换延迟),和分区容错。我们显式接受最终一致性为默认——那是 Dynamo 为可用性做的刻意取舍。

第 2 步 — 容量估算

假设 100 TB 数据、平均值 10 KB → ~100 亿键。1M 操作/秒、9:1 读写比,那是 ~900K 读和 ~100K 写每秒。商用节点各持 ~2 TB、N=3 复制,你需要约 (100 TB × 3) / 2 TB ≈ 150 节点,加余量。这些数字证明需要自动分区、复制和去中心化故障处理——没有单一协调者能跟上,且此机群规模下节点故障是日常事件。

第 3 步 — API 设计

API with consistency knobs

get(key, consistency = QUORUM)   → (value(s), version)
put(key, value, version, consistency = QUORUM)   → ok
delete(key, version)

# consistency ∈ {ONE, QUORUM, ALL} — 映射到多少
# 副本必须响应(读用 R,写用 W)

传给 put 的 version 是客户端从先前 get 得到的 context——它让存储检测并发修改。有未解决冲突时,一次读可能返回多个版本(下面细说)。

第 4 步 — 用一致性哈希分区

天真地把键分给 hash(key) mod N 个节点是个陷阱:改 N 重映射几乎每个键(见我们的分区笔记)。一致性哈希修这个。把键哈希到一个固定环(如 0…2¹⁶⁰);把每个节点哈希到同一环;一个键属于顺时针走遇到的第一个节点。现在增删节点只移动它与邻居之间的键——一小片。为避免不均分布(和节点离开时不均负载),每个物理节点被映射到散布环上的许多虚拟节点,这平滑数据和负载,使离开节点的份额分散到许多幸存者而非倾倒给一个。

第 5 步 — 复制

为持久性和可用性,每个键存在 N 个节点:拥有它的节点加环上接下来 N−1 个不同物理节点。这个有序列表是键的 preference list。任何节点都能为一个请求充当协调者(coordinator)(通常是 preference list 里第一个);它把操作转发给副本并收集响应。因为每个副本都能服务读和接受写,没有 leader、因此无故障转移——只要足够副本可达系统就保持可写。

第 6 步 — 可调一致性:Quorum

一致性是一个旋钮,不是固定设置。有 N 个副本,一个写等 W 个确认、一个读查询 R 个副本。关键不等式:

quorum tuning (N = 3)

W + R > N   ⇒   读 quorum 和写 quorum 重叠 ⇒ 读看到最新

  W=2, R=2, N=3 :  2+2 > 3  ✓  平衡(常见默认)
  W=1, R=3      :  写快,读较慢/一致
  W=3, R=1      :  读快,写持久但慢
  W=1, R=1      :  最快,但无重叠 → 可能读到陈旧

设置	行为	何时用
W=1, R=1	最低延迟,最终一致	缓存、指标、容忍陈旧
W=2, R=2 (N=3)	较强(quorum 重叠)	通用默认
W=N 或 R=N	一侧完全一致,低可用	读多或写少的关键数据

见我们的 DDIA 复制笔记看完整 quorum 推导。一个微妙处:网络分区下,宽松 quorum(sloppy quorum)让 W/R 由其他可达节点(不严格是前 N)满足,保持系统可用但削弱重叠保证——与下面的 hinted handoff 配对。

第 7 步 — 数据版本化与冲突解决

无 leader 且允许并发写,两个客户端能在不同副本上同时更新同一键,产生分歧版本。存储需要一种方式判断一个版本是否派生自另一个(可安全覆盖)、还是它们真正并发(真冲突)。向量时钟(vector clock)捕获这个:每个值携带一个 (node, counter) 对列表。若时钟 A 完全 ≤ 时钟 B,B 取代 A;否则它们并发、两者作为 sibling 保留。

vector clocks detect concurrency

write on A:  v = [A:1]
write on A:  v = [A:2]              # A:2 派生自 A:1 → 覆盖

现在两个客户端分叉:
  client X (见到 A:2):  [A:2, B:1]   # 经节点 B
  client Y (见到 A:2):  [A:2, C:1]   # 经节点 C
  → 谁都不 ≤ 另一个 → 并发 → 两者都作为 sibling 保留
  → 下次读返回两者;应用(或 LWW)合并它们

调和要么是最后写入胜(简单,但静默丢数据——时钟偏移下有风险,见不可靠时钟),要么是应用级合并(如 Dynamo 的购物车把购物车并集,使无 add 丢失)。存储暴露 sibling;应用决定。

第 8 步 — 处理临时故障:Hinted Handoff

若 preference list 里一个副本短暂宕机,协调者不阻塞。它转而写到下一个健康节点,标上一个记录预期接收者的 hint。当宕掉的节点恢复,持有者把数据交回并删除 hint。这个 hinted handoff 让写在瞬时宕机中继续成功——系统"总可写"的一个核心原因。

第 9 步 — 处理永久故障:用 Merkle 树反熵

当一个节点永久消失(或不可达久到 hint 过期),副本漂移分开。为高效重新同步而不比较每个键,每个节点在它的键范围上保留一棵 Merkle 树(哈希的树)。两个副本自顶向下比较树:若根哈希匹配,它们相同、无数据移动;若不同,它们只下降到不同的分支,只传输实际分歧的键。这个反熵(anti-entropy)修复最小化交换的数据。

第 10 步 — 成员关系与故障检测:Gossip

一个去中心化系统不能依赖一个谁活着的中央注册表。相反节点用 gossip 协议:每个节点周期性与几个随机对等节点交换它对集群成员关系和环分配的视图,所以关于加入、离开和分区方案的知识在数秒内流行病式传播到整个集群。故障检测同样去中心化(如对等节点停止听到某节点则怀疑它死了),避免任何单点故障或协调瓶颈。

第 11 步 — 读/写路径

把它放一起做一个 put:客户端把请求发给任何节点,它成协调者;它计算 preference list、把写(带更新的向量时钟)发给 N 个副本,W 个确认后返回成功。get 对称工作:协调者查询 preference list、等 R 个响应,若它们版本不一致它返回所有 sibling(并触发读修复(read repair)——把最新版本推回陈旧副本)。每个节点上的本地存储通常是为高写吞吐优化的 LSM-tree 引擎(见我们的存储与检索笔记)。

第 12 步 — 扩展与热点 key

吞吐和存储通过加节点增长;一致性哈希意味每个新节点以最小数据移动从邻居身上抬走公平的一片负载,而虚拟节点保持分布均匀。剩下的危险是热点 key——单个键收到不成比例的流量——任何分区都修不了它,因为它住在一组副本上。缓解:在客户端/边缘缓存热点 key,或把一个逻辑热点 key 用后缀拆成几个物理键并在读时合并。

第 13 步 — 关键取舍

可用性 vs 一致性(CAP)。这是个 AP 设计:分区下它保持可用并服务可能陈旧的数据而非拒绝请求。一个 CP 存储(如建在共识上的)会相反——见一致性与共识。
Quorum 调优。W/R 让每个负载挑它在延迟 vs 一致性曲线上的点;没有全局正确答案。
冲突解决。LWW 简单但丢写;向量时钟 + 应用合并保留数据,代价是客户端复杂度和 sibling 处理。
无主的简单 vs 推理困难。无 leader 意味无故障转移和极好可用,但最终一致把真实复杂度推给应用开发者。

总结

Dynamo 风格存储是教科书 AP 系统:一致性哈希做分区、N 路复制配 quorum 可调一致性,和去中心化故障处理(hinted handoff、Merkle 反熵、gossip)。每个选择都用强一致换可用性和规模——所以正确的面试动作是显式陈述那个取舍并把每个机制系回它。

🎯 面试速答

为什么一致性哈希而非 hash mod N?增删节点只重映射一小片键而非几乎全部;虚拟节点保持分布均匀。
W + R > N 保证什么?读 quorum 和写 quorum 至少重叠一个节点,所以一次读看到最新写——可调一致性旋钮。
无 leader 怎么处理并发写?向量时钟检测版本是因果有序还是并发;并发 sibling 被保留并合并(应用逻辑或 LWW)。
临时 vs 永久故障恢复?hinted handoff 覆盖瞬时宕机(写去一个带 hint 的替身);Merkle 树反熵通过只传输不同的键修复长期分歧。
是 CP 还是 AP?AP——分区下保持可用且最终一致。