用 Rust 从零实现一致性哈希:虚拟节点解决的是什么问题
分片最朴素的写法是
hash(key) % N。它能用,直到你要扩容。
加一台机器,N 从 4 变成 5。原来落在机器 2 上的 key,现在大部分都换了目标——几乎所有数据都要搬家。
一致性哈希就是为解决这件事发明的:增删节点时,只影响 1/N 的数据。 但它本身又带来了一个新问题,需要靠虚拟节点来修。
先看取模分片到底多痛
fn shard_of(key: &str, nodes: usize) -> usize {
let mut h = DefaultHasher::new();
key.hash(&mut h);
(h.finish() % nodes as u64) as usize
}4 台机器时,key "user:42" 可能落在 3 号机。扩容到 5 台之后,同一个 key 可能落在 0 号机。
统计一下:从 4 台扩到 5 台,大约 4/5 = 80% 的 key 会改变目标节点。
这意味着:缓存全部失效、需要迁移大量数据、迁移期间系统压力翻倍。对一个大集群来说,这是一次"全量重分布"。
一致性哈希要做的,就是把"80% 重分布"降到"20%"。
核心思想:把节点和数据都映射到一个环上
一致性哈希的第一步是构造一个哈希环:
0
359 ┌───────┐ 1
│ │
270 │ ● │ 90 ● = 节点
│ │
└───────┘
180规则很简单:
- 把哈希值空间看成一个环(比如
0..2^64,首尾相接) - 每个节点算出哈希值,落在环上
- 每个 key 算出哈希值,也落在环上
- key 归属顺时针方向遇到的第一个节点
use std::collections::BTreeMap;
pub struct HashRing {
/// 环上的点 -> 节点标识
ring: BTreeMap<u64, String>,
}
impl HashRing {
pub fn new() -> Self {
Self { ring: BTreeMap::new() }
}
pub fn add_node(&mut self, node: &str) {
let pos = hash(node);
self.ring.insert(pos, node.to_string());
}
pub fn remove_node(&mut self, node: &str) {
let pos = hash(node);
self.ring.remove(&pos);
}
/// 找到 key 归属的节点
pub fn locate(&self, key: &str) -> Option<&str> {
if self.ring.is_empty() {
return None;
}
let pos = hash(key);
// 顺时针找第一个 >= pos 的节点
self.ring
.range(pos..)
.next()
.or_else(|| self.ring.iter().next()) // 绕回开头
.map(|(_, node)| node.as_str())
}
}
fn hash(s: &str) -> u64 {
let mut h = 0xcbf2_9ce4_8422_2325u64;
for b in s.bytes() {
h ^= b as u64;
h = h.wrapping_mul(0x100_0000_01b3);
}
h
}为什么用 BTreeMap? 因为它提供 range(pos..)——找到环上"第一个不小于 pos 的点",这正是顺时针查找。复杂度 O(log n)。
为什么需要"绕回开头"? 因为环是首尾相接的。key 落在最后一个节点之后,应该归属第一个节点。
这个设计为什么能减少迁移
假设环上有 A、B、C 三台机器。现在加入 D,它落在 A 和 B 之间:
加 D 之前: ... A ──────────── B ...
加 D 之后: ... A ──── D ───── B ...
影响范围:只有原本落在 (A, D) 这段区间的 key 会从 B 改到 D只有这一段区间的数据需要迁移,其他完全不动。
统计上,如果节点在环上均匀分布,加入第 N+1 台机器时,只有 1/(N+1) 的数据需要移动。从"80% 重分布"变成了"20%"。
一致性哈希的价值不是"更快",而是"扩容的代价从全量变成了增量"。 它换来的是可运维性。
但均匀分布是奢望:数据倾斜
问题来了:节点的哈希值不会均匀分布在环上。
三台机器哈希出来可能是这样:
A
│
│ 这里空了一大片
│
B ───┴──────────────── C从 A 到 B 这一段弧很长,落在这里的 key 全都归 B。结果就是 B 承担了 50% 的数据,A 只有 5%。
节点越多这个偏差会自然减小,但现实中几十台机器的集群,倾斜依然很严重,因为哈希的随机性需要足够多的样本才能收敛。
这就是"数据倾斜"问题:环上节点分布不均,导致负载不均。
解法:虚拟节点
修法很巧妙:不要让一台物理机器在环上只有一个点,而是给它很多个点。
pub struct HashRing {
ring: BTreeMap<u64, String>,
/// 每个物理节点对应多少个虚拟节点
replicas: usize,
/// 节点名 -> 虚拟节点位置,方便删除
node_positions: std::collections::HashMap<String, Vec<u64>>,
}
impl HashRing {
pub fn new(replicas: usize) -> Self {
Self {
ring: BTreeMap::new(),
replicas,
node_positions: std::collections::HashMap::new(),
}
}
pub fn add_node(&mut self, node: &str) {
let mut positions = Vec::with_capacity(self.replicas);
for i in 0..self.replicas {
// 关键:给每个虚拟节点拼上唯一的后缀
let vnode = format!("{node}#{i}");
let pos = hash(&vnode);
self.ring.insert(pos, node.to_string());
positions.push(pos);
}
self.node_positions.insert(node.to_string(), positions);
}
pub fn remove_node(&mut self, node: &str) {
if let Some(positions) = self.node_positions.remove(node) {
for pos in positions {
self.ring.remove(&pos);
}
}
}
}"node#i" 这个后缀是虚拟节点能工作的关键。 它保证了同一台物理机的 N 个虚拟节点哈希到环上完全不同的位置——否则它们会聚集在同一处,等于没加。
虚拟节点怎么解决倾斜? 因为现在每台机器都有 100-200 个点散布在环上,这些点的集合在统计上趋于均匀。即使个别点扎堆,整体上每台机器负责的弧长会接近平均值。
不用虚拟节点:
A 占 5% B 占 50% C 占 45%
用 150 个虚拟节点:
A 占 33.1% B 占 33.4% C 占 33.5% ← 收敛到均值的 ±1% 内除此之外,虚拟节点还带来了两个额外好处:
1. 支持异构机器。 性能强的机器可以分配更多虚拟节点,自然承担更多数据。
// 配置驱动的权重
pub fn add_node_with_weight(&mut self, node: &str, weight: f64) {
let replicas = (self.replicas as f64 * weight) as usize;
// ... 用 replicas 个虚拟节点
}2. 迁移粒度更细。 一台机器下线时,它的数据被分散到很多其他机器上,而不是全部压给顺时针相邻的那一台。
虚拟节点的一致性哈希里,真正重要的是"虚拟"这件事——物理节点只是一个标签,环上打点的是它的 N 个分身。
副本:一次查询定位多个节点
分布式存储通常要存多副本。一致性哈希的做法是:从 key 的位置顺时针走,取前 R 个不同的物理节点。
/// 返回 key 的 R 个副本所在节点
pub fn locate_replicas(&self, key: &str, replicas: usize) -> Vec<String> {
if self.ring.is_empty() {
return Vec::new();
}
let pos = hash(key);
let mut result = Vec::with_capacity(replicas);
let mut seen = std::collections::HashSet::new();
// 从 pos 开始顺时针遍历,收集不同的物理节点
for (_, node) in self.ring.range(pos..).chain(self.ring.iter()) {
if seen.insert(node.clone()) {
result.push(node.clone());
if result.len() >= replicas {
break;
}
}
}
result
}注意 seen 这个去重集合是必需的。 因为一台物理机有多个虚拟节点,顺时针走的时候可能连续遇到同一台机器的多个点。不去重的话,R 个副本可能全落在同一台机器上——副本就失去了意义。
这是一个非常常见、也非常危险的实现 bug:测试环境节点少的时候,两个副本落在同一台机器的概率不低,但不容易被发现。
环的均衡度怎么衡量
上线前应该验证"虚拟节点数是否够"。方法很简单:采样大量 key,统计每个节点的占比。
pub fn measure_balance(ring: &HashRing, sample: usize) -> Vec<(String, f64)> {
let mut counts: std::collections::HashMap<String, usize> = std::collections::HashMap::new();
for i in 0..sample {
if let Some(node) = ring.locate(&format!("key-{i}")) {
*counts.entry(node.to_string()).or_insert(0) += 1;
}
}
let mut result: Vec<(String, f64)> = counts
.into_iter()
.map(|(n, c)| (n, c as f64 / sample as f64))
.collect();
result.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
result
}判断标准:最大占比和最小占比的差异应该在 ±5% 以内(对 100 个虚拟节点)。如果差异很大,就加大 replicas。
经验值:
| 物理节点数 | 建议 replicas |
|---|---|
| 3-10 | 100-200 |
| 10-50 | 100-150 |
| 50+ | 50-100 |
节点越多,需要的虚拟节点越少——因为大样本本身就趋于均匀。
一个重要的工程细节:哈希函数要选好
环上的均匀性完全依赖哈希函数的质量。用 DefaultHasher(标准库)够用,但对一致性哈希,我更推荐:
/// 用 xxhash / murmur3 这类快且分布均匀的哈希
fn hash(s: &str) -> u64 {
// 这里用 FNV-1a 举例,实际生产建议 xxhash64
let mut h = 0xcbf2_9ce4_8422_2325u64;
for b in s.bytes() {
h ^= b as u64;
h = h.wrapping_mul(0x100_0000_01b3);
}
// 最后做一次"雪崩"混合,避免低位规律
h ^= h >> 33;
h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
h ^= h >> 33;
h
}最后那两行混合很关键。 单纯 FNV 的高位分布好但低位有规律,如果直接取 % N 会出问题。做一次 finalizer(murmur3 的混合函数)能把所有位的随机性打散。
这里有个容易踩的坑:不要用 hash % N 做二次分片。 一致性哈希已经把"分布"交给环了,不要再叠加取模。
一致性哈希 vs 其他分片方案
| 方案 | 扩容影响 | 均衡性 | 实现复杂度 |
|---|---|---|---|
| 取模 | 几乎全部迁移 | 好 | 极低 |
| 一致性哈希 | 1/N | 靠虚拟节点 | 低 |
| Rendezvous(HRW) | 1/N | 好 | 极低 |
| 分片表(元数据) | 可控 | 完全可控 | 高(需要中心协调) |
Rendezvous 哈希值得一提,它是一致性哈希的一个更简单的替代:
fn rendezvous(key: &str, nodes: &[String]) -> &str {
nodes
.iter()
.max_by_key(|node| {
let mut h = std::collections::hash_map::DefaultHasher::new();
h.write(key.as_bytes());
h.write(node.as_bytes());
h.finish()
})
.unwrap()
}对每个 (key, node) 组合算一个哈希,取最大的那个节点。 它天然均匀(不需要虚拟节点),扩容影响也是 1/N。
代价是查询复杂度是 O(N)(要对所有节点算哈希),而一致性哈希是 O(log n)。所以:
- 节点数少(< 100)→ Rendezvous 更简单
- 节点数多、查询频繁 → 一致性哈希
Rendezvous 的存在提醒我们:一致性哈希不是唯一解。 选方案时要看"节点规模"和"查询频率"这两个变量。
现实中的坑
1. 节点下线要"优雅"。 直接 remove_node 会让它的数据瞬间压给邻居。生产做法是先把该节点的数据迁移走,再从环上摘除。
2. 环的状态需要一致。 每个客户端都要有相同的环视图,否则同一个 key 会被路由到不同节点。所以环的变更需要走配置中心分发,并且要有版本号。
3. 数据迁移要幂等。 迁移过程中会重试,接收方必须能处理"同一份数据收到两次"。
4. 热点 key 打不散。 一致性哈希只解决"节点间均衡",不解决"单个 key 过热"。一个千万 QPS 的 key 无论落在哪都会打爆那台机器——这需要本地缓存或者 key 拆分(key#0、key#1)来解决。
结论
一致性哈希的核心是两个递进的问题:
第一层:取模分片在扩容时几乎全量迁移 → 用哈希环把迁移降到 1/N。 第二层:环上节点分布不均导致倾斜 → 用虚拟节点(
node#i)把每个物理节点打散成上百个点。
再加上三个必须写对的工程细节:多副本要按物理节点去重;虚拟节点数要按集群规模调整;哈希函数要做低位混合。
理解了这些,你再看 Redis Cluster 的 16384 个槽、Cassandra 的 vnode、Envoy 的 ring hash——它们都是同一个环,只是虚拟节点叫法不同。