一致性哈希可能还不如随机

“一致性哈希”大概是分布式系统面试中出现频率最高的算法——没有之一。

如果你做过系统设计面试，你一定说过类似的话：“我们用一致性哈希来分片，加虚拟节点来均匀分布负载。” 面试官满意地点头，你满意地通过。

但你有没有在实际系统中量化过一致性哈希的效果？在你的 5 个节点上，它的负载均衡到底做得怎么样？

我跑了蒙特卡洛模拟。结论让我不太舒服。

第一章：实验——5 个节点上的尴尬

实验设计

将 100,000 个 key（均匀随机生成）分配到 N 个节点上，比较以下 5 种算法：

1. 一致性哈希环（无虚拟节点）：每个物理节点在环上只有一个哈希位置
2. 一致性哈希环（150 虚拟节点）：每个物理节点映射 150 个虚拟节点——这已经是 很多教程推荐的配置
3. Jump Consistent Hash：Google 2014 年提出的算法
4. Rendezvous Hash (HRW)：最高随机权重法
5. Maglev Hash：Google 2016 年为负载均衡器设计的算法

两个核心指标：

• 不均衡比 = 负载最重的节点的 key 数 / 平均每个节点的 key 数。理想值为 1.0，越大越差。
• 重分布比 = 新增 1 个节点后，需要迁移的 key 占比。理论最优是 1/(N+1)。

结果

N=5 个节点，100,000 个 key：

一致性哈希（无虚拟节点）的不均衡比是 3.67 倍——最忙的节点承载了平均负载的近 4 倍。在一个 5 节点集群中，这意味着一个节点在干 4 个节点的活，而其他节点可能在摸鱼。

加上 150 个虚拟节点后，不均衡比降到了 1.14x，勉强可用。但 Jump Hash、Rendezvous Hash、Maglev Hash 全部在 1.01x 左右——几乎完美均匀。

更有意思的是重分布比。无虚拟节点的一致性哈希只迁移了 8.2% 的 key，看起来很好？别高兴太早——这是因为分布本身就不均匀，新节点恰好分到了一个”人少”的区间。这不是优势，是巧合。

把节点数提高到 10 和 20：

N=10 个节点：

N=20 个节点：

规律清楚了：在常见的 5-20 节点部署规模下，一致性哈希环（即使有 150 个虚拟节点）的均衡性始终不如 Jump/Rendezvous/Maglev 三个替代方案。没有虚拟节点的一致性哈希在任何节点数下都是灾难。

那为什么所有人都在用一致性哈希环？

历史原因。2007 年 Amazon 发布 Dynamo 论文后，一致性哈希成了分布式存储的”标准答案”。在那个年代，Dynamo 需要的不只是 key 到节点的映射——它还需要范围查询（token range）、虚拟节点动态负载迁移、以及对任意节点增删的支持。一致性哈希环对 Dynamo 的需求是合理的。

但你的 5 节点微服务集群大概率不需要这些。

第二章：Jump Consistent Hash——5 行代码的完美均衡

2014 年，Google 的 John Lamping 和 Eric Veach 发表了一篇只有 4 页的论文：A Fast, Minimal Memory, Consistent Hash Algorithm。

核心算法只有 5 行：

int32_t jump_consistent_hash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (int64_t)((b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1)));
    }
    return b;
}

性质：

• 完美均衡：每个桶分到的 key 数量几乎完全相同。上面的模拟已经验证了：不均衡比始终在 1.01-1.02x。
• 最小重分布：从 N 个桶扩展到 N+1 个桶时，恰好有 1/(N+1) 的 key 被迁移。这是信息论下界——不可能做得更好了。
• O(ln N) 时间，O(1) 空间：不需要维护哈希环、虚拟节点列表。5 行代码，零状态。

为什么这么好？

传统一致性哈希环的问题在于：哈希函数不可能将少量节点均匀地映射到环上。5 个点在一个圆环上，间距天然不均匀。虚拟节点是一种暴力修复——用 750 个点（5 x 150）来近似均匀分布，但终究是近似。

Jump Hash 绕过了这个问题。它不用环。它用数学归纳法直接保证：当第 N+1 个桶加入时，每个 key 有恰好 1/(N+1) 的概率被分到新桶，其余 key 保持不变。均匀性是数学证明的，不是经验近似的。

限制：

Jump Hash 有一个严格约束：桶编号必须是 0, 1, 2, …, N-1，而且只能从末尾增删。你不能移除中间的某个桶（比如桶 3 挂了，你不能直接跳过它）。

这个限制在某些场景下根本不是问题： - Kafka 分区：分区编号天然是 0, 1, …, N-1 - 数据库分片：分片编号有序递增 - 缓存层：缓存实例按序号寻址

但在需要任意节点增删的场景下（比如 P2P 网络，或者节点可能随机宕机的集群），Jump Hash 不适用。

第三章：Maglev Hash——Google 负载均衡器的选择

2016 年，Google 发表了 Maglev: A Fast and Reliable Software Network Load Balancer 论文。Maglev 是 Google 的网络负载均衡器，处理 Google 所有外部流量的入口分发。

Maglev Hash 的核心思想是：预计算一张大的查找表（lookup table），每个 key 查表即可得到目标节点。

算法步骤：

1. 选一个大质数 M 作为表大小（论文用 65537）
2. 为每个节点生成一个 0..M-1 的排列（permutation），基于两个哈希值 offset 和 skip
3. 轮流让每个节点按自己的排列”填空”，直到表被填满
4. 查询时直接 table[hash(key) % M]

# 查询：O(1)
def lookup(key):
    return table[hash(key) % M]

性质：

• 近完美均衡：每个节点在表中占的槽位数几乎相等（因为轮流填充）
• 接近最小重分布：节点变更时，大约 1/N 的 key 被重新分配
• O(1) 查询：一次哈希 + 一次数组访问，比任何其他方案都快
• 天然支持加权：权重高的节点多填几轮，简单直观
• 缺点：建表需要 O(M * N) 时间和 O(M) 空间。M=65537 时，对于几十个节点，建表在毫秒级完成，不是问题

适用场景：

Maglev Hash 是为网络负载均衡设计的。它的优势在查询的极致速度——对每个数据包做一次哈希 + 查表，没有任何循环或递归。在每秒处理数百万数据包的负载均衡器中，O(1) 和 O(ln N) 的差距是真实可测的。

如果你在写负载均衡器、CDN 调度、或者任何需要极快查询的分流场景，Maglev Hash 是目前的最优解。

第四章：Rendezvous Hash——被低估的朴素方案

Rendezvous Hash（又叫 Highest Random Weight，HRW）是 1998 年由 Thaler 和 Ravishankar 提出的，比 Jump Hash 和 Maglev 都早得多。

算法简单到不需要解释：

def rendezvous_hash(key, nodes):
    return max(nodes, key=lambda node: hash(f"{key}-{node}"))

对于每个 key，计算它与所有节点的组合哈希值，取最大的那个节点。一行代码，完事。

性质：

• 完美均衡：和 Jump Hash 一样，数学可证的均匀分布
• 最小重分布：新增或移除一个节点时，恰好 1/N 的 key 被迁移
• 支持任意节点增删：不像 Jump Hash 要求有序编号，节点可以是任意字符串
• 零状态：不需要维护环、查找表、或任何全局数据结构
• 缺点：O(N) 查询——每个 key 都要遍历所有节点算一次哈希

O(N) 看起来很吓人？看你的 N 是多少。

如果 N = 5（5 个微服务实例），那是 5 次 MD5 计算。如果 N = 20（20 个缓存节点），那是 20 次。在现代 CPU 上，MD5 的吞吐量大概是每秒几百万次。20 次 MD5 的延迟在微秒以下。

当你的节点数在几十以内时，O(N) 和 O(1) 的差距根本不在你的瓶颈路径上。代码简洁性、可推理性、零状态的好处远大于那几微秒。

Rendezvous Hash 是我个人在节点数少（< 30）且需要任意增删的场景中的默认选择。不需要任何库，一行代码搞定，性质完美。

第五章：选型决策

汇总成表：

什么时候一致性哈希环才是对的

一致性哈希环（带虚拟节点）在以下条件全部满足时仍然是合理选择：

1. 节点数 > 100：虚拟节点的近似均匀效果在大规模下更好
2. 需要范围查询：比如 Cassandra 的 token range scan，需要知道哪些 key 落在哪个区间。环结构天然支持这个，其他算法不行
3. 节点动态性高：节点频繁加入/离开，且不是有序编号

这正是 Amazon Dynamo（2007）和 Apache Cassandra 的使用场景。这些系统的一致性哈希是经过深思熟虑的——它们用虚拟节点不是为了均匀分布，而是为了细粒度的负载迁移和范围查询支持。

但如果你的场景是”5 个 Redis 实例做缓存分片”或者”10 个微服务实例做请求路由”——你不需要一致性哈希环。Rendezvous Hash（代码最简单）或 Jump Hash（完美均衡 + 最小迁移）几乎肯定是更好的选择。

一个容易忽略的维度：实现复杂度

代码越少，bug 越少。在生产系统中，这是一个被严重低估的优势。

结尾：不是打脸，是工程判断

一致性哈希不是一个坏算法。它在 1997 年被发明时是突破性的创新，在 Dynamo/Cassandra 这类大规模分布式存储中至今仍然合理。

但它被过度使用了。

在大多数实际部署中——3 到 20 个节点，不需要范围查询，节点变更不频繁——Jump Hash、Rendezvous Hash、或 Maglev Hash 在均衡性、简洁性、可维护性上全面胜出。

本站已有的 一致性哈希原理 讲了”怎么用”，溢出问题分析 讲了”有什么坑”，这一篇讲的是”什么时候别用”。三篇合起来，算是一份完整的分布式哈希选型指南。

了解一个算法的适用边界，和了解它的工作原理一样重要。

参考资料：

1. Karger et al., 1997. Consistent Hashing and Random Trees – 一致性哈希原始论文
2. Lamping & Veach, 2014. A Fast, Minimal Memory, Consistent Hash Algorithm – Jump Consistent Hash
3. Eisenbud et al., 2016. Maglev: A Fast and Reliable Software Network Load Balancer – Maglev Hash
4. Thaler & Ravishankar, 1998. A Name-Based Mapping Scheme for Rendezvous – Rendezvous Hash (HRW)
5. DeCandia et al., 2007. Dynamo: Amazon’s Highly Available Key-value Store – Amazon Dynamo
6. 一致性哈希的原理和历史 – 本站：基础原理
7. 一致性哈希中的溢出问题 – 本站：概率分析