基于二元域再生码的编码研究∗

乔平安 任 静 田晶晶

（西安邮电大学计算机学院 西安 710061）

1 引言

大数据时代，信息资源的急速增长，存储系统对存储容量、数据可用性和可靠性提出了越来越高的要求。为了保护数据，存储系统常常会采用一些冗余策略。在过去的存储系统如GPFS，Ceph［1］采用的冗余策略是完全复制。虽然数据的完全复制适合于高负载系统，但它在存储空间或系统中整体性能的效率都十分低下。因而，研究分布式存储系统［2～4］中基于纠删码的冗余策略对海量数据存储具有重要意义。

2 基本概念

2.1 纠删码

分布式存储系统要提高系统的可靠性和容错性需要采用一定的策略。传统的冗余策略通常是采用完全副本技术。完整的复制生成源文件的多个副本，然后将它们分发到不同的存储节点。只需要源文件和副本有一个是完整的，就不会使得数据丢失。完整副本技术容易实现，比较适合高负荷的系统，但有耗费较多的存储空问的缺点［5～6］。

另一种冗余策略，纠删编码［7～11］。一般来说，纠删码可以用一个四元组｛n，k，b，k'｝来表示，其中，n是编码后的文件块个数，k是编码前文件块的个数，b 是每个文件块包含的比特数，k'是不小于k 的数。首先，用户的文件数据被分成k 个块，用集合表示为F=｛F1，F2，…，Fk｝，其中Fi（1 ≤i ≤k）是一个包含b 比特的文件块。我们假设纠删码的编码函数是E 并且解码函数是D，对原文件编码E（F）=｛F1'，F2'，…，Fn'｝，Fi'（1 ≤i ≤n）大小仍为b 比特。设E（F'）是E（F）中任意k'（k' ≥k）个文件块组成的了文件，那么D（E（F'））=F，即得到E（F）中的任意k'个文件块就可以用解码函数D还原出原文件。

通俗讲，一个（n，k）纠删码是把k 个源数据编码为n（n＞k）个数据，用其中任意k 个数据就可以还原出原来的数据。作为一种高效的数据冗余方式，它被运用于存储系统中。首先用户将要存储的文件被划分成固定大小的数据块，然后使用编码理论对其进行编码。对于k 个数据块，根据纠删码生成n 个一样大小并唯一标识的数据块（n＞k），存储在相应的存储系统中，只要保证存储系统中有k 个数据块是正确的，那么存储系统就被认为是可靠的。

纠册码提供了一种存储优化的冗余机制来保护存储的数据。在分布式存储系统中，编码的文件块存储在不同的节点上。当系统中某些节点由于某种原因失效时，用户仍然可以从文件的其余部分恢复原始文件。也就是说一定数量的节点故障不会导致用户数据丢失。

2.2 二元域再生码

再生码作为一种纠删码，首次由Dimakis 等提出［12］。再生码可用于对失效的节点进行数据修复且满足MDS 性质［13］。节点数据修复方法包括精确修复与功能性修复。在精确修复中，新加入的节点中的数据必须同失效的节点中的数据保持一致。而在功能性修复中，并不要求新加入节点的数据与失效节点的数据保持一致，只需要保证任取k 个节点的数据即可恢复所有的原始数据。

2013年，Hou等提出了一种基于二元域异或操作的再生码［14］，该种再生码以移位相加的方式进行编码。随后，Kenneth 等提出另一种运算在二元域上的再生码［15］。

表1 二进制循环移位再生码

表1 表示的是Kenneth 等提出的码长为5 位的二元域再生码的数据包构成。数据包c1和c2的前4位数据为原始数据，最后一位数据b1，4=b1，0+b1，1+b1，2+b1，3，同理b2，4=b2，0+b2，1+b2，2+b2，3。数据包c3和c4经c1移位异或c2而得。该种再生码基于循环移位相加方式进行编码，因此称之为二进制循环移位再生码。该再生码因只运算在二元域上，因此其编解码的复杂度较低，重建带宽效率较高，是一种性能较好的分布式存储方案。但是，该再生码的节点可扩展性较差，目前只适用于4 个分布式存储节点，有比较大的局限性。

3 基于二元域循环移位的编码设计

3.1 编码方案

基于上文提到的再生码编码的思想，本文提出一种适用于8 个分布式存储节点的编码方式，不仅满足MDS 码性质，还操作在二元域，具有较低的编解码复杂度和较低的存储开销，同时提高了存储系统的安全性和容错能力，具体方案如下。

将数据存储在8个存储节点中。其中，节点1、节点2、节点3 和节点4 存储4 个原始数据包，节点5、节点6、节点7、节点8存储4个编码数据包。前4个节点称为数据节点，后4 个节点称为校验节点。在这8 个节点中，每个节点中都存储m 位的信息，且m为正奇数。该编码过程包括两个步骤：数据节点内冗余编码和校验节点内冗余编码。

1）数据节点内冗余编码

假设有一个大小为B 的文件需要存储，首先将B 均分为4 等份，每份大小为B/4，令每份大小为m-1，即B/3=m-1。分别记这4 等份数据为b1'、b2'、b3'、b4'。然后对b1'、b2'、b3'、b4'进行编码，得到b1、b2、b3、b4这4个数据包，每份大小为m。码编码过程为将4个数据包中的m 位信息分成两部分，第一部分为bi，0，bi，1，…，bi，m-2，i∈（1，2，3，4）；第二部分为bi，m-1，i∈（1，2，3，4）。其中，根据式（1）编码得到bi，m-1。

2）校验节点内冗余编码

设有公式：

由公式可定义c1，c2，c3和c4。b（z）是一个4维向量，其第i个组成部分是bi（z）。

对c1，c2，c3和c4这4 个数据包进行编码，得到编码数据包c5，c6，c7和c8。c1～c8都是原始数据b（z）的线性组合，有：

将c1（z）～c8（z）依次串联得到c（z），即矩阵c（z）是一个8维向量，其第i个组成部分是ci（z），有：

其中：

A（z）是一个8×4 的矩阵，ai，j是其第（i，j）个元素，i=1，2，…，8。

最后，将ci（z）对应的8 个数据包。分散存储在8个分布式节点中。

3.2 编码应用实例

一个根据编码方案构成的码长为5 位的二进制循环移位再生码数据包构成如表2 所示，其中，m=5，其中c1包含b1，j，这5 位信息，j∈（0，1，2，3，4）；c5包含b1，j1+b2，j2+b3，j3+b4，j4这5 位信息，其中j1=j2且依次取1，2，3，4，0，而j3=j4且依次取0，1，2，3，4。如表2所示。

3.3 解码过程

解码过程分4 种情况，下面分别阐述各种情况的解码过程。

1）三个数据节点、一个校验节点

首先，从c1，c2，c3，c4中任取3 个数据包ci1，ci2和ci3，i1，i2，i3∈｛1，2，3，4｝；再从c5，c6，c7和c8中取1个数据包ci1'，i1'∈｛5，6，7，8｝；将ci1，ci2和ci3代入ci1'可解出ci4，i4∈｛1，2，3，4｝｛i1，i2，i3｝。

2）两个数据节点、两个校验节点

首先，从c1，c2，c3，c4中任取2 个数据包ci1，ci2，i1，i2∈｛1，2，3，4｝；再从c5，c6，c7和c8中取2 个数据包ci1'，ci2'，i1'i2'∈｛5，6，7，8｝；解出bi，m-2，i∈｛1，2，3，4｝｛i1，i2｝，最后利用bi，m-2启动锯齿形解码过程。

3）一个数据节点、三个校验节点

首先，从c1，c2，c3，c4中任取1 个数据包ci1，i1∈｛1，2，3，4｝；再从c5，c6，c7和c8中取3 个数据包ci1'，ci2'，ci3'，i1'i2'i3'∈｛5，6，7，8｝；将ci1带入ci1'，ci2'，ci3'，取ci1'，ci2'，ci3'的所有奇数位信息ci1，k'，ci2，k'，ci3，k'，k=2n+1，n∈｛0，1，…，（m-3）/2｝，可以解出bi，1，i∈｛1，2，3，4｝｛i1｝，然后将其带入ci1'，ci2'，ci3'，可以解出bi，2，依次迭代，直到解出所有信息位。

4）四个校验节点

取c5，c6，c7和c8来恢复出数据节点中所有的信息位。取c5，c6，c7和c8的所有奇数位信息c5，k，c6，k，c7，k，c8，k，k=2n+1，n∈｛0，1，…，（m-3）/2｝，可以解出：b4，1=c8，0+c5，k+c6，k+c7，k，b3，1=c7，0+c5，k+c6，k+c8，k，b2，1=c6，0+c5，k+c7，k+c8，k，b1，1=c5，0+c6，k+c7，k+c8，k，然后将其带入c5，c6，c7和c8可以解出b1，2，b2，2，b3，2，b4，2，依次迭代，直到解出所有信息位。

4 实验及性能分析

4.1 安全性和可靠性

由上述编解码的方法可以知道，当偷窃者窃取到任意存储节点的数目小于4 时，都不能完整地译码出源始编码，因此，任何一个节点编码后的备份数据对于偷窃者来说都不可用。同时，当失效节点数小于4 时，就可以成功地恢复出原始的数据。实验结果如表3。

从实验结果可以看出，在失效节点数小于4时，备份数据均可以以100%的概率成功恢复。可知本文提出的编码方式提高了系统的安全性，同时与传统的编码方式相比较增加了存储系统的容错能力，提高了系统的可靠性。

表3 二进制循环移位再生码可靠性测试

4.2 计算复杂度

1）编码复杂度

（1）数据节点编码

对于一个大小为4（m-1）的文件，首先将其分等分为4 个数据包，每个数据包包含（m-1）个信息位。然后再对这4个数据包中的（m-1）个信息位进行XOR运算，得到数据节点中的4个校验位。该过程共需4（m-2）步XOR运算。

（2）校验节点编码

将c1，c2，c3，c4编码得到c5，c6，c7，c8。需要4×3×m=12m步XOR运算。

因此，整个编码过程的复杂度为O（4（m-2）+12m）=O（16m-8）。

2）解码复杂度

解码有4 种情况，下面分别4 种情况讨论解码复杂度。

（1）三个数据节点、一个校验节点

抓取个数据包ci1，ci2，ci3，ci1'，将ci1，ci2和ci3代入ci1'可解出ci4，i4∈｛1，2，3，4｝｛i1，i2，i3｝。

上述过程中，解出ci4中的一个信息位需要3 步XOR 运算，因此解出m 个信息位共需要3m 步XOR运算。综上所述，整个解码过程的复杂度为O（3m）。

（2）两个数据节点、两个校验节点

抓取数据包ci1，ci2，ci1'，ci2'，将ci1，ci2代入ci1'，ci2'该过程需要4m 步XOR 操作。解出bi，m-2和剩下的2m-1个信息位分别需要m-2和2m-1步XOR操作。

因此，整个解码过程的复杂度为O（7m-3）。

（3）一个数据节点、三个校验节点

抓取数据包ci1，ci1'，ci2'，ci3'将ci1代入ci1'，ci2'，ci3'该过程需要m 步XOR 操作。利用数据包ci1'，ci2'，ci3'中所有处于奇数位的信息ci1，k'，ci2，k'，ci3，k'，解出bi，1，i∈｛1，2，3，4｝｛i1｝，该过程需要3（m-1）步XOR 操作。解出余下的信息位bi，j的过程需要6（m-1）步XOR操作。

因此，整个解码过程的复杂度为O（10m-9）。

（4）四个校验节点

利用数据包c5，c6，c7和c8中所有处于奇数位的信息c5，k，c6，k，c7，k，c8，k解出bi，1，i∈｛1，2，3，4｝｛i1｝，该过程需要4（m-1）步XOR 操作。解出余下的信息位bi，j的过程需要12（m-1）步XOR操作。

因此，整个解码过程的复杂度为O（16m-16）。

3）实验验证

由上述分析可知，这种编解码方式复杂度与节点编码信息量参数m 呈线性关系。在不同的文件大小及不同容错参数下，对编解码时间进行了测试，结果如图1所示。

从图1（a）分析可知编解码时间随文件数据量的增加而呈线性增加趋势，图1（b）分析可知当文件数据量一定时，解码时间随着失效节点数增加呈增加趋势。传统的适用于4 个节点的编码方式只能容许2 个节点失效，虽然复杂度较低但是有比较大的局限性且灵活性不强，可以看出本文提出的编码方式相较传统的编码方式虽然时间复杂度略微有所增加，但是具有选取参数的灵活性和线性的运算复杂度的优势。

图1 编解码耗时随参数变化图

5 结语

本文分析了当前分布式存储系统中的常用的的冗余策略，并介绍了一种基于二元域异或操作的再生码，基于这种编码方式我们提出一种适用于8个分布式存储节点的编码方式，通过理论分析和初步实验得出它以数据恢复时间的略微增加为代价，换取了更高的存储系统安全性能，同时具有线性的编解码复杂度，提升了系统可靠性。