经典算法深度解析｜纠删码（源码篇）：最小 RS encoder/decoder 与 read-modify-write 伪代码

前面的几篇文章，已经把纠删码讲到了实现层：

为什么它在数学上成立
为什么它在系统上会贵
为什么不同系统会做出不同取舍
为什么实现里会被 GF 运算、SIMD、full-stripe write 和 partial write 卡住

但很多工程师真正卡住的位置，其实还要再往下一层。

不是概念不会，而是：

代码到底该怎么组织
最小 encoder 长什么样
decoder 真正输入输出是什么
缺块恢复时矩阵是怎么选出来的
read-modify-write 更新时，旧数据、旧校验和新数据到底怎么串起来

所以这篇文章的目标很明确：

不给你一份工业级库实现，而是给你一份“足够接近源码的思维骨架”。

也就是说，读完之后你至少应该能做到：

自己写一个最小 RS encoder
理解 decoder 的矩阵恢复流程
看懂大多数 EC 库里 encode / reconstruct / update 的主路径
知道 partial write 为什么天然会把你拉回 read-modify-write

先把系列文章列出来：

1. 先定边界：这一篇不追求工业级完整性，追求“最小可理解实现”

真实生产库通常还会有很多附加维度：

SIMD 优化
表预计算
对齐与批处理
并行恢复
崩溃恢复一致性

这些前一篇已经讨论过。

这篇先故意把问题收窄，只保留最核心骨架：

数据按字节块组织
用系统化 RS 做 k+m
给出编码和恢复的矩阵流程
给出 partial write 的 read-modify-write 伪代码

这样你看到的不是“最快的代码”，而是“最适合长在脑子里的代码框架”。

2. 先定义几个最基本的数据结构

一个最小实现里，通常至少要有这些概念：

Field
    gf_add(a, b)
    gf_mul(a, b)
    gf_inv(a)

Matrix
    rows, cols
    data[rows][cols]

Stripe
    data_blocks[k][]byte
    parity_blocks[m][]byte

Codec
    k, m
    generator_matrix[(k+m) x k]

这里最关键的是最后两个：

Stripe 是一次编码/恢复的最小数据单元
Codec 持有当前 k+m 参数和生成矩阵

系统化 RS 的好处在这里就很明显：

前 k 行是单位矩阵
所以前 k 个输出块就是原始数据块
后 m 行才是真正的 parity 生成规则

3. 生成矩阵在代码里怎么表示

假设我们做一个 4+2 码，生成矩阵仍然可以写成：

G =
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[a b c d]
[e f g h]

在代码里，你完全可以先把它存成一个二维字节数组：

generator[6][4]

其中：

generator[0..3] 是数据块的 identity 行
generator[4] 生成 P0
generator[5] 生成 P1

如果你是自己写最小版本，前期完全没必要一上来就做复杂抽象。一个清楚的二维数组就够用。

4. 最小 encoder 的核心循环长什么样

对于系统化 RS，encoder 要做的事情非常直接：

数据块直接保留
按生成矩阵的 parity 行逐个生成校验块

一个最小伪代码可以写成：

function encode(data_blocks[0..k-1], generator, k, m):
    block_len = len(data_blocks[0])
    parity_blocks = new byte[m][block_len]

    for p in 0..m-1:
        row = generator[k + p]
        for i in 0..block_len-1:
            acc = 0
            for d in 0..k-1:
                acc = gf_add(acc, gf_mul(row[d], data_blocks[d][i]))
            parity_blocks[p][i] = acc

    return parity_blocks

这段代码虽然朴素，但已经把核心说全了：

最外层按 parity block 生成
中间层按块内字节位置遍历
最内层按所有 data block 做线性组合

你完全可以把这看成“矩阵乘法的展开版”。

5. 为什么工业实现不会直接这么写

因为上面的代码虽然正确，但有几个明显问题：

gf_mul 调用太频繁
cache locality 不够好
没有向量化
对多个 parity block 的共享计算没有尽量批处理

所以高性能库通常会在这个骨架上做这些事情：

系数预处理
查表或 nibble table
一次同时生成多个 parity block
块内按更大向量宽度批处理

但注意：

工业实现再怎么优化，也还是这个三层循环的变体。

理解这一点非常重要，因为它能帮你在读优化代码时不迷路。

6. decoder 真正要解决的问题是什么

encoder 很直接，decoder 则复杂得多。

因为编码时你知道完整数据，恢复时你面对的是：

某些块丢了
某些块还在
你要从幸存块里选出足够多的 k 个块
再把原始数据解出来

所以 decoder 的本质问题是：

从幸存块对应的生成矩阵行里，构造一个可逆子矩阵，然后反推原始数据。

7. 最小 decoder 的数据流是什么

假设一个 4+2 的 stripe 丢了 D1 和 P0，还剩：

D0  D2  D3  P1

这时恢复过程可以拆成下面几步：

记录哪些块幸存
从生成矩阵里取出这些幸存块对应的 4 行
组成一个 4x4 子矩阵 A
求 A^-1
用 A^-1 乘以幸存块向量，恢复出原始 D0..D3

示意如下：

survivor blocks  --->  survivor rows from G  --->  invert submatrix  --->  recover data

这个流程一旦想明白，你再看任何 RS reconstruct 代码，都会顺很多。

8. 最小 decoder 伪代码

可以先写成非常直接的形式：

function decode(survivor_indexes, survivor_blocks, generator, k):
    A = pick_rows(generator, survivor_indexes)   # k x k
    A_inv = invert_matrix(A)

    block_len = len(survivor_blocks[0])
    recovered_data = new byte[k][block_len]

    for out in 0..k-1:
        for i in 0..block_len-1:
            acc = 0
            for s in 0..k-1:
                acc = gf_add(acc, gf_mul(A_inv[out][s], survivor_blocks[s][i]))
            recovered_data[out][i] = acc

    return recovered_data

这里最重要的是理解矩阵意义：

A 表示“当前幸存块和原始数据之间的线性关系”
A_inv 表示“如何把当前幸存块重新映射回原始数据”

只要这一层想清楚，剩下就只是实现细节。

9. 为什么很多库的 reconstruct 不一定先恢复全部数据块

上面的最小 decoder 是“先恢复完整原数据向量”。

这在理解上很干净，但并不总是最高效。

现实里如果你只缺 D1，更高效的做法常常是：

直接构造恢复缺块所需的恢复系数
只计算目标块
不把整个 D0..D(k-1) 都完整求出来

也就是说，工业实现常常会区分：

恢复整个原始数据向量
只恢复目标缺块

但这不改变底层本质，它只是把“求全量解”优化成“求目标投影”。

10. `invert_matrix()` 为什么是实现里的一个逻辑拐点

很多人第一次自己写 decoder，会在矩阵求逆这里卡住。

这完全正常。

因为前面的 encode 更像规则循环，这里则突然变成了线性代数操作。

最小版本里，你完全可以用高斯消元：

function invert_matrix(A):
    augmented = [A | I]
    perform Gaussian elimination over GF(2^8)
    return right_half(augmented)

注意两点：

所有加减乘除都在有限域里做
普通整数除法在这里是错的，必须用域上的逆元

这也是为什么很多初学者明明觉得“流程都懂了”，代码还是跑不对。问题通常就在这里。

11. read-modify-write 到底该怎么写成伪代码

前一篇实现篇已经讲过概念，这一篇把它压成更像代码的形式。

假设：

一个 partial write 只更新某个数据块的局部范围
受影响的 parity block 一共有 m 个

那么一个最小 read-modify-write 路径可以写成：

function update_partial(data_block_id, offset, old_data_slice, new_data_slice,
                        old_parity_slices[0..m-1], parity_coeffs[0..m-1]):

    delta = xor_bytes(old_data_slice, new_data_slice)

    for p in 0..m-1:
        coeff = parity_coeffs[p][data_block_id]
        encoded_delta = gf_mul_bytes(coeff, delta)
        old_parity_slices[p] = xor_bytes(old_parity_slices[p], encoded_delta)

    write_new_data(data_block_id, offset, new_data_slice)
    write_updated_parities(old_parity_slices)

这段伪代码其实在表达一个关键事实：

parity 不需要从头全量重算
它可以根据“旧数据和新数据的差量”做增量更新

这就是 read-modify-write 成立的核心。

12. 为什么 `delta` 这件事这么关键

很多人第一次看 partial write 更新，会下意识想：

新数据来了
那就拿新数据重新算 parity

但这往往意味着你得读更多东西。

而引入 delta = old XOR new 之后，更新思路就变成了：

旧 parity 表示旧数据的线性组合
新 parity 只是在旧 parity 基础上叠加对应差量

写成抽象式子就是：

new_parity = old_parity + coeff * delta

这里的 + 仍然是 GF 加法，通常也就是 XOR。

这套思路非常重要，因为它决定了 partial write 不必每次都退化成 full reconstruct。

13. 但 read-modify-write 为什么依然不轻松

因为上面的伪代码其实把很多真正麻烦的问题折叠掉了。

真实系统里你还得继续解决：

old_data_slice 从哪里读
old_parity_slices 从哪里读
多个并发 partial write 是否会打到同一组 parity
数据块和 parity 块的写回顺序如何保证一致性
写回一半宕机了怎么办

这也解释了为什么很多工程师第一次看 read-modify-write，会觉得公式不难，但路径很脏。

因为它本质上已经不是“纯编码算法”，而是“编码算法 + 并发更新协议”。

14. 一个更接近真实系统的写路径骨架

如果把 partial write 放进真实系统，一条更完整的数据流通常像这样：

client write
    -> locate stripe and target block
    -> lock or serialize conflicting updates
    -> read old data slice
    -> read old parity slices
    -> compute delta
    -> update parity slices
    -> persist data and parity with ordering / logging
    -> release lock

这条路径一写出来，你就能直接看见 EC 覆盖写为什么总是比副本更麻烦：

它需要更多旧状态
它需要更新更多对象
它需要更严肃的一致性顺序

所以很多系统宁可通过：

append-only
后台 compaction
stripe 聚合
delayed encoding

来尽量躲开这条路径。

15. 如果你真的准备自己写一个最小 EC demo，推荐顺序是什么

如果你要把这一篇变成实际代码，我会建议按这个顺序推进。

15.1 第一步：先写一个可验证的 GF 层

至少要有：

gf_add
gf_mul
gf_inv

先用小样例验证闭包和逆元逻辑。

15.2 第二步：写最小 encoder

先不做 SIMD，不做查表，不做多线程。

只要能把 k 个 data block 编出 m 个 parity block，就已经够用。

15.3 第三步：写矩阵求逆和最小 decoder

这一步是整个 demo 的逻辑拐点。

15.4 第四步：做故障注入测试

例如：

任意删 1 块
任意删 2 块
看能否恢复

15.5 第五步：再补 partial write 更新路径

先做最简单的单线程 read-modify-write。

只有在这一步走通以后，再去谈并发、日志和性能优化才不容易乱。

16. 读源码时最值得盯住哪几个函数

如果你接下来要去看某个 EC 库的真实源码，我最建议优先盯住这几类函数：

encode 或 encode_data
reconstruct / decode
invert_matrix / gaussian_elimination
update / partial_write / rmw
初始化阶段的矩阵或表预处理函数

原因很简单。

这几类函数几乎正好对应我们这篇文章拆出来的五条主线：

编码
恢复
矩阵变换
增量更新
热路径准备

一旦这五条线在脑子里连上，真实工业代码虽然更复杂，但就不再显得神秘。

17. 这一篇最该记住的结论

把源码篇压缩一下，真正重要的结论其实是这些：

最小 encoder 本质上就是生成矩阵乘以数据向量的展开循环
decoder 的核心是从幸存块对应行构造可逆子矩阵，再反推原始数据
partial write 的核心不是“重算全部 parity”，而是基于 delta 做增量更新
read-modify-write 一旦落到真实系统，就会迅速和并发控制、一致性顺序耦合在一起
工业实现再复杂，也仍然是这些骨架的优化版，而不是另一套完全不同的东西

如果这些点想明白了，你再去看 ISA-L、Jerasure 或某个分布式存储的 EC 写路径，通常都会轻松很多。

18. 到这里，这一组 EC 文章基本形成了完整教学链路

现在这一组已经从：

原理
代价
工程落地
真实系统取舍
实现热点
源码骨架

一路串起来了。

如果只学前两篇，你得到的是“知道 EC 是什么”。

如果连这一篇也看完，你通常已经能做到另一件更重要的事：

把 EC 从一个抽象名词，真正还原成一组能落进代码、数据流和恢复路径的结构。

这时再回头看三副本、RS、LRC、Ceph、HDFS、Azure LRC，你通常会更容易判断：

它们各自在优化什么
它们各自在回避什么
为什么同样叫 EC，工程难点却完全不一样

这也是这一组文章真正想完成的事。

如果继续往前推进，下一层最值得单独拿出来讲的，通常就是性能调优本身：

benchmark 应该怎么设计才不自欺欺人
NUMA 和线程模型为什么会决定吞吐上限
repair 为什么一定要限流，限流又该放在哪一层

这些问题我放到下一篇性能篇里展开：

它通常不是单点热点优化，而是算术、内存、线程、NUMA、网络和后台恢复之间的联动问题。

所以这一篇专门讲这件事。

系列文章如下：

1. 先说结论：很多 EC 性能问题，其实是测错了，不是写慢了

这是最常见也最误导人的问题。

很多 benchmark 只测：

单线程 encode
热 cache 下的大块顺序数据
纯内存路径

然后得出一个结论：

这个实现每秒能跑多少 GB，所以系统性能应该没问题。

这类结论通常不够用。

因为真实系统里，你真正关心的往往是：

full-stripe write 吞吐
partial write 延迟
degrade read 尾延迟
repair 打开后前台业务会掉多少性能
多线程情况下是否被 NUMA 和内存带宽卡住

所以第一原则不是“先优化”，而是：

先确认你测到的是不是你真正要优化的那条路径。

2. benchmark 至少要分三层

一个相对靠谱的 EC 性能分析，通常至少要把测试拆成三层。

2.1 算法核 benchmark

也就是最纯的一层：

encode 吞吐
decode 吞吐
GF 运算核函数速度

这层适合回答：

SIMD 是否有效
查表方案谁更快
不同库之间核函数差距多大

2.2 路径 benchmark

也就是把它放回典型数据路径：

full-stripe write
partial write
degrade read
single-block repair

这层适合回答：

read-modify-write 到底有多贵
partial write 占比一高会不会直接拖垮延迟
repair 的真实读取放大是多少

2.3 系统 benchmark

也就是让它和真实资源争用一起出现：

多线程混跑
网络与磁盘参与
repair 与前台业务并发
缓存冷热切换

这层适合回答的才是：

上线后整体体验会怎样
是否需要额外限流
CPU、内存、网络谁是主瓶颈

如果只做第一层，通常只能说明你的核函数不错，说明不了系统不会出问题。

3. 为什么 EC 特别容易被内存带宽卡住

很多人第一次优化 EC，会先觉得它是算术密集型任务。

但一旦 SIMD 和查表都做起来，瓶颈往往很快转向内存。

原因不复杂。

一个 EC 编码过程本质上就是：

持续扫描多个 data block
对每个字节位置做规则运算
把结果写进 parity block

这意味着：

读流量非常稳定
写流量也不小
访问模式虽然规则，但数据量大

于是当计算核足够快时，真正限制吞吐的经常是：

L1/L2/L3 cache 命中率
memory channel 带宽
NUMA 跨节点访问
写回压力

这就是为什么某些实现再怎么优化 gf_mul，最终整体吞吐也上不去。因为它早就不是算术瓶颈了。

4. NUMA 为什么在 EC 场景里尤其重要

只要你的机器有多个 NUMA node，EC 的吞吐和延迟表现就很容易受影响。

4.1 问题出在哪里

如果线程跑在 NUMA node 0，但它处理的数据页主要分配在 NUMA node 1，那么：

每次读取都要跨 node
延迟变高
可用带宽下降
多线程时争用更严重

对 EC 这种持续扫大块内存的数据平面任务来说，这个代价会被不断放大。

4.2 这意味着什么

如果你要认真测 EC 性能，至少要关心：

线程绑核
内存首次分配在哪个 NUMA node
数据 buffer 是否按 worker 局部化
repair 线程和前台线程是否抢同一 NUMA node

如果不看这些，benchmark 结果往往会很飘。

5. 线程模型为什么不只是“开更多线程”

EC 很适合并行，但并行不等于无限堆线程。

5.1 太少线程的问题

CPU 跑不满
多核优势浪费
repair 恢复时间偏长

5.2 太多线程的问题

cache 抖动
内存带宽争用
上下文切换
锁竞争
前台和后台任务互相打架

这说明线程模型真正要优化的是：

任务粒度和资源局部性，而不是线程数本身。

很多时候更靠谱的设计是：

固定 worker 池
每个 worker 处理较大、较完整的 stripe 任务
尽量减少跨 worker 共享状态
repair 和前台写使用不同优先级队列

6. 批处理粒度为什么会直接改变吞吐曲线

如果任务切得太小，EC 性能通常会急剧恶化。

因为小任务会放大很多固定成本：

函数调用
queue 开销
buffer 管理
cache warmup
同步与调度成本

这也是为什么很多系统会刻意：

聚合写入
合并 repair 小任务
用更大的 stripe chunk 做批处理

它们不是只为了编码更省事，也是为了让性能曲线别在小粒度下直接塌掉。

7. degrade read 为什么特别容易拉高尾延迟

degrade read 的平均值有时还可以，但它很容易把 P99 和 P999 拉高。

原因是它通常要同时依赖：

多个远端块读取
一次解码
最慢副本返回时间

这意味着一次降级读的尾延迟往往接近：

多个远端读取里的最慢者
再加上本地 decode 时间

如果某个源节点抖一下，你的延迟就会被直接放大。

所以性能调优里一个很关键的问题不是“平均降级读耗时”，而是：

降级读在高并发和节点抖动下的尾部表现到底有多差。

8. repair 为什么一定要限流

这是 EC 生产调优里最关键的一条，没有之一。

如果 repair 不限流，它极容易出现下面的连锁反应：

大量拉取幸存块
占满东西向网络
幸存节点读 IO 飙高
前台读写延迟上升
前台变慢又让 repair 更难完成

这本质上就是一个负反馈被反向放大的过程。

所以成熟系统几乎都会做 repair 节流。

问题不是“要不要限”，而是“限在哪一层”。

9. repair 限流可以放在哪几层

比较常见的节流层包括：

任务层：同时允许多少 repair task 并发
节点层：单个源节点/目标节点最多承受多少 repair IO
网络层：跨机架或跨可用区 repair 带宽上限
时间层：业务高峰期自动降速
优先级层：危险条带先修，低风险条带后修

如果这些层次都没有，repair 很容易从“恢复系统”变成“拖垮系统”。

10. 为什么前台路径和 repair 路径最好分开看

很多调优失误来自一个错误假设：

既然 repair 也要 encode/decode
那前台和后台用同一套线程池、同一套资源配额应该就行

现实里这往往不够。

因为两者目标完全不同：

前台路径关心低延迟和稳定尾部
repair 路径关心可持续吞吐和不要打穿前台

所以更合理的做法通常是：

分队列
分优先级
分资源上限
在必要时甚至分 NUMA 局部性或 CPU 集合

这不是过度设计，而是因为两条路径的优化目标本来就不同。

11. benchmark 里最值得单独记录的指标是什么

如果只能挑一批最值钱的指标，我会优先看这些：

encode 吞吐
decode 吞吐
full-stripe write 吞吐
partial write P50 / P99
degrade read P50 / P99
repair 读取放大量
单节点 repair 输入/输出带宽
CPU 利用率与 memory bandwidth 利用率
NUMA remote access 比例

这些指标凑在一起，才能帮助你回答：

慢在哪
慢得稳不稳
慢是算术问题、访存问题，还是后台争用问题

如果只看一个总吞吐数，信息量通常远远不够。

12. 为什么“CPU 还有空闲”不代表系统没到瓶颈

这是一个很容易误判的信号。

你可能看到：

CPU 使用率只有 50%
于是以为系统还有很多余量

但实际上，瓶颈可能已经在：

内存带宽
某个 NUMA node
网络 egress
某一批热点磁盘

这种情况下，CPU 空闲只说明“不是每个核都在算满”，不说明数据路径还有富余。

所以在 EC 调优里，单看 CPU 使用率往往会误导你。

13. 一条很实用的调优顺序

如果让我给一个比较稳的调优顺序，我通常会建议这样做：

先确认真实热点路径是 full-stripe、partial write、degrade read 还是 repair
再确认瓶颈主层是算术、内存、NUMA、网络还是后台争用
先修最粗颗粒的问题，比如 repair 不限流、线程模型混乱、任务太碎
再做核函数级优化，比如 SIMD、表布局、循环展开