如果你写过任何一个分布式缓存或分库分表，大概率脱口而出过一句话："用 hash(key) % N 分片就行。" 这句话看起来天衣无缝——直到有一天，流量上来，老板让你加一台机器。然后你会发现：加一台机器，几乎所有的 key 都要搬家，缓存命中率瞬间归零，数据库被打到宕机。Hussein Nasser 在 The Backend Engineering Show 这一期《Consistent Hashing》里，就把这个"加一台就雪崩"的血案讲得透透的，并且给出了工程界用了快三十年的解药：一致哈希环（Consistent Hashing Ring）。
这篇文章不是搬运视频。我会把 Hussein 那期约 25 分钟的节目拆开，补上它没展开的历史（这个算法其实是 1997 年 MIT 为了解决"WWW 热点"发明的）、Google 后来发的两个变种（Jump Hash、Maglev），以及一个大多数人会踩的认知误区——一致哈希的"一致"，根本不是"结果不变"，而是"搬得最少"。
| 项目 | 内容 |
|---|---|
| 视频标题 | Consistent Hashing | The Backend Engineering Show |
| 频道 | Hussein Nasser（后端工程教育者，频道订阅量数十万级） |
| 时长 | 约 25 分钟 |
| 核心主题 | 分布式系统中如何用一致哈希在节点增删时最小化数据迁移 |
| 适合人群 | 后端/系统设计岗、准备面试、做缓存/分库分表的工程师 |
hash(key) % N 为什么会要命Hussein 开场就摆出了一个最朴素的分片方案，几乎所有教科书第一页都这么写：
server = servers[hash(key) % N] # N = 服务器数量
3 台机器 A、B、C，hash("user_123") % 3 = 1 落到 B。看起来很美。但当你把 N 从 3 改成 4 时，灾难发生了。 Hussein 在节目里和配套文章里都算了这笔账：从 N=3 到 N=4，大约有 75% 的 key 会落到一个不同的服务器。推广一下就是——增删一台机器，会有 (N−1)/N ≈ 91%（10 台时） 的 key 重新映射。
这不是一个"理论上的小问题"，而是会直接引爆生产事故的雷：
这一点是视频的原话重点。Hussein 反复强调："naive modulo hashing 在分布式系统里根本不能用。"我的补充：很多人在单机 toy 项目里用
% N没事，是因为单机不扩缩容；一旦上了集群，% N的真正成本不是"算一次哈希"，而是"扩容一次全员搬家"。
这就引出了一致哈希要达成的目标：增删一个节点时，只有约 K/N 的 key 被重新映射（K 是总 key 数，N 是节点数）。10 台集群加 1 台，只有约 10% 的 key 动，而不是 91%。
% N 为什么灾难性？因为 N 直接出现在了公式里，N 一变，整个映射表就翻盘。一致哈希的天才之处在于——让 N 不出现在公式里。
做法是把哈希空间首尾相连，弯成一个环（32 位哈希就是 0 ~ 2³²−1 首尾相接；MD5 则是 2¹²⁸）。然后做三件事：
hash("Server_A") = 85，hash("Server_B") = 190，hash("Server_C") = 310。节点本身是环上的几个"哨兵"。hash("user_123") = 50。user_123 在位置 50，顺时针走，第一个碰到的是 85 位置的 A → 归 A。这是视频和几乎所有讲解的核心。我的延伸：这个"环 + 顺时针找邻居"的本质，是把"全局取模"换成了"局部邻居查找"。N 不再参与任何运算，N 变化时，只有"邻居关系被改变的那一小段弧"上的 key 会受影响。
见证奇迹的时刻——加一台 D 到位置 130：
user_123（位置 50）→ 顺时针第一台还是 A(85)。没动。user_456（位置 120）→ 以前顺时针是 B(190)，现在 D(130) 更近了。从 B 搬到 D。user_789（位置 250）→ 顺时针还是 C(310)。没动。3 个 key 只搬了 1 个（33%），而不是朴素方案的 75%。推广到 N 个节点：加一台，只搬约 1/(N+1) ≈ 1/N 的 key。这就是视频标题里"consistent"的真正含义——一致的不是结果，而是"扰动最小"。
下面这张图把"一个 key 如何被定位 + 复制"的内核画了出来：
flowchart LR
K[输入 key] --> H["hash(key) → 环位置 P"]
H --> R["在有序位置数组中二分<br/>找第一个 ≥ P 的节点"]
R --> W{找到?}
W -- 是 --> M[该节点 = primary 主副本]
W -- 否 到环尾 --> M0[回绕到环首节点]
M --> Rep[继续顺时针取 RF-1 个不同物理节点]
M0 --> Rep
Rep --> Out[返回 primary + replicas]
实现上有一个工程细节视频一笔带过，但极其关键：所有节点位置要维护成一个排序数组，查找时用二分（bisect）。这样定位一个 key 是 O(log N)，而不是线性扫描。环的"圆"是逻辑上的，物理上就是一张排序表 + 二分。
很多人听完上面就以为一致哈希搞定了。Hussein 在节目后半段戳破了第二个坑：3 个真实节点撒在 2³² 的环上，几乎是必定不均匀的。比如 A(50)、B(200)、C(250)——A 到 B 这段弧长 150，C 到 A 这段弧长 160，B 到 C 只有 50。结果就是 A 和 C 拿走了 86% 的 key，B 几乎饿死。负载均衡？不存在的。
解药是虚拟节点（Virtual Nodes / VNodes）：让一台物理服务器在环上占很多个位置，而不是一个。
Server_A:0、Server_A:1、…、Server_A:149，各自哈希到环上。视频提到了虚拟节点这个概念。我的数据补充：开源实现里虚拟节点数差异很大——Memcached 的 libketama 默认 160 个，Cassandra 默认每个节点 256 个 token。Cassandra 的设计哲学就是"节点容量 ∝ token 数"，所以一致哈希在 Cassandra 里同时完成了分片和按容量加权两件事。
加权是虚拟节点带来的一个意外红利：如果 A 的内存是 B 的两倍，就给 A 配两倍的虚拟节点，它就自然承担两倍的 key。这一条朴素 % N 永远做不到。
Hussein 讲到一个很优雅的点：一致哈希天然适合做副本（replication）。如果副本因子 RF=3，那就让 key 不只存顺时针第一台，而是存顺时针的前 RF 个不同物理节点。user_123 → primary 是 A，顺时针再找两个不同物理节点 C、B，三台各存一份。
这恰恰是 Cassandra、Amazon Dynamo 的真实做法：写请求由 coordinator 并行写到 RF 个顺时针节点；A 宕机时从 C、B 读；A 恢复时用 hinted handoff / anti-entropy（gossip）补齐。分片、副本、故障转移，三件事被同一张环统一了。这是我认为一致哈希最"性感"的地方——一个数据结构同时回答了"放哪""存几份""谁顶上"三个问题。
一致哈希不是论文玩具，它在你每天用的系统里：
| 系统 | 怎么用 | 关键细节 |
|---|---|---|
| Amazon DynamoDB | 分区键 → 哈希 → 环 → 节点 | 灵感源头（Dynamo 2007 论文），虚拟节点做负载均衡 |
| Apache Cassandra | 分区键哈希成 64 位 token，映射到环 | 默认每节点 256 个 vnode，副本顺时针走 |
| Redis Cluster | 16,384 个 hash slot 的变体 | CRC16(key) % 16384 = slot，slot 分配给节点，扩容=迁移部分 slot |
| Akamai CDN | 一致哈希把请求路由到最近边缘节点 | 新增 PoP 只"偷"相邻 PoP 的缓存 |
| Memcached 客户端 | 客户端侧一致哈希选服务器 | libmemcached / Spymemcached 原生支持 |
| HAProxy / nginx | 一致哈希做 sticky 负载均衡 | balance uri consistent，保证同一客户端命中同一上游 |
视频主要讲了 Dynamo/Cassandra/Memcached。我重点补充 Redis Cluster 这个"异类"：它没有用连续环，而是用了固定 16,384 个槽。为什么？因为连续环的负载依赖哈希随机性的"大数定律"，而固定槽让运维可预测——你能精确知道加一台要搬哪几个槽。这是工程上"可预测 vs 更灵活"的经典权衡：Cassandra 选了动态 token（灵活但难预测），Redis 选了固定 slot（好运维）。
这是我看完视频后最想给所有人泼的一盆冷水——也是一致哈希最被神化的地方。
误区一：以为"consistent"=结果永远不变。错。它的一致性指的是拓扑变化时的"最小扰动"（minimal disruption），节点一变，结果当然变，只是变得少。
误区二：以为一致哈希能负载均衡。这是最大的陷阱。一致哈希均衡的是 key 的数量，不是 流量。如果一个热点 key 承担了 90% 的读请求，无论你怎么调环，这 90% 的流量永远砸在同一个节点上——一致哈希对此完全无能为力。
这是我的延伸判断，视频里有所暗示但没有展开。Hussein 倾向于把一致哈希讲成"负载均衡算法"，但从工程实战看，更准确的说法是"数据/请求的放置算法"。流量均衡需要的是另一层手段：热点 key 多副本、读打散、本地缓存。把一致哈希当万金油，是很多线上事故的根源。
一致哈希的原始环有两个缺点：内存要存虚拟节点表（Cassandra 256×节点数），且负载依赖随机性。Google 先后发了两个里程碑式的变种：
Jump Consistent Hash（2014，Lamping & Veach）：一个 O(1) 空间、O(log N) 时间的算法，根本不存环，只用几行代码和 hash(key) + 循环就能算出 bucket ∈ [0, N)，并且同样满足"增删一个 bucket 只动 1/N"。代价是它假设节点编号是连续整数（0..N−1），所以不适合"指定节点"的环，但非常适合"分桶"场景。这篇论文只有 4 页，是简洁美的天花板。
Maglev（2016，Google 软件负载均衡器）：Google 生产级负载均衡用的"查找表"一致哈希。它维护一张约 上百万条目的固定查找表，既保证最小扰动（节点增删影响极小），又保证近乎完美的均衡（每个节点分到的查询路径偏差 <1%）。这解决了原始环"随机性导致不均"的痼疾，代价是建表要解一个约束满足问题。
视频没有讲这两个变种，这是我补的"进化线"。理解了 Jump 和 Maglev，你才会明白：原始 Karger 环是起点，不是终点；现代大规模系统多半用的是改良版。
graph TD
A["一致哈希 Consistent Hashing<br/>Karger et al. MIT 1997"]
A --> B["痛点: 朴素 hash%N"]
A --> C["核心: 哈希环"]
A --> D["均衡: 虚拟节点"]
A --> E["容错: 顺时针副本"]
A --> F["演进: Jump / Maglev"]
A --> G["落地系统"]
B --> B1["增删1台 ≈ (N-1)/N 键搬家"]
B --> B2["缓存雪崩 / DB 雪崩"]
C --> C1["节点与键共置同一环"]
C --> C2["键归顺时针第一个节点"]
C --> C3["增删仅动该弧段 ≈ K/N"]
D --> D1["每物理节点多位置 150/256"]
D --> D2["加权: 容量 ∝ 虚拟节点数"]
E --> E1["RF 个顺时针不同物理节点"]
E --> E2["故障自动转下一副本"]
F --> F1["Jump Hash 2014: O(1) 空间"]
F --> F2["Maglev 2016: 查表均衡+最小扰动"]
G --> G1["DynamoDB / Cassandra"]
G --> G2["Redis Cluster 16384 slots"]
G --> G3["Akamai / Memcached / HAProxy"]
1. 别再无脑 % N。 任何会扩缩容的分布式缓存、分库、会话路由，第一步就该上一致哈希。判断标准很简单：问自己一句"加一台机器会怎样"。如果答案是"全员搬家"，那就是 % N，必须换。
2. 面试/设计时的标准话术（Hussein 在节目里反复演练的就是这个）："我用一致哈希把数据/请求分布到 N 个节点。每个节点映射到环上的多个虚拟节点位置；key 来了，哈希到环上一个点，顺时针找第一个节点。相比朴素取模，增删节点时只有约 1/N 的 key 重新映射，不会触发缓存雪崩或大规模数据迁移。" 记住这句，系统设计题里 80% 的"如何分片"都能稳稳接住。
3. 选型要看场景。 - 要弹性扩缩、无停机、节点能力相当 → 连续环 + vnode（Cassandra 式）。 - 要运维可预测、精确控制迁移 → 固定 slot（Redis Cluster 式）。 - 要极致均衡 + 最小扰动、能接受建表成本 → Maglev（大型 LB）。 - 只要分桶、节点是连续编号、内存敏感 → Jump Hash。
4. 永远记住"热点"是另一层问题。 一致哈希解决的是"放哪"，不是"流量怎么分"。热点 key 必须叠加多副本 + 读打散。把一致哈希当负载均衡神器，迟早要交学费。
5. 工程实现的三件套：排序数组存节点位置、二分定位 key、虚拟节点数随容量加权。把这三件事写对，一个生产级的一致哈希路由层就成了。
ConsistentHashRing 写一遍（排序数组 + bisect + vnode），再对比 Redis Cluster 的 16384 slot 实现，你会对"环 vs 槽"的权衡有肌肉记忆。一致哈希把"加一台机器全员搬家"的灾难，压成了"只搬 1/N"——它的"一致"不是结果不变，而是扰动最小；而它最大的局限，是只均衡 key、不均衡流量。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。