返回文章列表

用 Rust 从零实现一致性哈希:虚拟节点解决的是什么问题

523 字·4 分钟阅读
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

规则很简单:

  1. 把哈希值空间看成一个环(比如 0..2^64,首尾相接)
  2. 每个节点算出哈希值,落在环上
  3. 每个 key 算出哈希值,也落在环上
  4. 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——它们都是同一个环,只是虚拟节点叫法不同。