（转）存储系统中的纠删码（Erasure Codes）—XOR 码和RS 码（二）

白丁

（转）存储系统中的纠删码（Erasure Codes）—XOR 码和RS 码（二） [复制链接]

纠删码（Erasure Codes）能够总体上分为XOR 码和RS 码两类，XOR 码基于有限域GF(2)，编、解码只需要按位异或（bit-wise exclusive-OR）即可完成，速度较快；RS 码基于有限域GF(2 w )，编、解码需要有限域上（后面的文章将详细介绍）的运算，速度慢于XOR码。常见的XOR码有：

低密度奇偶校验码（Low Density Parity Code, LDPC）
柯西-里德所罗门码（Cauchy-Reed-Solomon Codes，CRS）
RAID码（如RAID5、RAID6）
奇偶码（EVENODD）
X-码（X-code）

按照编码理论来说，RS码是一个字长为n，维度为k，码字间距为n-k+1 的最小距离可分码（MDS codes），但为了能够让读者能够更容易接受，我们这里的RS 码是基于有限域上GF(2 w )编解码运算的编码。

一、XOR 码和RS 码的生成矩阵

上一节中我们介绍了生成矩阵（Generator Matrix）定义了线性码的编码方法，XOR 码的生成矩阵中的元素只有0 和1，在RS 码中，生成矩阵的元素是从0到2 w -1 的整数。

图1 校验矩阵（Parity matrix）生成校验块

如图1，如果是XOR 码，左边的校验矩阵中m ij 为0或1，那么校验块的计算则只有数据块D0~D3的异或过程（有限域上加减法都是异或运算）；反之如果是RS码，校验块的计算则包含了m ij 和数据块Dj 的乘法，有限域上的乘法是非常慢的，因为在有人则提出利用计算机GPGPU 或SIMD指令集加速m ij 和数据块Dj 的乘法。

在实际系统中往往更考虑性能，其次是一般性，虽然RS 码慢于XOR 码，但其具有更佳的一般性（generality），可以支持任意大小的n、k、m 参数。而XOR 码对于这些参数总有或多或少的限制，但总体来说真实系统中XOR 码应用要比RS 码应用更广泛（CRS 应用于oceanstore，RAID 码广泛应用于阵列）。

二、扁平和非扁平（Flat or not）

扁平和非扁平是纠删码所具有的特性。当一个编码方法是扁平的（flat），编码后每个条带上的存储节点中仅有一个编码块；当一个编码方法不是扁平的，则编码后每个条带上的存储节点中具有多个编码块。

（a）非扁平编码（b）扁平编码

图2 非扁平编码（r=4）和扁平编码

图2 给出了非扁平编码和扁平编码的两个例子：图2 (a) 中非扁平编码每个条带中将原始数据等分为k×r 块数据块（d 0,0 到d 5,3 ），编码为m×r 个大小的校验块（c 0,0 到c 1,3 ），图2 (b) 中扁平编码将原始数据块分为k 块，编码为m 块校验块。从生成矩阵的角度来看，扁平编码生成矩阵有n 行k 列，非扁平编码生成矩阵有n×r 行、k×r 列，图3 给出了CRS 码（非扁平XOR码）和Reed-Solomon 码（扁平RS码）生成矩阵的编码过程。

图3 k=3、m=2（、w=4）的非扁平码（CRS码、左）和扁平码（RS码、右）的编码过程，

其中红色部分为一个编码块的编码过程

常见的扁平和非扁平编码方法如下：

扁平（flat）	非扁平（non-flat）
XOR 码	LDPC 码	CRS 码，X-码，RDP码，STAR码， SD码，PDMS码等
RS 码	RS码	Rotated-RS码，再生码等

其中，斜体 RS码 表示的是我们一般的Reed-Solomon 码，而不是用于统称表示所有有限域上计算的编码。它们四者的速度关系为：Flat XOR codes > Non-flat XOR codes > Flat RS codes > Non-flat RS codes 。

三、Flat XOR codes — 低密度奇偶校验码（LDPC, Low Density Parity Codes）

Flat XOR codes只有一类LDPC 码，因此Flat XOR codes 也可称为LDPC 码。LDPC 码广泛应用于通信领域，因为其编解码速度快，码率高（虽然不是MDS 码）。虽然它也是线性码，但不同构造编码矩阵和解码矩阵即可进行数据的编、解码。类似于生成矩阵，每个LDPC 码可以唯一地用一个双边图（bipartite graph）来表示。

图4 一个k=8，m=4 的LDPC 码的双边图

图4 中给出了一个k=8，m=4 的LDPC 码的双边图，左边方块表示分块后的八块原始数据块（u 1 ~u 8 ），右边的圆圈表示校验块，校验块（圆圈）与数据块（方块）的连线表示数据块参与了该校验块的异或运算，每个校验块（圆圈）是所有与其相连的数据块（方块）异或的结果。利用双边图还能够快速地进行丢失数据块的修复。