【存储】Erasure-Code(EC)2：使用初等数学讲明白EC的工作原理
参考文档:
- Erasure-Code: 工作原理, 数学解释, 实践和分析: https://drmingdrmer.github.io/tech/distributed/2017/02/01/ec.html
一、问题背景：数据丢了怎么办？
假设你有一份重要文件，比如一张照片，你想把它存到几台服务器上，以防某台服务器坏了导致数据丢失。
- 最简单的方法：复制多份（比如存3份）。只要有一份在，就能恢复。
- 缺点：浪费空间！存3份就要3倍存储。
纠删码的目标：用更少的冗余，实现同样的容错能力。
例如：把原始数据分成 4 块，再生成 2 块“校验块”，总共存 6 块。即使其中任意 2 块丢了，也能靠剩下的 4 块完全恢复原始数据！
这就是 EC 的核心思想：用数学方法生成冗余，而不是简单复制。
二、用小学数学举个例子
场景：
你有2 个数字要保存：
- d1=5
- d2=7
你担心其中一个数字会丢，所以想加一个“校验数”。
方法：加法校验
计算一个校验值：
p = d1 + d2 = 5 + 7 = 12
现在你保存三个数：5, 7, 12
情况1：d1丢了（只剩 7 和 12）
你可以算：
d1 = p − d2 = 12 − 7 = 5
情况2：d2 丢了（只剩 5 和 12）
d2 = p − d1 = 12 − 5 = 7
✅ 只要丢不超过1个原始数据，就能恢复！
但注意：如果两个原始数据都丢了（只剩12），就无法知道是 (1,11) 还是 (2,10)…… 所以这个方案只能容忍丢1块。
三、升级：用线性方程组（初中数学）
为了能容忍更多丢失，我们需要多个校验值，并且它们之间要“独立”。
例子：2个原始数据，2个校验块（可容忍丢任意2块！）
原始数据：
- d1 = 5
- d2 = 7
我们生成两个校验块：
- p1 = d1 + d2
- p2 = d1 + 2⋅d2
计算得：
- p1 = 5 + 7 = 12
- p2 = 5 + 2 × 7 = 19
现在总共有 4 块数据：5, 7, 12, 19
容错能力测试：
情况1：丢了 d1d1 和 d2d2，但有 p1=12 p2=19
我们有方程组：
- x + y = 12
- x + 2y = 19
用消元法：
- 第二式减第一式：(x + 2y) − (x + y) = 19 − 12 ⇒ y = 7
- 代入得：x = 12 − 7 = 5x = 12 − 7 = 5
✅ 恢复成功！
情况2：丢了 d2 和 p1p1，剩下 d1=5, p2=19
我们知道：
- d1 = 5
- p2 = d1 + 2d2 = 19
所以：
5 + 2d2 =19 ⇒ 2d2 = 14 ⇒ d2 = 7
再算 p1 = 5 + 7 = 12
✅ 全部恢复！
情况3：丢了 p1p1 和 p2p2，但 d1,d2 都在 → 直接重新算校验块即可。
💡 关键：只要剩下的数据块数量 ≥ 原始数据块数量（这里是2），并且方程“不重复”，就能解出原始数据！
四、一般化：(n, k) 纠删码
- 把原始数据分成k 块（比如 k=4）
- 用数学方法生成m 块校验数据
- 总共存n = k + m 块
性质：任意丢失最多 m 块（即只要剩下 ≥ k 块），就能完全恢复原始 k 块数据！
这就像解一个k 元一次方程组：
- 每个校验块是一个线性方程（比如 p=a1d1+a2d2+⋯+akdkp=a1d1+a2d2+⋯+akdk）
- 只要收集到 k 个线性无关的方程，就能唯一解出所有 didi
✅ 这就是纠删码的数学本质：用线性代数构造冗余，通过解方程恢复数据
五、实际中怎么选系数？
上面例子用了 1, 2 作为系数。实际系统（如 Reed-Solomon 码）会用更巧妙的系数（比如在有限域上用范德蒙矩阵或柯西矩阵），确保任意 k 个方程都可解。
但核心思想不变：每个校验块 = 原始块的加权和，权重设计得足够“独立”。
六、优点 vs 复制
全屏复制
| 方法 | 存储开销（存4块数据，容忍丢2块） | 能否恢复 |
|---|---|---|
| 三副本 | 4 × 3 = 12 块 | 能 |
| EC (6,4) | 6 块 | 能（只要≥4块在） |
👉EC 节省大量存储空间，特别适合云存储（如 HDFS、Google File System、Azure、Facebook 等都用 EC）。
总结（一句话）
纠删码（EC）就是把原始数据看作未知数，用线性方程生成校验值；只要剩下的数据够多（≥原始块数），就能像解方程一样把丢掉的数据算回来！