LRC码最小距离限的深入分析

郝晓慧，车书玲，张欣瑜

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

在各种数据快速发展的今天，分布式存储系统需要在保证数据的高稳定可靠性的同时，还必须减少存储花销，因此数据冗余机制中最早使用的独立磁盘冗余阵列(Redundant Array of Independent Disks， RAID)已经不适合应用于数据中心级的大规模部署．之后出现的3-副本的冗余机制可靠性高，优化了读性能，在数据中心级的大规模部署中多有应用，但随着数据的不断增加，分布式存储系统的不断增大，3-副本的冗余机制需要大量的存储空间来存储特定的数据，造成巨大的成本压力，不再适合应用于大的分布式存储系统[1]．删除码在分布式存储系统中的应用弥补了前面两种机制的不足，较3-副本具有更低的成本和更高的技术含量[2-5]，虽然带来了网络负载，但是减少了额外需要冗余设备的数量，大大提高了存储设备的利用效率．

局部修复码(Locally Repairable Codes， LRCs)的提出，对删除码在分布式存储系统中的研究有了进一步的提升．对删除码中的LRC的研究主要分为两类:构造和参数分析(码长n，最小距离d，局部性r，信息位k，分组个数t等)，并讨论其最佳性． 其中最小距离是衡量码字检错和纠错能力的依据，即码的抗干扰能力，对LRC有重要的研究意义．文献[6]介绍了Singleton限; 文献[7]结合构造算法证明了Singleton-like限; 文献[8]提出了和有限域有关的最小距离限; 文献[9]提出和LRC分组个数有关的最小距离限; 文献[10]提出由Singleton-like限推导出来一定范围码字适用的新最小距离限．

笔者从最小距离出发，总结了已有的关于LRC的最小距离限，并基于已有的限，提出了两种新的最小距离限，第1种新的最小距离限适用于所有码字，第2种适用于更小范围码字．通过在相同码长、信息位和局部性的条件下，与已有限的分析比较得出，第1种最小距离限性能与Singleton-like限一样好，第2种性能优于已存在的最小距离限的结论，并给出了相应的理论推导及仿真分析．

1 LRC的最小距离限

这里主要介绍有关LRC的最小距离、局部性等基本概念，以及已有的5种最小距离限，下面以定理的形式给出．

定义1 局部修复码(LRCs)：当[n，k，d，r] LRC的任何一个符号发生错误时，只需使用本地组内包含的其他至多r个符号即可恢复出原始数据，其中，d表示最小距离，r表示局部性．

定义2 最小距离(minimum distance，d): 假设u和v是码C任意两个非零且不相同的码字，则码C的最小距离d= min {d(u，v)}，d是u和v之间的汉明距离，简单来说，C的最小距离就是C的任意两个码字之间不同元素数量的最小值[6]． 对于任意[n，k，d] LRC，任意d-1 个删除节点都可以被修复．

定义3 局部性(Locality，r): 修复一个节点需要访问的最大节点数．

定理1 [n，k，d]线性分组码的最小距离等于d的充要条件是:H矩阵中任意d-1列线性无关．

定理2 Singleton限：[n，k，d]线性分组码的最大可能的最小距离[6]等于n-k+1，即

d≤n-k+1 ．

(1)

定理3 Singleton-like限：[n，k，r] LRC信息位符号局部性为r时，则最小距离满足[7]

d≤n-k-k/r+2 ．

(2)

定理2及定理3没有考虑有限域的大小对最小距离限的影响，下面提供了和域相关的LRC最小距离限．

定理4q元[n，k，r] LRC的最小距离[8]满足

(3)

定理5 当[n，k，r，t] LRC有t个大小为r的不相邻恢复集时，则最小距离满足[9]

由定理3，可推出下面定理6中的最小距离限．

定理6 [n，k，r] LRC的最小距离在nmod(r+1)≥k+k/rmod(r+1)情况下满足[10]

d≤n-k-n/(r+1)+2+(n-k-n/(r+1))/r．

(6)

下文中用到以上各个公式时，均由定理m中的式(n)表示，m和n分别表示定理的标号和公式的标号，Singleton限及Singleton-like限仍由该名称表示． 下面将介绍通过理论推导提出LRC的最小距离限．

2 LRC的新最小距离限

由上节的最小距离限可知，定理6中的式(6)的最小距离限是基于Singleton-like限推导出来的，但是在推导过程[10]中，存在范围限制，并不适合所有码字．因此，文中提出一个新的适合所有码字的最小距离限，该限基于Singleton-like限进行推导． 在该新限基础上，结合定理6中的式(6)的最小距离限，推导出另外一个适合一定范围内的最小距离限．

定理7 对于任意的[n，k，r] LRC，其最小距离满足

证明 当r|k时，由Singleton-like限得证．

当r|/k时，有

根据(d+1/r-2)/(r+1)-1/r及n/(r+1)分别是整数、小数分为4种情况，验证每一种情况，可得

d-2-(d+1/r-2)/(r+1)-1/r≤n-k-n/(r+1)．

根据(d+1/r-2)/(r+1)-1/r分别是整数、小数分为两种情况，由d-2为整数，可得

推论1 当nmod(r+1)≥k+k/rmod(r+1)，且r|/k时，有最小距离满足

d≤n-k-n/(r+1)+2+(n-k-n/(r+1)-1)/r．

(9)

证明 由式(8)，同定理6，有nmod(r+1)≥k+k/rmod(r+1)，且r|/k时，

3 LRC的最小距离限的分析比较

这里将对上两节中给出的各种LRC的最小距离限从不同角度进行分析和比较，其内容进一步分成两个部分: 第1部分是已有LRC最小距离限之间关系的分析比较；第2部分是新提出的最小距离限与已有限之间关系的分析比较，分别得出新提出的最小距离限存在的优越性，并以仿真图的形式形象描述它们之间的关系．

3.1 Singleton限、Singleton-like限、定理5中的式(5)的最小距离限及定理6中的式(6)的最小距离限的分析比较

推论2 在GF(q)域上，相同n，k，r，t时，Singleton-like限和定理5中的式(5)的最小距离限相同[7]．

图1 n=63和r=2时的仿真图

推论3 当k>r时，Singleton限始终大于Singleton-like限[7]及定理5中的式(5)的最小距离限．

证明 当k>r时，d≤n-k-k/r+2≤n-k-1+2=n-k+1，且由推论2，得证．

推论4 Singleton-like限与定理6中的式(6)的最小距离限存在一定的关系，可分为以下3种情况:

(1)r+1|n，r≥1，Singleton-like限等于定理6中的式(6)的最小距离限．

证明 由式(6)的定义范围可知[10]，当r+1|n时，有r|k．

以上推论可由图1直观地表示出来．

(2)r+1|/n，r|k，Singleton-like限等于定理6中的式(6)的最小距离限加1．

式(6)的最小距离限: 当r|k时，k+k/rmod(r+1)=k+ (k/r) mod(r+1)=k[(r+1)/r] mod(r+1)= 0，则nmod(r+1)≥ 0，即 0

(3)r+1|/n，r|/k， Singleton-like限等于定理6中的式(6)的最小距离限．

证明 当r|/k时，0

由上述范围，式(6)可化为d≤n-k+2+n/r-(1+1/r)n/(r+1)-k/r，式(6)减去Singleton-like限，得

由推论4可知，当r+1|n，和r+1|/n，r|/k时，Singleton-like限等于定理6中的式(6)的最小距离限，当r+1|/n，r|k时，定理6中的式(6)的最小距离限更紧．

以上推论可以由图2直观地表示出来．

图2 n=63和r=5时的仿真图图3 10≤n≤120,R=2/5,r=3时的仿真图

从另外一个不同的角度思考时，则有以下结论．

推论5 码率R=k/n，如果R可以化简为如下形式:R=m/(r+1)，且gcd(m，r+1)=1，其中m可为任意正整数，则此时Singleton-like 限等于定理6中的式(6)的最小距离限．

证明 给定码率R及r，R=k/n=m/(r+1)，则(r+1)|n，gcd(m，r+1)=1，m与r+1互质，是保证码率的分母只能为r+1，在这种情况下，和推论4的情况(1)相同．

以上推论可以由图3直观地表示出来．

3.2 新提出的定理7中的式(8)、推论1中的式(9)与已有的Singleton-like 限、定理6中的式(6)的最小距离限的分析比较

推论6 当nmod(r+1)≥k+k/rmod(r+1)，且r|/k时，有

(1) 当r|(n-k-n/(r+1)-1)时，式(8)的最小距离限等于式(9)的最小距离限;

(2) 当r|/(n-k-n/(r+1)-1)时，式(8)的最小距离限等于式(9)的最小距离限加1．

证明 将上述条件分别代入式(8)及式(9)，根据上下取整关系，得证．

推论7 推论1中的式(9)及定理6中的式(6)中的最小距离限满足nmod(r+1)≥k+k/rmod(r+1) 时，有

(1) 当r|/k，且r|(n-k-n/(r+1))时，式(9)中的最小距离限等于式(6)中的最小距离限减1;

(2) 当r|/k，且r|/(n-k-n/(r+1))时，式(9)中的最小距离限等于式(6)中的最小距离限．

推论7可以由图2直观地表示出来．

推论8 对于r|/k条件下的[n，k，r] LRC， Singleton-like 限与定理7中的式(8)的最小距离限相等．

证明 当r|/k时，式(8)可化为

推论8可以由图4直观地表示出来．

以上关系由表1举例说明．

表1 n=20，不同k及r情况下，Singleton-like限和式(6)、式(8)、式(9)中最小距离限的紧程度

图4 n=42和r=3时的仿真图

表1中S和9分别表示在n，k，r情况下，Singleton-like限、推论1中的式(9)的最小距离限是最紧的；S/6、S/8、S/6/8分别表示在n，k，r情况下，定理6中的式(6)的最小距离限等于Singleton-like限、定理7中的式(8)的最小距离限等于Singleton-like限、定理6中的式(6)的最小距离限等于Singleton-like限并等于定理7中的式(8)的最小距离限，即一样紧．

4 结 束 语

笔者通过对LRC最小距离限的研究，提出了适合于一定码字的最小距离限，提供了判断最小距离最佳性的新限，分析了已有限之间存在的内在联系，具体成果如下:

(1) 通过理论推导提出了两个新的最小距离限，分别适用于所有码字和一定范围内码字，并与已存在的限通过理论推导及仿真进行了分析比较，得出了新提出的最小距离限的优越性．

(2) 理论推导并仿真分析得出已有最小距离限间的内在联系，为接下来对最小距离限的研究提供了一定的理论基础．