纠删码.md

- 纠删码（Erasure Code）原理
- 纠删码基础概念

纠删码（Erasure Code）原理

里德-所罗门码（Reed-Solomon Code，RS 码）是一种基于有限域代数结构的纠删码（Erasure Code），因其高效的数据恢复能力和灵活的冗余配置，被广泛应用于多个领域。

分布式存储系统领域（如 RustFS,Minio）

数据分片与冗余 将原始数据分为 k 个分片，生成 m 个校验分片（总计 n=k+m）。任意丢失≤ m 个分片均可恢复数据。示例：RS(10,4) 策略允许同时丢失 4 个分片（存储利用率 71%= 10/14），相比三副本（33%）节省 50% 存储空间。
故障恢复机制 通过高斯消元法或快速傅里叶变换(FFT) 算法，利用存活分片重建丢失数据，恢复时间与网络带宽成反比。
动态调整能力 支持运行时调整(k,m)参数，适应不同存储层级（热/温/冷数据）的可靠性需求。

通信传输领域

卫星通信 处理深空信道中的长延时、高误码率问题（如 NASA 火星探测器使用 RS(255,223)码，纠错能力达 16 字节/码字）。
5G NR 标准 在控制信道采用 RS 码结合 CRC 校验，确保关键信令的可靠传输。
无线传感器网络 解决多跳传输中的累积丢包问题，典型配置 RS(6,2)可容忍 33%的数据丢失。

数字媒体存储领域

二维码（QR Code） 使用 RS 码实现容错等级调节（L7%, M15%, Q25%, H30%），即使部分区域污损仍可正确解码。
蓝光光盘 采用 RS(248,216)码组合交叉交织，纠正因划痕导致的连续突发错误。
DNA 数据存储 在合成生物分子链时添加 RS 校验，抵御碱基合成/测序错误（如 Microsoft 实验项目使用 RS(4,2)）。

纠删码基础概念

核心参数定义

k: 原始数据分片数量
m: 校验分片数量
n: 总分片数量（n = k + m）
恢复阈值: 任意 k 个分片可恢复原始数据
容错能力：最多可容忍丢失 m 个块

方案类型	冗余度	故障容忍度
3 副本	200%	2 节点
RS(10,4)	40%	4 节点

数学原理

纠删码基于有限域（Galois Field，GF）上的线性代数运算。

编码过程：
[C] = [G] × [D]

其中：
- [D] 是 k×1 的数据向量（原始数据块）
- [G] 是 n×k 的生成矩阵
- [C] 是 n×1 的编码向量（编码后的块）

编码过程：
[C₁]   [1  0  0]   [D₁]   [D₁        ]
[C₂] = [0  1  0] × [D₂] = [D₂        ]
[C₃]   [0  0  1]   [D₃]   [D₃        ]
[C₄]   [p₁ p₂ p₃]         [P₁ = 校验块]
[C₅]   [q₁ q₂ q₃]         [P₂ = 校验块]

结果：
C₁ = D₁  ← 直接就是原始数据
C₂ = D₂  ← 直接就是原始数据
C₃ = D₃  ← 直接就是原始数据
C₄ = P₁  ← 校验块
C₅ = P₂  ← 校验块

编码过程详解

原始数据：100MB
分成 k=6 个数据块，每个约 16.67MB
D1, D2, D3, D4, D5, D6

使用生成矩阵 G（Generator Matrix）（n×k）生成校验块：

[P1]   [1  1  1  1  1  1]   [D1]
[P2]   [1  2  3  4  5  6]   [D2]
[P3] = [1  4  9 16 25 36] × [D3]
[P4]   [1  8 27 64 125 216] [D4]
                            [D5]
                            [D6]

将 6 个数据块 + 4 个校验块 = 10 个块分布到不同节点。

解码过程详解

场景：丢失 2 个块
假设丢失 D2 和 P3，剩余 8 个块可用。

步骤 1：构建恢复矩阵
从生成矩阵中提取对应行，形成可逆矩阵。

步骤 2：求解线性方程组
已知：D1, D3, D4, D5, D6, P1, P2, P4 未知：D2, P3通过矩阵运算求解：[D2] = [恢复矩阵]^(-1) × [已知数据]

步骤 3：验证
恢复后验证数据完整性。

计算开销
编码：O(k×m) 复杂度
解码：O(k²) 或更高（取决于丢失块数）

修复开销
修复 1 个块需要读取 k 个块
修复带宽 = k × 块大小

数据完整性校验方法

简单校验和（Simple Checksum）

原理
将数据按字节相加，取模或取反。

示例

数据：0x12, 0x34, 0x56
校验和 = (0x12 + 0x34 + 0x56) mod 256 = 0x9C

CRC（Cyclic Redundancy Check，循环冗余校验）
MD5（Message Digest Algorithm 5）
SHA（Secure Hash Algorithm）
Adler-32

数据完整性校验：结合校验和（checksum）机制确保对象分片数据在读取时一致，例如 ZFS 会在读取时校验每个数据块的校验和，并在校验失败时进行修复。
RustFS 默认使用 crc32c（CRC-32 Castagnoli）作为校验和算法

常见纠删码类型

Reed-Solomon 纠删码（RS码）
RS码是最常用的纠删码，基于多项式插值。
优点：容错能力强，存储效率高
缺点：计算开销大（特别是解码）
应用：Ceph、HDFS、GlusterFS
LRC（Locally Repairable Code，局部修复码）
特点：局部校验块，修复时只需读取少量块
优势：修复带宽小，速度快
应用：Azure Storage、Windows Storage Spaces
旋转RS码（Rotated RS）
特点：优化修复过程，减少修复时的数据读取量
应用：Facebook 的分布式存储
奇偶校验码（Parity）
最简单的纠删码（k+1 模式）
只能容忍 1 个块丢失
应用：RAID 5

Table of Contents