图解一致性哈希：哈希环、虚拟节点与再平衡

你用 hash(key) % 10 把缓存分布到十台服务器上。流量增长后，你加了第十一台服务器，命中率随即崩溃：几乎每个键现在都映射到了另一台服务器，于是缓存在所有地方同时变冷，后面的数据库承受了全部负载。一致性哈希正是为了防止这种情况而存在的。

本文用一张图讲解哈希环和虚拟节点，衡量它们能带来多大帮助，给出一个简洁的实现，并比较你在真实系统中会遇到的替代方案：rendezvous 哈希、jump hash、Maglev 和固定哈希槽。

为什么取模哈希会失效

使用 server = hash(key) % N 时，映射取决于 N。一旦 N 改变，只有当一个键的哈希值对两个 N 取模得到相同余数时，它才会留在原处，而这很少见。用一百万个键做一次快速模拟，结果如下：

理想值是 1/11，约 9.1%：新服务器应当接走属于它的那一份，其他一切都不应移动。哈希环已经很接近了；剩下的差距来自新服务器的令牌恰好落在了比平均略大的弧段上。

对缓存来说，区别在于命中率短暂下滑还是彻底冷启动。对分片数据库或一组有状态的工作节点来说，区别在于迁移十分之一的数据还是几乎全部数据。

哈希环

一致性哈希由 Karger 等人于 1997 年为 Web 缓存提出，它把服务器和键都映射到同一个环形哈希空间上，例如从 0 到 2^64 - 1 的整数，最大值之后回绕到 0。

1. 对每台服务器的名称做哈希，得到它在环上的位置。
2. 对每个键做哈希，得到它在环上的位置。
3. 从键的位置开始顺时针前进。遇到的第一台服务器就是这个键的所有者。

添加一台服务器会把它放在一个位置上，它只接管自己与前一台服务器之间的键。其他所有键都留在原处。移除一台服务器时，它的键交给顺时针方向的下一台服务器。其他一切都不变。

虚拟节点：修正不均衡

如果每台服务器只有一个位置，服务器之间的弧段是随机且不均匀的，于是有些服务器拥有的环远比其他服务器多。用十台服务器做同样的模拟，可以看出差距有多大：

解决办法是对 cache-a#0、cache-a#1 这样的名称做哈希，给每台服务器许多位置，这些位置称为虚拟节点或令牌（token）。虚拟节点还带来另外两个好处：

• 权重。 内存翻倍的服务器分到翻倍的令牌。
• 更平缓的故障。 一台服务器宕机时，它的许多小弧段会分给许多不同的后继者，因此它的负载会分散到整个集群，而不是让某一个邻居的负载翻倍。

代价是更大的查找表，以及成员变化时要迁移的更多元数据。Cassandra 在实践中展示了这种取舍：在 4.0 版本把默认值降到 16 之前，它默认每个节点使用 256 个令牌；新的默认值配合一种令牌分配算法，把这 16 个令牌均匀而非随机地放置。

一个小型实现

一个哈希环就是一个有序的令牌位置列表加上二分查找：

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

对于 T 个令牌，查找的开销是 O(log T)。生产环境的版本还会处理令牌冲突，并让每个客户端看到完全相同的成员列表，因为服务器列表不同的两个客户端会对键的位置产生分歧。

环上的复制

存储系统不仅用环来路由，也用它来放置数据。Amazon 的 Dynamo 论文把每个键存放在从其位置顺时针出发的前 N 台不同服务器上，也就是它的 preference list，并跳过属于已在列表中的服务器的额外令牌。当 N = 3 时，失去一台服务器后，它持有的所有数据仍在环上相邻的服务器中保留两份副本。

同样的“顺时针前进并跳过重复”思路也可以扩展到机架和可用区：不断跳过令牌，直到副本分布在不同的故障域中。

你会遇到的替代方案

Jump consistent hash 适合分片有编号且只增不减的分片存储。Rendezvous 哈希适合服务器数量少、每次查找 O(N) 无关紧要的场景。哈希槽用显式的、由运维人员控制的迁移取代自动放置，许多团队在数据库上更偏爱这种方式。

热点键与有界负载

一致性哈希均衡的是键，而不是流量。一个名人用户或一款爆款商品仍然会落在同一台服务器上。带有界负载的一致性哈希（consistent hashing with bounded loads）把每台服务器的负载上限设为高于平均值的某个百分比，并把溢出部分交给顺时针方向的下一台服务器。HAProxy 通过 hash-balance-factor 设置实现了这一点。对于真正的热点键，你仍然需要对该键做复制、合并请求，或在前面放一个小型本地缓存。

运维陷阱

• 更换哈希函数或令牌方案会像取模哈希一样把一切重新打乱。把它当作一次迁移来对待。
• 成员列表必须一致。 从单一来源分发服务器列表，例如协调服务或负载均衡器的配置，并一步完成变更。
• 反复上下线的服务器会造成抖动。 每隔几分钟健康检查失败一次的服务器，会让它的键来回迁移。在移除和重新加入之前加入迟滞机制。
• 新服务器从冷状态开始。 新的缓存节点会立即接收它那一份请求；如果后端扛不住缓存未命中，就先预热它，或逐步提高它的权重。

哈希环图

这张图的读法如下：

• 圆就是哈希空间。 位置沿顺时针方向递增，顶部是最大值回绕到零的地方。
• 彩色令牌是虚拟节点。每种颜色代表一台服务器，每台服务器都有若干令牌分布在环上。
• 键位于各自的哈希位置，箭头顺时针指向拥有它们的令牌。
• 虚线令牌属于正在加入的服务器 D。 只有紧挨在 D 的令牌逆时针一侧的键会更换所有者。
• 图例和 Markdown 块列出了各服务器以及上文模拟得到的迁移数字。

清晰地绘制哈希方案

• 画环，而不是画表。 顺时针规则是视觉化的；查找表会掩盖为什么只有部分键会移动。
• 按服务器给令牌着色并添加图例，而不是从每个令牌各画一条连线到它的服务器。
• 展示一次成员变化。 静态的环只能解释路由；有一台服务器加入的环才能说明这项技术的全部意义。
• 在旁边放上真实数字：迁移的键数和负载分布。它们比图本身更有说服力。

一致性哈希出现在本博客的许多系统设计文章中：数据库分片图用它放置数据，负载均衡器图用它实现粘性路由，缓存策略图用它构建分布式缓存。

在 Archboard 中构建

1. 使用 Google 或 GitHub 登录，并新建一张图。
2. 添加一个基础节点包中的大 椭圆 形状作为哈希环。
3. 在环上添加小 椭圆 形状作为令牌，并按服务器着色：服务器 A、B、C 各两个，新服务器 D 两个虚线的。
4. 在环旁边竖排添加四个数据节点包中的 Redis 节点作为图例，颜色与各自的令牌一致。
5. 在环上添加基础节点包中的 文本 标签表示键，并画短箭头指向拥有它们的令牌。
6. 添加一个基础节点包中的 Markdown 块，写明键迁移和负载的数字。

这个示例共用 14 个图表节点，在 Free 套餐的限制之内。

常见问题

一致性哈希解决什么问题？ 在增加或移除服务器时，它让大多数键留在原来的服务器上。使用取模哈希时，改变服务器数量会让几乎所有键重新映射；使用一致性哈希时，只有大约 1/N 的键会迁移。

一致性哈希中的虚拟节点是什么？ 每台物理服务器以不同的名称在环上放置很多次。位置越多，弧段越均匀，还能按容量给服务器加权，并把故障服务器的负载分散到许多其他服务器上。

每台服务器应该有多少个虚拟节点？ 足以在你的集群规模下实现均匀分布即可：在我们的模拟中，十台服务器各配 100 个虚拟节点时，最忙的服务器与平均值的差距保持在 7% 以内。具备更聪明的令牌分配机制的系统，例如 Cassandra 4.0 及之后的版本，使用的数量要少得多。

Redis Cluster 算一致性哈希吗？ 不算环意义上的一致性哈希。Redis Cluster 把键映射到 16,384 个固定哈希槽，再把槽分配给节点；迁移数据意味着显式地迁移槽。

一致性哈希和 rendezvous 哈希有什么区别？ 两者在成员变化时都只迁移约 1/N 的键。Rendezvous 哈希为每个键给每台服务器打分并选出最高者，它不需要环，但每次查找的开销是 O(N)。

免费开始 — 1 个席位，无需信用卡。