数据放置：一致性哈希、CRUSH 与 Weka bucket

一个不能靠查表回答的问题

「对象 X 在哪个节点上」—— 最直觉的答案是建一张大表,每个对象记一行。 你运维过的系统里没有一个这么干,原因你也清楚:十亿对象的表本身就是个存储系统, 每次读写都先查它一次,它成了单点和瓶颈。Ceph 的答案是 CRUSH:位置不存,现场算, 客户端拿着 osdmap 自己算出对象在哪,不问任何人。

所以放置问题的本质是设计一个确定性函数:输入对象 key 和集群视图,输出节点列表。 好函数要同时满足四条,缺一条都会在生产上还债:

1. 确定性:任何节点、任何时刻,算同一个 key 结果一致 —— 否则读写找不到对方
2. 均匀:对象和容量按权重摊开,不能有热点节点
3. 最小搬迁:加减一个节点,只搬理论最小量的数据 —— 这是三大流派真正的分水岭
4. 故障域约束:一个对象的多个副本/分片,必须落在不同故障域

一致性哈希与虚拟节点

先看反面教材:hash(key) mod N。N 从 5 变 6 时,一个 key 的新位置和旧位置相同的 概率只有约六分之一 —— 超过 80% 的数据要搬家,扩容一次等于重灌一次集群。

一致性哈希把「mod N」换成「环上找后继」:把哈希空间想成一个环,节点哈希到环上, 对象顺时针找到的第一个节点就是归宿。加入新节点只切走后继节点的一段区间: 5 节点变 6 节点,理论搬迁量约六分之一 —— 正好是最小值(新节点应得的份额)。

裸环有个大坑:5 个节点只在环上占 5 个点,区间长度全凭运气,实测负载差能到正负 50%。 解法是虚拟节点:每个物理节点在环上放 150 个点,大数定律把方差抹平, 负载偏差收敛到几个百分点以内;权重也顺手解决了 —— 8TB 的节点放 300 个点,4TB 的放 150 个。

use std::collections::BTreeMap;

pub struct HashRing {
    /// 环:哈希值 → 物理节点 ID。BTreeMap 的 range 查询就是"顺时针找后继"
    ring: BTreeMap<u64, String>,
    vnodes_per_weight: u32, // 每单位权重的虚拟节点数,forge 取 150
}

impl HashRing {
    pub fn add_node(&mut self, node_id: &str, weight: u32) {
        for i in 0..weight * self.vnodes_per_weight {
            let point = hash64(format!("{node_id}:{i}").as_bytes());
            self.ring.insert(point, node_id.to_string());
        }
    }

    /// 从 key 的哈希点开始顺时针取 n 个互不相同的物理节点
    pub fn pick(&self, key: &[u8], n: usize) -> Vec<String> {
        let start = hash64(key);
        let mut picked = Vec::with_capacity(n);
        // 环上从 start 往后遍历,跨过尾部回到头部;跳过已选中的物理节点
        for (_, node) in self.ring.range(start..).chain(self.ring.range(..start)) {
            if !picked.contains(node) {
                picked.push(node.clone());
                if picked.len() == n {
                    break;
                }
            }
        }
        picked
    }
}

注意 pick 里的「跳过重复物理节点」:这就是最朴素的故障域约束 —— 同一个对象的 6 个 EC 分片不能有两个落在同一节点。要按机架约束,把跳过条件换成机架即可。

CRUSH 回顾:从运维视角到实现视角

你对 CRUSH 的运维记忆大概是:crush map、bucket 树、step chooseleaf firstn 0 type host、 以及改 weight 引发的搬迁。换到实现视角,CRUSH 本质是带层级约束的加权哈希选择: 把故障域组织成一棵树(root → rack → host → osd),每选一个副本就从树根往下走, 每层用伪随机函数(straw2)按权重抽签,「不同副本走不同子树」这条约束在下降过程中强制执行。

和哈希环比,CRUSH 的强项和你踩过的坑各一条:

• 强项:故障域是一等公民。哈希环要靠 pick 时跳过,约束复杂(机架 + 主机两级)时环的 代码会越来越丑;CRUSH 的树结构天然表达任意层级
• 坑:搬迁量并非总是最优。你调过 weight 之后看着 misplaced 比例远超预期 —— straw2 已经比早期算法好很多,但树形抽签在拓扑变化时仍可能牵连无辜的对象

还有一条你熟的中间层:Ceph 不直接放对象,而是 对象 → PG → OSD 两级映射, PG 才是搬迁和对账的单位。记住这个思想,马上要用。

Weka 的答案:两级映射,小表走共识

Weka 把「现场算」和「查表」调和了:元数据空间哈希成 64k 个 bucket(纯哈希,永不变), bucket 到节点的归属是一张只有 64k 行的小表,由集群共识层管理。对象层面是算的, 归属层面是查表的 —— 表小到可以走共识协议,每次变更全集群原子生效,搬迁单位是整个 bucket, 可控可观测。这和 Ceph 的 PG 是同一个思想,只是 Weka 把粒度切得更细、表管得更严。

forge 采纳同款设计,数据面和元数据面统一用slot 表:

• key 哈希到 256 个 slot(固定,永不变;规模再大可以扩到 4096,思想不变)
• slot → 节点列表的表由 Raft 管理(下下课兑现),带版本号 cluster_epoch
• 初始分配用上面的哈希环生成(继承均匀性),此后的每次变更都是显式的表更新 —— 加节点时由再平衡逻辑挑选搬迁代价最小的 slot 挪过去

这样三大流派各取所长:哈希环给初始分布,CRUSH 的故障域思想放进 slot 分配约束, Weka 的小表共识给变更以原子性和可审计性 —— 你以后排查「这个对象为什么在这」时, 答案是一行可以 git blame 式追溯的表记录,而不是一个黑盒函数。

动手:模拟加减节点,统计搬迁量

放置算法的验收不用起集群,写个模拟器就行 —— 一百万个 key,各方案算一遍, 数一数变更前后位置不同的 key 有多少。你应该复现出这样的数量级:

裸环和虚拟节点环的搬迁比例接近,差别全在第三行:均匀性才是虚拟节点解决的问题。

在 forge-cluster crate 里实现放置层,分三块:

1. placement::HashRing:虚拟节点一致性哈希环,add_node(node_id, weight)、remove_node、pick(key, n) 返回 n 个互不相同的物理节点;哈希用 xxhash-rust 的 xxh3_64;每单位权重 150 个虚拟节点;
2. placement::SlotTable:256 个 slot 的放置表,字段含 slot 到节点列表的映射和 cluster_epoch(u64);提供 from_ring(ring, replicas) 用哈希环生成初始分配,以及 locate(key) 先 xxh3 哈希到 slot 再查表;slot 内节点列表必须物理节点互不相同;
3. examples/migration_sim.rs:模拟器,100 万个随机 key,对比三种方案(mod N、裸环、150 虚拟节点环)在 5 加 1 节点和 5 减 1 节点两种变更下的:搬迁 key 比例、变更后各节点负载的最大最小比。输出一张对齐的文本表格。

单元测试:pick 返回的节点互不相同;同一 key 反复 pick 结果稳定;SlotTable::locate 与表内容一致。生产路径不许 unwrap。跑 cargo test -p forge-cluster 和模拟器,把表格贴给我。

小结

• 放置的本质:确定性函数替代大表,四条标准 —— 确定、均匀、最小搬迁、故障域
• mod N 扩容搬 83%,一致性哈希只搬六分之一;虚拟节点解决的不是搬迁而是均匀性
• CRUSH 用层级树把故障域做成一等公民,代价是拓扑变化时搬迁量不总是最优
• Weka 式两级映射是 forge 的选择:海量 key 哈希到 256 个 slot,slot 表小到可以走 Raft
• 表在哪、谁改、怎么保证所有人看到同一份 —— 这个坑留给 Raft 课;下一课先把数据保护做出来