具有多个相交修复集的局部修复码的新构造

滕 佳 明

(复旦大学计算机科学技术学院上海市智能信息处理重点实验室 上海 200082)

0 引 言

进入大数据时代,传统的集中式网络存储已经难以满足日益增长的大规模存储空间的需求,而分布式存储系统因其海量存储能力、高扩展性和低成本的特点被广泛使用和开发。分布式存储系统规模往往非常庞大,一般包含几千到几千万个存储节点不等。然而数量庞大的节点集群经常会产生如网络中断、系统维修等故障,致使节点失效频发。分布式存储系统一般通过引入冗余来提高系统的容错性。良好的容错技术要求存储系统具有低的冗余开销、低修复带宽、高的错误容忍度。

最常见的容错技术是多副本机制,只要有一个副本可用,系统就可以容忍数据的丢失。但是其存储负载过大,存储效率很低。另一种常见的容错技术是纠删码。传统的纠删码使用MDS(Maximum Distance Separable)码,是一类存储开销与可靠性达到最优权衡的码,著名的Reed-Solomon码就是MDS码的典型代表。在纠删码分布式存储方案中,原始文件首先被分成k个数据块,接着编码成n个编码块,存储在n个节点中。当有存储节点失效后,访问任意k个节点就可以译码恢复出原始文件,然后再编码生成失效节点的数据。由于纠删码对原始数据进行了编码,所以减少了冗余占有的存储空间,提高了存储效率。但是在修复节点时,数据传输量远大于失效节点本身的数据量,当节点在网络中分布较分散时,节点的修复需要消耗大量的网络带宽。

针对纠删码的这一问题,Gopalan等[1]最早提出了局部修复码的概念。局部修复码修复任意一个节点只需要访问至多r<

但是当局部修复码的一个修复集中存在多个错误时,局部修复的特性便不再可用,退化到传统纠删码的修复策略。具有可用性的局部可修复码的提出就是为了解决该问题。在具有可用性的局部可修复码(即具有多个不相交修复集的局部可修复码)中,每个节点都对应多个彼此不相交修复集,其中每个修复集都可以单独用来修复故障节点。局部修复码中的可用性使得该编码可以对码字中的任意元素进行并行读取。该特性对于热数据(hot data),即同时会被大量用户同时访问的数据,是非常重要的。

关于具有可用性的局部修复码的研究相对于传统局部可修复码并不算多。文献[6-9]中给出了关于此类编码参数的界以及一系列构造。大部分关于此类编码的文献是关于信息位局部修复性以及可用性的[10]。但是局部修复码中的可用性会降低其可到达的码率上界[6]。

为了解决该问题,文献[10]提出了一类一般化的局部修复码,该构造允许码字中每个符号的不同修复集在少量坐标位置相交。这个特性使得这类编码可以达到更高的码率上界,并且同时可以保持局部可修复码的负载平衡特性。文献[10]还给出了一个该类编码的显示构造,并利用该类构造推导得出了该类编码的码率下界。

但是该类编码有一些局限性,虽然码率得到了提高,但是其编码的最小距离仅为2,这意味着该编码不容许出现任意一位以上的错误,容错性很差。本文提出的编码最小距离大于2,并且存在大量最小距离较大的实例,解决了该类构造编码最小距离过小的问题。本文推广了Wang等[14]提出的WZL码,使其适用于修复集可以相交的情况。事实上,WZL码是本文提出的构造的一个特例。同时本文给出了码率的上下界,通过程序发现存在许多码率大于WZL码的实例。本文研究了具有多个相交修复集的局部修复码,提出了一种新的构造方法。该编码是基于二元域的,因此编解码效率很高,具有一定的实用价值。本文提出的编码的最小距离优于文献[10]构造(目前唯一已知的修复集可以相交的可用性局部修复码构造),提供了更好的容错性。

1 预备知识

1.1 局部修复码

1.2 具有可用性的局部修复码

(1)

在下面简要的列举一些现有结论。第一个关于编码最小距离d的界由文献[11-12]给出:

(2)

文献[6]改进了上述界,表示为:

(3)

同时该文献也给出了(r,t)-LRC码率的界:

(4)

该界同时适用于线性和非线性码。文献[13]给出了针对线性码更紧的界,表示为:

(5)

1.3 WZL码

由于本文的编码构造依赖文献[14]中的编码构造思想的,因此在这里介绍一下WZL码的相关概念。

(6)

上述定义的矩阵H(m,t)具有如下结构:

(7)

式中:H(m,m)=H(m,1)T=(1,…,1)T,且dim(H(m,1))=dim(H(m,m))=m。同时,文章也给出了上述矩阵的秩。

1.4 具有多个相交修复集的局部修复码

现在将(r,t)-LRC推广至允许修复集合最多相交x位的情况,文献[10]给出了(r,t,x)-LRC的定义。

(1) 对于每一对l,l′∈[t],l≠l′:

(8)

(2) 对于所有j=1,…,t以及码字中的一对元素a,a′∈q,a≠a′,有:

(9)

文献[15]给出了(r,t,x)-LRC的最小距离上界。

(10)

接下来对(r,t,x)-LRC的概念做一个扩展,给出信息位(r,t,x)-LRC的定义:

(1) 对于每一对l,l′∈[t],l≠l′:

(11)

(2) 对于所有j=1,2,…,t以及码字中的一对元素a,a′∈q,a≠a′:

(12)

2 具有全局修复性的(r,t,x)-LRC新构造

这一节正式提出具有全局修复性的(r,t,x)-LRC的构造方法。本文将WZL码的构造方法加以推广,使其修复集合可以相交,并给出该构造的码率和最小距离的上下界。

2.1 构造方法

该构造基于校验矩阵。对于任意的正整数a、b、m,满足a

(13)

下面给出一个H(m,a,b)的具体例子。

例1由H(5,1,3)作为校验矩阵的编码,可以得到r=6,t=3,x=2,该编码的码长为10,维度为5,码率为1/2,最小距离为4。

接下来证明该矩阵H(m,a,b)的一些性质来帮助理解该编码。

2.2 H(m,a,b)的性质

引理4对于任意的正整数a、b、m,满足a

(14)

下面给出了矩阵H(m,a,b)的秩的一些性质。

推论1rank(H(m,a,b))≥max{rank(H(m-1,a,b)),rank(H(m-1,a-1,b-1))+rank(H(m-1,a,b))}

(15)

其中:

(16)

上述推论是关于矩阵H(m,a,b)的秩的一个粗略估计,若去掉其中的max函数,仅取:

rank(H(m,a,b))≥rank(H(m-1,a-1,b-1))+

rank(H(m-1,a,b))

(17)

利用上述推论,可以通过递推式计算出rank(H(m,a,b))的最小值。方法如下:

将矩阵H(m,a,b)的秩视为一个数列,记为P数列的第一项P1=rank(H(m-a,0,b-a)),第二项P2=rank(H(m-a,1,b-a)),第三项P3=rank(H(m-a,1,b-a+1)),第四项P4=rank(H(m-a+1,1,b-a+1)),以此类推,数列的第n项为:

(18)

则P3a+1=rank(H(m,a,b))。

结合推论1可得:

rank(H(m,a,b))=P3a+1≥P3a+P3a-2

(19)

然后计算a=1时矩阵秩的最小值:

rank(H(m,1,b))≥rank(H(m-1,0,b-1))+

rank(H(m-1,1,b))=

1+rank(H(m-1,1,b))≥

2+rank(H(m-2,1,b))≥

⋮

m-b+rank(H(b,1,b))=

m-b+1

(20)

可以得到该数列的初始值:

P1=1

P2≥m-b+1

P3≥m-b

P4≥m-b+1

(21)

由此,问题便化简为解一个三阶线性递归序列,其特征方程为λ3-λ2-1=0。具体求解过程可以参考相关文献。由于该结果较为复杂,故不在此列出。

综上结果,可以给出该编码的维度的取值范围。

引理5以矩阵H(m,a,b)作为校验矩阵的编码的维度为:

(22)

推论2以矩阵H(m,a,b)作为校验矩阵的编码的码率界为:

(23)

最后说明该编码最小距离的性质。

引理6以H(m,a,b)作为校验矩阵的编码的最小距离d≥3。

证明要证明最小距离d≥3,只需证明校验矩阵H(m,a,b)任意两列不相等。矩阵中任意两列的关联集合至少有一位不相等,记为x1∈Fi,x1∉Fj,x2∈Fj,x2∉Fi,而每一行的关联集合都不相等,所以必定存在一行的关联集合E包含x1∈E,但不包含x2∉E,剩下的元素包含在Fi中,所以E⊆Fi,EFj,因此i列和j列不相等,得证。

再结合式(1)与式(4),可以给出该编码最小距离的界:

推论3以H(m,a,b)作为校验矩阵的编码的最小距离的取值范围:

(24)

2.3 对比其他构造

目前,关于具有相交修复集的局部修复码的构造还很少,仅有的一篇为文献[10]利用WZL码给出了一类(r,t,x)-LRC的显示构造。首先选择一个(r,t)-WZL码的校验矩阵H(r+t,t),之后利用H(r+t,t)构造一个(r,t,x)-LRC的校验矩阵H,构造方法如下:

(25)

但是当x≥1时,其校验矩阵的每一列都有x列与其相等,所以用这种方法构造的编码的最小距离仅为2。当该编码出现大于1个错误时,该编码无法恢复原有码字。

而本文构造的编码最小距离大于2,并且存在大量最小距离达到t+1的例子,现举一例如下:

例2由H(7,2,4)作为校验矩阵的编码,可以得到r=9,t=6,x=3的,该编码的码长为35,维度为14,码率为2/5,最小距离为7。

表1列出了更多关于最小距离的例子。

表1 (r,t,x)-LRC最小距离对比

相较于WZL码,本文的编码在一些情况下码率大于(r,t)-WZL码,在此举出一例:

例3由H(7,1,4)作为校验矩阵的编码,可以得到r=19,t=4,x=9,该编码的码长为35,维度为29,码率为29/35,最小距离为3。与其对应的(r=19,t=4)-WZL码的码率为19/23<29/35。

表2列出了一些在r、t相同时WZL码与本文构造的码率对比。

表2 (r,t)相同时码率对比

表3列出了WZL码[14]、Kruglik等[10]构造的码与本文构造三者的参数对比。

表3 三种构造参数对比

3 构造信息位的(r,t,x)-LRC

由于矩阵H(m,a,b)的秩很难求出,只能得到该构造的一个不紧的码率上下界,所以考虑构造信息位的(r,t,x)-LRC来解决此问题。

构造一个校验矩阵H′(m,a,b):

(26)

证明由定理1证明可知,这等同于证明矩阵H′(m,a,b)的每一行都有r+1个1,信息位的每一列有t个1,任意两列有最多x+1个元素相交。

(27)

由此可见,该编码的码率与WZL码相同。

例4由H′(5,1,3)作为校验矩阵的编码,可以得到r=6,t=3,x=3,该编码的码长为15,维度为10,码率为2/3,最小距离为4。该编码码率与最小距离WZL码一致。

4 结 语