存储系统中的纠删码(Erasure Codes)—XOR 码和RS 码(二)

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

 

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

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

无标题

图1 校验矩阵(Parity matrix)生成校验块

 

如图1,如果是XOR 码,左边的校验矩阵中mij 为0或1,那么校验块的计算则只有数据块D0~D3的异或过程(有限域上加减法都是异或运算);反之如果是RS码,校验块的计算则包含了mij 和数据块Dj 的乘法,有限域上的乘法是非常慢的,因为在有人则提出利用计算机GPGPU 或SIMD指令集加速mij 和数据块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 块数据块(d0,0 到d5,3),编码为m×r 个大小的校验块(c0,0 到c1,3),图2 (b) 中扁平编码将原始数据块分为k 块,编码为m 块校验块。从生成矩阵的角度来看,扁平编码生成矩阵有n 行k 列,非扁平编码生成矩阵有n×r 行、k×r 列,图3 给出了CRS 码(非扁平XOR码)和Reed-Solomon 码(扁平RS码)生成矩阵的编码过程。

RS_to_CRS2    RS_to_CRS1

图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)来表示。

ImageFigure 1Bipartite graph of LDPC codes

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

 

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

存储系统中的纠删码(Erasure Codes)—XOR 码和RS 码(二)》上有2条评论

  1. 您好,看到您这一句“有人则提出利用计算机GPGPU 或SIMD指令集加速mij 和数据块Dj 的乘法”。想请问一下目前 有GPU实现有限域操作 相关库或是相关文章吗,您这的参考文献具体是那篇文献呀?

    • 您好!有的,随便搜索下还是不少的。比如 ICS16 的《Fast Multiplication in Binary Fields on GPUs via Register Cache》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据