专业书籍精读 · System Design Interview 卷一 · 第 5 章
System Design Interview: An Insider's Guide · Vol 1 · Ch 5 · Alex Xu · 2020
你网购的包裹要先进分拣中心：几个仓库排在那里，每个包裹按单号被分到其中一个。分拣规则要满足两件事——快（不用查册子，看一眼单号就知道去哪个仓库）、稳（下次找这个包裹，还得算到同一个仓库）。这一章讲的就是这条分拣规则，以及它在仓库数量变化时会出什么事。
你大概觉得：本来 4 个仓库，新开第 5 个，那把大约五分之一的货挪过去就行了。可用最常见的那条规则，你得把差不多八成的货全部重新搬一遍——不是搬到新仓库，而是每个包裹都要换一个不同的旧仓库。开一个仓库，全城的货都得动。
那条最常见的规则是：单号除以仓库数，看余数。4 个仓库，余数 0、1、2、3 各对应一个。简单又快。问题出在「仓库数」这三个字被写进了公式里：仓库从 4 变成 5，除数就从 4 变成 5，几乎每个包裹算出来的余数都变了——它们不是「大部分不动、少数搬去新仓库」，而是集体换了个位置。
后果很直接：分拣中心其实是缓存。平时几乎人人都能就近拿到东西；仓库一变，大家全找错地方，请求哗地一下全砸到后面那个又慢又金贵的总库上。压垮系统的不是新加的那台机器，是那次搬家本身。
换个办法。把所有可能的单号想象成一条首尾相接的圆形跑道，每个包裹按单号落在跑道上某一点；仓库也按自己的名字落在跑道上某一点。规则改成一句话：包裹从自己的位置出发，顺着跑道往前走，遇到的第一个仓库就归它。
妙处在于：公式里再也没有「仓库数」这个东西了。新开一个仓库，就是往跑道上插一个新点——只有「从新点往回退到上一个仓库」的那一小段包裹需要挪，其余整条跑道上的包裹一个都不用动。关掉一个仓库同理：它那一段的包裹顺着跑道交给下一个仓库，别人不受影响。
光这样还不够均匀。仓库落在跑道上的位置是随机的，可能三个仓库挤在一起、留下一段特别长的空当归第四个——那个仓库就被撑爆了。补丁很土也很有效：让每个仓库在跑道上开几十上百个「分店」，名字带编号，各自算各自的落点。分店一多，长短弧被打散又摊平，每个仓库分到的总量自然就接近了——这就是「虚拟节点」。
诚实说一句代价：分店不是越多越好——一个仓库的货散在越多小段上，就跟越多的邻居搅在一起，某天两个仓库同时出事，波及面反而更大。
老办法把「仓库数」写进了公式，所以仓库一变，全城的货都要搬。一致性哈希把仓库排成一圈、只让每个包裹找顺时针方向最近的那一个，于是加减仓库只惊动一小段。再给每个仓库开一堆分店，把长短不一的弧摊匀。
想进到具体算法、量级和示意图？ → 切到精读版
你以为一致性哈希（consistent hashing）是「一种更好的哈希函数」，其实它根本没让数据分得更均匀——把数据摊平的是后来打的那个补丁（虚拟节点）。它真正买到的只有一样东西：把扩缩容时必须搬动的数据，从「几乎全部」压到「1/N」。这一章是全书最像纯算法的一章，值得记住的其实是那个思路：凡是把「机器数量」写进路由公式的方案，都会在加机器的那一刻自爆。
user:8613。系统靠它决定这条数据放在哪台机器上。%。hash(key) % 4 就是「除以 4 看余数」，结果必是 0–3 之一。0 到 2^160-1 之间的一个数）。本章只借用它「输出散得开」这一条性质。Part II「系统案例」的第二题，也是全书最短、最「零件」的一章：没有 API、没有数据模型，只有一个算法。它正好接住 Ch4 限流器留下的尾巴——几十台无状态的限流器，配额状态怎么分到多台缓存上；往后它是 Ch6「设计键值存储」的第一块砖，Dynamo 那一整套都盖在这个环上。对应现实：Dynamo 与 Cassandra 的数据分区、CDN 的边缘节点选择、Google 的 Maglev 负载均衡器，以及任何一个多节点缓存层。
问题只有一句：机器数量会变，而最直觉的路由公式受不了这个。
最直觉的公式是 serverIndex = hash(key) % N——N 台服务器，算个余数就知道去哪台。够快、够稳（不用维护任何路由表）、分布也够均匀。唯一的毛病是：N 出现在公式里。
严格算一下这毛病有多大。4 台缓存挂掉一台，N 从 4 变 3：只有约 1/4 的 key 还落在原机器上，其余 75% 全部换了归属；理想情况本该只搬走那台自己的份额，也就是 25%。加机器同样糟：4 台变 5 台约 80% 的 key 换位置，理想值 20%。
不解决会怎样？算一笔账：缓存层扛 100,000 QPS、命中率 99%，每秒只有 1,000 个请求穿透到数据库。一台缓存挂了，客户端按新的 N 重新取模，瞬间约 75% 的 key 找错机器，命中率跌到 25% 附近，穿透请求变成每秒 75,000 个，放大约 75 倍。连接池打满、响应变慢、超时重试再叠一层——缓存还没恢复，后端先塌了。原书把这个现象叫 cache miss 风暴：击垮系统的不是那台挂掉的机器，是紧接着的那次全局搬家。
这是全章唯一的核心思路，其余都是它的工程化：换一种不需要知道有几台机器的定位方式——机器和 key 都在同一个固定坐标系里安一个位置，归属由相对位置决定，不由总数决定。加减机器只是往坐标系里增删一个点，其他点纹丝不动。
那个固定坐标系就是哈希环。取一个哈希函数（书里用 SHA-1），它的输出范围是 0 到 2^160-1；把这条线的首尾接起来，就成了一个环。然后三步：
加一台服务器 s4：它插进环上某个位置，只有「从 s4 逆时针回退到上一台服务器」这一段区间里的 key 改换门庭，环上其余部分完全不受影响。删一台同理：它负责的那一段整体顺时针交给下一台。
这正是 Karger 等人 1997 年那篇原始论文给出的性质：哈希表大小变化时，平均只需重新映射 k/n 个键（k 是键总数、n 是槽位数）——人话就是「加一台机器，只搬 1/n 的数据」。
直接用上面的环，会撞上两个都跟「随机」有关的问题，原书把它们并列点出：
毛病一：分区大小不均。服务器在环上的落点是哈希算出来的，等于随机撒点，相邻两点的弧长天差地别。更糟的是它会因节点变动而恶化：移除一台服务器，它那一段并到邻居头上，邻居的负担可能一下变成别人的两倍。
毛病二：key 分布不均。就算弧长恰好均匀，key 本身也可能扎堆落在某一小段上。极端情况下有的机器管着一大片热闹区间，有的机器一个 key 都分不到。
注意这两条说的是同一件事的两面：基本的一致性哈希只保证「搬家便宜」，从来没保证「分得均匀」。很多人把这两件事混为一谈，是这一章最常见的误读。
补丁是：一台物理服务器不再只在环上占一个点，而是占很多个点。服务器 s0 派出 s0_0、s0_1、s0_2…… 每个化身各自算哈希、各自落点，查询规则完全不变（顺时针找第一个虚拟节点），只是最后要把虚拟节点映射回它背后的物理机。
直觉一句话：一台机器不再拿整副身家赌一段弧的长短，而是赌两百段小弧的平均。赌一次方差极大，赌两百次就被大数定律摁下去了。原书引了一份实验的数字：虚拟节点取 100 个时，各机器负载的标准差约为均值的 10%；取 200 个时约为 5%。书里给出的代价是存储开销——环上的点多了，映射表更占内存、查找也更慢。（书没讲的那个更重要的代价，见「易错点」。）
虚拟节点还顺手解决了一个 Dynamo 论文专门强调、书里没展开的问题：异构。集群里的机器往往不一样强，而虚拟节点让「多分点活」变得极简单——给强的机器多派几个化身，权重直接落在数量上，路由逻辑一行不改。
原书为这件事单开一节，因为「知道要搬多少」和「知道要搬哪些」是两回事。规则很短：加节点，受影响区间是从新节点位置逆时针回退到上一个节点；删节点，受影响区间是从被删节点逆时针回退到上一个节点，这段 key 顺时针交给下一个节点。
为什么必须算准？真实系统搬数据靠的是按 token 区间做范围扫描并流式传输（Cassandra 的 bootstrap 就是这么干的）。区间算窄了会漏搬、数据永久丢失；算宽了等于全量扫描，一次扩容能把集群 I/O 打满几小时。
表 1 · 三种路由方案：搬家量、均匀度与控制力的三角
| 方案 | 加/减一台要搬多少 | 均匀度 | 元数据开销 | 能否处理异构 | 适合 |
|---|---|---|---|---|---|
取模 hash % N | ≈ 全部（4→3 搬 75%） | 好 | 零，客户端自己算 | 否 | 分片数永不变，或允许停机全量重建 |
| 一致性哈希 + 虚拟节点 | 1/N，理论最优 | 取决于化身数（100 个 ≈ 10% 标准差） | 每节点 V 个 token，需在集群内传播 | 是，多给化身即可 | 无中心协调的对等集群：Dynamo、Cassandra、缓存层 |
| 集中查表（固定 slot） | 想搬哪块搬哪块，完全可控 | 最好，可主动 rebalance | 一份权威映射表 + 分发机制 | 是，按 slot 数量分配 | 需要精确控制数据放置：Redis Cluster（16384 个 slot）、Vitess |
第三行值得多看一眼：一致性哈希不是唯一答案，很多成熟系统选了「固定一大堆 slot + 一张映射表」。代价是多一个控制面（谁维护那张表、怎么发给所有客户端），换来的是「哪块数据搬到哪」由人说了算——热点能手工挪走、扩容能分批做。一致性哈希的优势在「不需要任何中心」，代价是「你也指挥不动它」。
表 2 · 虚拟节点数怎么定（数字取自 Apache Cassandra 官方生产建议）
| 每台 token 数 | 均匀度 | 扩容灵活性 | 可用性影响 | Cassandra 官方说法 |
|---|---|---|---|---|
| 1 | 最差 | 差：必须成倍扩容才保持均衡 | 最好，数据只与最少的邻居共享 | 「最大可用性、最大集群规模、最少对端」 |
| 4 | 中 | 好：约每次加 20% 节点 | 好 | 推荐给最终会超过 30 节点的集群 |
| 8 | 较好（约 10% 波动） | 好 | 较好 | 「性能影响极小」 |
| 16（当前默认） | 好 | 最好，适合频繁伸缩 | 较差 | 不推荐用于超过 50 节点的集群 |
表 3 · 一致性哈希解决了什么、没解决什么
| 内容 | |
|---|---|
| 解决 | 扩缩容的搬家量降到 1/N；无中心路由——每个客户端本地算一下就知道去哪台，不需要问任何人；靠化身数量表达机器权重 |
| 没解决 | 单个热 key（它只有一份，落哪台哪台热）；跨分片查询与事务；副本放置（要跳过同机架 / 同机房）；迁移期间的读写去哪 |
这套算法是无中心分布式存储的入场券：只要你想做一个「客户端自己就能算出数据在哪、不用问任何协调者」的系统，就绕不开它。面试里它也是极高频的追问点——拉开差距的从来不是「环 + 虚拟节点」这六个字，是受影响区间怎么算、以及虚拟节点数为什么不是越大越好。
num_tokens: 16，并直言 16 「不推荐用于超过 50 节点的集群」——这是对「虚拟节点越多越好」最直接的反驳。Apache Cassandra 官方文档「Production recommendations · Tokens」↗① 病根一句话：hash(key) % N 把机器数量写进了路由公式，所以 N 一变、几乎所有 key 都要换机器。4 台挂成 3 台，约 75% 的 key 搬家；理想值只有 25%。
② 代价是雪崩不是麻烦：缓存层 100,000 QPS、命中率 99% 时，一次全局再哈希能把穿透到数据库的请求从每秒 1,000 拉到 75,000，放大约 75 倍。
③ 解法只有一个思路：把 N 从公式里拿掉。哈希空间首尾相接成环，服务器和 key 各自落点，key 顺时针遇到的第一台就是归属。加减一台只搬 1/N——这正是 Karger 1997 年论文给出的 k/n 性质，也是理论最优。
④ 基本环有两个毛病，都源于随机落点：弧长不均（移除一台后邻居可能负担翻倍）与 key 扎堆。记住：环只保证搬家便宜，从没保证分得均匀。
⑤ 虚拟节点是那个补丁：一台机器在环上派出多个化身，用大数定律压方差。100 个化身标准差约 10%、200 个约 5%；顺带还能表达机器强弱——强的多派几个。
⑥ 环不是唯一答案：Redis Cluster 走的是 16384 个固定 slot + 一张映射表，多一个控制面，换来「哪块搬到哪」完全可控。
⑦ 但化身不是越多越好：Cassandra 官方说更多 token 会降低可用性，默认值是 16，且不推荐用于 50 节点以上的集群。生产上的答案是十几个，不是几百个。
⑧ 它没解决的：单个热 key（Discord 的热分区就是活例）、跨分片事务、副本放置、迁移期的读写路由。面试里能说清受影响区间怎么算和虚拟节点的可用性代价，才算真懂这一章。