一致性哈希与随机树（Consistent Hashing and Random Trees）

一句话

这篇论文先把「怎样才算分配得好」形式化成四条性质（均衡、单调、分散度、负载），再给出满足它们的极简构造：把机器和数据用哈希映到同一个环上，每份数据归顺时针遇到的第一台机器——于是增删一台机器只需迁移约 1/n 的数据，且各客户端手上的机器名单不完全一致时，分配结果依然高度一致。另一半用「随机树」把单个热点的访问层层摊开。它后来成了 Akamai、Chord、Dynamo、Cassandra 乃至现代负载均衡器的共同零件。

Glossary · 术语表

坐标

作者是 David Karger、Eric Lehman、Tom Leighton、Matthew Levine、Daniel Lewin、Rina Panigrahy，来自 MIT 理论组，论文题为《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》，发表于 STOC 1997。它接续 1990 年代中期「Web 缓存该怎么组织」的一串工作，回答的是万维网刚爆发时最现实的工程灾难——热点；1998 年 Leighton 与 Lewin 把这套理论创业落地成 Akamai（Lewin 于 2001 年 9 月 11 日在美国航空 11 号航班上遇难）。下游则几乎覆盖了后二十年的分布式存储（见「影响」一节）。

问题与动机

1990 年代中期的万维网有个要命现象：一个页面被门户首页一挂，请求量能在几分钟内涨几个数量级，源站直接被打死。自然的解法是在网络里摆一堆缓存分担，问题随即变成：一个页面该由哪台缓存负责？

最直接的答案是取模分桶：cache = hash(URL) mod n，即「把 URL 哈希成数、除以缓存台数取余」。它有两个硬伤。

第一，机器集合一变、全盘重排。n 从 10 变 11，绝大多数 URL 的归属都改了——全体缓存瞬间失效、请求一起回源，恰恰在扩容那一刻把源站打死。

第二，也是当年更棘手的：大家的名单对不上。缓存由不同机构运营、随时上下线，各浏览器知道的列表天然不一致；若各按自己名单的 n 取模，同一页面在不同客户端会算到不同缓存上——同一份内容在很多缓存里各存一份、每台都得回源取一次，空间与带宽双浪费。

还有第三件事取模根本没碰：页面本身就热。分配再均匀，一个疯传页面也只有一台缓存负责，照样被压垮——这是后半「随机树」的活。

核心思想 / 方法

先定义「什么叫分得好」：四条性质

论文真正的贡献有一半在于它先把问题定义清楚了。它引入 ranged hash function（带视图的哈希函数）：普通哈希只有一个固定映射，它却对每一种可能的视图 V（某客户端知道的那批桶）各给出一套「项 → 桶」的分配，并要求这族函数同时满足四条：

• 均衡（balance）：任一视图下各桶分到的项大致一样多，即「别忙闲不均」。
• 单调（monotonicity）：往视图里加桶时，项只允许从旧桶迁到新桶，绝不许在两个旧桶间横向搬，即「扩容时别做无谓搬家」——取模分桶恰恰彻底违反这条。
• 分散度（spread）：同一个项在所有客户端的视图下加起来，总共只被分到很少几个桶，即「别让同一页面在全网存很多份」。
• 负载（load）：同一件事从桶的角度看——任何一个桶在所有视图下加起来也只被分到不太多的项，即「别让某台机器被各家名单联手压垮」。

后两条正是冲着「视图不一致」去的：即使大家名单不同，结论也要大体一致。这就是「一致性哈希」里「一致」的真正含义——不是数据一致性，而是不同视图下分配结果的一致，这个常年被误解的点值得单独记住。

构造：一个环，顺时针取最近

满足这四条的构造朴素得让人意外：用哈希把桶映到单位区间 [0,1)（首尾相接看成一个环），再把项也映到同一个环上。规则一句话：bucket(item) = 环上第一个 hash 值 ≥ hash(item) 的桶（到头则绕回开头）——就是「顺时针最近」。

单调性几乎是白送的：项的位置只由它自己的名字决定，与有几个桶无关；插入一个新桶只会把「紧邻它逆时针那一小段」里的项从原来的后继手上接过来，环上其余弧段完全不动，删桶同理。期望迁移量因此是：加入第 n+1 个桶时只有约 1/(n+1) 的项换手，且全部搬进新桶。

虚拟节点：把均衡买回来

但只这样还不够均衡：n 个随机点把环切出的 n 段弧长短差得很多，最长那段可以是平均值的好几倍。论文的做法是把每个桶复制成 Θ(log C) 个点撒到环上（C 是可能出现的桶总数），一台机器于是在环上有许多「分身」，长弧短弧互相抵消，各机器分到的总弧长便集中到平均值附近。这个技巧后来被工业界叫做虚拟节点（virtual node / vnode），还带来两个红利：下线时它的多段弧被不同的机器分头接管（不砸单个邻居）；容量不同的机器可多撒或少撒分身来加权。

在此之上论文证明（高概率成立，即出错概率随规模迅速趋近于零）：均衡——每个桶拿到 O(1/|V|) 比例的项；单调——无条件成立（这是构造自带的性质，不靠概率）；在「每个客户端至少看到全部桶的 1/t」的假设下，分散度与负载都被压在 O(t·log C) 量级。分量在于：一条查一次哈希就能算出答案、不需要任何协调的规则，同时拿到了这四条。

随机树：给单个热点分摊

一致性哈希解决「谁负责」，没解决「负责不过来」。论文后半给每个页面配一棵随机树：把一批缓存当节点，用「页面名字 + 节点编号」哈希出一棵 d 叉树——页面不同，树的形状与成员就不同。请求这样走：客户端不直奔「那台负责的机器」，而是随机挑这棵树的一片叶子去问；叶子没有就问父节点，一路往上，只有树根也没有才回源站。妙处在两点：其一，每个节点只被自己的 d 个孩子问，扇入是常数，没有哪台机器直面全网；其二，节点第一次取到页面后就缓存住，后续再问直接命中，往上传的请求数被卡死。热点压力于是沿树迅速衰减，源站只挨到很少几次回源；又因为树按页面名字随机生成，不同热点的树根落在不同机器上，不会合力压垮同一台。论文证明：在其请求模型下任何机器承担的请求量高概率不超过其「公平份额」的对数级倍数。

两半是同一个信念的两面：不靠中心协调、不靠全局状态，只靠「大家算同一个哈希」就把分工定下来——环定空间上的分工，树定压力上的分摊。这也是它能在 1997 年那种「谁也管不了谁」的互联网上落地的原因。

关键结果

先说清楚：这是一篇理论论文（STOC），结论是定理而非实验数字——它没跑系统评测，所以没有可引用的吞吐 / 延迟数据。它给出的保证是：

• 迁移量：桶数从 n 增到 n+1，期望只有 1/(n+1) 的项换手（取模分桶几乎要重排全部）；单调性无条件成立。
• 均衡：每桶复制 Θ(log C) 份后，高概率下各桶项数落在平均值的常数倍内。
• 分散度 / 负载：在「每视图至少含全部桶的 1/t」的假设下都在 O(t·log C) 量级——同一页面在全网只被少数几台缓存各存一份。
• 随机树：高概率下没有机器（含源站）承受超过公平份额对数级倍数的请求。

真正的「实验」是后来的工业验证：Akamai 用它撑起全球 CDN，Dynamo、Cassandra 把它当默认放置方式沿用至今。

为什么重要 / 影响

它把一件人人都在做、却做得很糙的事（数据分片）变成了有定义、有保证的原语，于是成了一整代系统的共同零件——Chord 等 DHT 的环、Dynamo 的数据放置、Cassandra 的 token 环、memcached 的 ketama、七层负载均衡器挑后端的逻辑，底下都是这个环。更深一层的贡献是「视图不一致也能一致分配」——这正是无中心系统能工作的前提，也是后续二十年「如何更均衡、更省内存地分片」这条研究线的起点。

局限与批评

• 它均的是键数，不是热度。分到一样多的 key，不等于分到一样多的请求；一个超热 key 仍旧只落一台机器。工业界靠热点复制与请求合并来补，理论上的补丁是 2016 年前后的有界负载一致性哈希：给每桶设容量上限，满了顺延到下一个桶。
• 虚拟节点有成本。要达到好均衡，环上点数是机器数的几十到上百倍，这份元数据要在集群里传播维护；Dynamo 论文比较过三种分区策略，最终放弃最朴素的随机 token 方案，正因为它带来的重建与元数据开销。此外副本放置常要满足「不同机架 / 可用区」的约束，环本身不表达这些，只能在上层打补丁。
• 不是唯一解。Rendezvous hashing（HRW，1990 年代中期）「对每台机器算个分数、取最高」，同样单调且更均衡，只是朴素实现要遍历所有机器；jump consistent hash（Google，2014）几乎不占内存、极快，但只支持从尾部增减桶；Maglev hashing（Google，2016）用预计算查找表换更好的均衡，代价是牺牲一点点单调性。
• 保证依赖假设：它建立在「哈希足够随机」与「视图不太偏斜」之上，视图高度失衡、或有人刻意构造 key 去撞同一段弧时，界就不成立了。
• 论文的另一半几乎被遗忘。随机树协议没被工业界照搬——真实 CDN 用的是 DNS 重定向、分层缓存、请求合并等更工程化的手段；今天提起这篇论文，绝大多数人只记得标题的前两个词。

要点