基于正交拉丁方的局部修复码构造

刘帅帅，王静，刘哲，徐忠环

(长安大学 信息工程学院，陕西 西安 710064)

分布式存储系统在云计算时代得到了广泛应用[1].为了保证系统的持续可靠运转，须采用冗余策略来应对系统中的节点故障[2].“复制”策略操作简单，但存储效率较低；纠删码均衡了存储开销和纠错性能，但在修复过程中须重构原始文件，带来巨大的修复带宽开销[3].

Gopalan等[4]提出局部修复码(locally repairable codes,LRCs).当一个数据节点发生故障时，系统会通过获取r(r≪k) 个节点的数据在局部组内修复故障节点，而不再重构原始文件，带来了修复过程中带宽消耗与磁盘访问数量的减少，有效地提高了修复效率.文献[4]证明 (n,k,r) 局部修复码最小距离满足Singleton-型界，其中，n为码长，k为码字中信息位个数，r为局部性参数.Tamo等[5]利用RS码和特殊的MDS码构造了一类最小距离最优局部修复码，但须在较大的有限域上编码，增加了实现的复杂性.Jin等[6]利用有理函数域上的自同构群推广了RS码的构造，得到一类字母表大小与码长相当的最小距离最优局部修复码，但参数须满足 (r+1)|n.Luo等[7]基于循环码和校验多项式构造了一类码长与字母表大小无关的局部修复码，但只有在最小距离d∈{3,4} 时才能实现最小距离最优.

为了实现多故障节点修复，文献[8]提出具有(r,t)局部性的局部修复码，不相交的t个修复集提高了系统的鲁棒性，同时支持数据的并行读取.其中，t表示可用性参数.Jin等[9]利用有理函数域上的自同构群构造了具有多个修复集的局部修复码，但码的最小距离没有达到上界且没有考虑码率.Hao等[10]通过替换正则矩阵中特定行和列的方法，得到一类参数为 (r,t,δ) 的最小距离最优局部修复码，但字母表大小须满足q≥r+δ-2，且码率较低.Ma等[11]利用弱独立集构造出维度最优的二元线性局部修复码，但其参数须满足r∈{2,3}.Tan等[12]利用线性代数和部分几何构造信息位具有 (r,t) 局部性的局部修复码，其最小距离最优且码率较高，但当可用性较大时构造复杂度较高.Hao等[13]研究LDPC码与局部修复码之间的关系，并构造3种信息位具有 (r,t) 局部性的局部修复码，实现了最小距离最优.其中，第1种基于射影平面的构造码率只有0.5，参数须满足r=t；第2种删除仿射平面中特定点线的构造方法与第1种构造方法的性能相同；第3种基于阵列LDPC码的构造须对循环排列矩阵进行多次矩阵乘法运算，带来较大的计算开销.

针对上述问题，提出基于正交拉丁方的二元局部修复码构造方法，无须生成抽象几何图形和矩阵乘法运算，减小了构造复杂度.根据正交拉丁方元素与矩阵位置的对应关系构造关联矩阵，得到一类具有全符号局部性的局部修复码，该码的码率和码长渐近边界条件；将关联矩阵级联一个单位矩阵，构造出一类信息位具有 (r,t=2) 局部性的单校验局部修复码，该码的最小距离和码率均满足边界条件，为最优局部修复码.为了修复系统中的高故障率节点，利用正交拉丁方完备组构造一类具有高可用性的单校验局部修复码，可根据节点故障概率来选择可用性t，提高系统的鲁棒性.

1 背景知识

1.1 局部修复码

定义1 具有(r,t) 局部性的局部修 码[8].在有限域Fq中的[n,k,d]q线性分组码，给定集合{1,2,···,n}，c=[c1,c2,···,cn] 是一个码字，如果其中 一个码元符号ci具有局部性r和可用性t，那 么须满足以下条件：

1）存在t个子集，R1(i),···,Rt(i)⊂{1,2,···,n}{i}，满足

2）Rj(i)∩Rl(i)=Ø，j≠l且j,l∈{1,2,···,t} ；

3）ci∈span(cl)，其中l∈Rj(i),j∈{1,2,···,t}，即向量ci属于张成的线性空间.其中，称Rj(i) 为ci的局部 修复组.

对于 (n,k) 局部修复码，若其所有符号都具有 (r,t) 局部性，则称该码为具有全符号局部性的局部修复码(all symbol-locally repairable codes,AS-LRCs)；若只有信息位符号具有 (r,t) 局部性，则称为具有信息符号局部性的局部修复码(information symbol-locally repairable codes,IS-LRCs)[8].

Rawat等[8]证明了当每个局部修复组中只包含一个校验符号时，信息位符号具有 (r,t) 局部性LRCs的最小距离界为

满足边界条件(式(1))的LRCs，称为最小距离最优的LRCs.

Tan等[12]证明对于信息位符号具有 (r,t) 局部性的 [n,k,d]q局部修复码，其最小距离满足

Tamo等[14]提出具有 (r,t) 局部性的LRCs码率边界为

式中：R为码率.

Prakash等[15]提出，当可用性t=2 时，(n,k,r,t=2)-LRCs的码率边界和码长边界为

1.2 拉丁方

定 义2 拉丁方[16].设S={1,2,···,n} 为n元 集合为集合S上的n阶方阵.如果方阵L的每行每列都是集合S中元素的一个全排列，则称L为S上的一个n阶拉丁方.

定理1[16]对于n元集S上的拉丁方，若n≠2,6，则必然存在一对n阶正交拉丁方.

定义4 正交拉丁方组[16].对于n元集S上的t(t≥2) 个拉丁方，若它们两两正交，则它们组成n阶(t个)正交拉丁方组.

定 理2[16]用N(n) 表 示n阶正交 拉丁方组中拉丁方的最大个数，则N(n)≤n-1.

定义5 正交拉丁方完备组[16].若n阶正交拉丁方组中含有N(n)=n-1 个拉丁方，则称为n阶正交拉丁方完备组.

定理3[16]若q为素数，v为正整数，p=qv为素数幂，且p≥3，则存在p阶正交拉丁方完备组.

定义6 支撑集[17].给定向量v=[v1,v2,···,vn]，则它的支撑集为 supp(v)={i|vi≠0},i=1,2,···,n.

2 具有全符号局部性的局部修复码构造

设集合 Ω={1,2,···,m2}，矩阵X为由集合 Ω 中m2个元素排列成的m阶方阵，即

定理4将 关联 矩阵作为校验矩阵H1，可以构造参数为n=m2、k=(m-1)2、t=2、r=m-1的AS-LRCs，其中m≥3 且m≠6.

证明由关联矩阵可知构造的局部修复码的码长n=m2，由于集合 Ω 中的每个元素在集合B1和B2中分别只出现1次，在集合B中共出现2次，故关联矩阵中所有行向量构成了一个线性相关组，且其中不存在零向量.用bi(1≤i≤2m) 表示关联矩阵的行向量，bi≠0，将所有行向量按分量相加得到零向量，即随机删除1个行向量bl(l∈{1,2,···,2m})，根据正交拉丁方的正交性，剩余的行向量构成线性无关组.因此关联矩阵的秩为局部修复码的维度为k=m2-(2m-1)=(m-1)2.关联矩 阵每列汉明重量为2，且每列“1”元素所在的行向量的支撑集只在该“1”元素坐标处相交，所以每个符号位具有2个不相交的局部修复组，即可用性t=2.关联矩阵每行汉明重量为m，当某个符号位丢失时须获得另外m-1 个符号位的信息才能恢复，故修复局部性r=m-1.

由集合B和集合 Ω 的映射关系易得关联矩阵：

将关联 矩阵M6×9作 为校验矩 阵H1，可以构造参数为n=9、k=4、t=2、r=2 的AS-LRCs.若 码元符号c1故 障，其修复集为R1(1)={6,8} 和R2(1)={5,9}，故c1=c6⊕c8=c5⊕c9，其中 ⊕ 表示异或运算.其他码元符号可以通过类似的方法进行修复.

定理5定理4构造的AS-LRCs的最小距离为d=4，且d＞t+1.

证明AS-LRCs的最小距离d=4 表明其校验矩阵H1即关联矩阵中任意3列线性无关，且存在4列线性相关.

1）若3列选自同一组，则对应于拉丁方同一行上的3个不同元素，由拉丁方的性质可知这3个元素处于不同的m-子集中，故这3列必然线性无关，如例1中 {h1,h2,h3} ；

2）若3列中2列选自同一组，剩余1列选自其他组，同一组的2列必然线性无关，同组的2列相加可以得到一个汉明重量为4的列向量，而选自其他组的列向量汉明重量为2，因此这3列必然线性无关，如例1中 {h1,h2,h4} ；

3）若3列分别选自不同组，且对应于拉丁方中3个不同的元素，则与3列选自同一组的情况1)相同，3个列向量线性无关，如例1中 {h1,h4,h7} ；若选自不同组的3列对应于拉丁方中2个不同的元素，则对应于同一个元素的2列相加可以得到一个汉明重量为2的列向量，且2个“1”元素所在的2行所对应的m-子集处于同一个Bh(h=1,2)中，而剩余1个列向量中“1”元素所在的2行所对应的m-子集分别处于不同的Bh(h=1,2) 中，故这3列必然线性无关，如例1中 {h1,h6,h7} ；若选自不同组的3列均对应于拉丁方中同一个元素，则3列所对应的集合 Ω 中的元素所构成的子集只能在Bh(h=1,2)中某个m-子集出现一次，在另一个集合Bh(h=1,2) 中，子集中3个元素必处于3个不同的m-子集中，故这3列必然线性无关，如例1中 {h1,h6,h8}.综上所述，关联矩阵中任意3列线性无关，所以d≥4.

综上所述，定理4构造的AS-LRCs最小距离为d=4，且满足d＞t+1=2+1=3，得证.

如表1所示为几种典型的AS-LRCs在可用性t=2 时的参数.表中，w为任意正整数，m(m≥3,m≠6) 为拉丁方的阶数.可以发现，当可用性t=2时，定理4构造的AS-LRCs最小距离最大，并且满足d＞t+1.

表1 几种典型AS-LRCs构造参数对比Tab.1 Comparison of structural parameters of several typical AS-LRCs

由于不存在一对6阶的正交拉丁方，定理4无法构造局部性r=5 的AS-LRCs.下面通过改变集合的构造方法，可以得到任意局部性r≥2 的AS-LRCs.

定理6在m阶方阵X上叠合一个m阶标准型拉丁方，即该拉丁方第1行与第1列的元素均按顺序排列.集 合仍然利用前面的方法构造，而集合则利用标准型拉丁方每列元素在方阵X中对应的位置索引构 造，集 合B=B1∪B2.将集合B和集合Ω 的关联矩阵作为校验矩阵，可以构造参数为n=m2、=(m-1)2、t=2、r=m-1 的AS-LRCs，其中m≥3.

可以证明定理6构造出来的AS-LRCs最小距离仍满足定理5.

例2当m=6时，Ω={1，2，···，36}，方阵X为

6阶标准型拉丁方如下：

由集合B和集合Ω 的映射关系得到关联矩阵M12×36，将其作为校验矩阵可以构造一个参数为n=36、k=25、t=2、r=5的AS-LRCs.

所构造的AS-LRCs码率为

如图1所示为定理6构造的AS-LRCs码率与Prakash等[15]提出的码率边界的比较.图中，R为码率，R=k/n.可以发现，随着局部性参数r的增大，即拉丁方阶数m的增大，AS-LRCs的码率将逐渐接近码率边界，即式(4)中的边界条件.

图1 可用性 t=2 时的码 率比较Fig.1 Code rate comparison with availability t=2

不过，由于

定理6中的AS-LRCs码率始终小于边界条件(式(4)).

将码的参数代入码长边界（式(5)），可以得到

可以看出，定理6构造的AS-LRCs码长仅比最优码长界大1，能够更好地均衡系统的冗余.

3 具有信息位局部性的局部修复码构造

3.1 信息位具有 (r,t=2) 局部性的局部修复码

证明由校验矩阵H2可知构造的局部修复码的码长n=2m+m2，且右边级联单位矩阵I2m×2m使得校验矩阵H2满秩，因此局部修复码的维度矩阵H2的前m2列对应信息位符号，后 2m列对应校验位符号.关联矩阵中每列的汉明重量为2，且每列“1”元素所在行向量的支撑集只在该“1”元素坐标处相交，所以每个信息位具有2个不相交的局部修复组，即可用性t=2.同时，校验矩阵H2每行的汉明重量为m+1，当某个信息位符号丢失时须获得另外m个符号位的信息才能恢复，故修复局部性r=m，且每个局部修复组中只有一个校验符号.

定理8定理7构造的IS-LRCs的最小距离为d=3，且最小距离最优.

证明校验矩阵H2的前m2列汉明重量均为2，后2m列为单位矩阵I2m×2m.从校验矩阵H2的前m2列中任选一个列向量，表示为ξ，它是单位阵I2m×2m中特定2列的线性组合，故矩阵H2中存在3列线性相关，d≤3.另一方面，从校验矩阵H2中任选2个列向量 {hs1,hs2}，其中 1 ≤s1,s2≤2m+m2，若2列都选自单位阵I2m×2m，显然它们线性无关；若2列都选自关联矩阵类似于定理5可以证明它们线性无关；若其中一列选自单位阵I2m×2m，另一列选自关联矩阵由于列重不同，它们必然线性无关.因此，校验矩阵H2中任意2列线性无关，从而d≥3.综上所述，定理7构造的IS-LRCs的最小距离为d=3.

将参数n=2m+m2、k=m2、t=2、r=m代 入最小距离边界条件(式(1))，可得

满足边界条件(式(1))，所以定理7构造的ISLRCs最小距离最优.

定理7构造的IS-LRCs码率为

满足码率边界条件（式(4)），因此定理7构造的IS-LRCs码率最优.

此外，局部性r与维度k的比值为

即当系统发生单节点故障时，新生节点需要连接的帮助节点数仅为同参数下纠删码的 1/m，能够有效降低修复过程中的磁盘I/O开销，加快修复效率.

3.2 信息位具有 (r,t) 局部性的局部修复码

3.1节构造的IS-LRCs的可用性参数仅局限于t=2，对于存储系统中的高故障率节点，可能无法确保数据的可靠访问，须为其提供更高等级的保护.利用正交拉丁方完备组构造可以灵活调节可用性参数的局部修复码.

故障率 τ 是指节点发生故障的频率，即单位时间内节点发生故障的次数[20].通常用系统的平均无故障时间(mean time to failure,MTTF)来表示节点故障率，即

式中：MTTF为系统从开始运行到发生故障的平均工作时间.

对第2章中的构造进行扩展，将方阵X与s个m阶相互正交拉丁方叠合，其中 2 ≤s≤m-1，m为素数幂，且m≥3，s的取值规则为

式中：τmax为系统中信息位节点故障率的最大值，τmax=,i=1,2,···,k.

其中，0≤k≤(s+1)m,0≤j≤m2.

定理9在关联矩阵M1右边级联(s+1)m阶单位矩 阵I(s+1)m×(s+1)m，构造校 验矩阵H3，即H3=[M1|I(s+1)m×(s+1)m]，其中m为素数幂，且m≥3.由校验矩阵H3可构造参数为n=sm+m+m2、k=m2、t=s+1、r=m的单校验IS-LRCs，且最小距离最优，d=s+2=t+1.

证明由校验矩阵H3可知构造的局部修复码码长n=sm+m+m2，且右边级联单位矩阵使得校验矩阵H3满秩，因此局部修复码的维度k=m2.矩阵H3的前m2列对应信息位，后(s+1)m列对应校验位.将关联矩阵M1的行按顺序分为s+1 组，每组包含m个行向量，每组对应一个子集Bh(h=1,2,···,s,c)，集合 Ω 中的每个元素在每个子集Bh(h=1,2,···,s,c) 中出现一次，故关联矩阵M1的列重 为s+1，且每列“1”元素所在s+1 行中任 意2行的支撑集只在该“1”元素坐标处相交，所以每个信息位具有s+1 个不相交的局部修复组，即可用性为t=s+1.同时，校验矩 阵H3的行重为m+1，所以当某个信息位符号丢失时须获得其他m个符号位的信息才能恢复，故修复局部性r=m，且每个局部修复组中只有一个校验符号.

类似于定理8，可以证明校验矩阵H3中任意s+1 列线性无关，且存在s+2 列线性相关，故最小距离为d=s+2.此外，将码的参数代入式(1)得到

代入式(2)得到

因此最小距离d=t+1，定理9构造的IS-LRCs最小距离最优.

例3令m=4，则 Ω={1，2，···，16}，矩阵X为

假设系统中至少有一个信息节点在单位时间内的故障次数大于等于4，即 τmax≥4，则s=m-1=3.给出3个两两正交的4阶拉丁方:

由集合B和集合 Ω 的映射关系得到关联矩阵M16×16，由H3=[M16×16|I16×16] 可以得 到参数 为n=32、k=16、t=4、r=4的IS-LRCs，且最小距离d=t+1=5.

假设系统中所有信息节点在单位时间内的故障次数均小于4，且最大故障率为3，即 τmax=3，则s=τmax-1=2.任意选择2个4阶正交拉丁方与集合Bc构造关 联矩阵M12×16，由H3=[M12×16|I12×12] 可以得到参数为n=28、k=16、t=3、r=4的IS-LRCs，且最小距离d=t+1=4.

定理9构造的IS-LRCs局部性r与维度k的比值为

在大规模分布式存储系统中，局部性r与维度k的比值将随着拉丁方阶数m的增大而显著减小，因此该IS-LRCs能够有效减小故障节点修复时间，提升修复效率.

进一步可以得到码率：

又因为 2≤s≤m-1，故

即定理9构造的IS-LRCs码率下界为0.5.

如表2所示为几种典型的基于校验矩阵构造的IS-LRCs与定理9构造的IS-LRCs的码率对比.表中，参数n、k均用可用性t和局部性r表示，基于阵列LDPC码构造的IS-LRCs可用性t只能取偶数，v为大于1的正整数.

表2 几种典型IS-LRCs构造参数对比Tab.2 Comparison of structural parameters of several typical IS-LRCs

为了更加直观地对比几种方法构造出的局部修复码的码率，如图2所示给出了当局部性r=11时，几种方法构造出的局部修复码码率与Tamo等[14]提出的码率上界的比较.可以看出，定理9构造的IS-LRCs码率始终大于基于阵列LDPC码和基于正则矩阵构造的IS-LRCs码率，当局部性r取其他值时，可以得到相同的结论.随着可用性t的增大，系统中存储的冗余数据增多，码率将缓慢减小，体现了可用性t和码率R这2个参数之间的均衡关系.此外，Tamo等[14]提出的码率上界适用于有限域Fq上的二元及多元局部修复码，而定理9构造的是二元局部修复码，有限域的大小在一定程度上限制了码率的提高.

图2 局部性 r=11 时的码 率比较Fig.2 Code rate comparison with locality r=11

4 结语

考虑到具有 (r,t) 局部性的局部修复码不仅可以实现多故障节点的局部修复，还支持数据的并行读取，提出利用正交拉丁方构造二元局部修复码的方法，分别构造出全符号具有 (r,t=2) 局部性和信息位具有 (r,t=2) 局部性的局部修复码.进一步考虑到系统中存在高故障率节点，利用正交拉丁方完备组构造一类扩展可用性的单校验局部修复码，提高了系统的可靠性.理论分析表明，所构造的具有全符号局部性的局部修复码码率和码长渐近边界条件；信息位具有 (r,t=2) 局部性的单校验局部修复码的最小距离和码率均满足边界条件，为最优局部修复码；扩展可用性的单校验局部修复码最小距离最优，码率较高，始终大于等于0.5.此外，所有的构造均基于二元有限域，即所有的编解码只涉及异或运算，大大提高了编解码速度，更加适用于实际的分布式存储系统.

本研究构造的局部修复码的参数与正交拉丁方的阶数相关，故正交拉丁方的存在性在一定程度上限制了参数的取值，构造参数能够更加灵活取值的局部修复码是未来值得研究的问题.