案例 9：设计分布式键值存储

这道题考的是分布式系统的基本功：分区、复制、一致性、故障处理，再加上单机存储引擎。它没有唯一的标准答案，关键在于每个选择都能说清楚代价。下文以 Dynamo 风格（高可用、一致性可调）为主线，最后再对比基于 Raft 的强一致方案。

说明：这里的“Dynamo 风格”指 Amazon 2007 年 Dynamo 论文里的无主（leaderless）复制设计，Cassandra、Riak 都沿用了这套思路。它和 AWS 今天的 DynamoDB 服务不是一回事：DynamoDB 的每个分区有 leader，副本之间用 Multi-Paxos 复制。

1. 需求澄清

功能需求

• put(key, value)、get(key)、delete(key)
• key 和 value 都比较小（value 一般小于 10 KB）

非功能需求

• 数据量大到单机放不下，需要水平扩展
• 高可用：单个节点或机架故障不影响读写
• 低延迟：p99 在 10 ms 以内
• 一致性可调：有的业务要强一致，有的能接受最终一致

一定要问：发生网络分区时，系统优先保证可用还是一致？ 这个答案决定了整体路线。

2. 量级估算

• 100 亿个 key，每条平均 1 KB，共 10 TB；3 副本就是 30 TB
• 每台机器可用磁盘按 2 TB 算，至少 15 台，留出余量约 20~30 台
• 峰值 100 万 QPS，分到 30 台，每台 3 万多，基于 LSM 的单机引擎可以承受

3. 数据分区：一致性哈希

朴素的 hash(key) % N 在增删节点时，几乎所有 key 都要搬家。一致性哈希把节点和 key 都映射到同一个环上，key 归属于顺时针方向遇到的第一个节点。增删一个节点只影响相邻的一段区间。

hash ring (0 ~ 2^64-1), clockwise:
 ... A1 ---- k1 ---- B2 ---- C1 ---- k2 ---- A2 ---- B1 ...
 k1 -> B2 (物理机 B)    k2 -> A2 (物理机 A)
 N=3 时 k1 的 preference list: B, C, A

虚拟节点：每台物理机在环上放 100~200 个虚拟节点（上图的 A1、A2 都属于 A）。

• 负载更均匀，不会因为位置随机让某台机器分到过大的区间
• 节点下线时，它的数据分散给多台机器，而不是全部压给一个邻居
• 机器配置不同时，可以给配置高的机器分配更多虚拟节点

新节点加入时，从相邻节点流式拷贝它接管的区间，拷贝完成后再切换路由。成员信息通过 gossip 在集群内传播。

4. 复制

每个 key 存 N 份（通常 N = 3）：从 key 在环上的位置出发，顺时针选出 N 个不同的物理节点，这个列表叫 preference list。生产环境还要求副本分布在不同机架，甚至不同可用区。

5. 一致性：Quorum（N / W / R）

• W：写入时需要多少个副本确认才算成功
• R：读取时需要多少个副本响应
• 当 R + W > N 时，读的副本集合与写的副本集合必然重叠（至少共有一个副本）。在严格 quorum、没有并发写的前提下，读就能拿到最新已确认的写入

注意：R + W > N 并不等于线性一致。并发写入会产生冲突；sloppy quorum（见第 8 节）下写入可能落在 preference list 之外的节点上，读写集合不一定重叠；只在部分副本成功的写入也不会回滚。所以还需要版本控制。

6. 读写路径

flowchart TD
  accTitle: Quorum 写入（N=3，W=2）
  put["put(k, v)"] --> coord["Coordinator：hash(k) → preference list A, B, C"]
  coord --> a["A：追加 WAL → MemTable → ack"]
  coord --> b["B：追加 WAL → MemTable → ack"]
  coord -.-> c["C：慢或宕机，稍后通过修复机制补齐"]
  a --> ok["收到 W=2 个 ack，返回 OK"]
  b --> ok

Coordinator 可以是收到请求的任意节点（由它转发），也可以用“智能客户端”缓存分区表，直接把请求发给正确的节点，少一跳网络。

读路径类似：并发发给 N 个副本，等到 R 个响应，返回版本最新的值。如果发现某个副本版本落后，顺手把新值写回给它，这叫读修复（read repair）。

7. 冲突与版本

• 最后写入者胜（LWW）：每次写入带时间戳，取最大的那个，Cassandra 用的就是这种方式。实现简单，但各机器时钟会漂移，并发写入时其中一次会被静默丢弃，丢掉的甚至可能是实际上更晚的那次
• 向量时钟：每个版本记录 {节点: 计数器}，能判断两个版本是先后关系还是并发关系。并发时把多个版本都返回给客户端，由业务逻辑合并（比如购物车取并集）
• CRDT：使用天然可合并的数据类型（计数器、集合等），副本之间自动收敛

面试中可以这样回答：默认用 LWW，对不能丢写的业务提供向量时钟或 CRDT。

8. 故障处理

Merkle tree 的价值在于：两个副本可能各有上亿个 key，但只需要交换少量哈希值，就能定位到哪几段不一致。

删除要写墓碑（tombstone）。无主复制下不能直接把 key 物理删掉：如果某个副本当时宕机、没收到删除，之后反熵或读修复一比较，会把它手里的旧值当成“别的副本缺了的数据”同步回去，已删除的数据就“复活”了。所以 delete 实际上是写一条带版本的墓碑，像普通写入一样走 quorum、hinted handoff 和修复。墓碑要保留一段 grace 期（Cassandra 默认 gc_grace_seconds 为 10 天），这段时间必须比所有副本完成一轮反熵修复的周期更长，过期之后才能在 compaction 中真正清掉。

9. 单机存储引擎：LSM-tree

flowchart TD
  accTitle: LSM-tree 的写路径与读路径
  subgraph write ["写路径"]
    direction LR
    wal["WAL（顺序追加）"] --> mem["MemTable（内存，有序）"] -->|"写满后 flush"| l0[("SSTable L0")] -->|"compaction"| l1[("L1")] --> l2[("L2 …")]
  end
  subgraph read ["读路径：每个 SSTable 先查 Bloom filter"]
    direction LR
    r0["MemTable"] --> r1["L0"] --> r2["L1"] --> r3["…"]
  end

• 写入只需顺序追加日志、写内存表，把随机写变成了顺序写，所以写吞吐很高
• 读可能要查多层 SSTable，靠每个文件的 Bloom filter 跳过不含该 key 的文件，再加上 block cache
• 删除时写入一个墓碑标记（tombstone），等 compaction 时才真正清理；多副本场景下还要先过了第 8 节说的 grace 期
• 对比 B-tree：B-tree 读路径稳定，但有大量随机写；LSM 的写放大来自 compaction，读放大来自多层查找。KV 存储通常写入量很大，所以多选 LSM

10. 另一条路线：强一致（CP）

如果业务需要线性一致（配置中心、分布式锁、元数据服务等），可以把 key 空间切成多个 range，每个 range 是一个 Raft 组（Multi-Raft）：

• 写入由 leader 发起，复制到多数派后才提交
• 读走 leader（或用 lease read、read index），保证读到最新值
• 代价：leader 宕机后的选举期间，该 range 不可写；跨地域部署时，每次写入都要等一次跨区往返

11. 面试答题清单

1. 先问分区时选可用还是一致，据此确定路线
2. 按顺序讲：一致性哈希 + 虚拟节点、复制、N/W/R、冲突解决、故障处理、存储引擎
3. 每个机制都说明它解决什么问题、付出什么代价
4. 常见失分点：认为 R + W > N 就等于强一致；用 LWW 却不提时钟问题；忘了讲节点加入或退出时数据怎么迁移；删除不写墓碑，数据被反熵同步“复活”

12. 回答分级

分区与复制

• Bad：用 hash(key) % N 分片，加减节点几乎所有 key 都要搬；副本放在同一个机架。
• Good：一致性哈希加虚拟节点；N 个副本放在顺时针方向的 N 台不同物理机上，跨机架或可用区。
• Great：讲清新节点先从邻居拉取数据、再接流量，成员信息靠 gossip 传播；虚拟节点让故障节点的数据分散到多台机器恢复，也能按机器容量分配数量。

一致性与冲突

• Bad：认为 R + W > N 就是强一致；用最后写入者胜出（LWW）却不提时钟偏差。
• Good：解释 N/W/R 的取值和代价，说清读写集合重叠的含义；用版本处理并发写。
• Great：指出在并发写、sloppy quorum 和部分成功写入下，R + W > N 都不等于线性一致；按业务选择 LWW、向量时钟或 CRDT；需要线性一致时改走按范围分组的 Multi-Raft，并说明选主期间不可写、跨地域写要多一次往返。

故障与删除

• Bad：节点故障后只能等它恢复；删除时直接把 key 删掉。
• Good：用 gossip 检测故障，用 sloppy quorum 加 hinted handoff 应对临时故障，用读修复补齐落后的副本。
• Great：用 Merkle 树做反熵，只同步不一致的范围；删除写墓碑，墓碑的保留期要长于一轮完整的反熵修复，否则被删的数据会“复活”；单机引擎选 LSM-tree，并说清写放大和读放大。

13. 不同级别的期望