最优局部修复码的构造

杨佳蓉，王 娥，李静辉，余春雷

(1.长安大学 信息工程学院，西安 710018; 2.四川文理学院 智能制造学院，四川 达州 635002)

0 引言

在大数据时代，由于数据的急剧增长，分布式存储系统变得越来越重要[1]。分布式存储技术是将互联网上产生的各种数据和信息同步、分散地存储在多个独立设备中的技术。它可以通过使用网络将数千个存储节点连接在一起，以支持数据的持续增长，同时分布式系统还具有高访问、高性能、低成本等优点。但是分布式存储系统中存在不同种类的设备，包括存储节点、路由器和交换机，这些设备可能会不时出现故障，导致系统无法正常工作。为了保证存储节点故障的可靠性，在分布式存储系统中采用了各种编码技术。

最简单的方法是直接复制，但是复制方案会导致较大的存储开销，与复制相比，纠删码在保证数据可靠性的同时，可以大大降低存储负载，极大地提高了存储设备的利用率。然而在故障节点的修复过程中，经典的纠删码在访问的辅助节点数量、修复带宽等方面效率低下。为了保证数据的可靠性和节点的有效修复，后续的研究中陆续提出了再生码和局部修复码(LRCs, locally repairable codes)。再生码可以通过提高修复程度和减少从每个节点下载的数据来减少修复带宽，而局部修复码则可以有效修复故障节点，通过在修复过程中使用少量的节点来降低修复成本[2]。

许多学者已经对局部修复码进行了研究，Gopalan等在文献[3]中首次提出局部修复码，并证明了适用于任意码字的Singleton-like限。文献[4]和文献[5]分别介绍了修复局部性的概念，如果码字的第i个码元能够被其它至多r个码元修复，则称该码元具有修复局部性r。文献[6]证明了在分布式存储系统中使用局部修复码时可以更有效地修复故障点，还提出了一个最优的和显式的局部修复码，实现了任意高的数据率。在文献[7-8]中，Shahabineja等研究了局部修复码的信息位的最优平均局部性，实现了奇偶校验位的最优最大局部性，但在构造算法中复杂度较高。Wang等人[9]推导出了每个修复组中包含多个奇偶校验符号时的最小距离界。Tamo等人在文献[10]中提出了所有符号具有(r,t)局部性的局部修复码的最小距离界。在文献[11]中，Pamies-Juarez等人利用部分几何图构造了具有多个不相交修复组的局部修复码[11]。

在构造最优局部修复码方面，Tamo在文献[12]中提出了一组使用多项式构造最优局部修复码的方法，但码率不高。在文献[13]和文献[14]中，Tamo和Luo等人提出了环状局部修复码的构造方法，其最小距离达到了最优界，但是码率较小。在文献[15]中Hao等人给出了最优三元局部修复码的分类。Kruglik等人在文献[16]中从二分图的角度出发构造二元LRCs，并对Tamo等人提出的所有符号具有(r,t)局部性的局部修复码的最小距离的界进行了改进，达到了最小距离最优，但是其构造算法略复杂。Jung-Hyun Kim等人提出一种基于超图的二进制局部修复码的构造[17]，给出了具有(r,t)局部性的超图存在的必要条件，增加了最小距离，但是码率受超图参数的影响较大。在文献[18]中，Wang等人利用区组设计中的DBBD设计构造二元局部修复码，其最小距离和码率都达到了最优界，但是局部性有所限制。Silberstein等人在文献[19]中提出了基于各种反编码的二元最优局部修复码，但是其局部性只能取2或3，不能适用于任意局部性的情况。张茂等利用不相交局部修复组、sunflower和射影几何等理论构造了一般域上的两类局部修复码[20]，所构造的两类码在相同的码的最小距离和局部度下提高了码率，但是码率没有达到最优。

针对上述问题，本文提出一种基于方形网络的局部修复码的构造方法。具体地，利用方形网络中顶点与边的对应关系构造关联矩阵，然后在关联矩阵右侧添加单位矩阵得到局部修复码的校验矩阵，进而基于该校验矩阵构造局部修复码，所构造的局部修复码最小距离和码率都达到了最优界；进一步地，将方形网络中水平方向和垂直方向的的关联矩阵分别进行扩展，新构造的局部修复码参数选择灵活，算法复杂度较低，在修复故障节点时可以实现故障节点的快速精确修复。与现有局部修复码相比，本文构造局部修复码在满足最小距离最优界的同时码率也达到了最优，且适用于任意局部性。

1 基础知识

局部修复码属于线性码，设码C是有限域Fq上的[n,k]线性码，码C的第i位具有局部性r是指第i位是其它r位在有限域Fq中的线性组合，如果码C的任意位都具有局部性r，则称码C是具有局部性r的局部修复码。局部修复码是一种特殊的纠删码，当分布式存储系统的一个节点发生故障时，该节点可以通过其它不超过r个存活节点进行修复，r称为码的修复局部性。除了局部性之外，局部修复码的另一个重要特性是可用性，如果码字符号可以从t个不相交修复集中恢复，则这个符号具有(r,t)可用性。

定义1[21-22]:如果一个码字符号ci满足以下三个属性则说明它具有(r,t)局部性:

如果只有k个信息符号具有(r,t)局部性，则称该码为具有信息局部性的(n,k,r,t)-LRCs。

简单来说，LRCs是纠删码的一种，可以用n表示码长，k表示维度，d表示码的最小距离。如果局部修复码的所有信息位码元都具有(r,t)可用性，则可以称该码具有(r,t)可用性的局部修复码，记作(n,k,r,t)iLRCs。如果其信息位码元的每个修复集都只有一个校验位码元，那么称该码为单校验(n,k,r,t)iLRCs，如果局部修复码的所有码元都具有(r,t)可用性，那么这个码称为全符号(n,k,r,t)aLRCs，本文主要研究单校验(n,k,r,t)iLRCs。

令u和v是线性码C中任意两个非零码字，两个码字之间不相等， 码C的最小距离可以表示为d=min{d(u,v)}，也就是码字之间的最小汉明距离，对于码(n,k,d)，如果d个节点同时出现故障，分布式存储系统就不能被修复[23]。

定理1[24]：若局部修复码信息位码元的每个修复集中只含有一个校验位，那么该单校验(n,k,r,t)iLRCs的最小距离满足：

(1)

称达到式(1)中边界的局部修复码是最小距离最优的单校验(n,k,r,t)iLRCs。

定理2[25]:若线性分组码C是信息位具有局部性r和可用性t的局部修复码，最小距离满足:

d≥t+1

(2)

如果上式中局部修复码的最小距离d取等号，则此局部修复码为最小距离最优的局部修复码。

定理3[26]:(n,k,d)LRC码的局部参数r满足:

(3)

定理4[27]:特别地，Prakash等人提出了可用性t=2的最优码率的(n,k,r,t=2)LRCs，该码满足:

(4)

2 最优局部修复码的构造

2.1 方形网络

定义2[28]:由若干个单位边长的正方形拼接而成的网络称为方形网络，方形网络中水平向上和垂直向上的直线相等。

给定一个方形网络，其中顶点p2(p≥2)个，p为正整数。p表示方形网络中水平方向和垂直方向的每条直线上的顶点数量，由此可知，方形网络中水平和垂直方向上的直线也分别为p条。令方形网络的顶点表示分布式存储系统中的数据包，水平方向和垂直方向的直线代表分布式存储系统中的存储节点，我们将这样的p×p方形网络称为分布式存储系统中的方形网络。

给出分布式存储系统中的一个3×3的方形网络，这里p=3，如图1所示。该方形网络在水平方向和垂直方向上共有6条直线v1,v2，…,v6，代表分布式存储系统中的6个存储节点，方形网络中的9个顶点d1,d2,…,d9，代表分布式存储系统中节点存储的数据包。

图1 3×3方形网络

2.2 基于方形网络构造局部修复码

本小节基于方形网络构造局部修复码，将方形网络的顶点与分布式存储中需要存储的数据块相对应，方形网络中水平方向和垂直方向的直线对应于分布式存储系统中的存储节点。

构造1:利用方形网络构造局部修复码的具体步骤如下:

步骤1: 给定一个p×p方形网络，p为正整数且p≥2。将方形网络中的顶点dj(1≤j≤p2)按照先从上到下再从左到右的规则进行编号，直线vi(1≤i≤2p)也按照同样的规则进行编号。

步骤2：根据2.1，给定的方形网络中一共有2p条直线和p2个顶点,。令第i条直线对应于局部修复码中的第i个存储节点，第j个顶点对应局部修复码中第j个的数据块。

步骤3：构造基于方形网络的局部修复码的校验矩阵H=[M|I2p]，其中关联矩阵M=(nij)2p×p2，当方形网络的顶点dj(1≤j≤p2)正好在其直线vi(1≤i≤2p)上时，第i个节点存储顶点上的数据块dj，基于方形网络的关联矩阵中nij=1，否则为0。

步骤4：由校验矩阵构造的码C是信息位具有局部性r和可用性t的局部修复码，码C的参数满足条件n=2p+p2,k=p2,r=p,t=2。由于M是基于方形网络的关联矩阵，每一列的汉明权重都等于2，这意味着每个信息符号都有t=2个修复集，M的每一行都有汉明权重p，且M的任意两个不同的行最多有一个位置是相同的，因此该码具有局部性r=p，每个信息符号的修复集是不相交的，每个修复集只包含一个校验位。

例1:给定一个方形网络，其中p=3，如图1所示。根据方形网络中顶点与直线的对应关系可以构造关联矩阵:

(5)

定理5:基于方形网络构造的(n=2p+p2,k=p2,r=p,t=2)局部修复码为最小距离最优的局部修复码，并且d=t+1。

证明:基于方形网络构造的(n=2p+p2,k=p2,r=p,t=2)局部修复码，其信息位码元的每一个修复集中只包含一个校验位，根据定理1，将其参数代入边界条件:

(6)

即d≤t+1，又根据定理2可得d≥t+1，因此所构造的局部修复码的最小距离d=t+1，达到了最小距离最优界，是最小距离最优的局部修复码。

定理6:基于方形网络构造的(n=2p+p2,k=p2,r=p,t=2)局部修复码的码率是最优的。

证明:(n=2p+p2,k=p2,r=p,t=2)局部修复码的码率:

(7)

其码率满足定理4中Prakash等人提出的可用性t=2时局部修复码的边界，所以此码是码率最优的局部修复码。

2.3 基于方形网络构造扩展局部修复码

上节中基于方形网络构造的局部修复码是最小距离最优的码，并且达到了码率最优界，但是该局部修复码的局部性有所限制。为进一步提高局部度，本节运用方形网络构造扩展关联矩阵，以此构造局部修复码的校验矩阵，可以得到适用于任意局部性的局部修复码。

构造2:基于方形网络构造扩展局部修复码的具体步骤如下：

步骤1：首先将方形网络中的顶点dj(1≤j≤p2)按照构造1的规则进行编号，直线vi(1≤i≤2p)也按照同样的规则进行编号。其中第i条直线对应于局部修复码中的第i个存储节点，第j个顶点对应局部修复码中第j个数据块。

步骤2：如构造1步骤3中直线与顶点的存储关系，将基于方形网络中水平方向构造的关联矩阵定义为M1，垂直方向构造的关联矩阵定义为M2，另外用Ip表示p阶单位矩阵，Sp表示副对角线为1的单位矩阵。基于方形网络构造扩展局部修复码的关联矩阵为:

(8)

步骤3：将矩阵M′与单位矩阵级联作为方形网络的扩展校验矩阵H′=[M′|I2p]，由此扩展校验矩阵可以构造参数为(n=p2+3p,k=p2+p,r=p+1,t=2)的局部修复码。

由于M′是基于方形网络扩展的关联矩阵，由方形网络的性质可以知道每一列的汉明权重都等于2，这意味着每个信息符号都有t=2个修复集，M′的每一行都有汉明权重p+1，M′的任意两个不同的行最多有一个位置是相同的，因此基于方形网络扩展矩阵构造的局部修复码具有局部性r=p+1，每个修复集只包含一个校验位。

例2:给定一个方形网络，其中p=3，如图1所示，基于方形网络得到的关联矩阵为M，根据水平方向构造关联矩阵M1和垂直方向构造关联矩阵M2：

(9)

(10)

将M1和M2上下级联，并在新矩阵的右方级联一个3阶单位矩阵和一个副对角线为1的3阶矩阵，进而可得矩阵:

(11)

最后将M′作为方形网络的扩展关联矩阵，和单位矩阵I2p级联生成校验矩阵H′=[M′|I2p]，由此可以构造出(n=18,k=12,r=4,t=2)的局部修复码，从两种构造的参数对比可知，与例1相比，基于方形网络扩展矩阵的局部修复码适用于任意局部性的情况。

定理7:基于方形网络的扩展矩阵构造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修复码为最小距离最优的局部修复码，并且d=t+1。

证明:基于方形网络的扩展矩阵构造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修复码，根据定理1，将其参数代入边界条件:

(12)

即d≤t+1，又根据定理2可得d≥t+1，因此所构造的局部修复码的最小距离d=t+1，正好达到最小距离最优界，是最小距离最优的局部修复码。

定理8:基于方形网络的扩展矩阵构造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修复码的码率是最优的。

证明: (n=p2+3p,k=p2+p,r=p+1，t=2)局部修复码的码率:

(13)

其码率满足定理4中Prakash等人提出的可用性t=2时局部修复码的边界，所以此码是码率最优的局部修复码。

3 性能分析

3.1 码率分析

码率是局部修复码中一个重要的参数，码率表示码字中信息码元所占的比例。码的码率越大，表示其传输效率越高。本小节主要对基于方形网络构造的局部修复码的码率进行最优化分析。

3.1.1 与校验矩阵构造的LRCs比较

本小节将构造1、构造2与基于射影平面和基于仿射平面的局部修复码[24]进行比较。这四种局部修复码都是由校验矩阵构造的，但是构造方式有所不同，基于射影平面的局部修复码是利用低密度奇偶校验码的校验矩阵构造，基于仿射平面的局部修复码是将仿射平面的一个固定的点和经过这个点的线删除之后得到关联矩阵，由关联矩阵来构造局部修复码的校验矩阵。

图2 t=2时基于校验矩阵的LRCs的码率R和 局部性r的关系

3.1.2 与任意(r,t)局部性的LRCs的比较

将本文构造的局部修复码与可达到任意局部性(r,t)的局部修复码进行比较，码的参数比较如表2所示。

表2 与可达任意局部性的LRCs参数比较表

如图3所示，为最优码率界，将本文构造的局部修复码与可达任意局部性的基于直积码的局部修复码进行码率比较。可以看出，t=2时构造1和构造2的码率与Prakash等人提出的最优码率界重合，且始终大于基于直积码的局部修复码的码率。

图3 t=2时可达任意局部度的LRCs的码率R和 局部性r的关系

3.2 局部性分析

局部修复码中的局部性r意味着它最多可以从r个其它码字符号中修复故障节点，局部性将直接影响磁盘I/O和修复过程中需要连接的节点数量。将构造1和构造2进行对比分析可知，构造1的局部性r=p，而构造2的局部性r=p+1，构造2所构造的局部修复码在不牺牲码率和最小距离等关键参数的情况下，适用于任意局部性的情况。

表3是不同局部修复码局部性的参数对比分析，将本文构造的局部修复码与基于区组设计的局部修复码[18]、基于反编码构造的局部修复码[19]以及基于循环移位的局部修复码[29]相比，基于区组设计的局部修复码的局部性为2，限制了局部性的可选范围，从表3中可以看出基于区组设计的局部修复码的码率较低且不能适用于任意局部性的情况。

表3 不同LRCs关于局部性r的参数对比表

基于反编码构造的局部修复码的局部性为2或者3，局部性r的取值较小，只适用于具有小局部性的局部修复码，除此之外，此码的局部性r的可选择范围也被限制，无法灵活地构造不同局部性下的局部修复码。

基于循环移位的局部修复码的局部性也为2，其中大部分的局部修复组都只有一个信息符号和两个校验符号，每个信息符号的局部修复不能通过访问其它信息符号来实现，只能通过访问校验符号来实现，局部性有所限制。相比之下，本文构造的局部修复码的局部性可以达到任意值，参数选择更加灵活。

4 结束语

本文针对已有的局部修复码在最小距离最优的条件下码率不高，局部性无法适用于任意情况的问题，提出了基于方形网络构造局部修复码的方法，首先利用方形网络中顶点与边的对应关系来构造局部修复码的校验矩阵，所构造的局部修复码达到了最优码率界。为了进一步提升局部性，将方形网络水平方向和垂直方向上关联矩阵进行扩展，用扩展的关联矩阵构造局部修复码的校验矩阵，所构造的新的局部修复码不仅在最小距离最优界时达到了码率最优，并且提高了局部性。经过对码率和局部性的性能分析可知，本文构造的局部修复码不仅满足最小距离最优，并且达到了码率最优界，参数选择灵活，适用于任意局部性的情况。