近些年, 随着信息技术和大数据产业的发展, 数据量激增, 传统集中存储设备已无法满足海量数据存储要求. 分布式存储系统(DSS)应运而生, DDS是由许多廉价磁盘组成, 具有成本低、可用性强和可扩展性高等突出优势. 它作为可存储大量数据的存储系统已经被许多互联网企业应用, 例如Microsoft和Facebook^[1,2]. 然而分布式存储系统的节点易发生故障而造成数据丢失, 所以故障节点的修复成为研究的重点.

主要通过复制和编码来保证数据的可靠性. 传统的DSS多采用复制(replication)策略^[3], 其中三副本最为常见. 将文件复制2次即得到3个副本, 分别将其存储到系统的不同节点. 当有节点发生故障导致数据丢失, 可以通过其他正常节点的副本进行修复. 但是其占有的存储系统开销过于庞大. 于是Dimakis提出了纠删码(erasure codes)策略^[4]. 与复制策略相比, 经典的纠删码具有更大的数据可靠性和较小的存储开销. 其中最大距离可分(Maximum Distance Separable, MDS)码获得最优的存储开销性能. 但是纠删码修复故障节点时需要的修复带宽开销过大. 由于上述缺陷, Dimakis等^[4]开创性的提出并介绍了再生码, 研究发现在故障节点修复时其的修复带宽开销明显降低. 但是再生码修复故障节点时需要大量有限域的运算, 计算复杂度大.

2010年Rouayheb提出了部分重复(Fractional Repetition, FR)码, FR码是一种精确最小带宽再生码, 修复故障节点时的修复带宽减小, 同时不需要大量有限域的运算, 计算复杂度较小^[5,6]. 所以越来越多研究人员开始研究FR码, Ramamoorthy设计的FR码引入了组合设计的思想^[7]. 相继利用二部图^[8], Steiner系^[9]和序列^[10]构造FR码. 随后研究人员又研究了FR码的修复消耗最小化^[11].

部分重复码的现有编码方式节点的存储容量基本相同, 同时重复度也基本相同, 都属于同构编码方式, 但是分布式存储系统由于设备故障, 硬件差别等原因, 导致存储成本不同, 各个节点存储容量不同, 因此需要异构编码方式. 本文提出基于Hadamard矩阵和 $[7,\; 3,\;4]$ 图形分别构造异构的部分重复码的一般算法. 与现有的FR码相比, 采用Hadamard矩阵和 $[7,\;3,\;4]$ 图形构造FR码更加简洁明了, 其中基于Hadamard矩阵可实现由同构经过简单变换为异构编码方式; 基于 $[7,\; 3,\;4]$ 图形构造FR码可实现扩展延伸, 若当前结构无法满足需求, 可对其进行扩展, 直至满足需求, 而且无需改变现有结构. 经过与RS码理论分析对比发现, 设计的两种异构FR码的修复局部性、修复带宽开销进一步降低, 且可以实现故障节点精确无编码修复, 修复复杂度较低, 修复效率较高, 减少了修复故障节点的时间.

1 基础知识 1.1 Hadamard矩阵

定义1^[12]. 满足: ${{{H}}_n}{{{H}}_n}^{\rm{T}} = n{{{I}}_n}$ ; ${{{H}}_n}$ 是一个n阶方阵其由1或−1构成, ${{{I}}_n}$ 是一个n阶单位矩阵, 称 ${{{H}}_n}$ 为n阶Hadamard矩阵.

Hadamard矩阵具有如下性质:

(1)将Hadamard矩阵的任意两行(列)交换, 矩阵的任意一行(列)的所有元素乘−1, 得到的矩阵仍然是Hadamard矩阵.

(2) 若 ${{{H}}_n}$ 是 $n$ 阶Hadamard矩阵, 需要满足n是4的倍数 $(n > 2)$ .

本文所需的Hadamard矩阵均为标准型, 即 ${{{H}}_n}$ 的第1行和第1列全是1.

1.2 部分重复码

定义2^[13]. FR码. 给定一个部分重复码 $C = \left( {\partial ,M} \right)$ , 其中参数为 $\left( {n,k,d} \right)$ ,将重复度设为 $\;\rho $ (即编码数据块复制 $\;\rho $ 倍), 特定地, $M{{ = \{ }}{M_1},\cdots,{M_n}{{\} }}$ 为 $n$ 个子集的集合, $ {M}_{{i}} ({1<={{i}}<={{n}}})$ 中的每一个元素都属于集合 $\partial {{ = \{ 1}},\cdots,\theta {{\} }}$ .

另外还需满足以下两个条件:

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

2) $\partial $ 中每一个元素分别存在于 $M$ 的 $\;\rho $ 个子集中.

如果d和 $\rho $ 分别都为固定值则为同构FR码, 如果d不是固定的值则为存储容量异构的FR码; 如果 $\;\rho $ 不是固定的值则为重复度异构的FR码.

FR码的本质为将经过MDS编码后的数据块复制 $\;\rho $ 倍, 随后将其分别放置在 $n$ 个不同节点中, 其中同一个的编码数据块不能出现在一个节点中.

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

本节基于Hadamard矩阵构造存储容量不同的异构部分重复码. 首先选一个 ${{4s}}(s = 1,2,3,\cdots)$ 阶的Hadamard矩阵, 再将此Hadamard矩阵进行简单变换即可得到所需矩阵. 将编码数据块与矩阵进行类比联系, 分布式存储系统中的节点对应矩阵的行, 而不同的编码块对应于矩阵的列. 根据Hadamard矩阵, 引出存储容量不同的异构FR码一般性构造算法, 其具体步骤如下:

步骤1. 首先采用 $ (n,k)$ MDS编码( $n \ge k$ )对原始文件进行编码, 得到n个编码数据块 ${c_{1}}, \cdots ,{c_{k{\rm{ - }}1}},{c_k},{c_{k + 1}}, \cdots, {c_{{n}}}$ , 其中包括k个原始数据块和 $n - k$ 个校验数据块^[6];

步骤2. 取一个 $n + 1$ 阶标准型Hadamard矩阵 ${{{H}}_{n + 1}}$ (n+1为4的倍数), 由式(1)对 ${{{H}}_{n + 1}}$ 进行简单变换:

$ {{{K'}}_{n + 1}} = \frac{{{{{J}}_{n{\rm{ + 1}}}}{\rm{ + }}{{{H}}_{n{\rm{ + 1}}}}}}{2} $

(1)

矩阵 ${{{J}}_{n + 1}}$ 中元素全为1, ${{{H}}_{n + 1}}$ 为标准Hadamard矩阵, 得到的 ${{{K'}}_{n + 1}}(n \ge k)$ 是一个0-1矩阵, 将 ${{{K'}}_{n + 1}}$ 的第一行和第一列同时删去得到所需矩阵 ${{{K}}_n}$ ;

步骤3. 将矩阵 ${{{K}}_n}$ 中第j列出现的第 $\Big(({{j + 1}}){\rm{mod}} \left.{\left( {\dfrac{{n - 1}}{2}} \right)} \right)$ 个1改为0得到新的矩阵 ${{{K}}_{n{1}}}$ , 然后计算式(1):

${N_i} = \left\{ {j:{a_{ij}} = 1} \right\}$

(2)

其中, $j = 1,2 \cdots, n$ , i表示第i个FR节点, ${a_{ij}}$ 表示矩阵第i行第j列的值. 其中表示异构FR码的存储节点, 将矩阵 ${{{K}}_{n{1}}}$ 中第i行中全部的1所分别对应的列数提取出来, 即可得到一个节点 ${N_i}$ 存储的数据块, 得到节点存储容量不同的异构FR码.

具体的, 选取一个12阶的Hadamard矩阵如图1所示, 对其按步骤2操作得到11阶矩阵 ${{{K}}_{{\rm{11}}}}$ 如图2所示, 每一列的第 $ \left( {\left( {{{j}} + 1} \right)od \left( {\dfrac{{n - 1}}{2}} \right)} \right) $ 个1改为0得到新的矩阵 ${{{K}}_{{\rm{111}}}}$ 如图3所示. 随后节点对应矩阵的行, 而不同的编码块对应于矩阵的列. 所以我们得到了存储容量不同的异构的FR码, 每个节点的存储结构如图4所示, 其节点的存储容量 $ d={3},\;{4},\;5$ , 编码块的重复度 $\;\rho = {4}$ .

单个节点发生故障时, 可以根据存活的其他节点直接下载所需的数据, 即可恢复故障节点. 例如在图4中, 若第二个节点 ${N_{2}}$ 发生故障, 通过下载节点 ${N_{7}}$ 恢复数据块5和11, 下载 ${N_{\rm{9}}}$ 恢复数据块3和7, 即可完成节点 ${N_{2}}$ 的恢复; 同时也可以根据节点 ${N_3}$ , ${N_{\rm{8}}}$ , ${N_{{\rm{11}}}}$ 分别下载数据块3, 5, 7, 11, 也可完成故障节点 ${N_{2}}$ 的恢复. 单节点发生故障可采用多种方式来恢复, 同时也实现故障节点的精确无编码修复. 当两个节点发生故障时, 方法同一个故障节点修复.

3 可扩展的异构部分重复码

本小节提出一种基于 $[7,\;3,\;4]$ 简单图形构造可扩展异构部分重复码的算法, 此算法可以简单对部分重复码进行扩展, 如现有结构不满足已有需求需要进行扩容, 则不需破坏已有的结构, 只需在图形尾部直接旋转拼接图形扩展, 使得FR码可扩展, 具体构造步骤如下所示:

步骤1. 首先采用 $ (n,k)$ MDS编码( $n \ge k$ )对原始文件进行编码, 得到 $n$ 个编码数据块 ${c_{1}}, \cdots ,{c_{k{\rm{ - }}1}},{c_k},{c_{k + 1}}, \cdots, {c_{{n}}}$ , 其中包括 $k$ 个原始数据块和 $n - k$ 个校验数据块^[6];

步骤2. 取一个 $[7,3,4]$ 简单图形, 如图5所示.

步骤3. 通过 $[7,\;3,\;4]$ 简单图形构造FR码: 将外围3个顶点当作存储节点, 将内部的4个顶点当作数据块, 数据块按照顺时针存放, 临近存储节点的3个数据块存放在该存储节点.

将 $[7,\;3,\;4]$ 简单图形的外围3个顶点当作存储节点, 将 $[7,\;3,\;4]$ 简单图形内部的4个顶点当作数据块, 数据块按照顺时针存放, 临近存储节点的3个数据块存放在该存储节点.

步骤4. 通过将 $[7,\;3,\;4]$ 简单图形旋转拼接构造可扩展FR码:

1)将扩展的 $[7,\;3,\;4]$ 简单图形的外围罗马数字代表一个节点, 外围的第 $i$ 个点表示分布式存储系统中的第 $i$ 个存储节点 ${N_i}$ , 共有 $n$ 个存储节点( $i={\rm{I}},{\rm{II}},\cdots, n$ ); 将与存储节点直接相连的数据块当作该存储节点存放的数据块, 即可得到存储容量和重复度异构的FR码.

2)当数据块 $n=3t + 4$ 时, 需要 $t{\rm{ + 1}}$ 个 $[7,\;3,\;4]$ 简单图形旋转拼接, 构造出具有 $t{\rm{ + 3}}$ 个存储节点, $n$ 个数据块的FR码. 当数据块 $ n=4+3t+s({{\rm{s}}=1},{2})$ 时, 需要 $t{\rm{ + 2}}$ 个 $[7,\;3,\;4]$ 简单图形旋转拼接, 构造出具有 $t{\rm{ + 3}}$ 个存储节点, $n$ 个数据块的FR码.

若构造一个具有6个存储节点, 13个数据块的FR码. 可将基本图形翻转拼接3次, 得到如图6所示图形, 按上述方法可得到6个存储节点所存放的数据块, 如图7所示, 若当前结构无法满足需求, 可对其进行扩展, 直至满足需求, 而且无需改变现有结构, 如图8所示.

可以看出共有6个存储节点. 存储节点N₁和N₅的存储容量是5, 存储节点N₃和N₄的存储容量是7, 并且重复度 ${\;\rho _{}}$ 为2或3的一个异构的FR码.

当单个节点发生故障时, 如图7中, 当第二个节点 ${N_{2}}$ 发生故障时, 通过下载节点 ${N_{1}}$ 恢复数据块1和4, 下载 ${N_3}$ 恢复数据块2, 来完成节点 ${N_{2}}$ 的恢复; 当节点 ${N_3}$ 发生故障时, 通过下载节点 ${N_{1}}$ 恢复数据块3, 4和7, 下载 ${N_{2}}$ 恢复数据块2, 下载 ${N_{4}}$ 恢复数据块6和10, 下载 ${N_{5}}$ 恢复数据块8, 即可完成节点 ${N_3}$ 的恢复. 具体修复方式可选择性较大, 同时实现故障节点的精确无编码修复.

4 性能分析

本小节对基于Hadamard矩阵构造存储容量异构的部分重复码和基于 $[7,\;3,\;4]$ 简单图形构造可扩展的异构部分重复码进行性能分析, 主要考虑修复带宽开销和修复局部性方面的性能, 并与常见的RS编码进行性能比较. 为了便于比较, 基于Hadamard矩阵构造存储容量异构的部分重复码算法选取 $(11,\;9)$ FR码, 基于 $[7,\;3,\;4]$ 简单图形构造可扩展异构部分重复码的算法选取 $(13,\;9)$ FR码, 取 $M=1000\;{\rm{Mbit}}$ .

4.1 修复带宽开销

修复带宽开销指的是恢复失效节点时下载的数据量大小. 例如采用 $(11,\;9)$ RS编码, 由于RS编码恢复故障节点需要下载全部原文件, 所以修复带宽开销为 $\eta = M$ ; 采用基于Hadamard矩阵构造存储容量不同的异构部分重复码构造 $(11,\;9)$ FR码时, 发生节点故障时的修复带宽开销为 $\eta {=3}M/{{k}},5M/{{k}}$ 或者 $7M/{{k}}$ . 为便于比较, 本文选取中间值作为代表值. 在采用基于 $[7,\;3,\;4]$ 简单图形构造可扩展异构部分重复码的算法构造 $(13,\;9)$ FR码时, 发生节点故障的修复带宽开销为 $\eta {=3}M/{{k}},5M/{{k}} $ 或者 $7M/{{k}} $ , 而采用 $(13,\;9)$ RS编码时, 发生节点故障的修复带宽开销为 $\eta =M$ . 由于图形特殊构造, 随着节点增多修复带宽开销基本都是 ${7}M{/{{k}}}$ , 所以选取其为代表值. 以上2项数据与RS码仿真对比如图9所示.

经过对比不难发现本文提出的两种异构部分重复码构造的算法, 节点发生故障时修复带宽开销比RS编码明显降低. 当节点数少于16时, 基于Hadamard矩阵构造的异构FR码修复带宽开销小于基于 $[7,\;3,\;4]$ 简单图形构造异构FR码. 但是当节点数逐渐增大, 基于 $[7,\;3,\;4]$ 简单图形构造异构FR码的修复带宽开销小于基于Hadamard矩阵构造的异构FR码.

4.2 修复局部性

发生节点故障时需要连接的存活节点数目称为修复局部性. 当发生单节点故障时, $(11,\;9)$ RS编码需要连接9个节点恢复原文件用以修复故障节点, 修复局部性为9; 而基于Hadamard矩阵构造存储容量异构的FR码构造的 $(11,\;9)$ FR码, 单节点故障时需要连接2个或者3个节点来修复, 故修复局部性为2或者3.

采用基于 $[7,\;3,\;4]$ 简单图形构造可扩展异构部分重复码的算法构造 $(13,\;9)$ FR码时, 发生节点故障时需要连接2, 3或者4个节点来恢复故障节点, 所以修复局部性为2, 3或4; 而 $(13,\;9)$ RS码发生单节点故障时, RS码修复局部性为9.

分析发现修复单个故障节点时, 基于Hadamard矩阵构造存储容量异构的FR码和基于 $[7,\;3,\;4]$ 简单图形构造可扩展异构FR码的修复局部性, 优于RS编码的修复局部性. 但是 $[7,\;3,\;4]$ 简单图形构造的异构FR码无法修复多节点故障, 是下一步研究的方向.

5 结论

本文提出基于Hadamard矩阵和 $[7,\;3,\;4]$ 图形分别构造异构的部分重复码的一般算法. 与现有的FR码相比, 采用Hadamard矩阵和 $[7,\;3,\;4]$ 图形构造FR码更加简洁明了, 其中基于Hadamard矩阵可实现由同构经过简单变换为异构编码方式; 基于 $[7,\;3,\;4]$ 图形构造FR码可实现扩展延升, 若当前结构无法满足需求, 可对其进行扩展, 直至满足需求, 且无需改变现有结构. 经过与RS码理论分析对比发现, 设计的两种异构FR码的修复局部性、修复带宽开销进一步降低, 性能进一步提高.