经典算法深度解析｜纠删码（实现篇）：GF 运算、SIMD、full-stripe write 与小写更新路径

前面的几篇文章，已经把纠删码的三个主要层次搭起来了：

1. 数学上为什么可行
2. 系统上为什么会贵
3. 不同存储系统为什么会做出不同取舍

但如果你真的开始写代码、接库、做 benchmark，很快会发现另一层现实：

真正把 EC 跑快、跑稳、跑得可维护，难点往往不在公式，而在实现路径。

很多团队第一次做 EC 性能优化时，会先盯住一个点：

1. 生成矩阵怎么选
2. k+m 参数怎么配
3. LRC 还是 RS

这些当然重要。

但只要真正落到代码层，往往先暴露出来的是下面这些问题：

1. GF 乘法到底怎么实现
2. 查表和 SIMD 到底能带来多少收益
3. full-stripe write 为什么写起来舒服，partial write 为什么总在惹麻烦
4. read-modify-write 和 reconstruct-write 应该怎么选
5. 数据块在内存里该怎么排布，CPU 才不会被 cache miss 打穿
6. 性能瓶颈究竟在算力、内存带宽，还是网络与磁盘

所以这篇文章专门不讲系统选型，也不再重复 RS 的理论推导，而是从“一个工程师真正开始写 EC 实现”这个视角，往下拆实现层最关键的几件事。

先把整个系列列出来：

1. 纠删码（一）：从多副本到 Reed-Solomon、有限域与 MDS 本质
2. 纠删码（二）：故障恢复、更新放大、修复带宽与 LRC 演进
3. 纠删码（三）：条带布局、故障域、降级读与分布式存储里的工程落地
4. 纠删码（实战篇）：Ceph、HDFS 与 Azure LRC 的实现取舍
5. 纠删码（实现篇）：GF 运算、SIMD、full-stripe write 与小写更新路径
6. 纠删码（源码篇）：最小 RS encoder/decoder 与 read-modify-write 伪代码
7. 纠删码（性能篇）：benchmark、NUMA、线程模型与 repair 限流
8. 纠删码（案例排障篇）：repair 打满网络、degraded read 尾延迟飙升与 partial write 放大
9. 纠删码（架构选型篇）：什么时候该用三副本、RS、LRC，什么时候根本不该上 EC

1. 先说最容易误判的一点：EC 的性能问题，常常不是“乘法慢”这么简单

很多人第一次想到 EC 性能，会立刻想到有限域乘法。

这当然合理。

因为从直觉上看：

1. XOR 很便宜
2. GF 乘法比 XOR 复杂很多
3. 所以性能瓶颈应该主要在乘法

这在某些情况下没错，但并不完整。

真实实现里，EC 的性能通常同时受下面几层影响：

1. 算术层：GF 加法、乘法、逆元、矩阵变换
2. 指令层：SIMD 宽度、向量化效率、指令集支持
3. 内存层：块布局、cache locality、prefetch、写回压力
4. 调度层：线程切分、pipeline、NUMA、任务粒度
5. 系统层：网络、磁盘、对象切分和数据对齐

也就是说，EC 实现几乎总是一个“混合瓶颈”问题。

有时矩阵运算才是瓶颈。

有时其实是：

1. 访存太散
2. 小块太多
3. pipeline 太碎
4. 线程同步太重
5. 读旧校验块的远端 IO 太贵

所以实现层第一原则不是“先优化一个热点函数”，而是：

先搞清楚你到底是在做计算优化、内存优化，还是整条数据路径优化。

2. GF(2^8) 在实现里到底意味着什么

上一篇理论篇已经说过，RS 通常工作在 GF(2^8) 上。

到实现层，这句话的真正含义是：

1. 数据天然按字节处理
2. 每个字节位置都独立参与同一套线性组合
3. 对整个块的编码，本质上是在重复做“每个位置一遍相同系数运算”

如果一个数据块长度是 L 字节，一个 k+m 条带有 k 个数据块，那么生成一个校验块时，概念上是在做：

for i in 0..L-1:
    P[i] = a0*D0[i] + a1*D1[i] + ... + a(k-1)*D(k-1)[i]

这里：

1. + 往往就是 XOR
2. a*D[i] 是有限域乘法

从这个角度看，EC 编码其实很像一类高度规则的向量运算。

这也是它特别适合做：

1. 批处理
2. 向量化
3. 查表优化
4. pipeline 展开

但也正因为它是“对大块重复同一种模式”，只要块太小、调用太碎、内存太散，CPU 就很难真正跑起来。

3. GF 加法为什么几乎不是问题，GF 乘法为什么才是核心

在 GF(2^8) 中，加法通常等价于 XOR。

这对实现非常友好：

1. XOR 指令廉价
2. 易于向量化
3. 几乎没有数值稳定性问题

所以真正的重点通常在 GF 乘法。

3.1 为什么不能直接用普通整数乘法

因为有限域乘法不是普通的 a * b。

它需要：

1. 按域元素定义做乘法
2. 对不可约多项式取模
3. 保证结果仍落在 256 个域元素里

这意味着你不能把它简单理解为：

1. CPU 执行一个整型乘法
2. 再截断成 8 bit

那样结果是错的。

3.2 所以实现者最先面对的问题是什么

不是“数学对不对”，而是：

这个 GF 乘法我到底要怎么算才快？

常见路线大致有三种：

1. 按位算法
2. log/antilog 查表
3. 乘法表或拆分表

4. 按位算法为什么通常只是教学入口

最直接的 GF 乘法写法，是按位迭代：

1. 检查乘数当前位
2. 条件 XOR 到结果
3. 被乘数左移
4. 若溢出则按不可约多项式归约

它的优点是：

1. 容易理解
2. 方便验证正确性
3. 适合写 reference implementation

但它通常不是高性能生产路径。

原因很简单：

1. 分支多
2. 位级操作细碎
3. 很难和块级批处理形成高吞吐

所以在生产编码库里，按位算法更像“正确性基线”，而不是主力热路径。

5. 查表为什么是很多实现的第一层提速

GF 乘法的一个常见优化思路是查表。

5.1 log/antilog 表

如果把非零域元素表示成某个生成元的幂，那么：

a * b = exp(log(a) + log(b))

这样乘法就被转成：

1. 两次查表
2. 一次加法
3. 一次查表

这比按位算法通常要快得多。

5.2 预计算乘法表

另一条路更暴力：

1. 对每个系数 c
2. 预计算 mul[c][x]，表示 c * x
3. 编码时直接 P[i] ^= mul[c][D[i]]

这对 EC 特别有吸引力，因为在一个 stripe 内，生成矩阵的系数通常是固定的。

也就是说：

1. 你不会在每个字节位置重新发明系数
2. 你是在大量重复“同一个系数乘以不同数据字节”

所以“为固定系数预计算表”这件事非常划算。

5.3 查表的代价是什么

它不是没有成本。

查表会带来：

1. 更多内存访问
2. cache 压力
3. 可能受限于 L1/L2 命中率

这也解释了一个常见现象：

某些实现理论指令数更少，实际却没更快，因为瓶颈已经从算术转到访存。

6. 为什么很多高性能库最终都要上 SIMD

如果查表解决的是“单次乘法太贵”，那么 SIMD 解决的是：

同一套运算模式太规则了，不并行做就浪费了。

6.1 EC 为什么天生适合向量化

因为每个数据块本质上是长字节数组，而对每个位置做的运算形式几乎相同：

P[i]   = a*D0[i] + b*D1[i] + c*D2[i] + ...
P[i+1] = a*D0[i+1] + b*D1[i+1] + c*D2[i+1] + ...

这就是标准的数据并行场景。

所以使用 SSE、AVX、AVX2、AVX-512，或者对应架构上的 NEON/SVE，几乎是非常自然的事情。

6.2 SIMD 在这里到底带来什么

它本质上是在一个指令里同时处理：

1. 16 字节
2. 32 字节
3. 64 字节

甚至更多。

结果就是：

1. XOR 吞吐显著提高
2. 查表或 nibble-based 乘法可以批量展开
3. 整体编码吞吐更接近内存带宽上限

6.3 为什么很多实现会配合 nibble table

一种很常见的技巧是把 8 bit 乘法拆成高 4 bit 和低 4 bit 两部分，通过更小的查表块配合 SIMD shuffle 来做。

这么做的目的通常是：

1. 降低大表带来的 cache 压力
2. 更好适配向量化指令
3. 用更规则的数据通路提高吞吐

这就是为什么很多高性能 GF 实现，看上去不像“普通算术代码”，更像是：

1. 字节拆分
2. shuffle
3. mask
4. XOR 合并

如果只从算法教科书视角看这些代码，往往会觉得很奇怪；但从 CPU 热路径视角看，它们非常合理。

7. 编码矩阵为什么通常要预处理

理论上你有一个生成矩阵 G 就够了。

但在实现里，直接拿原始矩阵每次从头算，往往不合算。

7.1 预处理的目的是什么

常见包括：

1. 把矩阵转成系统化形式
2. 为每行系数生成乘法表
3. 为解码阶段缓存逆矩阵或中间结构
4. 为某些常见故障模式缓存恢复路径

7.2 为什么解码阶段尤其受益于预处理

因为编码时矩阵固定，解码时矩阵取决于“丢了哪些块”。

这意味着：

1. 每种缺块组合都要选取不同子矩阵
2. 还要做求逆或等价变换
3. 如果每次故障都从头做完整高斯消元，会增加恢复延迟

所以成熟实现通常会尽量：

1. 简化矩阵选取
2. 减少在线求逆成本
3. 对常见模式做缓存或快速路径

8. full-stripe write 为什么总被认为是“理想写路径”

只要你做过 EC 写路径，几乎一定会反复听到一个词：full-stripe write。

原因很简单。

它基本代表了最干净、最顺手、最少历史包袱的写入场景。

8.1 它到底是什么意思

就是一次写入正好覆盖一个完整 stripe 所需的全部数据块。

例如 k=4，每个 data chunk 1 MB，那么 4 MB 对齐写入正好构成一整条数据带。

系统此时可以直接：

1. 接收新数据块 D0..D3
2. 计算校验块 P0..Pm
3. 一次性写出整个 stripe

示意如下：

Incoming write:  D0  D1  D2  D3
Encode parity:   P0  P1
Flush stripe:    D0  D1  D2  D3  P0  P1

8.2 它为什么这么重要

因为它避开了最昂贵的一类操作：

1. 不需要读旧数据
2. 不需要读旧校验块
3. 不需要计算差量更新
4. 不需要把局部更新强行映射回完整条带历史

这意味着 full-stripe write 往往有：

1. 更少 IO 往返
2. 更顺的 pipeline
3. 更高的编码吞吐
4. 更清晰的一致性边界

所以很多系统都会尽量通过：

1. 聚合写入
2. log-structured 布局
3. 后台 seal
4. 延迟编码

来人为制造更接近 full-stripe 的写入条件。

9. partial write 为什么总会把你拉回现实

只要写入不能覆盖完整 stripe，问题就开始变得麻烦。

例如你只更新 D1 里某个 4 KB 范围。

这时系统不能只改那 4 KB 数据就结束，因为校验块仍必须和新数据保持一致。

9.1 这会触发什么问题

1. 旧数据是什么
2. 旧校验是什么
3. 新校验要怎么算
4. 这次写入和别的并发写如何串起来
5. 崩溃时如何保证数据块和校验块不会半新半旧

一旦问题来到这里，EC 就不再像“数学编码”那么干净，而更像“事务性更新协议”。

10. read-modify-write 是怎么工作的

对于 partial write，最典型的做法是 read-modify-write。

以某个局部范围更新为例，步骤通常是：

1. 读取旧数据块的对应范围
2. 读取受影响校验块的对应范围
3. 计算数据差量 delta
4. 用 delta 更新各个校验块
5. 写回新数据和新校验

概念图可以写成：

old data slice   ----
                    \ 
new data slice   -----> delta -----> update parity slices -----> write back
                    /
old parity slices ---

10.1 它的好处是什么

1. 不必读取整个 stripe
2. 对局部更新更节省读取量
3. 在小修改场景下通常比整条带重构更现实

10.2 它的坏处是什么

1. 需要读旧数据和旧校验
2. 写路径更复杂
3. 一致性处理更难
4. 高并发下更容易出现锁竞争或日志放大

所以 read-modify-write 常常不是“优雅路径”，而是“不得不支持的现实路径”。

11. reconstruct-write 又是什么时候更合适

另一条路线是 reconstruct-write。

思路是：

1. 从幸存数据中读出足够多的整块或大范围数据
2. 在内存中恢复完整相关条带视图
3. 把更新后的整条带重新编码写回

11.1 它什么时候可能更好

1. 更新范围比较大
2. 多个局部更新可以合并
3. 原本就已经要读很多数据
4. 后台整理阶段允许批处理重写

11.2 它什么时候通常更差

1. 纯小写更新
2. 延迟敏感写入
3. 网络远端读取成本很高

所以 read-modify-write 和 reconstruct-write 之间，通常不是“谁绝对更先进”，而是：

哪条路径对当前写入粒度和系统状态更合算。

12. 一致性问题为什么会突然变难

在副本系统里，一个覆盖写已经不算简单；到了 EC，复杂度又上一个台阶。

因为你更新的不是一份数据，而是：

1. 数据块本身
2. 多个相关校验块
3. 可能还有日志或映射元数据

所以系统必须处理类似下面的问题：

1. 如果数据块写成功而校验块没写成功怎么办
2. 如果校验块部分成功怎么办
3. 如果写到一半宕机，恢复时如何知道哪一组是最新一致视图

这也是为什么很多实际系统会引入：

1. 写前日志
2. copy-on-write
3. 两阶段提交风格的元数据切换
4. 版本号或 epoch 标记

换句话说，EC 一旦支持覆盖写，它就在部分路径上开始接近“小型事务系统”。

13. 内存布局为什么会直接决定你能不能跑满 CPU

很多人优化 EC 时过于关注 GF 运算，反而低估了内存布局。

但在高吞吐编码里，内存经常是决定性因素。

13.1 连续块布局的好处

如果每个数据块在内存里连续、对齐、长度规则，那么：

1. SIMD 更容易稳定工作
2. prefetch 更有效
3. cache line 利用率更高
4. 循环展开更容易写得干净

13.2 分散小 buffer 的坏处

如果你的实现到处都是：

1. 小切片
2. 不对齐偏移
3. 频繁分配
4. pointer chasing

那么即使数学核很强，也会被：

1. cache miss
2. TLB 压力
3. allocator 开销
4. 分支与边界处理

这些问题拖住。

所以高性能 EC 代码看上去往往有点“硬核”：

1. 大块缓冲区
2. 对齐分配
3. 批处理循环
4. 尽量少的抽象层

这是因为它本质上更接近一个数据平面组件，而不是普通业务逻辑代码。

14. 为什么 benchmark 很容易测错

EC 的 benchmark 很容易给出误导性结论。

常见原因包括：

1. 只测纯内存编码，不测真实写路径
2. 只测大块顺序，不测 partial write
3. 只测单线程，不测并发争用
4. 只测 encode，不测 degrade read 和 repair
5. 忽略 NUMA、cache warming 和数据对齐影响

结果就是：

1. 某个实现 microbenchmark 非常好看
2. 一进真实系统却没明显收益

所以更可靠的测试方法通常要至少分三层：

1. 算法核 benchmark：纯 encode/decode 吞吐
2. 路径 benchmark：full-stripe、partial write、repair
3. 系统 benchmark：网络、磁盘、后台重建与前台业务混跑

如果只做第一层测试，通常只够回答“这个库快不快”，还回答不了“这个系统会不会好用”。

15. 为什么 ISA-L、Jerasure 这类库长期重要

很多团队最终不会自己从头写整套 GF 内核，而是会依赖成熟库。

这并不只是为了偷懒，而是因为这些库通常积累了大量实现经验：

1. 指令集优化
2. 系数预处理
3. 平台兼容
4. 各种边界条件
5. 较成熟的性能基线

它们的价值不在于“替你理解原理”，而在于：

把最容易写错、最难写快的那部分热路径沉淀下来了。

当然，这不意味着接入库就完事。

因为系统层仍然要自己解决：

1. 什么时候 encode
2. 什么时候 read-modify-write
3. 怎么切任务
4. 怎么和 IO pipeline 对齐

也就是说，库能解决的是“核函数”，解决不了的是“整条数据面设计”。

16. 从实现角度看，EC 最值得刻意追求的是什么

如果从实现层给一个非常务实的目标，我会更倾向于下面这几条。

16.1 尽量制造 full-stripe write 条件

因为这是最干净的路径。

16.2 让 partial write 路径尽量可预测

不要让它在边界条件下突然退化得非常糟。

16.3 让热路径尽量向量化、批处理、少分配

否则很容易在 CPU 和内存层浪费掉理论优势。

16.4 明确 repair、degrade read 和 normal write 是三条不同路径

很多系统设计问题，都是因为把这三条路径混成“一套通用处理流程”。

16.5 把可观测性做进实现里

至少要能看见：

1. encode 吞吐
2. decode 吞吐
3. partial write 占比
4. read-modify-write 次数
5. degrade read 延迟
6. repair 读取放大量

没有这些指标，后面的优化往往只能靠猜。

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

如果把实现篇压缩成最核心的几句话，大概是这些：

1. EC 的实现瓶颈通常是算术、访存、调度和 IO 的混合结果
2. GF 加法通常便宜，GF 乘法才是实现重点
3. 查表和 SIMD 是高性能 EC 的常见基础设施
4. full-stripe write 通常是最理想的写路径
5. partial write 会把系统拖回 read-modify-write 或 reconstruct-write 的复杂世界
6. 一旦支持覆盖写，EC 实现往往要同时处理一致性问题
7. 真正决定体验的，往往不是码型名字，而是数据路径怎么组织

这也解释了为什么很多关于 EC 的讨论，在理论上差异不大，到了工程上却能跑出完全不同的结果。

18. 这一组文章到这里，基本把 EC 的五个层次讲全了

如果把整个系列重新压缩一下，现在其实已经有五层：

1. 原理层：为什么可恢复
2. 代价层：为什么恢复和更新很贵
3. 系统层：条带、故障域、冷热分层与后台重建
4. 实战层：Ceph、HDFS、Azure LRC 的真实取舍
5. 实现层：GF 运算、SIMD、写路径和内存布局

这五层拼起来，才比较接近一个工程师真正会遇到的 EC 全貌。

如果只学第一层，你会觉得它是个漂亮算法。

如果把五层都看完，你通常会更愿意把它理解成：

纠删码不是“一个编码函数”，而是一整套从代数、数据布局、故障恢复到 CPU 热路径都必须相互咬合的系统工程。

这也是为什么它明明已经非常成熟，依然始终值得认真学一遍。

如果你想把这一篇里的实现讨论继续压到更接近代码的层面，下一篇我把最小 RS encoder/decoder、恢复流程和 read-modify-write 伪代码单独展开：

1. 纠删码（源码篇）：最小 RS encoder/decoder 与 read-modify-write 伪代码
2. 纠删码（性能篇）：benchmark、NUMA、线程模型与 repair 限流
3. 纠删码（案例排障篇）：repair 打满网络、degraded read 尾延迟飙升与 partial write 放大
4. 纠删码（架构选型篇）：什么时候该用三副本、RS、LRC，什么时候根本不该上 EC

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

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

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

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

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

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

---

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

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

```text
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]

其中：

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

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

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

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

1. 数据块直接保留
2. 按生成矩阵的 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

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

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

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

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

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

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

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

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

但注意：

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

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

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

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

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

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

所以 decoder 的本质问题是：

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

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

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

D0  D2  D3  P1

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

1. 记录哪些块幸存
2. 从生成矩阵里取出这些幸存块对应的 4 行
3. 组成一个 4x4 子矩阵 A
4. 求 A^-1
5. 用 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

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

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

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

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

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

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

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

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

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

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

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

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

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

这完全正常。

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

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

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

注意两点：

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

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

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

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

假设：

1. 一个 partial write 只更新某个数据块的局部范围
2. 受影响的 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)

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

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

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

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

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

1. 新数据来了
2. 那就拿新数据重新算 parity

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

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

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

写成抽象式子就是：

new_parity = old_parity + coeff * delta

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

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

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

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

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

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

这也解释了为什么很多工程师第一次看 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 覆盖写为什么总是比副本更麻烦：

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

所以很多系统宁可通过：

1. append-only
2. 后台 compaction
3. stripe 聚合
4. delayed encoding

来尽量躲开这条路径。

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

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

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

至少要有：

1. gf_add
2. gf_mul
3. gf_inv

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

15.2 第二步：写最小 encoder

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

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

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

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

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

例如：

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

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

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

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

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

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

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

原因很简单。

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

1. 编码
2. 恢复
3. 矩阵变换
4. 增量更新
5. 热路径准备

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

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

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

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

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

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

现在这一组已经从：

1. 原理
2. 代价
3. 工程落地
4. 真实系统取舍
5. 实现热点
6. 源码骨架

一路串起来了。

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

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

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

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

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

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