纠删码调研

背景

纠删码是用来保护数据安全的核心技术，例如磁盘扇区中会嵌入少量的额外矫正信息来容忍一定限度的比特翻转错误。当发生错误的比特数太多或者物理组件不可用，存储系统会将对应的数据视为擦除（erasure）。为此，存储系统依赖纠删码应对此种错误，纠删码通过增加系统冗余度提供数据保护。

最简单的数据保护方案是复制，但是复制需要消耗大量资源和存储开销，且可能存在保存同一份数据的两个存储组件同时故障的情况。像Reed-Solomon等纠错码比简单复制复杂，可以处理更多种类的错误，纠删码可以追溯到纠错码（ECC）但又不是一个概念，后者通常应用在通信邻域。纠删码通常暴露错误发生位置，提供的错误处理能力也比纠错码强大的多。

简单编码机制

考虑一个由n个磁盘组成的存储系统，其中k个数据盘用来保存用户数据，m=n-k个盘用来保存纠删码的编码信息。m个编码盘中的数据由k个数据盘计算得来，当不超过m个盘损坏时数据可以从剩余盘计算恢复。最简单的纠删码假定每块盘保存一个w bits的字，数据盘中记为$d_0,…d_{k-1}$，编码盘中记为$c_0,…,c_{m-1}$。编码数据定义为用户数据的线性组合：

$\begin{gathered} c_0=a(0,0)d_0+\quad...\quad+a(0,k-1)d_{k-1}\\ c_1=a(1,0)d_0+\quad...\quad+a(1,k-1)d_{k-1}\\ ...\\ c_{m-1}=a(m-1,0)d_0+\quad...\quad+a(m-1,k-1)d_{k-1}\\ \end{gathered}$

系数a(i,j)也是w bits的字，编码过程涉及字的乘法加法，解码过程涉及利用高斯消元或矩阵逆求解线性方程组。当w=1时所有的数据只有一比特，纠删码算法是标准的模2运算，加法是二进制$\oplus$,乘法是二进制AND。当w取值大于1时，运算为GF($2^w$)，基于伽罗华域运算，加减乘除都是定义在模p上的运算，操作数范围为0到$2^{w-1}$。实际上每个磁盘可能包含多个w比特的存储字，所有磁盘上同一序号的存储字同时参与编解码。w=1运算最简单，w=8时每个存储字占一个字节。通常w越大，纠删码可以做的越复杂，但是伽罗华域的运算也会越复杂。综上，纠删码可由w和系数矩阵a(i,j)定义。

数据块大小（stripe）

数据块大小是数据块进行编码计算时，数据分块的大小。在不同的存储系统中数据块大小不同，在RAID存储系统中，常见的分块大小是4KB~128KB，在分布式存储系统中数据块较大，一般为64MB大小。条带是纠错编码存储一次性读入或写入数据的大小，在系统码中，一个条带往往包含了k个原始数据块和m个校验块。上图左侧，其中n=4个磁盘中的每个磁盘包含相同比例的数据和编码条带。上图右侧，包含n=8个磁盘，但每个条带由三条数据条带和一条编码条带组成，条带的分配是唯一的区别。因此，擦除码可以与图的左侧相同Panasas使用这种方法来允许灵活的块分配，并允许将额外的磁盘无缝地添加到存储系统。

RAID-4 和 RAID-5

有关RAID更多内容可以参考RAID磁盘阵列的分级与结构总结。这里论文主要基于RAID-4和RAID-5讲解，他们使用相同的简单纠错码，只是RAID-5每个磁盘都保存数据和编码。这里的纠错码是一种MDS，其中m=1，w=1，唯一的编码位被标记为p，他是所有数据位的异或。

$p=d_0\oplus d_1\oplus ...\oplus d_{k-1}$

Linux RAID-6

添加一个磁盘(Q)到RAID-4/5系统中，该系统使用6个磁盘进行存储。使用一个(6,2)MDS码。以w=8为例，通过以下算法进行计算：

$\begin{gathered} p=d_0 \oplus d_1 \oplus \cdots \oplus d_{k-1} \\ q=d_0 \oplus 2\left(d_1\right) \oplus \cdots \oplus 2^{k-1}\left(d_{k-1}\right) \end{gathered}$

其中，由于伽罗瓦域中加法相当于异或操作，因此P盘的纠错码相当于RAID-4/5，同时由于：

$q=2\left(2\left(\cdots 2\left(2 d_{k-1} \oplus d_{k-2}\right) \cdots\right) \oplus d_1\right) \oplus d_0$

所以Q盘仅可以使用加法和乘法进行计算。

常见编码举例

Reed-Solomon Codes（RS码）

RS码是当且仅当$n\leq 2^w$时存在的MDS码。例如，存储系统包含256个或更少的磁盘，可以在$GF(2^8)$中定义一种计算。有多种方式来定义$a(i,j)$系数。最简单是“Cauchy”结构：在$GF(2^w)$中选择n个不同的数字，并将它们分成两组X和Y，使得X具有m个元素，Y具有k个元素。计算纠删码系数：

$a(i, j)=\frac{1}{x_i \oplus y_j}$

Array Codes（阵列码）

避免伽罗瓦域计算
仅通过异或运算实现纠错码

阵列码的数据字节是编码字节的线性组合。常见的阵列码包括：

应用场景	方案
RAID-6	RDP、EVENODD、Blaum-Roth和Liberation-codes
m=3	STAR阵列码
任意k和m	Cauchy Reed-Solomon、通用EVENODD、通用RDP

图3描述了使用RDP码，k=4,m=2,n=k+m=6,r=4,w=1的实例，上图中灰色线描述了P盘的编码方式，彩线描述了Q盘的编码方式。

纠删码常见优化思路

向量指令的出现降低了Galois Field算法的CPU负担，因此不涉及Galois Field运算的阵列码近些年吸引力在下降。但是它们在恢复方面具有有趣的性质，使它们成为简单码的可行替代方案。

减少恢复操作的磁盘IO

当使用简单纠删码且单个磁盘发生故障时，恢复其内容需要从幸存的磁盘读取k−1个条带，以计算故障磁盘上的每个条带。使用阵列代码，可以显着减少从幸存的磁盘读取的数据量。如图4所示的例子中（使用RDP纠删码），磁盘$D_0$损坏时，若使用简单纠删码，恢复将等效于仅从P驱动器进行解码，必须从幸存的磁盘读取16bit; 但由于RDP的结构，通过从幸存的磁盘读取12bit来恢复$D_0$。这种方法意味着恢复时可以减少25%的磁盘IO操作。