一种基于分布式存储系统的Piggyback码

周 悦，李贵洋，江小玉，李 慧，韩鸿宇

(四川师范大学 计算机科学学院， 成都 610101)

E-mail ：gyli@sicnu.edu.cn

1 引 言

随着数据信息量的爆炸式增长，分布式存储系统由于其数据存储的可靠性和高效性而备受关注.在分布式存储系统中，一份完整的数据被分块存储在一系列存储节点上，这些存储节点在物理上是相互独立的，并通过网络进行通信访问.然而，存储节点经常会因为软、硬件故障或者系统维护升级等原因产生暂时或永久的失效，尤其对于现有的具有超大规模的存储集群，其存储节点的数量十分庞大，因此发生节点失效已是常态[1,2].于是，分布式存储系统便引入冗余以确保可靠性，在分布式系统中常用两种冗余策略：副本和纠删码，副本策略易于实现但会耗费大量的存储空间，而纠删码能在保证相同的可靠性的情况下，大大提升存储效率[3,4].为了处理海量的信息，许多分布式存储系统都采用纠删码冗余策略，比如Google GFS[5]，Hadoop HDFS[6]，以及Microsoft Azure[7].

在采用纠删码[8]的分布式存储系统中，一旦发生存储节点失效，便从其他未失效的节点上读取数据来修复失效节点上的数据.MDS码[9]是一种广泛用于数据存储的纠删码，它在存储效率和可靠性权衡方面是最优的，然而，仅为了修复单个失效节点，MDS码却下载了相当于整个原始数据的数据量.2010年，Dimakis等人[10]引入了再生码的概念，以减少分布式存储系统中节点失效时的修复带宽，其通过从每个未失效的节点中下载部分数据来修复失效节点，MSR码作为最重要的再生码之一，其不仅保持了MDS性质，还具有较低的修复带宽.但是，具有显式构造的MSR码都是低码率的，冗余度高，而构造高码率的MSR码，其条带数为数据节点数k的指数级[11]，显然，如此庞大的条带数将产生大量的文件碎片读取，这对于磁盘性能是十分不利的.

2013年，Rashmi等人[12]提出了Piggybacking框架的概念，并在2017年对文章内容进行了改进和完善[13]，其生成的Piggyback码在不添加额外存储空间的情况下，不仅保留了MDS性质，还具有较低的修复带宽，并且不受编码参数的限制.同年，具有实践意义的Piggybacked-RS码[2]被Facebook公司提出，并用于新的分布式存储系统的设计以提高节点修复性能.2015年，Piggyback码中的RSR-I码在HDFS上得到实现[14].随后，有关piggyback码的其它研究成果不断地被提出[15-18]，可见，Piggyback码因其既能保持MDS性质，又能降低修复带宽，还易于工程实现而被日益重视.

在本文中，用平均修复带宽率γ来衡量修复失效节点时的修复带宽[13]，用有限域上的乘法计算量[15]来衡量编码复杂度E和修复复杂度R.针对Piggyback码中减少修复带宽方面最典型的RSR-II码，所存在的修复失效节点时需要在有限域上求解方程组的问题，提出了一种新的Piggyback码，该码基于分布式存储系统中广泛使用的系统型MDS码，在实例数要求和修复带宽方面，保持了RSR-II码的低实例数和低修复带宽优点，并通过构造新的piggybacks添加规则，既降低了编码过程的复杂性，还避免了RSR-II码在修复失效节点时需对方程组进行求解，具有更低的编码复杂度和修复复杂度.

本文的其余部分组织如下：第2节介绍了相关理论基础；第3节详细阐述了新的Piggyback码的一般性构造及修复算法；第4节将新的Piggyback码和RSR-II码在编码复杂度和修复复杂度上进行了对比分析，并得出了相关结论.最后，对全文进行了总结.

2 相关理论基础

2.1 系统型MDS码

MDS码是纠删码中很重要的一类，一个(n，k)-MDS码先将原始数据分割成k份，再将这k份数据进行编码生成n份编码数据分别存储到n个存储节点(Node)上，其可以通过任意k个存储节点上的全部数据来恢复原始数据，换句话说(n，k)-MDS码可以容忍任意r(r=n-k)个存储节点失效，该性质被称为MDS属性.系统型MDS码是指原始的数据被分割后以未被编码的形式分别存储在k个节点上，这些节点被称为系统节点，而剩余的r个节点上存储的是k个系统节点上的数据进行线性组合后的编码结果，被称为校验节点.从实际应用的角度来看，系统型MDS码具有更优的性质，因为其可以直接从系统节点上读取原始数据而不需要进行解码操作.

图1 系统型(6，4)-MDS码

2.2 Piggybacking框架

图2 Piggybacking框架

2.3 RSR-II码

vi=ar-1+iar-2+i2ar-3+…+ir-2a1

(1)

(2)

由于篇幅所限，RSR-II码的编码构造及修复算法详见文献[13].下面给出RSR-II码的例子，该例子以系统型(13，9)-MDS码作为基础码，校验节点的个数为r=4，因此实例数为2r-3=5.首先，对基础码添加piggybacks后如图3(a)所示，然后，在同一节点的不同实例间进行可逆线性变换，得到最终的编码结果如图3(b)所示.

图3 RSR-II码例子

3 新的Piggyback码

3.1 新的Piggyback码例子

本小节的例子同样是以系统型(13，9)-MDS码作为基础码，校验节点的个数r=4，其实例数也为2r-3=5.首先，将系统节点均分到r-1=3个节点集中，S1={1，2，3}，S2={4，5，6}，S3={7，8，9}.向量p1，p2，p3，p4是长度为k=9的编码向量，对应于基础码的4个校验节点，定义如下：

p1=[p1，1p1，2p1，3p1，4p1，5p1，6p1，7p1，8p1，9]

p2=[p2，1p2，2p2，3p2，4p2，5p2，6p2，7p2，8p2，9]

p3=[p3，1p3，2p3，3p3，4p3，5p3，6p3，7p3，8p3，9]

p4=[p4，1p4，2p4，3p4，4p4，5p4，6p4，7p4，8p4，9]

对于2≤i≤4，选择向量定义如下：

qi，1=[pi，1pi，2pi，30 0 0 0 0 0]

qi，2=[0 0 0pi，4pi，5pi，60 0 0]

qi，3=[0 0 0 0 0 0pi，7pi，8pi，9]

图4 新的Piggyback码例子

3.2 新的Piggyback码的一般性构造

在新的Piggyback码的编码构造中，其基础码的实例数为m=2r-3(r≥3)，可用{a1，a2，…，a2r-3}表示各实例对应的长度为k的数据向量，用{p1，p2，…，pr}表示长度为k的编码向量，其对应于基础码的r个校验节点上的r个编码函数.新的Piggyback码的piggyback函数是前r-1个实例中的系统节点上数据的线性组合，所得到的值为piggybacks，将会被添加到后r-1个实例中的后r-1个校验节点上.构造新的Piggyback码的过程如下：

图5 新的Piggyback码的一般性构造

并且有

最后，对后r-1个校验节点上的数据分别在实例间进行可逆线性变换，从第r-1个实例中减去后r-2个实例上的数据，得到最终的编码构造如图5(b)所示.

在新的Piggyback码的构造中可以看出，新的Piggyback码不再是将前r-1个实例中的系统节点数据都添加到后r-2个实例中，而是将前r-2个实例与后r-2个实例一一对应，并分别添加前r-2个实例中系统节点的数据到后r-2个实例中，并且需满足前r-2个实例中位于不同节点集中的数据都能够分别添加到后r-2个实例的后r-1个校验节点上，这样既保证了后r-2个实例的后r-1个校验节点中添加的piggybacks只含有ar-1和对应的一个aj，j∈{1，…，r-2}属于同一个节点集中的数据，由于前面已恢复ar-1，因此只需要下载aj，j∈{1，…，r-2}中失效节点所在的节点集中的其他未失效节点的数据即可恢复，这样的添加规则，在减少了修复所需的数据下载量的同时，使得最后求解的是独立的方程，而不是方程组的求解，故无需引入系数向量来确保方程组可解，降低了编码复杂度和修复复杂度.

3.3 新的Piggyback码的修复算法

假设在新的Piggyback码中失效的系统节点为μ，即需要恢复的数据为{aμ，1，aμ，2，…，aμ，2r-3}，下面给出失效节点μ的修复算法：

首先，从后r-2个实例的节点{1，2，…，k+1}/μ中下载全部数据，由基础码的MDS性质，可分别从每一个实例中进行解码操作，得到失效的数据{aμ，r，…，aμ，2r-3}.

然后，在第r-1个实例中，总会在节点{k+2，…，k+r}中找到一个节点包含失效数据aμ，r-1，由于ar，…，a2r-3已通过上一步获得，故可以通过继续下载含有aμ，r-1的节点集中其他未失效数据来解线性方程恢复aμ，r-1.

最后，在后r-2个实例中，总会在节点{k+2，…，k+r}中找到分别包含失效数据{aμ，1，aμ，2，…，aμ，r-2}的节点，由于ar，…，a2r-3已获得，并且上一步已恢复aμ，r-1，故可以通过分别下载含有{aμ，1，aμ，2，…，aμ，r-2}的节点集中其他未失效数据来求解r-2个独立的线性方程分别恢复{aμ，1，aμ，2，…，aμ，r-2}，修复完成.

从上述修复过程可以看出，在第一步中的数据下载量为(r-2)k，如果节点集Si的大小为th，在第二步中的数据下载量为th，在最后一步中的数据下载量为(r-2)th，否则节点集Si的大小为tl，在第二步中的数据下载量为tl，在最后一步中的数据下载量为(r-2)tl.由上一小节可知，在大小为th的节点集中的系统节点数为tth，在大小为tl的节点集中的系统节点数为(r-1-t)tl.下面得出新的Piggyback码的平均修复带宽率如公式(3)所示：

(3)

(4)

由上述修复算法和平均修复带宽率分析可见，新的Piggyback码在修复失效节点时无需进行有限域上方程组的求解操作，并且保持了RSR-II码的平均修复带宽率.

4 复杂度对比分析

4.1 编码复杂度

在对原始数据进行计算生成编码数据的过程中，系统型MDS码仅需通过k个系统节点进行线性组合生成校验节点，生成一个校验节点包含了k次乘法运算和k-1次加法运算，其复杂度为ke2+(k-1)e，为方便后续表达，令x=ke2+(k-1)e.系统型MDS码需要生成r个校验节点，则其复杂度为rx，忽略复杂度较低的加法运算可得，系统型MDS码的编码复杂度为EMDS=rke2.

新的Piggyback码也将原始数据分为了2r-3个实例，其生成校验节点的复杂度为(2r-3)rx，接着根据新的Piggyback码添加piggybacks的规则，其复杂度为2(r-2)(r-1)se2+(r-2)(r-1)e，最后在实例之间进行可逆线性变换，其复杂度为(r2-3r+2)ke，将全过程省略复杂度较低的加法运算可得，新的Piggyback码的编码复杂度为ENew=(2r2-3r)ke2+(2r2-6r+4)se2.

图6(a)中比较了RSR-II码和新的Piggyback码在几种常用(n，k)码的(k，r)参数下的编码复杂度的对比图，图6(a)中以编码过程中所进行的乘法计算量作为衡量编码复杂度的标准，从图6(a)中可以看出，相比校验节点数r，编码复杂度受系统节点数k的影响减少幅度更大，随着系统节点k和校验节点r数量的增加，新的Piggyback码相比RSR-II码都拥有更低的编码复杂度.

4.2 修复复杂度

在修复过程中，系统型MDS码修复单个失效系统节点仅需要解决线性组合问题，其中进行了k次乘法运算和k-1次加法运算，其复杂度为ke2+(k-1)e，即x，省略复杂度较低的加法运算可得，系统型MDS码的修复复杂度为RMDS=ke2.

在RSR-II码和新的Piggyback码修复失效节点的过程中，由RSR-II码和新的Piggyback码的修复算法可知，在第一步中由基础码的MDS性质需要求解r-2个线性组合问题，其复杂度为(r-2)x.在第二步中，需要减去r-2个校验节点的数据得到含有失效节点的节点数据集的线性组合方程，再减去节点集中已知的节点数据即可得到失效节点数据，其复杂度为(r-2)(x+e)+se2+(s-1)e.在最后一步中，RSR-II码需要减去r-2个校验节点的数据以及r-2个节点集的线性组合数据来得到含有r-2个方程的方程组，其中每个方程含有r-2个未知数，考虑通过Gauss消元法进行求解[19]，解方程组过程中的乘法计算量为(r-2)3，其复杂度为(x+se2+(s+1)e)(r-2)+(r-2)3e2.与RSR-II码不同的是，在最后一步中，新的Piggyback码仅需分别减去r-2个校验节点的数据以及r-2个节点集的线性组合数据来得到r-2个独立的方程，其中每个方程只含一个未知数，因此不需要进行有限域上方程组的求解，具有更低的复杂度为(x+se2+(s+1)e)(r-2)+(r-2)e2.将全过程省略复杂度较低的加法运算可得，RSR-II码的修复复杂度为RRSR-II=(3rk+rs-6k-s)e2+(r-2)3e2，新的Piggyback码的修复复杂度为RNew=(3rk+rs-6k-s)e2+(r-2)e2.

图6 复杂度对比图

表1 系统型MDS码、RSR-II码和新的Piggyback码对比表

图6(b)中比较了RSR-II码和新的Piggyback码在几种常用(n，k)码的(k，r)参数下修复单个失效系统节点时修复复杂度的对比图，图6(b)中同样以修复过程中所进行的乘法计算量作为修复复杂度的衡量标准.其中，当校验节点数为3时，RSR-II码的方程组中方程的个数为1，故在(9，6)码的参数下RSR-II码和新的Piggyback码的修复复杂度相同.另外，从图6(b)中可以看出，相比系统节点数k，修复复杂度受校验节点数r的影响减少幅度更大，随着系统节点k和校验节点r数量的增加，新的Piggyback码相比RSR-II码都拥有更低的修复复杂度.

4.3 综合分析

表1中将系统节点数为k，校验节点数为r的系统型MDS码、RSR-II码和新的Piggyback码在实例数、平均修复带宽率、编码复杂度以及修复复杂度方面进行了比较.从表1中可以看出，系统型MDS码虽然具有较少的实例数和较低的编码复杂度和修复复杂度，但在面对频繁的失效节点修复时，其修复带宽太高，RSR-II码和新的Piggyback码通过增加实例数并且在实例上添加piggybacks，以编码复杂度和修复复杂度为代价来实现了修复带宽的降低.本文提出的新的Piggyback码相比RSR-II码在具有相同的平均修复带宽率的同时，使其编码复杂度和修复复杂度得到了进一步的降低.

5 结束语

本文提出了一种新的Piggyback码，并给出了编码的一般性构造和修复算法，相比已有的RSR-II码，其在保持同样较低的平均修复带宽率的情况下，降低了编码复杂度和修复复杂度.此外，在大数据时代海量数据存储的背景下，对于减少现代分布式存储系统中修复带宽和计算负载的编码已有很多其他的理论研究成果，但这些编码要么在校验节点数量的选择上存在限制，要么需要额外的存储空间，而Piggybacking框架无需增加额外的存储空间，并且在参数选择上也灵活自由.因此，考虑设计不同的Piggyback码可为构建现代分布式存储编码提供丰富的设计空间，可作为以后研究的重点.