一致性哈希

1997 年，大卫·卡格（David Karger）等人在 ACM STOC 会议上发表了论文《一致性哈希及随机树：分布式缓存协议以减轻万维网上的热点》（第 654 至 663 页）。当时的背景是万维网流量爆炸：热门内容把单个源站服务器打垮，而多台缓存服务器分摊内容时又面临一个痛苦的现实问题——当分布式缓存集群中一台服务器宕机时，为什么几乎所有的缓存都失效了？ 顺带一提，作者中的汤姆·莱顿与丹尼·列文次年共同创办了 Akamai，把论文里的想法做成了整个 CDN 产业。

问题：普通哈希在分布式场景下的脆弱性#

假设有 $n$ 台缓存服务器，用普通哈希将对象分配到服务器：

$$\text{server} = \text{hash}(key) \bmod n$$

当服务器数量从 $n$ 变为 $n+1$（增加一台）或 $n-1$（宕机一台）时，模数改变，几乎所有键的映射都会改变——即使只有一台服务器失效，也导致全部缓存失效，流量全部打到后端数据库，形成缓存雪崩。算一笔账：从 4 台扩到 5 台时，一个键在新旧两种取模下落到同一台服务器的概率只有约五分之一，也就是说大约 80% 的键要换服务器；集群规模越大，这个比例越接近百分之百。

一致性哈希：环上的映射#

一致性哈希的核心思想：把哈希空间想象成一个环（圆圈），服务器和键都映射到环上，每个键属于环上顺时针方向最近的服务器。

构建哈希环：

1. 将哈希值空间 $[0, 2^{32})$ 首尾相连，形成环
2. 用哈希函数将每台服务器的标识（如 IP 地址）映射到环上的某个位置
3. 用相同的哈希函数将每个键映射到环上
4. 每个键分配给环上顺时针方向遇到的第一台服务器

加入新服务器：只有新服务器"接管"了原来属于其顺时针邻居的那部分键，其他所有键不受影响。

一个直观画面：环是一只钟面，三台服务器落在三点钟、七点钟、十点钟方向。键 user:42 落在两点钟，归三点钟的服务器管。三点钟的机器宕机后，user:42 顺时针走到的下一台是七点钟——只有落在两点到三点这段弧上的键换了主人，钟面上其余所有的键原地不动。

服务器宕机：该服务器的键转移给其顺时针邻居，其他键不受影响。

平均而言：增删一台服务器，只影响约 $k/n$ 个键（$k$ 为键总数，$n$ 为服务器数），远优于普通哈希的"全部失效"。

虚拟节点：解决负载不均#

仅靠 $n$ 台服务器在环上的 $n$ 个点，负载分布可能非常不均——某些服务器负责很大的弧段，某些负责很小的弧段。十年后 Dynamo 论文重述这个缺陷时只用了两句话：随机放点"导致数据和负载分布不均"，而且"忽略了节点之间的性能差异"。

虚拟节点（Virtual Nodes）：每台物理服务器在环上放置多个"虚拟节点"（如 100–200 个）。每个虚拟节点代表该物理服务器的一份，键映射到虚拟节点后归属对应的物理服务器。

虚拟节点使键更均匀地分布到各服务器，且服务器性能差异可以通过调整其虚拟节点数量来体现（性能强的服务器持有更多虚拟节点）。

Dynamo 最终采用的方案更进了一步：把哈希环预先等分成固定数量的等长分区，每台物理节点只领走若干份"令牌"（token），而不是自己往环上随机撒点。这样加入或移出一台机器时，分区的交接整齐得多，节点间同步的元数据也小得多——虚拟节点从"随机撒点"演进成了"固定分区加令牌"。

实际应用#

从存储到缓存、从负载均衡到 CDN，这张表横跨四个层次，但共同的诉求只有一个：集群成员变化时，迁移量尽量小。

缓存客户端是另一个更早成熟的工程现场。2007 年 4 月，Last.fm 的工程师理查德·琼斯开源了 libketama：他们原先的 memcached 客户端正是用"哈希取模"选服务器的，每次增减机器，整个缓存池几乎全部失效。换成环上的一致性哈希后，扩缩容只影响一小段键，这个库随即成为各语言 memcached 客户端的标准配置。ketama 的实现细节也值得一记：它对每台服务器的标签算若干次 MD5，每个 16 字节的摘要拆成四个环上位置，于是一台服务器自然落在环上的 160 个点——虚拟节点在这里不是一个附加选项，而是默认动作。

Amazon Dynamo（2007）是将一致性哈希大规模工业化应用的里程碑。Dynamo 论文（DeCandia et al., SOSP 2007）深刻影响了此后十年的分布式系统设计，Cassandra、Riak 等系统都是其直接继承者。

后来的演进#

环不是唯一的答案，后续工作沿着"更省内存"与"更严保证"两个方向推进。

Jump Consistent Hash（谷歌，2014 年）：不维护任何环结构，用一个只依赖键与节点数的公式直接算出归属，内存开销几乎为零，迁移量同样是理论下限。代价是节点只能按编号整体追加，不能任意命名和加权。

Maglev（谷歌，2016 年）：为网络负载均衡器设计，用一张预计算的查找表换取"同一条连接始终落到同一后端"的性质，支撑谷歌的入口流量调度。

有界负载一致性哈希（Mirrokni 等，2018 年）：把任何节点的负载硬性压到平均值的 $(1+\varepsilon)$ 倍以内，代价是扩容时的迁移量按 $1/\varepsilon$ 放大。均匀性从"统计上的希望"变成了"最坏情况下的承诺"。

值得注意的是，所有这些后来者的评估标准都没有超出 Karger 论文写下的四行定义——一个足够好的形式化，寿命可以远超它最初的场景。

代价与争议#

热点（Hotspot）问题：如果某个键极其流行（如微博热搜），即使一致性哈希也无法分散——该键始终属于同一台服务器。工程上的标准做法是给热键加随机后缀拆成若干份，让它们散到不同机器上，读取时再并行取回聚合；本质上是把一致性哈希不会自动提供的并行度手工加回来。也可对热点键做多副本（应用层处理）。

单调性与迁移代价：一致性哈希保证增加服务器时旧数据不需要移动，但实际分布式系统中数据需要通过网络迁移，迁移过程中可能出现临时的不一致。

与 Range Sharding 的比较：另一种常见的分片策略是范围分片（Range Sharding），将键空间分成连续的范围（如 A-M 在服务器1，N-Z 在服务器2）。范围分片支持有效的范围查询；一致性哈希分布更均匀但不支持范围查询。HBase 用范围分片，Cassandra 默认用一致性哈希（也支持 range partitioner）。

Rendezvous Hashing（最高随机权重）：塞勒（Thaler）与拉维尚卡（Ravishankar）1996 年提出的替代方案（密歇根大学技术报告，1998 年正式发表于 IEEE/ACM 网络汇刊）——比 STOC 论文还早一年。它对每个键在所有服务器上计算哈希，选得分最高的服务器，无需维护环这一数据结构；语义与环上等价（增删节点同样只影响约 $k/n$ 的键），代价是每次查询要对全部节点各算一次哈希，节点很多时计算开销不可忽略。

一致性哈希的基本保证#

正式地，一致性哈希（Karger et al., 1997）满足以下性质：

平衡性（Balance）：每台服务器负责的键数量大致均等（加入虚拟节点后接近均匀分布）。

单调性（Monotonicity）：添加新服务器时，键的迁移只发生从"现有服务器到新服务器"，而不是在现有服务器之间。这保证了扩容时缓存不失效的最小化。

分散性（Spread）：同一个键在不同客户端视角下（因为各客户端可能看到不同的服务器集合）被分配到的服务器尽可能少，减少数据冗余。

负载（Load）：即使不同客户端持有不同的服务器集合视图，任何一台服务器被分配到的键数量也不会超过最优分配的 $O(1)$ 倍（期望意义上）。

这四个性质是 Karger 等人原论文中对"好的分布式缓存协议"的正式化，也是后续所有分布式哈希评估的基准框架。后来的每一个竞争者——Chord、Rendezvous、Jump、Maglev——都要在这四行标准前交卷。

哈希环的数学性质#

一致性哈希的性质可以用随机过程精确描述。设 $n$ 台服务器均匀随机分布在哈希环（$[0, 1)$）上，每台服务器负责的弧长近似服从指数分布，均值为 $1/n$。这来自一个经典结论：$n$ 个均匀随机点把圆周切成 $n$ 段，各段长度独立地看近似是均值为 $1/n$ 的指数变量。

这直接决定了负载的不均匀性：在没有虚拟节点时，各服务器负载的方差为 $1/n^2$（标准差 $\sim 1/n$），但最大值的期望约为均值的 $\Theta(\log n / \log\log n)$ 倍——即使均匀随机分布，仍有服务器可能负担显著高于平均的负载。

引入每台服务器 $r$ 个虚拟节点后，各服务器负载的方差降至 $O(1/(rn^2))$，最大负载与均值之比降至 $O(\sqrt{\log n / r})$。工程实践中 $r = 100$ 到 $r = 1000$ 能达到足够的均匀性。

这个分析也说明了为什么早期 Dynamo 论文（2007）推荐每个节点 $100$ 到 $200$ 个虚拟节点——这是在节点数约为几十台时均匀性与内存开销之间的合理折中。

数据复制与一致性的张力#

一致性哈希解决了"数据去哪台服务器"的问题，但分布式系统还面临更深层的挑战：当一台服务器故障时，其数据如何不丢失？答案是副本（Replication）——每份数据存储在多台服务器上。

Amazon Dynamo 的做法：每个键存储在其在环上的"首选列表"中的前 $N$ 台服务器（通常 $N = 3$）。这引入了一致性问题——三个副本可能看到不同的写入顺序。读写时用类仲裁协议控制一致性强度：读操作至少联系 $R$ 个副本、写操作至少写入 $W$ 个副本，只要 $R + W > N$，读写两群副本必有交集，就能读到足够新的数据——"多一致"变成了一个可调参数。Dynamo 选择最终一致性（Eventual Consistency） + 向量时钟（Vector Clock）来检测写冲突，并由应用层解决冲突（如购物车合并）。

这是分布式系统中CAP 定理（Brewer, 2000）的体现：在网络分区（P）存在时，系统只能在一致性（C）和可用性（A）之间选一个。Dynamo/Cassandra 选择了可用性（AP），强一致性系统（如 Google Spanner）选择了一致性（CP）。

负载均衡中的一致性哈希#

除了存储系统，一致性哈希也广泛用于有状态的负载均衡。先划一条常被混淆的边界：完全无状态的负载均衡（任意请求交给任意一台空闲机器）根本不需要一致性哈希；只有当后端保存了与请求者相关的状态——会话、缓存、数据分片——"同一个请求者回到同一台机器"这件事才值钱。

会话粘滞（Session Affinity）：同一用户的请求需要被路由到同一台后端服务器（如因为服务器上有该用户的会话状态）。基于用户 ID 的一致性哈希保证了这一点，同时在服务器增减时只有少量用户的会话受影响，而非普通哈希的全体迁移。

CDN 边缘路由：当某个热门内容需要从源站拉取时，CDN 用一致性哈希决定哪个边缘节点负责缓存它，避免同一内容被多个边缘节点重复拉取（"缓存坍塌"）。

跨域连接#

• 随机过程：把服务器均匀随机撒到环上，每台负责的弧长近似服从指数分布，均值是环长除以台数。指数分布的标准差与均值同量级，所以裸环上的负载必然不均，最大负载相对均值还带一个随规模缓慢增长的因子。虚拟节点是对这个分布做平均：每台放若干个点，负载方差按点数下降，工程上取上百个正是为把该因子压到可忽略。
• 负载均衡：普通取模哈希在台数变化时几乎重排全部键，环上映射只把一段弧交给邻居。关键性质叫单调性：新增节点只引起"旧节点到新节点"的迁移，不会触发旧节点之间的互相搬运。这一条决定了能否在线扩容——迁移量与集群规模无关，只与新增比例有关。
• 网络效应：哈希均匀化的是键，不是流量。真实访问量服从幂律，少数键占掉大部分请求，而一个键只能落在一台机器上，于是分片再多也化不开单个热键。可检验的后果很明确：增加节点数对热点毫无帮助，唯一出路是把这个键人为拆成多份再二次聚合，也就是手工把并行度加回来。
• 分布式计算理论：环只回答"数据放哪"，不回答"多份副本谁说了算"。副本一引入，网络分区时就必须在一致性与可用性之间选边，这是结构性取舍而非实现质量问题。选可用性的系统要靠版本信息检测冲突并把合并交给应用层，选一致性的系统则要在分区期间拒绝服务——同一套分片方案，上层语义可以完全不同。
• 选区划分：选区重划与它共享一条诉求——边界变动时尽量少的人改变归属。但选区还有两条硬约束：各区人口大致相等，且地理必须连续。随机哈希天然满足前者却违反后者，所以行政区划只能用连续的范围划分。这也反过来说明范围分片为何支持区间查询而哈希分片不支持：连续性被保留还是被抹掉，决定了之后能问什么问题。

参考文献#

• Karger, D. et al. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. STOC 1997, pp. 654–663.
• Thaler, D. G. & Ravishankar, C. V. Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Transactions on Networking 6(1), 1–14, 1998.（Rendezvous Hashing）
• DeCandia, G. et al. Dynamo: Amazon's Highly Available Key-Value Store. SOSP 2007, pp. 205–220.
• Stoica, I. et al. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. SIGCOMM 2001.
• Lamping, J. & Veach, E. A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294 (2014).（Jump Consistent Hash）
• Mirrokni, V., Thorup, M. & Zadimoghaddam, M. Consistent Hashing with Bounded Loads. SODA 2018.