Construction of Fractional Repetition Codes Based on Hadamard Matrix

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

定义1^[17-18] $n$阶方阵${{{\mathit{\boldsymbol{H}}}}_n}$，其元素为1或−1，并且满足：

称${{{\mathit{\boldsymbol{H}}}}_n}$为$n$阶Hadamard矩阵，其中${{{\mathit{\boldsymbol{I}}}}_n}$是$n$阶单位矩阵。

若${{{\mathit{\boldsymbol{H}}}}_n}$的第1行和第1列全是1，该${{{\mathit{\boldsymbol{H}}}}_n}$为Hadamard矩阵的标准型。以下所涉及的Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_n}$均为Hadamard标准型矩阵。

Hadamard矩阵有如下一些性质：

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

2) 若${{{\mathit{\boldsymbol{H}}}}_n}$是$n$阶Hadamard矩阵$(n > 2)$，则$n$是4的倍数。

定义2 ^[19] 令：

其中${{{\mathit{\boldsymbol{J}}}}_n}$表示元素全为1的$n$阶矩阵，则得到$n$阶0-1矩阵${{{\mathit{\boldsymbol{K}}}}_n}$。

性质1　矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中除第一行之外，每一行都有$n/{\rm{2}}$个1和$n/{\rm{2}}$个0。

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

定义3(FR码)^[21] 分布式存储系统中参数为$(n,k,d)$的部分重复码$C = \left( {\eta ,M} \right)$，将数据块复制$\rho $倍(即重复度为$\rho $)，特定地，$n$个子集的集合$M{\rm{ = }} $$ \{ {M_1},{M_2}, \cdots ,{M_n}\}$，子集中的元素都来自于集合$\eta {\rm{ = }} $$ \{ {\rm{1}},2, \cdots ,\theta \} $。

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

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

2) $\eta $中的每个元素属于$M$中的$\rho $个子集。

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

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

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

1) 将原始文件$M$分成$k$个原始数据块，这里$k \geqslant 2$。对该$k$个原始数据块采用$(n,k)$MDS编码$(n \geqslant k)$，得到$n$个编码数据块${c_{\rm{1}}}, \cdots ,{c_{k{\rm{ - }}1}},{c_k}, {c_{k + 1}}, \cdots ,{c_n}$，$n$个编码数据块包括$k$个原始数据块和$n - k$个校验数据块；

2) 取一个n+1阶标准型Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_{n + 1}}$，其中n+1=1,2，或n+1=0(mod4)；

3) 根据公式：

得到0-1矩阵${{{\mathit{\boldsymbol{K'}}}}_{n + 1}}(n \geqslant k)$，其中${{{\mathit{\boldsymbol{J}}}}_{n + 1}}$表示元素全为1的$n + 1$阶矩阵，${{{\mathit{\boldsymbol{H}}}}_{n + 1}}$为标准Hadamard矩阵，需满足$n + 1$为4的倍数；

4) 对0-1矩阵${{{\mathit{\boldsymbol{K'}}}}_{n + 1}}$进行变换，将第一行第一列删去得到新矩阵${{{\mathit{\boldsymbol{K}}}}_n}$；

5) 通过矩阵${{{\mathit{\boldsymbol{K}}}}_n}$构造FR码，具体过程为：

① 矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中每一行代表一个节点，用矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中的第$i$行表示分布式存储系统中的第$i$个存储节点${N_i}$，共有$n$个存储节点，$i = 1,2, \cdots ,n$；

② 由以下公式构造FR码：

式中，$j = 1,2, \cdots ,n$；$i$表示第$i$个FR节点；${a_{ij}}$表示矩阵第i行第j列的值；${N_i}$表示FR码的存储节点。${N_i}$中包含的数据块为矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中第$i$行所有1所对应的列数，将列数提取出即得到一个节点所存储的数据块，构成了所需FR码。

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

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

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

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

1) 取一个8阶标准Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_{\rm{8}}}$；由上节构造部分重复码方法的步骤1)～步骤4)得到新矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$，并利用新矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码；

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

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

② 如果$s$不能被$k{\rm{ = 5}}$整除，即$s = tk + m$且m=1，前t−1个局部修复组采用(7, 5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码，第t个局部修复组采用(7,6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码；

③ 若$s = tk + m$且$m = {\rm{2}}$，前$t - {\rm{2}}$个局部修复组采用(7, 5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码，第t−1个和第t个局部修复组采用(7, 6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码；

④ 若$s = tk + m$且$m = 3$或者4时，前t−1个局部修复组采用(7,5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码，第t个局部修复组采用(7,m)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码。

以包含$s = 11$个数据块的原始文件为例，$s = 2k + 1$，这里m=1，满足情况②。第1个局部修复组采用(7,5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码，第2个局部修复组采用(7,6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码。构造的分组FR码如图3所示。

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

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

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

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

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

当节点发生故障时，修复故障节点被下载的数据量大小称为修复带宽开销。在分布式存储系统中，原文件大小为$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码的单节点故障的修复带宽开销为${\rm{3}}M/{\rm{}}k$。单节点故障的3种编码方式修复带宽开销对比如图4所示。

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

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

修复局部性是指故障节点修复过程中需要连接的存活节点数目，即修复过程中的磁盘I/O开销。首先对于单节点失效，简单再生码修复时需要连接$2f$个存活节点，所以局部修复性为$2f$；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。

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

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

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

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