一致性哈希：负载均衡与扩容的数学之美

设想一个缓存集群有 4 个节点，数据按 hash(key) % 4 分配到各节点，运行得很好。某天流量涨了要扩容，加一个节点变成 5 个，路由公式变成 hash(key) % 5。这时会发生什么，原本归属节点 0 的 key，现在有很高概率被重新映射到节点 2 或 3。算一下，从 4 个节点扩到 5 个，大约 80% 的 key 会改变归属节点。对一个缓存集群来说，这意味着 80% 的缓存瞬间失效，所有这些 key 的请求穿透到 DB，DB 直接被击穿。这就是普通哈希在节点动态增删时的灾难。

一致性哈希就是为解决"节点数变化导致大规模数据迁移"这个问题发明的。1997 年 MIT 的一篇论文提出这个算法，核心思想是把哈希空间组织成一个环，让节点增删只影响相邻区段的数据。它不是什么高深的理论，但背后是对"迁移代价"的精确洞察，值得拆开讲清楚。

环形空间，把节点和 key 放到同一个环上

PlantUML

正在加载图表…

图：一致性哈希把节点和 key 都映射到 0~2^32 的环上，key 顺时针遇到的第一个节点即归属节点

一致性哈希的第一步是把哈希值空间想象成一个首尾相连的环。哈希函数的输出范围是 0 到 2^32-1，把这个区间当成一个圆环。然后把所有节点和所有 key 都用同一个哈希函数映射到这个环上。节点 A 映射到环上的某个位置，key1 也映射到环上的某个位置。

路由规则极其简单，一个 key 顺时针方向遇到的第一个节点，就是它的归属节点。比如 key1 在环上的位置顺时针往下走，第一个碰到的是节点 B，那 key1 就归 B 处理。key2 顺时针先碰到节点 C，就归 C。这个"顺时针找最近节点"的规则，是一致性哈希的全部精髓。

为什么这个设计能减少迁移，关键在于节点和 key 的映射关系只取决于它们在环上的相对位置。新增或删除一个节点，只改变它附近那一小段区间里 key 的归属。

节点增删时，迁移量被压到最小

PlantUML

正在加载图表…

图：4 节点扩容到 5 节点，普通哈希约 80% 数据迁移导致缓存失效打挂 DB，一致性哈希仅约 20% 相邻区段迁移

现在往环上加一个新节点 D，它落在节点 B 和节点 C 之间。按照顺时针规则，原来归属 C 的那些 key 里，顺时针先碰到 D 的，现在改归 D。但 B 和 C 之间这一段以外的所有 key，归属完全不变。也就是说，新增一个节点，只有这个节点附近一小段区间里的数据需要迁移，其余数据纹丝不动。

这个对比很直观。普通哈希扩容 N 到 N+1 个节点，大约 N/(N+1) 的数据要迁移，加一个节点到 4 节点集群，四分之三的数据要动。一致性哈希扩容同样的规模，只有大约 1/(N+1) 的数据迁移，加一个节点到 4 节点集群，只有四分之一的数据要动。对缓存这种"数据迁移等于缓存失效等于 DB 压力"的场景，这个差异是生死攸关的。删除节点同理，被删节点的数据顺时针转移给下一个节点，其余不变。

数据倾斜，环形空间的先天缺陷

朴素的环形空间有个问题，节点在环上的位置是哈希函数决定的，节点少的时候，它们在环上的分布很可能不均匀。比如只有 3 个节点，哈希后它们可能挤在环的某一侧，另一侧是大段空缺。结果是大部分 key 顺时针都落到某一个节点上，那个节点负载远超其他两个，倾斜严重。

哈希函数本身是均匀的，但样本量太小（节点少）时，统计均匀不等于实例均匀。这就像掷 3 次骰子，恰好都是同一个点数的概率不低。节点数越少，倾斜越明显，这恰恰是缓存集群常见的规模。

虚拟节点，用数量换均匀

PlantUML

正在加载图表…

图：朴素环形节点少时落点稀疏导致严重倾斜，虚拟节点让每个物理节点在环上有上百个落点，用数量换均匀

解决倾斜的办法是虚拟节点。每个物理节点不再只映射到环上一个位置，而是映射成多个虚拟节点散布在环上。比如每个物理节点生成 150 个虚拟节点，3 个物理节点就有 450 个虚拟节点密布在环上。虚拟节点越多，分布越接近均匀，因为大数定律开始起作用。数据先路由到某个虚拟节点，虚拟节点再映射回它的物理节点。

1
int VIRTUAL_NODES = 150;
2
TreeMap<Integer, String> ring = new TreeMap<>();
3
for (String node : physicalNodes) {
4
    for (int i = 0; i < VIRTUAL_NODES; i++) {
5
        String vnode = node + "-vn" + i;
6
        int hash = hash(vnode);
7
        ring.put(hash, node);  // 虚拟节点指向物理节点
8
    }
9
}

虚拟节点的数量是经验值。太少（比如 10 个）倾斜依然明显，太多（比如几千个）内存占用和查找开销变大，而且均匀度的边际收益递减。生产里 100 到 200 之间是常见的取舍。Memcached 的客户端一般用 160 到 200 个虚拟节点，实测能把不均衡度控制在 5% 以内。

虚拟节点还有个附带好处，支持异构集群。如果集群里机器性能不一，大机器多分点虚拟节点，小机器少分点，就能让强机器承担更多流量。这种加权虚拟节点在混合部署的集群里很实用。

路由查找的实现

一致性哈希的路由实现不复杂。环用一个有序的数据结构表示，Java 里用 TreeMap。查找时，先算 key 的哈希值，在 TreeMap 里用 ceilingEntry 找到第一个大于等于该哈希的虚拟节点。如果找不到（key 的哈希比环上所有虚拟节点都大），就回环到第一个虚拟节点，这就是"顺时针绕一圈"的体现。

1
public String getNode(String key) {
2
    int hash = hash(key);
3
    Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
4
    if (entry == null) {
5
        entry = ring.firstEntry();  // 回环首
6
    }
7
    return entry.getValue();
8
}

每次路由是一次 ceilingEntry，时间复杂度是 O(log N)，N 是虚拟节点总数。对几千个虚拟节点，这是纳秒级操作，性能完全不是瓶颈。

它在哪些地方生根

一致性哈希是很多分布式系统的基础算法，理解它就理解了这些系统的扩容行为。

分布式缓存是最典型的应用场景。Memcached 的客户端路由、Redis Cluster 的哈希槽（哈希槽是一致性哈希的工程化变体，把环预切成 16384 个固定槽位，节点增删时迁移槽位而不是 key）都用这个思路。缓存场景对迁移代价极度敏感，一致性哈希把迁移量降到最小。

分布式存储，Cassandra 和 DynamoDB 的数据分片用一致性哈希，数据按哈希环分布在节点上，扩容时只迁移相邻区段。负载均衡器，一些 LVS 和网关用一致性哈希做会话保持，节点增删时只有少数连接需要重建，而不是全部重连。分库分表的扩容迁移也能用一致性哈希减轻痛苦。

凡是"节点可能动态增删，且数据迁移代价高"的场景，一致性哈希都是首选的路由算法。

一致性哈希不复杂，难的是理解它为什么是这个设计。它把"节点增删导致大规模数据迁移"这个问题，转化成了"节点增删只影响相邻区段"这个问题，核心就是环形空间加顺时针路由这一招。再配上虚拟节点解决倾斜，就能在生产里稳定运行。理解它，就理解了分布式系统扩容友好性的底层逻辑。