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 个数字要保存d15d27你担心其中一个数字会丢所以想加一个“校验数”。方法加法校验计算一个校验值p d1 d2 5 7 12现在你保存三个数5, 7, 12情况1d1丢了只剩 7 和 12你可以算d1 p − d2 12 − 7 5情况2d2 丢了只剩 5 和 12d2 p − d1 12 − 5 7✅ 只要丢不超过1个原始数据就能恢复但注意如果两个原始数据都丢了只剩12就无法知道是 (1,11) 还是 (2,10)…… 所以这个方案只能容忍丢1块。三、升级用线性方程组初中数学为了能容忍更多丢失我们需要多个校验值并且它们之间要“独立”。例子2个原始数据2个校验块可容忍丢任意2块原始数据d1 5d2 7我们生成两个校验块p1 d1 d2p2 d1 2⋅d2计算得p1 5 7 12p2 5 2 × 7 19现在总共有 4 块数据5, 7, 12, 19容错能力测试情况1丢了 d1d1 和 d2d2但有 p112 p219我们有方程组x y 12x 2y 19用消元法第二式减第一式(x 2y) − (x y) 19 − 12 ⇒ y 7代入得x 12 − 7 5x 12 − 7 5✅ 恢复成功情况2丢了 d2 和 p1p1剩下 d15, p219我们知道d1 5p2 d1 2d2 19所以5 2d2 19 ⇒ 2d2 14 ⇒ d2 7再算 p1 5 7 12✅ 全部恢复情况3丢了 p1p1 和 p2p2但 d1,d2 都在 → 直接重新算校验块即可。 关键只要剩下的数据块数量 ≥ 原始数据块数量这里是2并且方程“不重复”就能解出原始数据四、一般化(n, k) 纠删码把原始数据分成k 块比如 k4用数学方法生成m 块校验数据总共存n k m 块性质任意丢失最多 m 块即只要剩下 ≥ k 块就能完全恢复原始 k 块数据这就像解一个k 元一次方程组每个校验块是一个线性方程比如 pa1d1a2d2⋯akdkpa1d1a2d2⋯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就是把原始数据看作未知数用线性方程生成校验值只要剩下的数据够多≥原始块数就能像解方程一样把丢掉的数据算回来
【存储】Erasure-Code(EC)2：使用初等数学讲明白EC的工作原理
发布时间：2026/5/19 5:41:37
参考文档:- Erasure-Code: 工作原理, 数学解释, 实践和分析: https://drmingdrmer.github.io/tech/distributed/2017/02/01/ec.html一、问题背景数据丢了怎么办假设你有一份重要文件比如一张照片你想把它存到几台服务器上以防某台服务器坏了导致数据丢失。最简单的方法复制多份比如存3份。只要有一份在就能恢复。缺点浪费空间存3份就要3倍存储。纠删码的目标用更少的冗余实现同样的容错能力。例如把原始数据分成 4 块再生成 2 块“校验块”总共存 6 块。即使其中任意 2 块丢了也能靠剩下的 4 块完全恢复原始数据这就是 EC 的核心思想用数学方法生成冗余而不是简单复制。二、用小学数学举个例子场景你有2 个数字要保存d15d27你担心其中一个数字会丢所以想加一个“校验数”。方法加法校验计算一个校验值p d1 d2 5 7 12现在你保存三个数5, 7, 12情况1d1丢了只剩 7 和 12你可以算d1 p − d2 12 − 7 5情况2d2 丢了只剩 5 和 12d2 p − d1 12 − 5 7✅ 只要丢不超过1个原始数据就能恢复但注意如果两个原始数据都丢了只剩12就无法知道是 (1,11) 还是 (2,10)…… 所以这个方案只能容忍丢1块。三、升级用线性方程组初中数学为了能容忍更多丢失我们需要多个校验值并且它们之间要“独立”。例子2个原始数据2个校验块可容忍丢任意2块原始数据d1 5d2 7我们生成两个校验块p1 d1 d2p2 d1 2⋅d2计算得p1 5 7 12p2 5 2 × 7 19现在总共有 4 块数据5, 7, 12, 19容错能力测试情况1丢了 d1d1 和 d2d2但有 p112 p219我们有方程组x y 12x 2y 19用消元法第二式减第一式(x 2y) − (x y) 19 − 12 ⇒ y 7代入得x 12 − 7 5x 12 − 7 5✅ 恢复成功情况2丢了 d2 和 p1p1剩下 d15, p219我们知道d1 5p2 d1 2d2 19所以5 2d2 19 ⇒ 2d2 14 ⇒ d2 7再算 p1 5 7 12✅ 全部恢复情况3丢了 p1p1 和 p2p2但 d1,d2 都在 → 直接重新算校验块即可。 关键只要剩下的数据块数量 ≥ 原始数据块数量这里是2并且方程“不重复”就能解出原始数据四、一般化(n, k) 纠删码把原始数据分成k 块比如 k4用数学方法生成m 块校验数据总共存n k m 块性质任意丢失最多 m 块即只要剩下 ≥ k 块就能完全恢复原始 k 块数据这就像解一个k 元一次方程组每个校验块是一个线性方程比如 pa1d1a2d2⋯akdkpa1d1a2d2⋯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就是把原始数据看作未知数用线性方程生成校验值只要剩下的数据够多≥原始块数就能像解方程一样把丢掉的数据算回来
