专业书籍精读 · System Design Interview 卷一 · 第 6 章
System Design Interview: An Insider's Guide · Ch 6 · Alex Xu · 2020
你往购物车里加一件商品，「购物车里现在有什么」这条记录得存在某处。它简单得不能再简单——一个名字对应一份内容，就像一本超大的通讯录。这一章教你把这本通讯录，从「一个人拿着的一个本子」，变成「几千台机器一起保管、坏掉几台照样能用」的东西。
亚马逊早年的购物车有个著名毛病：你删掉的商品，隔一会儿自己又回来了。这不是 bug，是刻意的取舍——宁可偶尔多一件商品，也绝不让「加入购物车」失败一次。这一章的整套设计，就是为了换来这句话：永远写得进去。
只有一个保管员时一切都好办：你问他、他答你，答案一定是最新的。可这个人会累（记不下那么多）、会请假（机器宕机）、会失联（网线断了）——那一刻整间店就停摆。换成一群人保管，新麻烦立刻来了：你去问，问到的是哪一份？万一他手里还是三分钟前的旧版本呢？
办法出奇地朴素：同一份记录抄给三个人保管。写的时候不用等三个人都签收，其中两个签收就算写成功；读的时候也不用问全部，随便问其中两个，谁手里的日期新就信谁。
妙就妙在：三个人里挑两个签收、再挑两个来问，这两拨人一定至少有一个是同一个——他既亲手签收过最新那份，又正好被你问到了。于是「不等所有人」和「一定读得到最新的」这两件看似矛盾的事同时成立了。剩下那个没签收的，事后会被悄悄补上。
那有人请假怎么办？三招，一招比一招重。互相打听：谁请假了、谁回来了没有中央点名的人，大家各自随机找几个同事聊两句、再把听来的传出去，几秒内全店都知道。找隔壁代管：三个人里少一个，就把东西交给隔壁，并贴张便条写清「这是替某某收的」，等他回来照条交还。比对总目录页：万一他请假太久、便条都过期了，两边账差一大截——这时不必一页页核对，先只比总目录页，一样就说明全都一样、直接收工；不一样再往下翻，一层层缩小，最后只搬真正对不上的那几页。
这套东西给你一个可以拧的旋钮：等几个人签收、问几个人，你自己定——等得越多越保险也越慢。购物车、点赞数、用户会话这类「偶尔差一点没关系」的东西非常适合它；而账户余额这种少一分都不行的，就别用这套——它天生允许你在极端情况下读到旧值，甚至让你删掉的东西自己回来。
把同一份数据抄给三个人，写只等两个签收、读只问两个，靠「两拨人必有重叠」保证读得到最新的；有人请假就找隔壁代管 + 留张便条，久了就比总目录页把账补齐。换来的是「永远写得进去」，代价是偶尔会读到旧值。
想进到具体机制、记号和示意图？ → 切到精读版
你以为这一章在设计「怎么存」，其实它九成篇幅在讲「机器挂了怎么办」。这是全书唯一一章不设计产品、而是造一个数据库——它把 Amazon Dynamo 那套无主（leaderless）设计拆成六个可独立替换的零件：分区、复制、quorum、冲突解决、故障处理、存储引擎。真正要带走的认知是：一旦你放弃了「有一个主节点说了算」，正确性就得靠这些机制一件件补回来——而每一件都要你先付出一点一致性。
put(key, value) 和 get(key) 两个动作的数据库，不支持表连接、多字段查询。N=3。W，读的门槛记作 R。本章是卷一 Part II「系统案例」的第 3 篇。上一章（Ch5 一致性哈希）交付的是一个零件，这一章是把那个零件装进一台整机——全书唯一一次带你走进数据库内部而不是产品外部。对应现实里 Amazon DynamoDB、Apache Cassandra、Riak、Voldemort 这一整族「Dynamo 系」存储，以及 ScyllaDB 这样的后来者。下启 Ch7（分布式唯一 ID），仍在「造基础设施」这条线上。
单机键值存储好写得离谱：一个内存哈希表就是全部。真正的问题只有一个——装不下，也挂得起。粗算个量级：10 亿个用户会话、每条 1 KB 就是 1 TB，一台 128 GB 内存的机器差着 8 倍；书里给的单机优化（压缩、热数据留内存、冷数据落盘）能顶一阵，但顶不过下一个数量级。更要命的是第二件事：不做分布式，写入可用性就等于一台机器的可用性——那台机器重启的三十秒里全站没人能加购物车，对亚马逊来说这是直接的营收损失。
所以这一章真正的题目不是「怎么存」，而是：当数据被抄成好几份、分散在会随时宕机的机器上时，「读到正确的值」这句话还是什么意思？
CAP 说的是一致性（Consistency）、可用性（Availability）、分区容忍性（Partition tolerance，指网络把集群切成互不相通的两半时系统还能不能工作）三者不可兼得。关键在于：P 不是一个选项，是一个事实——只要机器之间靠网络说话，网络就会断。所以真正的选择只在 C 和 A 之间，而且只在网络分区发生的那一刻才需要选。
书里的例子很干脆：三个副本 n1/n2/n3，n3 失联了。选 CP（如银行转账）：拒绝写入，宁可报错也不让余额出现两个版本。选 AP（如购物车）：照收不误，等 n3 回来再对账。Dynamo 选 AP，理由写在论文里——「加入购物车」这个动作永远不能失败。本章后面所有机制，都是在为这个选择擦屁股。
分区直接复用 Ch5 的一致性哈希环：key 哈希后落到环上某点，顺时针遇到的第一个节点就是它的归属。复制则是同一个动作再多走几步——从落点继续顺时针走，收下遇到的前 N 个节点。
这里有个必须记住的细节：环上是虚拟节点（virtual node），同一台物理机在环上有上百个位置，所以走的时候要跳过已经收过的物理机，否则三份副本可能挤在同一台机器上、一停电全没了。同理，生产环境还会要求这 N 个节点分布在不同机房 / 可用区——Netflix 的 Cassandra 集群就是 N=3 且横跨 3 个 AWS 可用区。
有了 N 份副本，「写成功」就得重新定义。Dynamo 的答案是三个数字：N 副本数、W 一次写要等几个副本确认、R 一次读要问几个副本。协调者把请求发给全部 N 个，但只要凑够 W（或 R）个回复就返回客户端。
核心结论是 W + R > N——白话讲就是：在 N 个副本里挑 W 个签收、再挑 R 个来问，只要这两个数加起来超过 N，两拨人就一定至少有一个重合（抽屉原理）。那个重合的副本既亲手写下了最新值、又被你读到了，所以你一定看得见最新的写入。Dynamo 生产中最常用的配置就是 (N,R,W) = (3,2,2)：2+2 > 3，成立。
注意这条保证的边界：它保证的是「读得到最新的那次写」，而不是线性一致（linearizability）。没有全局顺序、没有原子性、没有隔离级别——两个并发写谁在前谁在后，quorum 一个字都没说。这就直接引出下一件事。
无主系统里，两个客户端可以在同一毫秒往两个不同的副本写同一个 key，谁也不比谁「后」。单调递增的版本号在这里失效了，因为它假设了一条全局时间线。
Dynamo 的解法是向量时钟（vector clock）：每份值都带一串 [节点, 计数] 对，某个节点每改一次就把自己那格加一。比较两串时钟，如果一串的每一格都不小于另一串，说明它是后来的、可以直接覆盖；如果互有大小，说明这是两个真正并发的分支——系统检测到了冲突，但解不了，只能把两个版本一起交给客户端。
亚马逊购物车的合并策略就是取并集，这正是「删掉的商品会复活」的来源：删除在合并时打不过添加。代价还有两条：客户端被迫承担合并逻辑；时钟串会随参与写入的节点变多而变长，Dynamo 用截断阈值控制。不过实测数据很能安慰人——Dynamo 生产上 24 小时内 99.94% 的请求只看到一个版本，冲突罕见到几乎不用担心。
值得注意的是，Cassandra 没有采用向量时钟，而是退回最简单的「写入时间戳大的赢」（last-write-wins）：实现简单、客户端零负担，代价是并发写会被静默丢弃一个，且依赖机器时钟准确。这是同一族系统里很有代表性的一处分歧。
（1）检测：gossip。最朴素的做法是所有节点互相心跳，但 n 个节点就是 O(n²) 条链路，几百台就撑不住。gossip 改成：每个节点维护一张成员表（谁、心跳计数、最后更新时间），周期性随机挑几个同伴交换这张表，取每一项里更新的那份。信息像流言一样以对数级速度扩散全网，几秒内收敛，且没有单点。某项心跳计数长时间不涨，就先标记为可疑，再由多个节点确认后判定下线。
（2）临时故障：sloppy quorum + hinted handoff。如果严格要求「前 N 个节点里凑够 W 个」，那么挂掉两台就写不进去了——这违背了「永远可写」的初衷。宽松 quorum（sloppy quorum）改成：从环上顺着往下找，凑够 W 个健康节点就行，哪怕它本来不该存这个 key。这个临时代管的节点会给这份数据附一张提示（hint），写明「这是替 C 收的」；等 C 回来，它把数据回放给 C，然后删掉提示。Cassandra 的 hint 默认最多保留 3 小时，超时就交给下一层。
（3）永久故障：Merkle 树反熵。节点下线太久（或换了块新盘），差异可能大到没法靠提示补。逐条比对 10 亿个 key 显然不可行。Merkle 树把 key 空间切成桶，每个桶算一个哈希作叶子，父节点是子节点哈希的哈希，一路收拢到根。两个副本先比根哈希：一样就说明整棵树完全一致、一次比较收工；不一样就往下走，只沿着哈希不同的那条路下钻。同步的代价与差异量成正比，而不是与数据总量成正比——这是它全部的价值所在。
把上面五件事拼好，剩下的就是每台机器自己怎么落盘。这里书里跟的是 Cassandra 的路子。写：先顺序追加到 commit log（宕机后靠它重放），再写进内存里的 memtable；memtable 攒到阈值，整批排好序刷成一个只读的 SSTable。全程没有随机写，所以写吞吐极高。读：先查 memtable，命中就返回；不命中就用布隆过滤器快速排除掉绝大多数不可能含有这个 key 的 SSTable，只去真正可能的那一两个文件里取。
这一章的灵魂全在旋钮上。先看 NWR 怎么调：
表 1 · 同一个 N=3，四种 NWR 配置的性格
| 配置 | 性格 | 代价 | 适合 |
|---|---|---|---|
R=1, W=3 | 读极快，问一个就返回 | 写要等全部副本，任何一台慢或挂就写不进 | 配置项、只读为主的元数据 |
W=1, R=3 | 写极快，一个确认就返回 | 读要等全部副本，读延迟被最慢的那台决定 | 日志、埋点这类写重读轻的负载 |
R=2, W=2 | 满足 W+R>N，读得到最新写，读写都能容忍挂一台 | 读写延迟都由「第 2 快」的副本决定 | 绝大多数场景的默认；Dynamo 生产常用值 |
R=1, W=1 | 读写都最快、可用性最高 | 1+1 < 3，不保证读到最新写 | 能容忍陈旧值：计数器、缓存、位置上报 |
再看冲突怎么收场——这是同一族系统里分歧最大的地方：
表 2 · 三种冲突解决策略
| 策略 | 怎么做 | 诚实的代价 | 谁在用 |
|---|---|---|---|
| 时间戳取胜 last-write-wins | 比较写入时间戳，大的赢 | 并发写会被静默丢弃一个；依赖机器时钟准确，时钟漂移直接变成丢数据 | Cassandra（默认） |
| 向量时钟 vector clock | 记录因果关系，能区分「后写」和「真并发」 | 只能发现冲突、不能解决；多版本抛给客户端；时钟串会变长，需截断 | Dynamo、Riak |
| 应用层合并 / CRDT | 按业务语义定义合并规则（如购物车取并集、计数器求和） | 要为每种数据类型单独设计；语义可能反直觉——购物车取并集会让删掉的商品复活 | Amazon 购物车、Riak 数据类型 |
最后是那个真正该先问的问题——这套东西你到底该不该用：
表 3 · CP 还是 AP：拿业务当锚
| 场景 | 选 | 为什么 |
|---|---|---|
| 账户余额、库存扣减 | CP（关系库 / Spanner 这类） | 读到旧值就是超卖、就是钱错。宁可分区期间拒绝服务 |
| 购物车、用户会话、收藏夹 | AP（本章这套） | 写入失败的损失远大于偶尔多一件商品 |
| 点赞数、播放量、埋点 | AP，甚至 W=1 | 本来就是近似值，吞吐比精确重要 |
| 需要按多个字段查询 | 都不选 | 键值存储只有 get/put，做不了查询；别硬套 |
这一章是系统设计面试里的「元题」：它不像限流器、短链那样只对应一类产品，而是把分区、复制、一致性、故障检测、存储引擎五件事串在一根线上——面试官问「设计一个 KV 存储」，实际是在一次性检查你这五块知识是否成体系。落到真实世界，它就是 Amazon DynamoDB、Apache Cassandra、Riak、Voldemort、ScyllaDB 这一族系统的共同蓝图；Kafka 的分区副本、Elasticsearch 的分片分配，也都能在这套零件里找到对应。
(N,R,W) 就是 (3,2,2)，SLA 按 99.9 百分位而非平均值定；并披露 24 小时内 99.94% 的请求只看到一个版本——验证了向量时钟带来的多版本在实践中确实罕见。Dynamo 论文, SOSP 2007 ↗p99 读延迟从 40–125 ms 降到 15 ms——说明这套架构的瓶颈最终常常落在运行时而非算法上。Discord Blog「How Discord Stores Trillions of Messages」, 2023 ↗R+W>N 的实现；并写明 hinted handoff 的提示默认最多保留 3 小时（max_hint_window），超时就只能靠反熵修复——印证了本章「三个时间尺度分层处理故障」的分工。Apache Cassandra Documentation · Hints ↗W+R>N 的保证。宽松 quorum 收的是「任意 W 个健康节点」，不是「该存这个 key 的前 N 个里的 W 个」——写可能全落在临时代管者身上，读却在真正的 N 个副本里做，两个集合根本不重叠。它换来的是可用性，不是一致性。面试里能主动点出这一条，分量很重。W+R>N ≠ 强一致。它只保证「读得到最新的那次写」，不提供全局顺序、原子性和隔离级别。把它说成「线性一致」是最常见的错误。get/put，没有二级索引、没有范围查询、没有跨键事务。业务一旦需要「按第二个字段找」，这套设计就该重新评估。① 这章不是在设计产品，是在造一个数据库——放弃主节点之后，正确性得靠一堆机制一件件补回来。
② CAP 里 P 不是选项：网络一定会断，真正的选择只在分区发生时的 C 与 A 之间。Dynamo 选 AP，因为「加入购物车不能失败」。
③ 分区复用一致性哈希环，复制是顺时针收下前 N 个不同物理机（跳过同机虚拟节点，并跨可用区）。
④ Quorum NWR：W+R>N 靠抽屉原理保证读写集合必有重叠，所以一定读得到最新写；生产常用 (3,2,2)。
⑤ 但 W+R>N 不等于强一致，且 sloppy quorum 会把这条保证打破——这是最值得记住的一个坑。
⑥ 冲突：并发写没有先后，向量时钟只能发现冲突；Cassandra 干脆用时间戳取胜，简单但会静默丢写。
⑦ 故障按三个尺度分层：gossip 检测（避开 O(n²) 全互联）→ hinted handoff 顶临时宕机（默认 3 小时）→ Merkle 树反熵修永久差异（代价与差异量而非数据量成正比）。
⑧ 单机存储：commit log + memtable + SSTable 把随机写变顺序写，读靠布隆过滤器免掉无谓磁盘访问。
⑨ 选型一句话：能容忍陈旧值的（购物车、会话、计数）用它；一分钱都不能错的（余额、库存）别用；要按多字段查的，根本不该考虑它。