基于差集矩阵的部分重复码构造

王 静 何亚锦 雷 珂 刘向阳

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

②(西北工业大学电子信息学院 西安 710129)

1 引言

由于社交媒体和网络信息的兴起，数据呈现爆炸式增长，传统的集中式存储已经无法满足需求。分布式存储系统以其价格低廉、性能优异等优点，日益成为主流存储系统。在分布式存储系统中，即使存在故障节点的情况下，也需要保证数据存储的完整性和数据访问的速度。这个问题通常使用复制和纠删码策略[1,2]来解决。

复制策略就是将数据块复制若干倍，然后将其分别存放在不同的存储节点上。其中最常见的为3副本复制，如Google文件系统(Google File System,GFS)[3]。在节点故障的时候，由于副本的存在，只需简单复制数据即可修复。整个修复过程简单易实现，但是却增加了分布式存储系统的存储负担。为了进一步优化存储开销，提出纠删码策略。纠删码策略是将原始文件分成若干块进行编码产生冗余校验块来保证数据存储的可靠性，目前在Windows[4],Facebook的Hadoop集群(Facebook’s Hadoop cluster)[5]等已经投入使用。虽然纠删码减少了存储开销，但是在节点故障修复的时候，需要下载整个原文件，过程复杂，且修复带宽开销大。

为了进一步优化存储系统，文献[6]提出了再生码(Regenerating Codes, RC)，在单节点故障时，再生码不需重构原文件就能修复，降低了修复带宽开销，但是在修复过程中涉及的计算量比较大。Papailiopoulos等人[7]利用线性组合的思想构造了无参数限制的最小带宽再生码(Minimum Bandwidth Regenerating, MBR)，结构简单。Rashmi等人[8]提出了锯齿状最小存储再生码(Minimum Storage Regenerating, MSR)构造，在有限域F3上计算开销较小。随后，Guan等人[9]在较小的有限域内构造了MSR码，构造复杂度低。为了降低故障节点的修复局部性，Gopalan等人[10]和Papailiopoulos等人[11]提出了局部修复码(Locally Repairable Codes, LRC)的概念，即单个故障节点可以通过访问最多r个存活节点来实现数据恢复。文献[12]将再生码和局部修复码结合，提出了基于系统MSR码的局部再生码，节点故障修复时利用相邻局部码进行协作修复。文献[13]给出具有(r,t)局部性的局部修复码的最小距离上界，并且构造的LRC能容忍多节点故障，在修复过程中可以并行读取数据，减少修复时间。

El Rouayheb等人[14]提出了部分重复(Fractional Repetition, FR)码，它是基于最小带宽点的精确修复再生码，采用外部的最大距离可分(Maximum Distance Separable, MDS)码和内部的重复码构成。FR码在修复故障节点时，只需要复制相应的编码块，无需编码计算就可完成修复[15]。文献[16]给出了基于Steiner系的FR码的构造和仿射几何等可分解组合设计，并利用Kronecker和构造出具有较低修复局部性的新FR码。文献[17]提出了基于部分有序集的普遍好的FR码的简单构造，构造的FR码易于实现且可扩展，与MBR码相比，允许存储更大的文件。Zhu等人[18–20]研究了FR码与其对偶码之间的关系，进一步利用正则图和组合设计构造达到最小距离上限的FR码，并给出了FR码重构度的下限。

此后，还有很多学者进行了这方面的研究，FR码的构造一直是一个重要的研究课题。文献[21]引入一种新的组合模型，构造具有均衡访问频率的最优FR码。文献[22]基于二部图的任意周长构造出参数可调节的FR码，并证明其最优性。Prajapati等人[23]使用部分正则图构造异构的(每个节点上存储的数据包数量不同)普遍好的FR码，对于部分参数，使用环构造和t−设计构造普遍好的FR码。上述构造的FR码都是基于图构造的，过程相对复杂，并且重复度通常是由结构固定，不能对任意参数的FR码进行构造。

考虑到现有的FR码的构造算法复杂且不能灵活地选择构造参数，本文提出一种基于差集矩阵的FR码的构造算法，可以同时调整数据块的重复度和节点的存储容量，且在参数选取上不受限制。进一步可以通过调整差集矩阵的参数λ，构造局部性较小的FR码。实验结果表明，构造的FR码具有更低的修复局部性，修复简单且效率高，减少了故障节点的修复时间。

2 预备知识

2.1 FR码

(n,k,d)分布式存储系统(Distributed Storage System, DSS)中，其中n表示的是系统中的存储节点总数，k表示重构原始文件需要连接的节点数，d(≥k)表示修复单个故障节点需要连接的节点数。当存储节点故障时，新生节点需要从其他存活节点下载β个数据块进行精确修复，即修复后的数据和失效时的数据是完全一样的。文献[23]指出在精确修复模式下，当β=1时 ，系统的存储容量CMBR为

在DSS中，FR码外部采用MDS码，将MDS码编码后的θ个编码块复制ρ倍，再将它们分别存放在n个不同的存储节点上，每个节点的存储大小为α，连接任意k个节点就可以重构原始文件，记为FR(n,θ,ρ,α)。考虑到节点之间会存储相同编码块，本文给出FR码的文件大小M(k) 的定义，即任意k个节点Vi(i ∈{1,2,...,k})所获得的不同数据块的个数即求并集

文献[13]指出如果满足M(k)≥CMBR(n,k,d)，则称该FR码是最优的。

2.2 差集矩阵

如果矩阵G表示一个p阶可加群，其元素为0,1,...,p −1。 给定一个矩阵D，如果矩阵D中的任意两列的有序差中，G的每个元素都出现且出现的次数相同，本文称矩阵D为差集矩阵(difference matrix)，用D(λp,q;p)表 示。它是元素属于G的一个具有p水 平的λp×q的差集矩阵，λ表示D中的任意两列的有序差中，G中的每个元素出现的次数。

2.3 Kronecker和及正交排列

G表示一个n阶可加群，其元素为0 ,1,...,n −1。假设矩阵A=(aij)n×r,B=(bij)m×s，则矩阵A和B的Kronecker和为

其中，aij+B表 示aij与B中 的每个元素做模n加法运算。接下来，为了后面表述更加方便，用1r表示r×1 阶 的 全1 矩 阵，(r) 表 示r×1 矩 阵(0,1,...,r −1)T。

一个λn2×l的 矩阵，如果满足矩阵的任意两列由G的n个元素所构成的n2个序对，任一序对都出现在这两列的λ个行中，则称这个矩阵为正交排列，记为O A(n,l;λ)。

3 基于差集矩阵的FR码构造

本节利用差集矩阵构造FR码，构造的FR码可以调整编码块的重复度，并且可以通过设计参数λ，进一步调节节点之间共有的编码块数，达到减小修复局部性的目的。

3.1 基于差集矩阵的FR码的构造算法

设G为p阶可加群，元素为0 ,1,...,p −1。若存在元素属于G的一个差集矩阵D(λp,q;p)，构造矩阵为

具体地，基于差集矩阵λ=1的FR码的具体构造步骤如下所示：

当l>1,p>1 且l≤q+1(q为p的 最 小 素 因数)时，给出了 OA(p,(q+1);1)的通用构造方法，并在此基础上构造了普遍好的FR码。

设α=[0,1,...,p −1]T,αi=[i,i,...,i]T(i=0,1,...,p −1)， 定义函数Mj(α)=[0+j, 1+j, ...,p −1+j]T，其中i+j(i=0,1,...,p −1)表 示模p加 ，构造如式(5)的正交矩阵

矩阵O A可以进一步表示成

根据差集矩阵的定义，O A(p,(q+1);1)=[D(p,q;p)⊕(p),(p)⊕0p]，可以验证得

是一个模p加法群上的差集矩阵。这里的OA(p,(q+1);1),D(p,q;p) 中 的(p −1) 和(q −1)分 别 表示数p−1 和数q−1 ，而(p)=(0,1,...,p −1)T。

定理1正交排列 OA(p,(q+1);λ)构造FR码，共有p(q+1)个 节点，λp2个 编码块，重复度为q+1，节点存储大小为λp，即F R(λp2,p(q+1),q+1,λp)。节点故障时，需要连接p个节点修复。

证明正交排列OA(p,(q+1);λ)=[D(λp,q;p)⊕(p),(p)⊕0λp]矩 阵是一个λp2×(q+1)矩 阵，O A 的λp2行对应λp2个不同的编码块，O A 的q+1列对应着FR码的重复度。由构造过程可知， OA 的任一列都包含了所有的编码块，且每个编码块都正好与唯一的节点相关联，因此由正交排列 OA矩阵构造的FR码有q+1个 平行类，即正交排列O A矩阵的每一列都是一个平行类，本文称FR码是可分解的。每列取p个不同的元素，每个元素在该列中出现λp次。针对某列，将取相同元素所在行编码块放置在一个节点中，节点之间有λ个相同的编码块。故单节点故障时，只需从p个节点上下载λ个编码块即可修复。考虑多节点故障时，因为每个平行类含有p个节点，故多节点故障时同样仅需从p个节点中下载数据即可完成修复。 证毕

定理2由上述λ=1的差集矩阵构造的FR码是最优的FR码。

证明λ=1时 ，正交排列O A(p,(q+1);1)，矩阵O A任两列的元素所组成的有序对仅出现1次，即任意两列中的两行的元素对不会完全相同。由FR码的构造方法可知，每一列对应一个平行类，所以平行类之间的存储节点有一个编码块相同。假定FR码每个节点存储大小为d，即修复度，连接任意k个节点可以重构原文件。因为两个节点之间最多相交一个编码块，所以当连接k个不同的节点时，最多可以得到个重复数据块，根据FR码原文件大小的定义可得M(k)≥kd −()=CMBR。因此，由λ=1的差集矩阵构造的FR码是最优的FR码。 证毕

引理1当λ=1 且p为素数时，构造的FR码的重复度ρ=2。

证明p为素数时，其最小素因子q=1，则构造的差集矩阵为D(p,1;p)， 进一步得到一个p×2的正交矩阵 O A(p,2;1)，已知正交矩阵有两列，故构造的FR码的重复度ρ=2。 证毕

引理2当p为合数时，构造的FR码的重复度ρ ≥3。

证明p为合数时，可知其最小素因子最小为q(q ≥2) ， 构造的差集矩阵为D(p,q;p)，进一步得到一个p×(q+1)的 正交矩阵O A(p,(q+1);1)，又已知构造的FR码的重复度为q+1(q+1≥3)，所以构造的FR码的重复度ρ≥3。 证毕

定理3由λ=2的差集矩阵构造的FR码，令k=p+1 ，且k= 3w+v，任意连接k个节点所获得的最小文件大小为

证明考虑λ=2 ，故λp的最小素因子为2，即q=2 ，则进一步构造基于λ=2 的差集矩阵的FR(2p2, 3p, 3, 2p)码 。FR码每个节点存储大小为2p， 一个平行类含有p个节点，不论单节点还是多节点的节点故障，仅需连接p个节点即可修复。

考虑节点故障修复的局部性，令k=p+1 ，其中k= 3w+v，文件大小为M(k)=min|Ui∈kVi|,k ∈{1,2,...,p},|k|=k

考虑两个节点相交的编码块数，优先考虑不在一个平行类中的节点。任取k个节点所获得的编码块为2kp，根据k= 3w+v可知，有3−v个 平行类取w个 节点，有v个平行类取w+1个节点。由于同一平行类内的节点之间无相交编码块，而平行类间的两节点之间有一个相同的编码块。当0w＜2时 ，k个节点至少有2[()−v]个 编码块，w≥2 时，k个节点至少有2 [()−v()−(3−v)()]个 相同编码块。考虑p是每个节点存储的编码块数，p最小取2，故k最小为3。由构造过程可知，分别从3个平行类中取1个节点，则3个节点最少相交1个编码块。故

3.2 构造法的应用

例1当p为素数且p=3 时，其最小素因数q=1 ，则构造正交矩阵OA(3,2;1)=[D(3,1;3)]⊕(3),(3)⊕03] 如式(11)所示，矩阵O A(3,2;1)后面为所对应的编码块。

由于 O A(3,2;1)矩阵的每一列都包含了所有的编码块，且每个编码块只对应唯一的一个节点。因此每一列都是一个平行类。考虑矩阵的最后一列，前3个元素取第1水平0，即水平“0”，于是把“1,2,3”放到p2的第“1”个节点中。类似地，把“4,5,6”放到p2的第“2”个节点中，把“7,8,9”放到p2的第“3”个节点中，这3个节点构成平行类p2。 同理可以得到平行类p1的3个节点，最终得到6个节点。

将原文件M分成6 个数据块，采用(9, 6)MDS码编码，得到9个编码块。用户连接任意3个节点至少可以获得6个不同的数据块，即可重构原文件M。又由CMBR=3×3−=6，所以构造的FR码是最优的。构造的FR码的重复度ρ=2，并且有2个平行类，每个平行类包含了所有的数据块。

例2令p=4， 其最小素因子q=2，则可以得到一个 4×2 的差集矩阵D(4,2;4)。利用差集矩阵D(4,2;4) ，构造得到矩阵OA(4,3;1)=[D(4,2;4)⊕(4),(4)⊕04]， 如式(13)所示。矩阵O A(4,3;1)后面附的是相对应的编码块

采用系统( 16,13)MDS码，每个节点存储4个编码块。如果选取其中的任意两个平行类，则可以得到一个重复度ρ=2的FR码；如果取3个平行类，就得到了重复度ρ=3的FR码。

例3考虑λ=2 ， 利用差集矩阵D(6,2;3)，构造得到矩阵O A(3,3;2)=[D(6,2;3)⊕(3),(3)⊕06]，如下所示。通过该设计，我们可以得到一个ρ=3的FR码，并且有3个平行类。更具体地说，采用系统(18, 15)MDS码，对15个数据块编码，可以生成3个校验块，其中每个节点存储6个数据包。如果节点V1故障，则新生节点可以从节点V4下载{1,10}，从V5下 载{4,13}，从V6下载{7,16}，来修复故障节点V1；或者从V7下载{1,4}，从V8下载{7,10}，从V9下 载{13,16}，实现故障节点V1的修复。进一步可以看出，任意连接k=4个节点，用户都可以恢复原文件。且当λ=2时，上述构造出来的FR码是局部修复码，单节点的修复局部性为3

3.3 故障节点修复

分布式存储系统中出现节点故障，在修复过程中需要连接的节点集合称为修复组。本节主要从单节点故障、两节点故障以及多节点故障进行分类讨论，具体修复过程如下：

当单节点故障的时候，只需要连接任意一个完整平行类即可进行精确无编码修复。如例2构造的FR码，当第1个平行类p1中 的节点V1故障时，可以从平行类p2中 的节点V5下载编码块1，从节点V6下载编码块5，从节点V7下载编码块9，从节点V8下载编码块13，进行无编码精确修复。节点V1故障也可以从平行类p3中 的4个节点{V9,V10,V11,V12}进行修复，或者利用平行类p2和p3混合修复如修复集{V5,V6,V11,V12}等多种修复选择方案。连接任意修复组中的4个节点通过复制相关编码块即可进行无编码精确修复故障节点。

当系统中出现两个节点同时故障时，分为以下情况：如果重复度ρ=2，两个故障节点在同一个平行类中，则可以利用另一个平行类进行修复；如果两个故障节点不在同一个平行类，且两个故障节点有一个编码块相同，这种情况下就不能采用复制的方式进行修复，需要利用其余存活节点恢复原文件，进一步修复故障节点。如例1中的节点V1和V2故 障，两个故障节点都在平行类p1，则可以用另一个平行类p2中 的3个节点{V4,V5,V6}来修复故障节点。如果节点V1和 节点V4同时故障，由于两个故障节点中含有相同编码块，故不能采用简单复制的方式，可以连接其余两个节点V2和V3进行MDS码编码恢复原文件，进一步精确修复故障节点V1和V4。针对重复度ρ>2的情况，不论是两个故障节点在一个平行类，还是其他情况，均可以利用其他平行类中的节点下载相应编码块进行精确修复。如例2中的节点V1和V5故障，可以利用平行类p3中的4个节点{V9,V10,V11,V12}进行修复。

对于修复多个故障节点，可以分为以下4种情况：(1) 若多个故障节点都在同一个平行类，则可以利用其他平行类进行修复；(2)对于多个故障节点不在同一个平行类的情况，若还存在不包括故障节点的平行类，那么就可以直接用不包括故障节点的平行类进行修复；(3)若多个故障节点分布在所有平行类中，且不存在所有平行类中的故障节点都包含同一个或者多个编码块的情况，此时可以通过连接多个平行类中的存活节点来修复故障节点。(4)若多个故障节点分布在所有平行类中，且有一个或者多个编码块无法从现有存活节点中获得，此时无法再采用复制方式进行修复，需要利用存活节点先恢复原文件，从而修复故障节点。

4 性能分析

基于差集矩阵构造的FR码的性能分析主要集中在节点修复选择度、修复复杂度、修复带宽开销和修复局部性这几方面，并将其与里德-所罗门(Reed-Solomon, RS)码和简单再生码(Simple Regenerating Codes, SRC)进行性能比较。

表1给出了相同文件情况下RS码、SRC和基于λ=1差集矩阵构造的FR码的修复带宽开销和修复局部性。本文构造的FR码外部采用(k+3,k)MDS码。

表1 RS码、SRC和FR码的故障节点修复性能比较

4.1 节点修复选择度

节点修复选择度指的是故障节点修复过程中的修复选择方案。考虑单节点故障的修复选择度，对于 (n,k)R S码，从n−1 个存活节点随机选取k个来修复故障节点。因此， (n,k)RS码的修复选择度为。 对于SRC，从n−1个 存活节点随机选取f个存活节点来修复故障节点，故其修复选择度为。 基于λ=1差集矩阵构造的FR码，其选择度主要与重复度ρ和节点存储大小α有关。如果构造的FR码的重复度ρ=2，那么节点故障时的修复选择度仅为1，只需要连接具有相同编码块的存活节点即可修复。如果构造的FR码的重复度ρ>2时，故障节点修复可以有多种修复方案。对于任意单节点故障，都可以从其他ρ−1个存活节点选择修复。对于重复度为ρ、节点存储大小为α的FR码，节点故障的时候，只需要从其他副本中下载相应的数据块即可。由于任意两个节点之间最多相交1个编码块，修复一个节点中的第1个编码块和第2个编码块均有ρ−1 种选取方案，故其修复选择度为(ρ −1)α。从图1看出，当FR码节点存储大小α=3时，基于λ=1差集矩阵构造的FR码节点修复选择度随着重复度的增加呈指数倍增加。

图1 节点修复选择度与重复度ρ 之间的关系，其中α=3

4.2 修复复杂度

对于(n,k)R S码，在修复过程中需要连接k个节点恢复原文件，再重新编码生成故障节点。整个故障节点修复过程涉及大量的有限域运算，需要k2+k次有限域乘法运算和k2−1次有限域加法运算，因此RS码在单节点故障时的修复复杂度为O(2k2+k −1)。对于SRC，修复一个编码块需要进行f−1 次 异或运算，由于每个节点存储f+1个编码块，因此SRC的修复过程需要(f+1)(f −1)次异或运算，其修复复杂度为O(f2−1)。基于差集矩阵构造的FR码，整个过程只涉及文件的读取，无需编码，过程简单，修复复杂度明显低于RS码和SRC这两种编码方案。

4.3 修复带宽开销

分布式存储系统中出现节点故障，在修复过程中下载的数据量大小称为修复带宽开销。针对单节点故障，传统的(n,k)RS码在修复过程中需要下载整个原文件来修复故障节点，故单节点修复带宽开销为M；对于(n,k,f)SRC, SRC在修复过程中需要连接f个存活节点，每个节点存储f+1个数据块，且单个数据块大小为M/fk，故单节点修复带宽开销为 (f+1)M/k；针对本文基于λ=1差集矩阵构造的FR码，由构造可知一个平行类中有λp2个编码块，节点存储大小为λp， 由于外部采用系统(k+3,k)M DS码，故有λp2=k+3，经计算可知，一个平行类中含有p=个节点，每个数据块大小为M/k， 故基于λ=1差集矩阵构造的FR码的修复带宽开销为。考虑到基于λ=1构造的FR码是最优的，由文献[13]可知，M(k)≥CMBR√(n,k,d)， 故可以得出M(k)≥−(k −1)k/2。因此可以计算出FR码的最小修复带宽开销为k+3−，可计算出k=1时最小，修复带宽开销为4，此时M(k)≥2。

在性能分析部分提前设定相关参数，文件大小恒为M= 1000 Mb ，SRC的子文件数f=4。单节点故障时，SRC的修复带宽开销为5M/k，采用例2中构造的FR码的修复带宽开销为4M/k，由于文件大小为M= 1000 Mb ，并且基于λ=1构造的FR码是最优的，满足M(k)≥CMBR(n,k,d)，因此k存在最大值，当k取最大值时，修复带宽开销最小。单节点故障修复带宽开销如图2所示。

当两节点故障时，传统的 (n,k)RS码在修复过程中需要下载整个原文件来修复故障节点，故两节点修复带宽开销依旧为M；对于(n,k,f)SRC，其修复带宽受两个故障节点之间的节点数影响。如果节点数大于f−1，那么这两个故障节点可以分别连接f个存活节点来修复，此时的修复带宽开销为2(f+1)M/k，反之如果节点数小于f−1，不能按照单节点故障修复方法进行修复，需要先恢复原文件，进一步修复故障节点，故修复带宽为M。针对本文基于λ=1差集矩阵构造的FR码，由于一个平行类含有个节点，故两个节点故障时的修复带宽开销依旧为。

两个节点故障时，采用例2中FR码的修复带宽开销为4M/k， 而RS码和SRC的修复带宽开销为M。两节点故障修复带宽开销如图3所示，其中RS码和SRC的曲线重合。

从图2和图3可以看出，不论是单节点故障还是多节点故障，基于λ=1差集矩阵构造的FR码的修复带宽开销明显优于RS码和SRC简单再生码。

图2 λ =1时单节点故障修复带宽开销性能对比

图3 λ =1时两节点故障修复带宽开销性能对比

4.4 修复局部性

考虑单节点故障时，(n,k)RS码在修复过程中，需要连接k个节点，修复局部性为k；而SRC需要连接2f个节点，修复局部性为2f；针对基于差集矩阵构造的FR码，由构造可知一个平行类中共有λp2个编码块，节点存储大小为λp，一个平行类中包含p个节点，故单节点故障修复局部性为p。采用系统(k+3,k)MDS码，故有λp2=k+3，经计算可知，单节点故障的修复局部性为p=。

考虑两节点故障，SRC和 (n,k)RS码的修复局部性均为k。而本文提出的基于差集矩阵的FR码，一个平行类含有p个节点，故p个节点即√可以修复任意节点故障，因此修复局部性恒为p=。

假设F R 码外部采用 (k+3,k)M D S 码中的k=13 ， 则λ=1构 造的FR码外部采用( 16, 13)MDS码。如图4所示，考虑单节点故障，( 16, 13)RS码的修复局部性为13；当f取4时，SRC的修复局部性为8；采用例2中构造的FR码的修复局部性为4。当两个节点故障时，( 16, 13)RS码和SRC的修复局部性均为13，采用例2中FR码的修复局部性仍为4，具体如图4所示。与RS码和SRC相比，无论单节点故障还是两节点故障，基于λ=1的差集矩阵构造的FR码都具有较优的修复局部性。

图4 λ =1时单节点故障修复局部性性能对比

假设FR码外部采用(k+3,k)M DS码中的k=15，则基于λ=2的差集矩阵构造的FR码外部采用(18, 15)M DS码。如图5所示，单节点故障时，(18, 15)RS码的修复局部性为15；当f取4时，SRC的修复局部性为8；采用例3中FR码的修复局部性为3。考虑两节点故障时， ( 18, 15)RS码和SRC的修复局部性均为15，采用例3中FR码的修复局部性仍为3。与RS码和SRC相比，无论单节点故障还是两节点故障，基于差集矩阵λ>1的FR码都具有较小的修复局部性。

图5 λ =2时两节点故障修复局部性性能对比

5 结论

针对目前基于部分图构造的FR码，构造过程复杂，本文提出了一种基于差集矩阵的FR码的构造算法，可以容忍多节点故障，同时可以任意调整节点间的共有编码块数，在参数选取上比较灵活。进一步证明了提出的基于差集矩阵λ=1的FR码是最优的，并给出了基于差集矩阵λ=2构造的FR码的文件大小，且其修复局部性明显减小。性能分析和仿真结果表明，与传统的RS码和SRC相比，构造的FR码虽然牺牲了存储开销，但是可以显著减少故障节点的修复局部性和修复带宽开销，降低修复复杂度。