Lesson 0019 · 系统设计 · Phase 5 进阶案例 · 毕业进阶
大案例 VII：分布式 KV 存储（Dynamo 风格）
与你的 Mission 的关系
这是课程的毕业进阶题：不再是「用组件」，而是「成为组件」——自己设计 Redis/Redis Cluster 之下的那层存储。它把 L6 的一致性哈希、L9 的 quorum、L7 的可靠投递、L18 的故障隔离全部总装。面试中这是 senior/staff 级题目；读懂它，你再看任何 NoSQL 文档都像看说明书。
件 ①需求表（Step 1）
| 类别 | 内容 |
|---|---|
| 功能（MVP） | 仅两个操作：put(key, context, value) / get(key, context)；value ≤ 1MB。明确不做：二级索引、跨 key 事务、SQL 查询——砍功能是它扩展性的来源 |
| 非功能（本题灵魂） | 10 亿级 key；P99 < 10ms；可用性优先：网络分区时读写都不停（AP 系统明确站位，L9）；一致性可调（用户自选 W/R）；横向扩展无中心节点 |
| 关键洞察 | 「永远可写」意味着分区时两个机房各自接受写入 → 冲突必然出现 → 本题的深水区全部在冲突处理（件 ⑥），而不是存储本身 |
件 ②容量估算（Step 2，全程算式）
| 指标 | 算式 | 架构暗示 |
|---|---|---|
| 数据量 | 10 亿 key × 1KB = 1 TB；N=3 副本 → 3 TB（+ 压缩 ~×0.6 → 2 TB） | 20 节点集群每节点 ~100GB，廉价磁盘即可 |
| QPS | 读 10 万/s + 写 5 万/s；单节点安全线 ~2 万简单 KV QPS → ≥ 8 节点，取 20 留余量 | 分片 + 副本分担读——每个机制都要乘以 N 副本的写放大 |
| 写放大 | 每次 put 实际写 N=3 份（协调 + 复制）→ 集群真实写 IO 15 万/s | N 是可用性/持久性 vs 成本的旋钮 |
| 故障恢复 | 单节点宕机：接管它的 vnode 持有 ~1/20 数据（一致性哈希，L6）→ 100GB 迁移 @ 100MB/s ≈ 17 分钟 | 迁移期间 hinted handoff 兜写（件 ⑥） |
件 ③API 定义（Step 3）
put(key, context, value)
# context: 客户端上次 get 返回的版本向量（可空 = 新 key）
# resp: {key, new_context, nodes_confirmed} # nodes_confirmed 达到 W 才返回
get(key, quorum=true)
# 向 R 个副本并发读
# 单版本 → 直接返回 {value, context}
# 多版本 → {values: [v1, v2], context} # 冲突！交给客户端合并（件 ⑥）API 里的两个设计声明
context（版本向量）随值返回——客户端下次 put 带上它，系统才知道「你基于哪个版本改的」，这是检测并发写冲突的根基。get 可能返回多个值——API 层面就承认最终一致，不假装强一致（L9 的诚实）。
件 ④数据与元数据 Schema（Step 3）
| 存储 | 结构与设计 |
|---|---|
| 数据分区（vnode） | key → hash(key) → 环上顺时针首个 vnode；每物理节点 ~100 个 vnode（L6：均匀 + 异构加权） |
| 副本列表（preference list） | key 的 N=3 副本 = 环上顺时针 3 个 vnode；必须跨机架/跨 AZ（跳过同故障域节点）——一份机器故障不应丢副本 |
| 对象记录（每条数据） | key, [value, version_vector] 列表（可能多版本并存）, timestamp, ttl。LSM 引擎落盘（写优化，L16 同款选择） |
| 集群成员表（gossip） | node_id → {vnode 列表, 状态(up/down/leaving), 心跳版本}；每节点存全表，gossip 协议秒级收敛 |
件 ⑤put 与 get 的完整时序（Step 3，本课核心）
N=3, W=2, R=2 ｜ 客户端请求任意节点（它成为协调者 coordinator）
【put 流程】
client → coordinator(node5)
│ ① hash(key) → 定位 preference list [node5, node11, node17]
│ ② 本地写入（W 的第 1 份）
│ ③ 并行发给 node11、node17（W=2：至少 1 个远端确认）
│ ├─ 正常：写成功，回 ACK
│ └─ node17 宕机 → 写入「代收笔记」：
│ hint(node17, key, value) 存在 node11 上 ←【hinted handoff】
│ ④ 收到 2 份确认（含自己）→ 返回 client {new_context}
└ node17 恢复后：gossip 发现自己的代收笔记 → 补写 → 删除笔记
【get 流程（发现冲突）】
client → coordinator(node5)
│ ① 并行读 [node5, node11, node17]（R=2：最快 2 个响应即可）
│ ② 比较版本向量：
│ node5: [A:3, B:1] ＞ node11: [A:2, B:1] → 丢弃旧版，返回新值
│ node5: [A:3, B:1] vs node17: [A:2, B:2] → 互不支配 → 冲突！
│ ③ 两个版本都返回 + 合并后的 context
└ client 合并（购物车：并集）→ put(merged) → 全副本收敛到 [A:3, B:2]
【后台对账（反熵）】
每 vnode 对维护 Merkle 树（叶子=区块哈希）→ 比对树根
→ 根不同则下钻找差异区块 → 只同步差异数据 → 修复 hinted 丢失/静默损坏件 ⑥关键机制选型对比（冲突的两种哲学）
| 决策点 | 选项 A：向量时钟 | 选项 B：Last-Write-Wins | 结论与代价 |
|---|---|---|---|
| 冲突处理 | 记录「谁基于哪个版本改的」，并发写都保留，客户端合并 | 按时间戳只留最新，旧版本直接覆盖 | 购物车类场景必须 A（LWW 会丢掉另一机房的加购）；计数器/覆盖写类用 B 更简单。Dynamo 允许按应用选择——把一致性策略做成参数 |
| W/R 配置 | W=2, R=2（quorum，偏一致） | W=1, R=1（最低延迟，弱一致） | W+R>N=3 保证读到最新（L9 仲裁旋钮）；「写多读少」场景常见 W=2/R=3，反之 W=3/R=2——按读写比拧旋钮 |
| 临时故障 | 拒绝写（等节点恢复） | hinted handoff：邻居代收 | 选 B：「永远可写」的承诺靠它兑现；代价：代收期间该数据少一份真实副本（仍满足 N-1） |
| 数据修复 | 全量对账（扫全部数据） | Merkle 树增量对账 | Merkle 根比对 O(log n) 定位差异——100GB 的 vnode 只传差异区块；代价：维护树的开销。gossip 只管成员存活，管不了数据正确性 |
件 ⑦失败模式与应对（Step 4）
| 故障 | 应对 |
|---|---|
| 节点宕机（数据还在盘上） | gossip 标记 down → 读写避开；恢复后 hinted handoff 补齐 + Merkle 对账校验——临时故障不迁移数据 |
| 节点永久丢失（盘坏） | 新节点加入 → 按 vnode 归属从其他副本全量搬运（~100GB，一致性哈希保证只搬这一个节点的份额） |
| 机房级故障 | 副本跨 AZ 放置（preference list 规则）→ 单 AZ 全灭仍有 2 副本服务；W=2 时跨 AZ 写延迟上升（L2 RTT 数字兑现） |
| 向量时钟膨胀（客户端几百个合并版本） | 版本向量截断（保留最近 K 个参与方）；超长冲突自动降级 LWW 并告警——元数据膨胀是向量时钟的真实成本 |
| 热点 key（单个 key 10 万 QPS） | 存储层无解（单 key 定位单 vnode）→ 上移解决：应用层 key 加盐拆分 / 缓存层（L5 热 key 手段）——诚实承认：基础设施层治不了业务热点 |
| 删除的数据复活（副本同步旧值） | tombstone + GC 窗口（如 10 天内 tombstone 不可清）——删除也是一次写，必须走同样的复制与对账 |
件 ⑧演进路线（v1 → v2）
- v1：单机 KV + 主从复制——功能验证；
- v2：一致性哈希分片 + N=3 复制 + quorum + hinted handoff——「可扩展的 AP 存储」成型；
- v3：向量时钟 + 客户端合并、Merkle 反熵、gossip 成员管理、多机房副本——完整 Dynamo；
- v4（思考题）：加一层 Raft 的 CP 模式给「需要强一致的 key」——同一存储内按 key 选择 CAP 站位（L9 按数据项选一致性的终极形态）。
件 ⑨面试官追问预测
| 追问 | 答案要点 |
|---|---|
| 「为什么不用 Raft 做复制，非要 quorum？」 | Raft = CP：分区时少数派拒绝服务，违背「永远可写」的需求（购物车不能因为机房失联就停写）。quorum = AP：可用性优先、冲突留给合并。先选 CAP 站位，再选算法——不是 Raft 不够好 |
| 「客户端合并太麻烦，能全用 LWW 吗？」 | 能，但要明说代价：并发写会静默丢更新（两机房同时改同一条 = 丢一边）。适合不可变/覆盖语义（session、配置）；购物车、计数器必须向量时钟或 CRDT |
| 「W=2,R=2 就真的强一致吗？」 | 不是。quorum 只保证「读到至少一份最新」；并发写之间的冲突仍要靠版本向量暴露。quorum 读到最新 ≠ 线性一致——L9 一致性菜单里它仍低于线性一致 |
| 「和 Redis Cluster 什么区别？」 | Redis Cluster：主从 + gossip 分片，故障时从库接管（偏 CP-倾向的恢复模型），持久化弱；Dynamo：多副本无主、可调 quorum、为永远可写设计。可用性站位决定架构形态 |
| 「Cassandra 学了 Dynamo 什么？」 | 一致性哈希 + vnode、无主 quorum 读写、hinted handoff、tombstone——但它把冲突处理简化为 LWW + 时间戳（工程取舍：牺牲合并正确性换易用性） |
§·随堂检测
§·检索练习
盖住全部内容：① 默写 put 的 4 步时序（含 node17 宕机的分支）；② 默写 get 发现冲突的处理；③ 解释 W/R 旋钮与「永远可写」的关系。
核对要点
① 定位 preference list → 本地写 → 并行复制（宕机节点由邻居 hinted 代收）→ 收满 W 份确认返回 context。② 并行读 R 份 → 版本向量比较：支配关系淘汰旧版；互不支配 → 多版本返回 + context，客户端合并后 put 回写。③ W/R 越大越一致越慢；W+R>N 读到最新；但「永远可写」在分区时仍靠 AP 站位 + 冲突合并兑现——quorum 是延迟/一致的旋钮，不是强一致的证明。
§·本周行动
行动任务（约 40 分钟）
精读 Dynamo 论文 §4（本课骨架的原文），做两件事：① 对照件 ⑤⑥，找出论文里我没讲到的细节（提示：内部降级链、负载不均衡的季节模式）；② 查你们公司在用的存储（Redis Cluster？Cassandra？MongoDB？）对应本课哪个机制的哪种变体，写三行对照笔记。
§·延伸资源
- 首选精读：Amazon Dynamo (SOSP 2007)——本课的原文母体，§4 逐节对照[1]
- 工业后裔：Apache Cassandra 官网文档——Dynamo 思想 + Bigtable 数据模型的合成体[2]
- 向量时钟（维基百科）——版本支配关系的数学定义[3]
- ← 回到 Lesson 0015 毕业课 或 课程总目录
🎓 读论文遇到卡点（向量时钟支配关系、Merkle 树下钻）随时问。能把 Dynamo 讲明白的人，面试系统设计轮基本不会再有对手。