当今世界互联网快速发展, 数据海量化是互联网技术发展的必然结果^[1]. 如何快速、高效、可靠地存储这些数据资源成为研究热点和面临的巨大挑战. 传统的集中式存储将数据集中存放在专用服务器或者专用磁盘阵列中, 存储海量数据时存在诸多瓶颈, 例如系统性能、存储成本和可扩展性. 分布式存储系统将海量数据存储在多个廉价存储设备中, 海量存储能力、高吞吐量、高可用性、高可扩展性和低成本等突出优势使分布式存储系统成为海量数据的有效存储手段. 但是实际的分布式存储系统中不可避免地会出现节点故障, 如何高效地修复故障节点来保障分布式存储系统的高可靠性和高可用性成为目前急需解决的关键问题^{[2, 3]}.

现有的复制和纠删码策略能修复分布式存储系统中的节点故障, 但都存在各自的缺陷. 随后, Dimakis等人将网络编码应用到分布式存储系统中, 提出了再生码的概念^[4], 显著降低了故障节点的修复带宽开销. 再生码虽然能有效降低故障节点修复时的带宽开销, 但没有考虑磁盘I/O开销和修复局部性. 为了确保修复故障节点较低修复带宽开销的同时, 需要连接的存活节点数也较少, Papailiopoulos等人提出了局部修复码(locally repairable codes, LRC)^[5]. 进一步, Hao等人和Wang等人分别研究了局部修复码的构造以及协作局部修复码^{[6, 7]}.

再生码和局部修复码在故障节点修复过程中涉及大量有限域运算, 计算复杂度较高. 为了进一步降低计算复杂度和修复带宽开销, El Rouayheb等人提出一种精确修复的最小带宽再生码——部分重复(fractional repetition, FR)码^[8]. 目前对 FR码的研究主要有基于组合设计构造FR码^[9], 基于序列构造FR码^[10], 基于二分图构造局部修复 FR码^[11], FR 码的修复消耗最小化^[12]. 这些构造算法复杂, 并且大多只能构造同构的 FR码, 不能得到异构的 FR码. Silberstein等人基于组合设计和正则图, 提出了一种达到最大码率的 FR 码的构造方法^[13], 但其重复度受 FR 码结构的约束, 不能适用于任意参数. 基于Hadamard 矩阵构造的异构部分重复码^{[14, 15]}修复复杂度和修复带宽开销都有所降低. 基于矩阵变换和可调节环的部分重复码构造^[16]可以大范围的选择参数, 构造结构简单直观. Zhu等人提出基于组合设计的FR码, 可以调整存储节点的数量和节点的存储容量^[17]. 进一步, Zhu等人对一般好的部分重复码的重复度限和重构度限进行了讨论^[18-21]. 在实际的分布式存储系统中, 数据存储的结构多为异构的, 并且需要动态存储, 即在增加或减少数据时, 自动调节数据的存储分布.

为了解决上述问题, 本文构造了一种基于节点共边的异构部分重复码(heterogeneous fractional repetition codes based on node common edge, HFRC-NCE). 具体地, 结合节点共边的特性, 将热数据存储在多点共边上, 将冷数据存储在两点共边上, 使得热数据具有较高的重复度, 同时各个节点存储的数据容量不同, 实现数据的动态存储和异构存储. 性能分析表明, 与文献[8]基于完全图和文献[22]基于部分正则图构造的部分重复码相比, 虽然HFRC-NCE的存储开销和修复带宽开销略大, 但其构造简单, 减小了文件的重构度, 节点的修复选择度更高, 节点存储的数据容量更加多样性, 使得系统能更高效地修复故障节点.

1 点共边和部分重复码 1.1 点共边

图 $ G $ 通常用 $ G = (V, E) $ 表示, 其中 $ V(G) $ 和 $ E(G) $ 分别为图 $ G $ 中的节点集和边集. 图 $ G $ 中节点的个数称为图 $ G $ 的阶, 与节点相关联的边的总数称为节点的度, 将 $ \rho $ 点存在同一条边上记为 $ {E_\rho } $ , 如图1所示. 如果图 $ G $ 中任意两个不同的节点通过边相互连接, 称图 $ G $ 为完全图. 当图 $ G $ 中每个节点都具有相同的度, 则称图 $ G $ 为正则图.

$ n $ 阶完全图的各个节点相连的边的总和为 $ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ . 完全图可视为由 $ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ 个 $ {E_2} $ 构成的图, 在任意两点都通过边相连的前提下, 当图 $ G $ 中边的总和小于 $ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ 时, 说明图 $ G $ 中的边不仅有两点相连的情况, 还存在多点共边的情况.

图2为 $ \;\rho $ 点共边时相对于 $ n $ 阶完全图减少的边数. 当一个3阶完全图变为3点共边 $ {E_3} $ 会减少两条边, 一个4阶完全图变为4点共边 $ {E_4} $ 会减少5条边. 以此类推, $ n $ 阶完全图变为 $\; \rho $ 点共边 $ {E_\rho } $ 会减少 $ \left( \begin{gathered} \rho \hfill \\ 2 \hfill \\ \end{gathered} \right) - 1 $ 条边. 当图中边的总和 $ \theta $ 小于 $ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ 时, 图中必然存在3点及以上多点共边. 将 $ \;\rho $ 点共边 $ {E_\rho } $ 的个数记为 $ {P_\rho } $ , 则:

$ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) - \sum\nolimits_{\rho = 3}^n {\left( {\left( \begin{gathered} \rho \hfill \\ 2 \hfill \\ \end{gathered} \right){P_\rho } - {P_\rho }} \right)} = \theta $

(1)

$ \sum\nolimits_{\rho = 2}^n {{P_\rho }} = \theta $

(2)

具体地以图3中的6阶图为例, 图中共有9条边, $ n = $ $ 6, \; \theta = 9 $ . 根据式(1)和式(2), 得到 $ {P_2} = 6 $ 和 $ {P_3} = 3 $ , 则图3存在3条3点共边的边 $ {E_3} $ 和6条2点共边的边 $ {E_2} $ .

1.2 部分重复码

部分重复码的实质是由外部的最大距离可分码(maximum distance separable, MDS)和内部重复码构成, 首先将原始文件分成 $ M $ 个原始数据块, 原始数据块通过 $ (\theta , M) $ MDS码编码后, 生成 $ \theta $ 个编码数据块, 再将生成的编码数据块复制 $\; \rho $ 倍分别存储到 $ n $ 个节点中, 每个节点存储 $ d $ 个不同的编码块, 得到一个 $ (n, d, \theta , \rho ) $ 部分重复码, 满足 $ nd = \theta \rho $ .

图4为基于完全图构造的部分重复码, 由外部的 $ (15, $ $ 14) $ MDS码和内部重复度 $ \rho = 2 $ 的重复码构成. 将MDS码编码后的15个数据块依次存放在完全图的不同边上, 每个节点存储5个数据块. 每个节点故障时需要连接其他5个存活节点进行修复, 所以 $ d = 5 $ . 此系统至少需要4个节点来重构原文件, 所以 $ k = 4 $ , 并且满足 $ nd = \theta \rho $ .

2 基于节点共边的异构部分重复码 2.1 基于节点共边的异构部分重复码构造

在实际的分布式存储系统中, 存储节点的存储容量大多异构. 为了满足分布式存储系统存储容量异构的特点, 结合节点共边的特性, 按照热数据重复度高和冷数据重复度低的原则构造异构部分重复码. 具体步骤如下.

步骤1. 首先将原始文件分成 $ M\;(M = \theta - 1) $ 个原始数据块, 原始数据块通过 $ (\theta , M) $ MDS码编码后生成 $ \theta $ 个编码数据块, 将其存储到具有 $ n $ 个节点的 $ n $ 阶图中.

步骤2. 设 $ {P_\rho } $ 为一个未知参数, $ {P_\rho } $ 表示 $ \;\rho $ 点共边 $ {E_\rho } $ 的数目. 将MDS码编码后的一个数据块存放在共边 $ {E_\rho } $ 上, 则该共边 $ {E_\rho } $ 上的所有 $\; \rho $ 个节点都将存储该数据块, 相当于将此数据块重复存储了 $ \rho $ 倍. 本文中数据块的重复度 $ \;\rho $ 最大取4, 所以只会出现 $ {P_2} $ 、 $ {P_3} $ 和 $ {P_4} $ 三个未知参数.

步骤3. 通过已知的节点个数 $ n $ 和编码后的数据块个数 $ \theta $ , 结合式(1)和式(2), 可以解出符合条件的未知参数 $ {P_2} $ 、 $ {P_3} $ 和 $ {P_4} $ . 将MDS码编码后的数据块分为热数据块和冷数据块, 将热数据块存储在3点共边或者4点共边的边上, 将冷数据块存储在2点共边的边上, 通过以上的编码过程可以得到一个异构的部分重复码.

具体地, 通过例1来说明构造的过程.

例1. 首先将原始文件分成 $ M = 7 $ 个原始数据块, 通过 $ (8, 7) $ MDS码编码生成 $ \theta = 8 $ 个编码数据块, 将这些编码后的数据块存储到 $ n = 6 $ 个存储节点中, 在满足参数要求的情况下, 将节点数和编码后的数据块个数代入式(1)和式(2)中: $ \left( \begin{gathered} 6 \hfill \\ 2 \hfill \\ \end{gathered} \right) - \left( \begin{gathered} 3 \hfill \\ 2 \hfill \\ \end{gathered} \right) \times {P_3} - \left( \begin{gathered} 4 \hfill \\ 2 \hfill \\ \end{gathered} \right) \times {P_4} $ $+ {P_3} + {P_4} = 8$ , 解得未知参数 $ {P_3} $ 为1, $ {P_4} $ 为1, 表示有1条3点共边的边和1条4点共边的边, 通过与MDS码编码生成的 $ \theta = 8 $ 个编码数据块做差, 得到 $ {P_2} $ 为6, 即有6条两点共边的边, 将编码后的数据块1, 2看作热数据块, 将3, 4, 5, 6, 7, 8看作冷数据块, 将热数据块1存储在4点共边上, 将热数据块2存储在3点共边上, 将冷数据块3, 4, 5, 6, 7, 8依次存储在2点共边上, 通过此编码过程可以得到6个节点的数据块存储分布如图5所示.

2.2 节点修复

本文异构部分重复码是基于节点共边来构造的, 因此当节点发生故障时, 可以简单直观的通过图中的数据分布来修复节点, 当节点故障时只需连接图中相邻的存活节点进行修复, 下面分单节点故障和多节点故障进行讨论.

单节点故障修复: HFRC-NCE每个数据块最小的重复度为2, 即每条边的数据块最少存储在两个节点上, 故当单个节点发生故障时可从相邻的存活节点下载数据块进行修复, 并且当故障节点存储的数据块位于 $ {E_3} $ 或 $ {E_4} $ 时, 故障节点修复将有更多的选择方案. 如图5中的节点1发生故障时, 节点1中的3和6数据块可连接节点5和6下载相应的数据块进行修复, 节点1中的1数据块位于 $ {E_4} $ 上, 所以可通过连接节点2、3、4中的任意一个下载数据块1进行修复.

多节点故障修复: HFRC-NCE每个数据块最大的重复度为4, 即每条边的数据块最多存放在4个节点上, 故最多能同时修复3个故障节点, 存在以下3种情况:

(1) 当同时修复3个故障节点时, 这3个节点应在同一个 $ {E_4} $ 上.

(2) 当同时修复2个故障节点时, 这2个节点应在同一个 $ {E_3} $ 上.

(3) 当故障节点不在同一个 $ {E_3} $ 或 $ {E_4} $ 时, 只能修复单节点故障不能修复多节点故障.

图5中的节点1、2和3同时发生故障时, 节点1、2和3中的数据块1均可连接节点4下载数据块1进行修复, 节点1、2和3中的其他数据块可连接相邻的存活节点下载相应的数据块进行修复. 当节点5和6同时发生故障时, 节点5和6可以通过连接存活节点1、2、3和4下载相应的数据块进行修复. 当节点3和6同时发生故障时, 由于节点3和6不在同一多点共边上, 数据块8没有存活节点可供下载, 故不能同时修复节点3和6.

3 性能分析

本节主要分析HFRC-NCE的节点修复选择度、节点存储容量、重构度、存储开销和修复带宽开销, 并与完全图和部分正则图构造的部分重复码进行对比.

3.1 节点修复选择度

修复故障节点可选的方案数, 叫做该节点的修复选择度. 基于节点共边的异构部分重复码的节点修复选择度与各个数据块的重复度 $\; \rho $ 和节点容量 $ d $ 相关. 由于每个编码数据块存储到不同的共边上, 故每个数据块的重复度并不相同, 每个节点存储着不同数量的数据块. 当单节点发生故障时, 需要分情况讨论: 当发生故障的节点在3点或4点共边时, 单节点的修复选择度为 $ \;\rho - 1 $ ; 当发生的节点存储在多节点共边相交的位置时, 单节点的修复选择度为 $ \left( {{\rho _{\max }} - 1} \right) \times \left( {{\rho _{\max }} - 2} \right) $ , 当发生故障的节点在2点共边时, 单节点的修复选择度为1. 当多节点发生故障时, 多个节点需位于同一条共边上否则将无法修复, 多故障节点的修复选择度为 $ \;\rho - 2 $ . 图6所示为3种构造的部分重复码, 节点故障的最大修复选择度对比.

如图5当节点1、2、3中的一个发生故障时, 单节点的修复选择度为3; 当节点5、6中的一个发生故障时, 单节点的修复选择度为2; 当节点4发生故障时, 单节点的修复选择度为6. 当节点1和2同时故障时, 节点修复选择度为2; 当节点1和6同时故障时, 由于节点1在4点共边上, 节点6在3点共边上, 导致数据块6没有存活节点供其下载修复, 无法进行多节点修复.

基于完全图和部分正则图构造的部分重复码, 单节点的节点修复选择度为1, 并且当2个及以上节点故障时均不能进行修复. 因此HFRC-NCE提高了单节点及多节点的节点修复选择度, 并增加了故障节点可修复的个数.

3.2 节点存储容量

节点存储容量及每个节点存储的数据块容量, 表1为完全图和部分正则图构造的部分重复码和HFRC-NCE节点存储容量的对比.

通过部分节点的存储容量对比发现HFRC-NCE的节点存储容量更加多样化, 更适用于实际的分布式存储系统中.

相对于静态存储, 动态存储更适用于实际的分布式存储系统, HFRC-NCE在增删原始文件 $ M $ 时, 即更改MDS码编码后的数据块 $ \theta $ , 可以根据式(1)和式(2), 快速求得 $ {E_\rho } $ 的边数, 使得数据块复制的倍数有所变化, 进而改变节点的存储分布, 达到动态存储, 同时也体现了HFRC-NCE的节点存储容量的多样化.

3.3 重构度

用 $ k $ 表示文件的重构度, $ k $ 的定义为重构原文件所需的最少节点数. $ {C_{MBR}}(n, k, d) = kd - \left( \begin{gathered} k \hfill \\ 2 \hfill \\ \end{gathered} \right) = M $ , $ {C_{MBR}} $ 表示最小带宽再生码的存储容量, 等于从系统中任意 $ k $ 个节点所能获得的文件大小 $ M $ . $ n $ 阶完全图构造的部分重复码原始文件 $ M = \theta - 1 $ , 每个节点存储的数据块容量 $ d $ 为 $ n - 1 $ , 将 $ d $ 和 $ M $ 代入 $ {C_{MBR}} $ 的公式中可以求得 $ k = $ $ n - 2 $ , 即重构原始文件至少需要 $ n - 2 $ 个节点. HFRC-NCE的各个节点的数据块容量 $ d $ 不同, 当节点位于多点共边相交的位置时, 节点存储的数据块容量 $ d $ 最小; 当节点位于两点共边不位于多点共边时, 节点存储的数据块容量 $ d $ 最大. 在HFRC-NCE中, 当只存在 $ {E_2} $ 和 $ x $ 个 $ {E_3} $ 时, 数据块容量 $ d $ 最小为 $ n - 1 - x $ , 最大为 $ n - 1 $ ; 当只存在 $ {E_2} $ 和 $ x $ 个 $ {E_4} $ 时, 数据块容量 $ d $ 最小为 $ n - 2 - $ $ x $ , 最大为 $ n - 1 $ . HFRC-NCE的重构度会随选取节点的不同而变化. 下面通过表2不同的节点数和编码后的数据块来分析重构度.

通过表2可以得出, 在节点个数相同的情况下, HFRC-NCE的最小重构度 $ k $ 为 $ n - 4 $ , 完全图构造的部分重复码的重构度 $ k $ 为 $ n - 2 $ , HFRC-NCE的重构度小于基于完全图构造的部分重复码的重构度. 由于HFRC-NCE增加了部分数据块的重复度, MDS码编码后的数据块相对于完全图构造的部分重复码的编码块较少, 所以HFRC-NCE的重构度有所降低.

3.4 存储开销和修复带宽开销

存储开销为各个节点存储数据块所需的空间与原始文件 $ M $ 的比值. $ n $ 阶完全图构造的部分重复码, 将原始文件 $ M $ 经过MDS码编码后生成 $ \theta = \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ 个编码块, 每个节点存储 $ n - 1 $ 个数据块, 其存储开销为 $\dfrac{M}{\theta } \times n \times $ $ (n - 1) = 2M$ . $ n $ 阶部分正则图构造的部分重复码的存储开销也为 $ 2M $ . HFRC-NCE的原始文件 $ M $ 经过MDS码编码后生成 $ \theta < \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ 个编码块, 编码块复制不同的倍数存储到各个节点中, 编码块复制的倍数取决于此编码块所在的 $ {E_\rho } $ , 存储的数据块总和为 $ \displaystyle\sum\limits_{\rho \in \left\{ {2, 3, 4} \right\}} {{P_\rho }} \times \rho $ . 当HFRC-NCE只存在 $ {E_2} $ 和 $ {E_3} $ 时, 结合式(1)式(2)可推导出HFRC-NCE的存储开销为 $\dfrac{M}{\theta } \times \left(\dfrac{{3\theta - \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)}}{2} \times 2 + \dfrac{{\left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) - \theta }}{2} \times 3\right) = $ $ \dfrac{M}{{2\theta }} \times \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) + \dfrac{{3M}}{2}$ , 若HFRC-NCE的存储开销等于 $ 2M $ 需满足 $ \theta = \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ , 但HFRC-NCE的 $ \theta < \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ , 故HFRC-NCE的存储开销大于 $ 2M $ , 即大于基于完全图和部分正则图构造的部分重复码的存储开销. 同理, 当HFRC-NCE只存在 $ {E_2} $ 和 $ {E_4} $ 时, 结合式(1)式(2)可推导出HFRC-NCE的存储开销为 $\dfrac{M}{\theta } \times \left(\dfrac{{\left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) - \theta }}{5} \times 4 + \dfrac{{6\theta - \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)}}{5} \times 2 \right) = $ $ \dfrac{{2M}}{{5\theta }} \times \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) + \dfrac{{8M}}{5}$ HFRC-NCE的 $ \theta < \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right) $ , 故HFRC-NCE的存储开销仍大于 $ 2M $ . 图7所示, 当原始文件大小 $ M = $ $ 1000\; {\text{MB}} $ 时, 3种构造的部分重复码存储开销的对比.

修复带宽开销为修复故障节点时所需下载的数据量的大小. $ n $ 阶完全图构造的部分重复码, 原始文件大小为 $ M $ , 经过MDS码编码后生成 $\theta = $ $ \left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)$ 个编码块, 每个节点存储 $ n - 1 $ 个数据块, 则单故障节点的修复带宽开销为 $ \dfrac{M}{{\left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)}} \times (n - 1) $ . $ n $ 阶部分正则图构造的部分重复码, 原始文件大小为 $ M $ , 经过MDS码编码后生成 $ \theta = $ $ \dfrac{{{n^2} - 2n - 1}}{2} $ 个编码块, 其中 $ n - 1 $ 个节点每个节点存储 $ n - 2 $ 个数据块, 1个节点存储 $ n - 3 $ 个数据块, 则单故障节点的修复带宽开销为 $ \dfrac{M}{{\dfrac{{{n^2} - 2n - 1}}{2}}} \times (n - 2) $ 或 $ \dfrac{M}{{\dfrac{{{n^2} - 2n - 1}}{2}}} \times $ $ (n - 3) $ . HFRC-NCE每个节点存储的数据块数量不同, 故不同节点故障时的修复带宽开销不同. 图8所示, 当原始文件大小 $ M = 1000\;{\text{MB}} $ 时, 3种构造的部分重复码节点修复带宽开销的对比.

7阶完全图构造的部分重复码故障节点的修复带宽开销为 $ 6 \times \dfrac{M}{{21}} = \dfrac{{2M}}{7} $ , 7阶部分正则图构造的部分重复码故障节点的修复带宽开销为 $ 5 \times \dfrac{M}{{17}} = \dfrac{{5M}}{{17}} $ 或 $ 6 \times \dfrac{M}{{17}} = \dfrac{{6M}}{{17}} $ , $ n = 7, \theta = 15 $ 的HFRC-NCE, 单节点故障时的修复带宽开销为 $ 4 \times \dfrac{M}{{15}} = \dfrac{{4M}}{{15}} $ 或 $ 5 \times \dfrac{M}{{15}} = \dfrac{M}{3} $ . 因此, 单节点故障时, HFRC-NCE的修复带宽开销略大于基于完全图和部分正则图构造的部分重复码的修复带宽开销.

3.5 构造算法运算复杂度

衡量一个算法的好坏, 其算法运算复杂度是一个重要的指标. 本文构造的HFRC-NCE码, 在构造时只需根据已知的节点数和边数结合式(1)和式(2)求出两点共边和多点共边的情况, 之后将冷数据和热数据块分别存储在边上, 构造出的HFRC-NCE码简单直观. 本文的构造与文献[13]相比, 文献[13]运用大量组合设计的知识, 所需判断的情况过多, 加大运算复杂度, 因此本文的算法复杂度更优.

4 结论

当前部分重复码的构造大多为同构的并且为静态存储, 不太适用于实际的分布式存储系统. 本文结合节点共边的特性, 并将实际分布式系统的冷热数据块相结合, 构造的HFRC-NCE简单直观, 便于进行快速的节点修复. 通过与完全图和部分正则图构造的部分重复码对比, 可以发现, HFRC-NCE虽然具有较高的存储开销和修复带宽开销, 但能实现更多故障节点的修复, 降低了文件的重构度, 提高了节点的修复选择度, 使节点容量更加多样化, 并且在增删原始数据时, 能快速地调整节点的存储分布, 实现动态存储.