基于Hadamard 矩阵构造部分重复码

王 静，孙 伟*，何亚锦，沈克勤，张鑫楠，刘向阳

(1. 长安大学信息工程学院 西安 710064；2. 国防科技大学信息通信学院 西安 710106)

近年来，由于数据量的快速上升，急需一种适宜的大数据存储系统。分布式存储系统由许多廉价磁盘组成，以其突出优势成为海量数据存储的有效系统，并被广泛部署和使用[1]。但在分布式存储系统中，节点容易发生故障，造成数据丢失。因此，故障节点的快速修复研究成为了分布式存储系统可靠性的重中之重。

目前，分布式存储系统主要通过复制和纠删码策略来恢复节点故障。复制策略中三副本复制最为常见，故障节点修复具有较低的修复带宽开销，但需要存储大量的副本数据，存储开销较大。纠删码策略通过增加校验数据块来确保数据存储的可靠性，实现故障节点修复，且存储开销较小。虽然纠删码弥补了复制策略存储开销大的缺点，但是纠删码在修复故障节点时的修复带宽开销过大[2]。

鉴于复制和纠删码策略存在上述局限性，文献[3]将网络编码应用到分布式存储中，提出了再生码的概念，降低了故障节点的修复带宽开销。现在再生码研究重点在最小存储再生(minimum storage regeneration, MSR)码和最小带宽再生(minimum bandwidth regeneration, MBR)码[4-5]。再生码在修复故障节点时，需要连接大量存活节点以获得较低的修复带宽开销，且在修复过程中涉及有限域运算，计算复杂度相对较高。随后，文献[6]提出了局部修复码(locally repairable codes, LRC)，使修复过程中需要连接的存活节点数较小，修复带宽开销较低，具有较好的修复局部性。将再生码和局部修复码结合，文献[7-8]提出了局部再生码的概念，达到存储-带宽开销的最佳折中。其中，基于系统MSR码的局部再生码，故障局部码可以通过相邻局部码进行协作修复[9]。

文献[10]提出了一种精确最小带宽再生码—部分重复(fractional repetition, FR)码，故障节点修复过程中的计算复杂度和修复带宽开销都有所降低，可以实现故障节点的精确无编码修复。近年来，许多研究人员对FR 码进行了研究，文献[11]利用组合设计来构造FR 码。随后，学者们又相继给出了几种基于组合结构的FR 码构造，包括基于射影几何的FR 码构造[12]、基于正则图的FR 码构造[13]及基于可分组设计的FR 码构造[14]。

现有FR 码对于故障节点的修复，特别是多节点故障修复，其修复带宽开销和修复局部性较高，同时修复复杂度也较高。文献[13]提出了基于正则图构造FR 码，随后文献[15]提出了运用网格构造FR 码，但其都只能修复单节点故障。基于相对差集的FR 码构造，能够修复分布式存储系统中的多节点故障，但是随着参数的增大，其节点存储容量和构造复杂度会随之增大[16]。而且常见的FR 码构造随着系统规模和参数的增大，其节点数或节点容量增大，构造复杂度也会增大。本文提出基于Hadamard 矩阵构造FR 码，同时对其进行分组，运用8 阶Hadamard 矩阵提出了分组构造FR(Hadamard grouping fractional repetition, HGFR)码的一般算法，实现故障节点的局部修复。基于Hadamard 矩阵分组构造FR 码可以对多个节点故障进行快速精确无编码修复，有效降低了运算复杂度，同时运用了分组可以实现组内修复，复杂度进一步降低，实现故障节点的快速修复。理论分析发现，与RS 码和SRC 简单再生码相比，设计的FR 码在分布式存储系统节点发生故障时，修复局部性、修复复杂度和修复带宽开销进一步降低，且修复效率提高，减少了故障节点的修复时间。

1 Hadamard 矩阵和部分重复码

1.1 Hadamard 矩阵

Hadamard 矩阵是在工程技术上运用较多的一类矩阵，Hadamard 矩阵是特殊的1、-1 二元矩阵，具体定义如下：

定义1[17-18]n阶方阵 Hn，其元素为1 或-1，并且满足：

称 Hn为n阶Hadamard 矩阵，其中 In是n阶单位矩阵。

若Hn的第1 行和第1 列全是1，该Hn为Hadamard矩阵的标准型。以下所涉及的Hadamard 矩阵 Hn均为Hadamard 标准型矩阵。

Hadamard 矩阵有如下一些性质：

1) 将Hadamard 矩阵的任意两行(或两列)交换，Hadamard 矩阵的任意一行(或一列)的所有元素乘以-1，得到的矩阵仍然为Hadamard 矩阵。

2) 若 Hn是 n阶Hadamard 矩阵(n ＞2)，则 n是 4 的倍数。

定义2[19]令：

其中 Jn表示元素全为1 的n阶矩阵，则得到n阶0-1矩阵 Kn。

性质1 矩阵 Kn中除第一行之外，每一行都有n/2个1 和 n/2个0。

1.2 FR 码

FR 码是在MBR 码基础上提出的，典型的FR码由两部分组成，外部的MDS 码和内部的重复码[20]。

定义3(FR 码)[21]分布式存储系统中参数为(n,k,d)的部分重复码C=(η,M)，将数据块复制ρ倍(即重复度为 ρ)，特定地， n个子集的集合M={M1,M2,···,Mn}，子集中的元素都来自于集合η={1,2,···,θ}。

同时应满足以下两个条件：

1)每个子集的大小均为d ；

2) η中的每个元素属于 M中的ρ个子集。

上述定义中，数据块是经过MDS 编码后的数据块。FR 码的实质是将数据块复制ρ倍，然后将其排列到n个节点，同时使相同的数据块不出现在同一个节点上。图1 为经过(12,9)MDS 编码后构成(12,9,4)FR 码，其中ρ为2，数据复制2 倍，每个节点存放4 个编码数据块。

FR 码修复故障节点时直接从未失效节点中下载丢失的所需数据块，不进行编译码操作即可完成故障节点的迅速修复。FR 码可实现精确无编码修复，修复带宽开销和修复时间较低，修复复杂度较小，同时能够容忍ρ-1个节点故障。

图1 (12,9,4)FR 码

2 基于Hadamard 矩阵构造FR 码

本节基于Hadamard 矩阵构造FR 码。首先选取一个4t(t=1,2,3,···)阶的Hadamard 矩阵，对其进行简单的变换得到所需要的矩阵；再将矩阵与分布式存储节点和编码数据块相对应，矩阵的行代表存储节点，矩阵中不同的列表示不同的编码数据块。由Hadamard 矩阵引出FR 码一般性构造算法，其具体步骤如下：

1) 将原始文件 M分成k个原始数据块，这里k ≥2。对该 k个原始数据块采用(n,k)MDS 编码(n ≥k)，得到n个编码数据块c1,···,ck-1,ck,ck+1,···,cn，n个编码数据块包括k个原始数据块和n-k个校验数据块；

2) 取一个n+1 阶标准型Hadamard 矩阵Hn+1，其中n+1=1,2，或n+1=0(mod4)；

3) 根据公式：

得到0-1 矩阵K′n+1(n ≥k)，其中Jn+1表示元素全为1 的n+1阶矩阵，Hn+1为标准Hadamard 矩阵，需满足n+1为4 的倍数；

4) 对0-1 矩阵K′n+1进行变换，将第一行第一列删去得到新矩阵 Kn；

5) 通过矩阵 Kn构造FR 码，具体过程为：

① 矩阵 Kn中每一行代表一个节点，用矩阵Kn中的第i行表示分布式存储系统中的第i个存储节点 Ni，共有n个存储节点，i=1,2,···,n；

② 由以下公式构造FR 码：

式中，j=1,2,···,n； i表示第i个FR 节点； aij表示矩阵第i 行第j 列的值； Ni表示FR 码的存储节点。 Ni中包含的数据块为矩阵 Kn中第i行所有1 所对应的列数，将列数提取出即得到一个节点所存储的数据块，构成了所需FR 码。

采用上述FR 码的一般性构造算法，在包含n=11个存储节点的分布式存储系统中，构造FR 码。选取如式(3)所示的12 阶Hadamard 矩阵，利用式(1)对该Hadamard 矩阵进行变换，进一步得到所需的11 阶矩阵 K11，如式(4)所示。采用该 K11矩阵，按照步骤5)构造得到FR 码，该FR 码的节点存储结构具体如图2 所示。其中矩阵的行代表分布式存储系统中的存储节点，矩阵中不同的列表示不同的编码数据块，每个存储节点存储d=5个编码块，编码块的重复度ρ=5。

图2 FR 码的节点存储结构图

当一个节点发生故障时，可以运用其他节点对故障节点进行修复，在其他节点中找到并下载含有故障节点的数据块，故障节点即完成了修复，且该过程不需要进行编码译码操作。对于图2 中的FR码，若节点 N1发生故障，可以分别从存活节点 N3中下载数据块4 和6，从存活节点 N4中下载数据块2 和5，以及存活节点 N5中下载数据块10，实现节点 N1的修复。对于两个节点发生故障的情况，与一个节点故障修复的方法相同。

3 基于Hadamard 矩阵构造分组FR 码

运用Hadamard 矩阵构造FR 码发现，随着Hadamard 矩阵阶数的增加，FR 码的重复度和节点存储容量也会随之增加，从而导致存储开销也相应地增加，故障节点修复性能受到一定限制。为此，本节引入分组构造的思想构造部分重复码。当Hadamard 矩阵的阶数为12 时构造的FR 码的重复度为5，重复度较大；当阶数为8 时FR 码的重复度降为3，更满足实际存储需求，所以本文利用8 阶标准Hadamard 矩阵构造分组FR 码。

3.1 基于Hadamard 矩阵构造分组部分重复码

对分布式存储系统节点进行分组，并利用8 阶Hadamard 矩阵构造分组FR 码(hadamard grouping fractional repetition, HGFR)。分组FR 码的具体构造算法如下：

1) 取一个8 阶标准Hadamard 矩阵 H8；由上节构造部分重复码方法的步骤1)～步骤4)得到新矩阵 K7，并利用新矩阵 K7构造FR 码；

2) 记原始文件M 包含s个原始数据块，将原始数据块进行分组，得到t个局部修复组，每组分配k=5个原始数据块。包含以下几种情况：

① 如果s可以被k=5整除，即s=tk ，此时每个局部修复组内首先进行(7, 5)MDS 码编码，然后采用步骤3)中的矩阵 K7构造FR 码；

② 如果s不能被k=5整除，即s=tk+m且m=1，前t-1 个局部修复组采用(7, 5)MDS 码以及矩阵K7构造FR 码，第t 个局部修复组采用(7,6)MDS码以及矩阵 K7构造FR 码；

③ 若s=tk+m且m=2，前t-2个局部修复组采用(7, 5)MDS 码以及矩阵 K7构造FR 码，第t-1 个和第t 个局部修复组采用(7, 6)MDS 码以及矩阵K7构造FR 码；

④ 若s=tk+m且m=3或者4 时，前t-1 个局部修复组采用(7,5)MDS 码以及矩阵 K7构造FR 码，第t 个局部修复组采用(7,m)MDS 码以及矩阵 K7构造FR 码。

以包含s=11个数据块的原始文件为例，s=2k+1，这里m=1，满足情况②。第1 个局部修复组采用(7,5)MDS 码以及矩阵 K7构造FR 码，第

2 个局部修复组采用(7,6)MDS 码以及矩阵 K7构造FR 码。构造的分组FR 码如图3 所示。

图3 分组FR 码的节点存储结构图

3.2 故障节点修复

下面考虑分布式存储系统采用基于Hadamard矩阵的分组FR 码，其故障节点的修复。考虑到3 个以上节点同时故障的概率很低，本文只考虑分布式存储系统中1 个、2 个或者3 个节点故障，且在同一个或者不同局部修复组内的情况。具体故障节点修复过程如下：

1)当分布式存储系统只有1 个节点故障，此时只需考虑在一个局部修复组内对单一故障节点进行修复。具体地，在该局部修复组内其他存活节点中找到含有故障节点的数据块，直接下载故障节点丢失的数据块，即可完成故障节点修复，该过程不需要进行编码操作。如图2 所示，如第一个局部修复组中第一个节点发生故障，可以下载节点 N2、 N4、N6中的2、4 和6 这3 个数据块完成第一个节点的修复。

2)当分布式存储系统中有2 个节点同时发生故障时，存在以下两种情况：① 2 个故障节点在同一局部修复组内，可以从剩余的5 个存活节点中下载故障节点所含有的数据块，完成故障节点的快速修复；② 发生故障的2 个节点不在同一局部修复组，则需要在两个修复组内分别对其组内的故障节点进行修复。在图2 中，如节点 N2和节点 N10发生故障导致数据块丢失，可以在第一个局部修复组内从节点 N1、 N4、 N5中分别下载数据块4、1 和5 完成节点 N2的修复，在第二个局部修复组内从节点N9、 N11、 N13下载数据块11、10 和14 完成节点N10的快速修复。

3)当分布式存储系统中有3 个节点同时发生故障，存在以下两种情况：①发生故障的3 个节点不在同一局部修复组，该情况下的故障节点修复与前面两种修复过程完全一样，只需直接从局部修复组中下载所需的数据块；②发生故障的3 个节点在同一局部修复组中，如果3 个故障节点中没有同时含有同一个数据块，则可以直接从其他存活节点中下载丢失的数据块，完成故障节点的修复；否则，需要运用MDS 编码进行修复。如图2 中节点 N1、N2、 N3发生故障，剩余存活节点无法直接修复，需要从存活节点下载数据块进行MDS 编码修复数据块4，即完成故障节点 N1、 N2、 N3的精确修复。

4 性能分析

本节对提出的基于Hadamard 矩阵构造分组FR 码进行性能分析，修复带宽开销、修复局部性、修复复杂度为分析的主要性能，并与SRC 简单再生码以及RS 码进行比较。取文件大小M=1 000 Mb，SRC 简单再生码的子文件数f =4。

4.1 修复带宽开销

当节点发生故障时，修复故障节点被下载的数据量大小称为修复带宽开销。在分布式存储系统中，原文件大小为 M，当发生单节点故障时，若采用(n,k)RS 码，则需要下载全部的原文件来修复故障节点，所以采用(n,k)RS 码修复单节点故障的修复带宽开销为文件大小 M；对于(n,k,f)SRC 简单再生码，每个节点存储f+1个数据块，每个数据块大小为M/fk，当一个数据块发生故障， f个数据块被下载进行修复，所以1 个节点发生故障的修复带宽开销为(f+1)M/k；如果采用基于Hadamard 矩阵的分组FR 码，每个数据块大小为M/k，每个节点含有3 个数据块，所以基于Hadamard 矩阵的分组FR 码的单节点故障的修复带宽开销为3M/k。单节点故障的3 种编码方式修复带宽开销对比如图4所示。

图4 单节点故障时的修复带宽开销

当2 个节点发生故障时，若采用(n,k)RS 码，仍然需要下载全部的原文件来修复故障节点，所以(n,k)RS 码修复2 个故障节点的修复带宽开销仍为M；对于(n,k,f)SRC 简单再生码，如果2 个故障节点数大于f-1，则2 个节点发生故障的修复带宽开销为2(f+1)M/k，如果2 个故障节点数小于f-1，需要先恢复原文件，所以修复带宽开销为 M，这里f=4，所以2 个节点故障时，SRC 简单再生码的修复带宽开销为M；如果采用基于Hadamard 矩阵的分组FR 码，2 个故障节点在同一修复组时，修复带宽开销为3M/k，不在同一修复组时，修复带宽开销为6M/k。修复带宽开销对比如图5 所示。

图5 2 个节点故障时的修复带宽开销

从图4 和图5 可以看出，基于Hadamard 矩阵的分组FR 码，单节点和两节点故障时的修复带宽开销性能明显优于RS 码和SRC 简单再生码，且在图5 中RS 码和SRC 简单再生码由于修复带宽开销一样，所以曲线重合。

4.2 修复局部性

修复局部性是指故障节点修复过程中需要连接的存活节点数目，即修复过程中的磁盘I/O 开销。首先对于单节点失效，简单再生码修复时需要连接2 f个存活节点，所以局部修复性为 2 f；RS 码发生单节点故障时，需要连接k个节点恢复原文件修复故障节点，所以RS 码修复局部性为k；基于Hadamard矩阵的分组FR 码，连接3 个未发生故障的节点来恢复单个节点故障，所以其修复局部性为3。单节点故障时的修复局部性对比如图6 所示。

对于2 个节点发生故障，SRC 简单再生码需要先恢复原文件才可以修复故障节点，所以SRC简单再生码的修复局部性为k；对于RS 码，仍然需要恢复原文件，所以修复2 个节点的修复局部性也为k；基于Hadamard 矩阵的分组FR 码，分两种情况：1) 如果一个修复组中发生2 个节点故障，从3 个未失效节点中下载所需数据，修复局部性为3；2) 2 个故障节点不在同一个局部修复组内，其修复两个故障节点需要连接6 个存活节点，修复局部性为6。

图6 单节点故障时的修复局部性

修复故障节点时，可以看出基于Hadamard 矩阵的分组FR 码的修复局部性，优于简单再生码和RS 码的修复局部性。

4.3 修复复杂度

本文提出的基于Hadamard 矩阵的分组FR码，当发生节点故障时，可以直接从其他存活节点下载数据块进行修复，无需进行编码运算。对于RS 码修复故障节点需要先恢复原文件，之后再编码生成所需要的数据块，编码数据块由k个数据块在有限域GF(q)上运算得到。所以RS 码在修复单节点故障时需要k2+k次有限域乘法运算和k2-1次有限域加法运算。对于SRC 简单再生码，其修复一个故障节点需要进行(f-1)(f+1)次异或运算。可以看出，本文构造的FR 码修复复杂度明显低于RS 码和SRC 简单再生码的修复复杂度，可以快速修复故障节点，修复时间减少。

表1 给出了分布式存储系统中，RS 码、简单再生码和基于Hadamard 矩阵的分组FR 码分别在修复带宽开销、修复局部性及节点存储开销三方面的性能比较。从表1 可以看出，基于Hadamard 矩阵的分组FR 码其修复局部性和带宽开销较低。而且，基于Hadamard 矩阵的分组FR 码在修复节点故障时可以实现精确无编码修复，运算复杂度较低，修复时间减少，可靠性提高。

5 结 束 语

现有传统编码方式对于故障节点的修复，特别是对多故障节点的修复，其修复带宽开销和修复局部性能受限，同时修复复杂度较高。为此，本文提出了基于Hadamard 矩阵的FR 码，同时对其进行分组，运用8 阶Hadamard 矩阵提出了分组FR 码的一般性构造算法。理论分析发现，基于Hadamard矩阵的分组FR 码可以对多故障节点进行快速精确无编码修复，有效降低了运算复杂度，同时运用了分组可以实现组内修复，复杂度进一步降低。与RS 码和SRC 简单再生码相比，发生故障时的修复局部性、修复复杂度和修复带宽开销进一步降低，且修复效率提高，减少了故障节点的修复时间。