"加一台机器,数据怎么重新分配?" —— 这是分布式存储和分布式缓存绕不开的核心问题。普通取模(node = hash(key) % N)在节点变化时会让所有数据重新映射,代价巨大。一致性哈希给出了优雅的答案:节点增减只影响相邻节点的数据。这篇文章把一致性哈希讲透,从原始算法到虚拟节点、到 Jump Hash、再到现代系统(Redis Cluster、DynamoDB、CDN)的实际应用。
问题:为什么不能简单取模
三台节点,key 取模分配:
node 0:keys hash % 3 == 0
node 1:keys hash % 3 == 1
node 2:keys hash % 3 == 2现在加一台节点变 4 个:
node 0:keys hash % 4 == 0
node 1:keys hash % 4 == 1
node 2:keys hash % 4 == 2
node 3:keys hash % 4 == 3所有 key 的归属几乎都变了 —— 因为 mod 3 和 mod 4 的结果几乎完全无关。3 节点扩到 4 节点,理想只需要迁移 1/4 数据,但取模会迁移 3/4。集群越大问题越严重 —— 缓存层这样做等于"瞬间全部失效",数据库这样做等于"所有数据搬家"。
一致性哈希的核心思想
Karger 等人 1997 年提出。基本思想:把 key 和节点都映射到同一个哈希环上,key 顺时针找到第一个节点就归该节点。
哈希环:0 ~ 2^32 - 1,首尾相连成环
节点哈希:
hash("node-A") -> 1000
hash("node-B") -> 4000
hash("node-C") -> 7000
key 哈希:
hash("key1") -> 1500 -> 顺时针找到 node-B
hash("key2") -> 6000 -> 找到 node-C
hash("key3") -> 8000 -> 找到 node-A (绕回开头)关键性质:加一个节点 D(hash=5000),只有 4001~5000 这段 key 从 C 转到 D,其他不变。删一个节点也类似 —— 只有它负责的 key 顺时针交给下一个节点。变更只影响 1/N 数据(N 是节点数)。
简单实现
import bisect
import hashlib
class ConsistentHash:
def __init__(self, nodes=None):
self.ring = [] # 排序的哈希值
self.ring_map = {} # 哈希值 -> 节点
for node in (nodes or []):
self.add_node(node)
def _hash(self, key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node):
h = self._hash(node)
bisect.insort(self.ring, h)
self.ring_map[h] = node
def remove_node(self, node):
h = self._hash(node)
self.ring.remove(h)
del self.ring_map[h]
def get_node(self, key):
if not self.ring:
return None
h = self._hash(key)
# 找到第一个 >= h 的位置;没有就绕回 0
idx = bisect.bisect(self.ring, h) % len(self.ring)
return self.ring_map[self.ring[idx]]
# 用法
ch = ConsistentHash(["node-A", "node-B", "node-C"])
print(ch.get_node("user:1234")) # node-X
print(ch.get_node("user:5678")) # node-Y
# 加节点
ch.add_node("node-D")
print(ch.get_node("user:1234")) # 可能还是 X,也可能变成 D问题:数据倾斜
3 个节点随机散在环上,如果它们位置不均(运气不好),某个节点可能负责环的一大段,而另一个只负责一小段。结果:有的节点压力大,有的节点闲。
节点位置:A=100, B=200, C=3 000 000 000
负责区间:
A:200~100 (绕环一圈)— 极大!
B:100~200 — 极小
C:200~3000000000 — 中等这就是数据倾斜问题,简单一致性哈希在节点少时严重。
虚拟节点(Virtual Nodes / Vnodes)
解决倾斜的标准方案:把每个物理节点映射成 N 个虚拟节点,虚拟节点散到环的不同位置。
def add_node(self, node, vnodes=150):
for i in range(vnodes):
vkey = f"{node}#{i}"
h = self._hash(vkey)
bisect.insort(self.ring, h)
self.ring_map[h] = node # 都指向同一个物理节点虚拟节点数 150-1000 个能让分布接近均匀。Memcache、Redis 客户端的 ketama 算法、Dynamo 都用虚拟节点。
实战 1:Memcached 客户端的 Ketama
Last.fm 2007 年开源的 ketama,几乎成了一致性哈希在缓存层的事实标准。每个 Memcached 节点 160 个虚拟节点,用 MD5 哈希,客户端直接根据 ketama 算法找节点 —— 服务端无需协调,加节点只是改客户端配置。
# Python pylibmc / mc 库都支持 ketama
import memcache
mc = memcache.Client(
["10.0.0.1:11211", "10.0.0.2:11211", "10.0.0.3:11211"],
behaviors={"ketama": True} # 启用一致性哈希
)
mc.set("foo", "bar")这样设计的好处:加节点时大部分 key 的去向不变 —— 缓存命中率不会瞬间塌方。
实战 2:Redis Cluster 的"哈希槽"
Redis Cluster 没用经典一致性哈希,而是用固定 16384 个槽(slots):
slot = CRC16(key) % 16384
每个节点负责一段连续的槽:
node 0:slot 0 ~ 5460
node 1:slot 5461 ~ 10922
node 2:slot 10923 ~ 16383加节点时:把现有节点的部分槽迁给新节点,只迁移涉及的槽对应的 key。这其实是"预分片 + 显式槽分配",效果类似一致性哈希,但简化了实现 —— 客户端只要拿一份"槽 → 节点"映射表即可。
设计权衡:固定 16384 槽 = 易实现、易调试、迁移粒度合适;经典一致性哈希 = 更"动态",但实现复杂。Redis 选择更工程化的方案,大多数互联网级系统也这么做(Codis、Aerospike、Kafka 也是预分片)。
实战 3:Cassandra / DynamoDB 的环
Cassandra 用经典一致性哈希 + 虚拟节点。每个物理节点默认 256 个 vnode。一份数据存 N 个副本(replication factor),按"顺时针的下 N 个不同物理节点"放。
RF=3 时:
key 落在 node-A
副本存到 node-A、node-B、node-C(顺时针下两个物理节点)
读时配合 Quorum:
R+W > N 保证强一致
R=W=2,N=3 -> 强一致(慢)
R=1,W=1 -> 最终一致(快)DynamoDB 论文里的 Dynamo 模型也是这套思路。一致性哈希 + 多副本 + Quorum 是 NoSQL 数据库的经典设计。
Jump Consistent Hash:Google 的简化版
Google 2014 年提出 Jump Hash,只用几行代码、无需虚拟节点、分布均匀:
int jump_hash(uint64_t key, int num_buckets) {
int64_t b = -1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double)(1LL << 31) / (double)((key >> 33) + 1);
}
return b;
}
# 用法
node_idx = jump_hash(hash(key), num_nodes)性质:
- 不需要存任何环结构 —— 给定 key 和 N 直接算节点。
- 分布天然均匀,无需虚拟节点。
- N 从 K 变到 K+1 时,只有 1/(K+1) 的 key 改归属。
限制:节点必须用 0~N-1 编号,不能随意删除中间节点(只能在尾部加 / 减)。对"有序追加节点"场景特别合适。GFS / Bigtable / 某些 CDN 用。
Rendezvous Hashing(HRW)
另一种思路:对每个 (key, node) 对算 hash,key 归 hash 最大的那个 node:
def get_node(key, nodes):
return max(nodes, key=lambda n: hash(f"{key}:{n}"))性质和一致性哈希类似(节点变化只影响 1/N 数据),但实现极简,且支持"按权重分配"(节点 hash 乘权重)。CDN 的源站选择常用这个。
实战 4:CDN 边缘节点选择
CDN 用一致性哈希决定"哪个边缘节点缓存哪个 URL"。同一个 URL 总落到同一个节点 → 缓存命中率高;加边缘节点 → 只迁移 1/N 数据。
def select_edge(url, edges):
return hrw_hash(url, edges)
# 客户端总把同一 URL 请求同一个边缘,提升 cache hitAkamai、Cloudflare、Fastly 内部都有类似机制。
实战 5:分布式锁的归属
多个 Redis 节点做分布式锁,锁 key 要稳定地落到同一节点,否则锁不上。一致性哈希让 lock("order:1001") 永远去同一节点,自然保证。
"权重"支持
节点性能不一致(老机器 8 核,新机器 32 核)时,希望强节点承担更多 key。两种实现:
1. 多重虚拟节点
强节点给更多虚拟节点。8 核给 100 vnode,32 核给 400 vnode。
2. 加权 Rendezvous
def get_node(key, weighted_nodes):
return max(weighted_nodes, key=lambda n: -math.log(rand_from_hash(key, n.id)) / n.weight)常见坑
坑 1:虚拟节点数不够导致倾斜。 50 个 vnode 在 3 节点集群可能仍倾斜 20%+。生产场景至少 150-300 个。
坑 2:哈希函数选错。 用了分布不均的哈希(如简单的 key.hashCode())会导致 key 集中在某段环。MD5 / MurmurHash3 是常见选择。
坑 3:删节点不下线数据。 节点从环上移除后,它"本该负责"的 key 全转给顺时针下一个节点。但物理节点上的数据并没自动迁过去 —— 要么有后台同步,要么读侧实现"找不到就去下一个节点"的兜底。
坑 4:加节点时缓存命中率短暂下降。 新节点刚加入,它负责的 key 在新节点上还没缓存,要回源。这种"热点漂移"在大流量场景明显。常见缓解:预热(从邻居节点同步数据再上线)。
坑 5:哈希环序列化跨语言不一致。 Java 的 String.hashCode 和 Python 的 hash 算出不同值。多语言项目要统一用 MD5 / MurmurHash 等跨语言一致的哈希。
什么时候用一致性哈希
- 分布式缓存(Memcached、Redis Cluster、CDN 边缘)。
- 分布式数据库分片(Cassandra、DynamoDB)。
- 消息队列分区(Kafka 的 partitioner 默认就是这套思路)。
- 分布式锁的节点选择。
- 对象存储的副本分布(Ceph 的 CRUSH 是一致性哈希的进化版)。
什么时候不用
- 数据量小 / 节点固定:简单取模或哈希分片就够。
- 需要范围查询:一致性哈希让 key 完全随机分布,"查询 user_id 1000~2000"要扫所有节点。这类场景要用范围分片。
- 需要精细控制(把特定 key 强制放某节点):一致性哈希是"哈希决定",不支持。
Maglev Hashing:Google 的负载均衡器内核
Google 内部负载均衡器 Maglev 用的哈希算法,2016 年开源论文。它的核心是"预计算查找表":每个 backend 用伪随机偏好序列填一张大小为 M(素数)的表,key hash 后查表得后端。
构建查找表的简化逻辑:
N 个后端,每个有 (offset_n, skip_n)
for slot in 0..M-1:
选下一个后端 n(轮流给每个后端机会)
target = (offset_n + i * skip_n) % M
如果 lookup[target] 空:lookup[target] = n
n 的 i++查找时只要 lookup[hash(key) % M] 一次数组访问,极快。后端增减时 disrupt 率 ≈ 1/N,接近最优。Maglev 是 Google Cloud Load Balancer、Envoy 的 ringhash 算法的灵感来源。
分片 + 副本的组合
一致性哈希解决"每个 key 归哪个节点"。但实际生产数据还需要副本。常见组合:
1. 一致性哈希决定 primary 节点
2. primary 之后顺时针的 N-1 个不同物理节点是 replica
加节点 D 后:
受影响的 key:落在 D 负责的环段
这些 key 的 primary 从 C 变成 D
D 把这些 key 的副本同步到自己 + 下两个节点
读时配合 Quorum,读多数副本 -> 强一致这就是 Dynamo / Cassandra 的"preference list" —— 每个 key 有一个有序的副本列表,从环上顺序生成。读写按列表顺序尝试,失败就 fallback 到下一个。
热点处理
一致性哈希不能避免"单个 hot key 把节点压垮" —— 一个超热的 key 永远落到同一节点。常见缓解:
- 客户端分散:把热 key 复制成
key#0、key#1...key#9,客户端随机读其中一个。写要更新所有副本。 - 本地缓存:客户端 / 应用层缓存,减少对后端节点的请求。
- 动态识别 + 多副本:监控发现 hot key 后,临时给它在多个节点放副本。Redis Cluster 的"读 slot replication"思路。
Ceph 的 CRUSH:一致性哈希的进化版
Ceph 存储用 CRUSH 算法决定数据放在哪些 OSD(存储节点),它是一致性哈希的复杂演化:
- 支持层级结构:数据中心 → 机柜 → 主机 → OSD,可以"同一份数据 3 个副本必须分在 3 个不同机柜"。
- 支持权重:不同 OSD 容量不同,自动分配多 / 少。
- 确定性:给定 key 和 cluster map,任何节点都能算出"这个 key 该在哪些 OSD",不用查中心。
这种"分布式哈希 + 拓扑感知 + 副本约束"是大规模存储系统的标配设计。
真实迁移成本
"一致性哈希加节点只迁移 1/N 数据" 是数学性质。但工程上"迁移"本身有成本:
- 数据量大时,1/N 也可能是 TB 级,迁移耗几小时。
- 迁移期间,该数据的读可能 fallback 到旧节点(双写、影子读)。
- 必须限速避免迁移流量打挂网络。
所以"加机器"在生产系统里通常是计划性活动,有运行手册、限速策略、回滚机制。"挂掉一台立刻加新机器" 的设想多数情况下不现实 —— 你能挂的机器都是有冗余的。
写在最后
一致性哈希是"动态扩缩容"问题的优雅解。它的存在让"分布式系统加机器"从"瞬间全部失效"变成"1/N 影响",直接催生了 CDN、Memcached 集群、NoSQL 大规模化的可能。这是分布式系统设计里少数"原理简单 + 应用广泛 + 工程价值巨大"的算法。
给一个工程心得:一致性哈希的真正价值不在"哈希环",而在"变化局部化"。任何"节点数会变,但 key 到节点的映射希望稳定"的场景都该想到它。当你设计一个会扩缩容的分布式服务时,默认就选一致性哈希(或 Jump Hash / Rendezvous)分配,而不是取模 —— 这点投入在第一次扩容时就会给你巨大回报。
—— 别看了 · 2026