复制与纠删码

三笔账:你在采购评审上算过的

副本还是 EC,你运维时替公司算过这笔账,现在换到设计者座位上重算一遍。 以「可用容量 100TiB、容忍任意 2 个故障域失效」为口径:

前两行是 EC 赢:容量减半,写带宽减半。最后关键的一行是 EC 输: 重建读放大 4 倍 —— 这就是你亲历过的「EC 池重建比副本池猛得多」的数学根源, 一块盘挂掉,恢复它 10TiB 的数据要从别的盘读 40TiB。重建限速在 L4 专门处理, 这节课先把编解码本身做对。

RS 码的直觉:多项式插值,不用推公式

Reed-Solomon 听起来吓人,直觉却是初中几何:两点确定一条直线。 知道直线上任意两点,整条线就能画出来 —— 丢掉哪两个点都无所谓,只要还剩两个。

推广一步:4 个点确定一条三次曲线。把 4 个数据分片看作曲线上的 4 个点, 再在曲线上多取 2 个点当校验分片 —— 现在曲线上有 6 个点,任取 4 个都能还原整条曲线, 也就是任意丢 2 个分片都能算回来。这就是 4+2 的全部原理。

工程上有一个替换:普通算术里"多取的点"会越算越大、有精度问题, 所以实际运算在有限域(GF 256)上做 —— 一个 256 个元素的封闭算术系统, 加法恰好是 XOR,乘法查表,每个字节独立运算。你不需要会推, 但要记住结论:编解码是纯 CPU 计算,现代实现用 SIMD 指令并行处理,速度以 GB/s 计。

reed-solomon-erasure 实战:encode / reconstruct

forge-cluster 里加 ec 模块,用 reed-solomon-erasure crate:

use reed_solomon_erasure::galois_8::ReedSolomon;

pub const DATA_SHARDS: usize = 4;
pub const PARITY_SHARDS: usize = 2;

pub struct StripeCodec {
    rs: ReedSolomon,
}

impl StripeCodec {
    pub fn new() -> Result<Self, EcError> {
        Ok(Self { rs: ReedSolomon::new(DATA_SHARDS, PARITY_SHARDS)? })
    }

    /// 把一段数据编码成 6 个等长分片(不足 4 等分则补零,原始长度另记)
    pub fn encode(&self, data: &[u8]) -> Result<Vec<Vec<u8>>, EcError> {
        let shard_len = data.len().div_ceil(DATA_SHARDS);
        let mut shards: Vec<Vec<u8>> = Vec::with_capacity(DATA_SHARDS + PARITY_SHARDS);
        for i in 0..DATA_SHARDS {
            let start = (i * shard_len).min(data.len());
            let end = ((i + 1) * shard_len).min(data.len());
            let mut shard = data[start..end].to_vec();
            shard.resize(shard_len, 0); // 补零到等长
            shards.push(shard);
        }
        shards.push(vec![0u8; shard_len]); // 校验片 1
        shards.push(vec![0u8; shard_len]); // 校验片 2
        self.rs.encode(&mut shards)?;      // 原地算出两个校验片
        Ok(shards)
    }

    /// 缺失分片置 None,reconstruct 原地补齐;缺 3 个及以上返回 Err
    pub fn reconstruct(
        &self,
        shards: &mut [Option<Vec<u8>>],
    ) -> Result<(), EcError> {
        self.rs.reconstruct(shards)?;
        Ok(())
    }
}

两个必须逐行读懂的点(落盘红线的分布式延伸):

1. 原始长度要另外记。补零后的分片解码回来是 4 × shard_len 字节, 多出来的零必须按记录的原始长度截掉 —— 这个长度存进条带元数据,和 crc 一起
2. 每个分片落盘前单独算 crc32c。EC 能对付「分片没了」,对付不了「分片在但内容是脏的」—— 静默损坏的分片参与解码,会把错误扩散到重建结果里。先用 crc 把脏分片降级成缺失分片 (置 None),再交给 reconstruct,这是两套机制的正确分工

条带布局:stripe、chunk、故障域约束

名词钉死,后面几课都按这套用:对象切成条带(stripe),每个条带编码出 6 个 分片(chunk),分片是放置和落盘的最小单位。两个尺寸决策:

• 分片大小 256KiB,条带就是 4 × 256KiB = 1MiB 数据加 512KiB 校验。太小则 RPC 次数和元数据条目暴涨;太大则小对象浪费和重建粒度变粗。256KiB 也和 L2 测出的 NVMe 大块顺序写甜点区对齐
• 6 个分片必须落 6 个不同故障域 —— 上一课 SlotTable 的节点列表约束在这里兑现。 4+2 容忍任意 2 个故障域同时失效;两个分片挤在同一故障域,那个域一挂等于同时丢 2 片, 容错立刻见底

写路径把这些串起来:客户端(或代理节点)编码出 6 片,并行发往 6 个目标, 收齐 6 个确认才算成功 —— 先收齐 4+1 就返回的"优化"留给你思考:它把容错悄悄降到了 1。

小写问题:为什么 Weka 要攒满条带再落盘

EC 最疼的不是重建,是小写。改写条带里的 4KiB,不能只写那 4KiB: 两个校验片依赖全部 4 个数据片,于是要读旧数据片、读旧校验片、算增量、写回 1 数据片 加 2 校验片 —— 一次 4KiB 的逻辑写,变成约 3 次读加 3 次写的物理 IO, 外加"读-算-写"期间的条带锁。这就是你运维 Ceph EC 池时「4k 随机写惨不忍睹」的机制原因, 也是很多系统干脆规定 EC 池只许追加的原因。

Weka 的解法你在 L1 已经亲手写过一半了:一切皆追加。小写先以日志形式落盘 (小块数据用副本或小条带保护,持久性立刻成立),后台把攒够 1MiB 的数据聚合成满条带、 EC 编码、整条写入 —— 满条带写不需要读旧数据,读改写惩罚彻底消失。 这是 Bitcask 思想在分布式层的重演:L1 的引擎里你用追加日志消灭了原地改写, Weka 用同一招消灭了 EC 读改写。

forge 在 L3 阶段走捷径:对象存储的 put 是整对象写入,天然凑成满条带, 小写问题暂时不存在。到 L4 做文件系统、必须支持改写文件中间 4KiB 时, 日志聚合逻辑才真正登场 —— 但你现在就要在条带元数据里给它留好位置(版本号字段)。

在 forge-cluster crate 里实现 ec 模块,基于 reed-solomon-erasure crate(galois_8):

1. StripeCodec:new() 建 4+2 编码器;encode(data) 把任意长度数据切 4 等份补零、算 2 个校验片,返回 6 个等长分片;decode(shards, original_len) 接收 6 个 Option 分片(缺失为 None),重建后拼回原始数据并按 original_len 截断补零;
2. 每个分片配套 ShardMeta 结构:stripe_id、chunk_index、crc32c、original_len、stripe_version(u32,L4 的小写聚合预留,现在恒为 0);提供 verify(shard, meta) 校验 crc;
3. 单元测试:任意丢 0/1/2 个分片都能精确还原原始数据(包括长度不是 4 整数倍、以及空数据、单字节两个边界);丢 3 个分片必须返回 Err;
4. property test(用 proptest):随机长度 0 到 4MiB 的数据、随机丢 2 片,encode 再 decode 恒等于原数据;
5. criterion bench:1MiB 条带的 encode 与"丢 2 片 reconstruct"的吞吐,输出 GB/s。

生产路径不许 unwrap。跑 cargo test -p forge-cluster,贴测试结果和 bench 数字。

小结

• 三笔账:EC 容量和写带宽占优(1.5 倍对 3.0 倍),重建读放大 4 倍是它的原罪 —— 重建风暴的数学根源
• RS 的直觉是多项式插值:6 点定一条曲线,任取 4 点可还原;运算在有限域上,SIMD 下 GB/s 级
• EC 只管"缺失",不管"脏数据":每个分片独立 crc32c,先把脏片降级成缺失片再解码
• 条带 1MiB、分片 256KiB、6 片 6 个故障域;收齐 6 个确认才算写成功
• 小写的读改写惩罚用"追加 + 攒满条带"消灭 —— Bitcask 思想的分布式重演,L4 兑现
• 数据保护齐了,但 6 片落到哪 6 个节点,这张表由谁说了算?下一课:Raft