目前, 将海量数据存储在分布式存储系统中的不同存储节点上的数据存储方式已在实际系统中得到了广泛应用, 如Google文件系统^[1]、Hadoop文件系统等. 为确保分布式存储系统中数据的可用性和可靠性, 通常采用诸如复制策略^[2]或纠删码策略^{[3, 4]}的数据冗余策略. 以复制策略中的三副本复制为例, 三副本复制需要存储大量副本数据以确保系统较高的可靠性, 存储代价过高; 纠删码策略的提出使得修复造成的存储开销显著降低, 但其过大的修复带宽开销也成为了限制它的瓶颈.

2007年, Dimakis等人指出存储开销和修复带宽开销之间存在某种平衡, 平衡曲线上的点可通过再生码来实现^[5]. 再生码基于网络编码的概念, 其故障节点可通过连接一定数目的存活节点完成修复, 相比于纠删码降低了修复带宽开销. 目前再生码的研究主要集中在最小存储再生码和最小带宽再生码^[6].

El Rouayheb和Ramchandran为进一步降低修复过程中的运算复杂和带宽开销, 提出了一种基于最小带宽再生点的精确修复编码-部分重复(Fractional Repetition, FR)码^[7]. 部分重复码结合再生码和复制策略的优点, 有效减少了修复带宽开销和磁盘I/O开销^[8], 并实现精确的无编码修复.

目前, FR码主要采用分组设计^[9]、可分解设计^{[10, 11]}等方法进行构造. 朱兵等人基于分组设计提出一种重复度异构的FR码的构造^[12], 使得常用数据的备份更加充分, 且参数选取范围较大, 但同时也造成了较大的存储开销; Natalia Silberstein和Tuvi Etzion等人基于组合设计和正则图, 提出了一种达到最大码率的FR码的构造方法^[13], 但其重复度受FR码结构的约束, 不能适用于任意参数; Harout Aydinian和Holger Boche等人则基于部分有序集构造了一种普遍好的FR码^[14], 这种构造方法虽然简便, 但其重复度却也十分受限. 为此, 本文基于Harary图生成树构造出了一种新型的部分重复(Fractional Repetition based on Spanning trees of Harary graph, FRSH)码, 可以在很大范围内选择构造参数和数据块的重复度, 还能修复多个故障节点. 通过调整Harary图的构造参数, 可以构造出不同重复度的FR码. 相比现有的FR码, 采用Harary图生成树设计FR码更加简洁直观. 相较于RS码和SRC^[15], FRSH码在修复带宽开销、修复复杂度以及修复局部性等方面得到了更低的开销, 且改善了修复效率, 并将故障节点修复时间缩短.

1 预备知识 1.1 Harary图的基础知识

Harary图是一种正则图, 定义为 ${H_{k,m}}$ , 其中k为每个节点所邻接的节点个数, 即顶点的度; m为顶点个数. 根据k和m的取值, 可分为3种情况构造Harary图.

(1) k是偶数

设 $k = 2r$ , 则 ${H_{2r,m}}$ 构造如下: 先给出它的顶点0, 1, 2, …, i, …, j, …, m−1, 然后连接所有满足|i − j|≤r的顶点, 即可完成 ${H_{2r,m}}$ 的构造.

(2) k是奇数, m是偶数

设 $k = 2r + 1$ , 则 ${H_{2r + 1,m}}$ 构造如下: 首先构造出 ${H_{2r,m}}$ , 为满足 $k = 2r + 1$ , 还需添加一些边: 这些边连接了每个顶点i与顶点 $i + \dfrac{m}{2}$ $\left( { 0 \le i \le \dfrac{m}{2}} \right)$ , 连接完即可得到 ${H_{2r + 1,m}}$ .

(3) k是奇数, m是奇数

设 $k = 2r + 1$ , 此时的 ${H_{2r + 1,m}}$ 构造如下: 首先构造出 ${H_{2r,m}}$ , 为满足 $k = 2r + 1$ , 需要添加一些边: 这些边连接了顶点0与顶点 $\dfrac{{m - 1}}{2}$ 和 $\dfrac{{m + 1}}{2}$ , 再将每个顶点i连到顶点 $i + \dfrac{{m + 1}}{2}$ $\left( {0 \le i \le \dfrac{{m - 1}}{2}} \right)$ , 如此连接即可完成构造.

图1所示是构造的k=4, m=8的Harary图 ${H_{4,8}}$ .

1.2 生成树的基础知识

无圈图是指不包含圈的图, 连通的无圈图定义为树. 无圈图的生成树是指顶点与无圈图相同、边集是无圈图的边集子集, 且含边数最少的连通子图. 图2中T1是完全图K8的生成树, 它包含K8中的所有9个顶点, 边集是完全图K8边集的子集, 且包含了最小数目的边数.

由构造的Harary图 $G = {H_{k,m}}$ , 以顶点1为起始顶点得出生成树. 具体构造步骤如下^[16]:

步骤1. 画出边(1, v+1)和(1, m-v+1), v=1, 2, …, $\dfrac{k}{2}$ .

步骤2. 令 $p = \dfrac{k}{2} + 1$ , $j = \dfrac{k}{2}$ , 画出边(m−p+1, m−p−j+1), (m−p−j+1, m−p−2j+1), …, 直到形成从顶点m−p+1到顶点1的路径时停止.

步骤3. 令q=p+1, 重复步骤2画出边(m−q+1, m−q−j+1), (m−q−j+1, m−q−2j+1), …, 当存在从顶点m−p+1到顶点1的路径时停止, 否则转至步骤1.

图3为基于 ${H_{4,8}}$ , 且以顶点1为起始顶点构造的生成树.

1.3 离心率的基础知识

对于连通图G的一个顶点v, v的离心率定义为v到G中除v外所有顶点的距离的最大值. 例如图4中顶点1的离心率值为3, 由于距离顶点1最长的顶点是顶点6, 而从顶点1到顶点6的路径中共经过3个顶点, 即距离为3, 故顶点1的离心率, 其它顶点同理.G的半径定义为G中所有顶点离心率的最小值, 直径则定义为G的最大离心率, 分别记为rad(G)和diam(G). 在图4中顶点最小离心率为2, 最大离心率为4, 所以有rad(G)=2, diam(G)= 4.

2 基于Harary图生成树的部分重复码构造 2.1 构造方法

基于Harary图生成树与离心率, 给出重复度为 $\;\rho $ 的FRSH码的构造算法, 具体步骤如算法1.

算法1. 基于Harary图生成树的部分重复码构造

1) 给定一个Harary图的设计参数k和m, 其中k为每个节点所连接的节点个数, 即节点的度, m为顶点个数, m>0.本文暂且只考虑k为偶数的情况.

2) 根据给出的设计参数k和m构造Harary图.

3) 选定Harary图上任一顶点作为顶点1, 并从顶点1开始给Harary图的顶点顺时针编号, 每个顶点存储与其编号相同的数据块.

4) 由构造的Harary图以顶点1为起始顶点构造生成树.

5) 对得到的生成树的顶点按离心率分组, 将第一个生成树G的顶点按离心率分为 $\scriptstyle n\;(n \ge 1)$ 组, 分组后每组顶点的离心率相同, 并将各组顶点按编号从小到大的顺序分别写入n个节点中, 得到第一组节点.

6) 按照所需构造部分重复码的重复度 $\;\scriptstyle\rho \;(\rho \ge 1)$ 更换起始顶点, 重复步骤4)和步骤5)再得到 $\;\scriptstyle\rho - 1$ 个生成树, 并将它们的顶点按离心率分组后分别写入 $\scriptstyle n*(\rho - 1)$ 个新的节点中.

7)由生成树顶点按离心率的分组得到关联矩阵 $\scriptstyle{{M}}{\rm{ = }}\left( {{m_{s,t}}} \right)$ ( $\scriptstyle 1 \le s \le n\rho , 1 \le t \le m$ ).关联矩阵构造公式如下(v_t代表生成树中的任一顶点, e_s代表任一离心率取值):

$\scriptstyle \scriptstyle{m_{s,t}} = \scriptstyle\left\{ {\begin{array}{*{20}{l}} \scriptstyle{1,}&\scriptstyle{{\text{若}}{v_t}{\text{与}}{e_s}{\text{相关联}}}\\ \scriptstyle{0,}&\scriptstyle{\text{其它情况}} \end{array}} \right. $

再将生成树的关联矩阵等价为FR码的关联矩阵, 关联矩阵的行向量对应FR码的存储节点, 列向量对应FR码的编码块.行向量的重表示表示节点存储容量 $\scriptstyle d$ , 列向量的重表示编码块重复度 $\;\scriptstyle \rho $ . 由此即可得到重复度为 $\;\scriptstyle \rho $ 的FR码.

综上, 重复度为 $\rho $ 的FRSH码的构造过程中, 其包含的不同数据块个数即为Harary图的顶点数m; 重复度 $\;\rho $ 由生成树个数决定; 包含的节点个数为 $n\rho $ .

具体地, 我们以构造 $\;\rho = 3$ 的FR码的过程为例说明构造方法. 令k=4, m=11, 构造Harary图 ${H_{4,11}}$ , 并给其顶点编号, 如图5(a)所示. 再由构造的Harary图以顶点1为起始顶点得出第一个生成树, 如图5(b)所示.

将图5(b)中给出的生成树的顶点按离心率分组, 相同离心率顶点对应的数据块写入同一分组. 为满足重复度 $\;\rho = 3$ , 需重复步骤4)和步骤5), 分别以顶点3和顶点5为起始顶点再得到第2个生成树和第3个生成树(此处图略). 进一步将第2个生成树和第3个生成树的顶点存储数据按离心率分组, 构造关联矩阵 ${{M}}$ . 以图5(b)中的生成树为例, 本例中所有生成树顶点的离心率 ${e_s}$ 共有n=3个取值: ${e_1} = 3$ 、 ${e_2} = 4$ 、 ${e_3} = 5$ . 图5(b)中顶点2、3、4、5的离心率都为 ${e_1} = 3$ , 即 ${v_2}$ 、 ${v_3}$ 、 ${v_4}$ 、 ${v_5}$ 与 ${e_1}$ 相关联, 故有 ${m_{1,2}} = $ ${m_{1,3}} = {m_{1,4}} = {m_{1,5}} = 1$ , 以此类推便得到关联矩阵M.

${{M}} = {\kern 1pt} \left[ {{\rm{ }}\begin{array}{*{20}{c}} 0&1&1&1&1&0&0&0&0&0&0 \\ 1&0&0&0&0&1&1&0&0&0&0 \\ 0&0&0&0&0&0&0&1&1&1&1 \\ 0&0&0&1&1&1&1&0&0&0&0 \\ 0&0&1&0&0&0&0&1&1&0&0 \\ 1&1&0&0&0&0&0&0&0&1&1 \\ 0&0&0&0&0&1&1&1&1&0&0 \\ 0&0&0&0&1&0&0&0&0&1&1 \\ 1&1&1&1&0&0&0&0&0&0&0 \end{array}} \right]$

根据关联矩阵M, 构造重复度 $\;\rho = 3$ 的FR码, 构成的FR码如图6.

2.2 故障节点修复

本论文构造的任意FRSH码都包含 $\;\rho $ 个平行类, 且最多可容忍 $\;\rho - 1$ 个节点故障, 具体修复方案如下:

(1) 当单个节点失效时, 新生节点从存活平行类中下载失效节点对应数据块, 即可完成修复. 如节点N₁故障时, 损坏的数据块2、3、4、5可从剩余两个平行类N₄、N₅、N₆或N₇、N₈、N₉中下载. 这里选择连接存活节点N₄、N₉并分别下载4、5、2、3, 即可修复故障节点N₁.

(2) 当多个节点同时出现故障, 由于仍至少存在一个平行类包含全部数据块, 而本方法构造的FR码的任一平行类中包含的节点个数等于离心率分组数n, 故至多连接n个节点即可完成修复. 具体地, 当多个故障节点所包含的数据块个数 $d < {\alpha _{\min }} + {\alpha _{\max }}$ (这里 ${\alpha _{\min }}$ 和 ${\alpha _{\max }}$ 分别表示FRSH码中节点存储的最小数据块个数和最大数据块个数)时, 仅需连接 $n - 1$ 个故障节点即可完成修复. 例如当N₂和N₅同时失效时, 故障节点N₂和N₅共包含 $d{\rm{ = 6}}$ 个数据块, 满足 $d < {\alpha _{\min }} + {\alpha _{\max }}$ . 此时, 修复故障节点N₂和N₅需要连接 $n - 1 = 2$ 个存活节点完成修复. 这里选择存活节点N₇和N₉, 并分别从存活节点N₇和N₉下载数据块6、7、8、9和1、3, 实现故障节点N₂和N₅的修复.

(3) 当多个节点同时出现故障, 且多个故障节点所包含的数据块个数 $d \ge {\alpha _{\min }} + {\alpha _{\max }}$ 时, 需连接 $n - 1$ 或 $n$ 个不同节点即可完成故障节点修复. 同样先考虑图6中的节点N₄和N₅发生故障, 此时故障节点N₄和N₅包含 $d{\rm{ = 7}}$ 个数据块, 满足 $d \ge {\alpha _{\min }} + {\alpha _{\max }}$ . 为修复故障节点N₄和N₅需要从 $n - 1 = 2$ 个存活节点中下载对应数据块, 这里选择存活节点N₁和N₇, 并分别从N₁和N₇下载数据块3、4、5和6、7、8、9, 即可修复故障节点N₄和N₅. 另当N₂和N₇发生故障时, 此时故障节点N₂和N₇包含 $d{\rm{ = 7}}$ 个数据块, 同样满足 $d \ge {\alpha _{\min }} + $ $ {\alpha _{\max }}$ . 而此时修复N₂和N₇需连接 $n = 3$ 个存活节点N₄、N₅和N₆, 并分别下载6、7、8、9和1便可修复N₂和N₇.

综上, 对于重复度为 $\;\rho $ 的FRSH码, 修复单节点故障时在剩余平行类中连接对应存活节点(连接的节点数至多为n−1个)下载所需数据块即可; 修复多节点故障时, 当多个故障节点所包含的数据块个数 $d < {\alpha _{\min }} + $ $ {\alpha _{\max }}$ 时, 仅需连接 $n - 1$ 个故障节点即可完成修复; 当多个故障节点所包含的数据块个数 $d \ge {\alpha _{\min }} + {\alpha _{\max }}$ 时, 需连接 $n - 1$ 或 $n$ 个不同节点即可完成故障节点修复.

3 性能分析

基于Harary图生成树构造的FR码的性能分析主要集中在修复局部性、修复带宽开销和运算复杂度这几方面, 并将其与传统的RS码和简单再生码(Simple Regenerating Codes, SRC)进行性能比较. 表1给出了SRC、RS码与FRSH码在一般情况下的的节点存储开销、修复带宽开销以及修复局部性的计算公式, 之后我们会在给定具体文件大小和编码数据等条件下用柱状图的形式把上文构造的 $\;\rho = 3$ 的FR码与SRC、RS码的各种性能逐一进行比较.

3.1 修复局部性

修复局部性是衡量构造出的部分重复码性能的重要指标之一, 其定义为节点故障修复过程中连接的存活节点数目, 即磁盘I/O开销. 此处为方便比较, 我们假设原文件大小M=1000 Mb, 存储节点数则为 $n = 11$ , SRC子文件数 $f = 3$ , RS码和SRC的原文件重构度为 $k = 8$ , FRSH码外部采用(11, 8)MDS编码. 本小节仅考虑两种节点故障情况: 单节点故障与两节点故障.

当单节点出现故障时, SRC在修复失效节点时需要连接2f个节点, 这里取 $f = 3$ , 则SRC的修复局部性为6; 若采用(11,8)RS码, 需要连接 $k = 8$ 个节点以恢复出完整的原文件, 再由原文件修复故障节点, 故其修复局部性为8; 而本文构造的FRSH码需要连接2个节点来修复故障节点, 修复局部性为2.

在两节点故障的情况下, SRC与(11, 8)RS码都需要连接 $k = 8$ 个存活节点以修复故障节点, 故它们的修复局部性都为8; 而基于Harary图生成树构造的FRSH码的修复局部性为2或3, 为便于对比, 此处取恒为3作为比较. 由图7可见, 在单节点故障与两节点故障情况下, 本文构造的FRSH码的修复局部性都优于SRC和RS码.

另与基于图因子构造的部分重复码相比, 在单节点故障时两种部分重复码都需要连接两个节点进行修复; 在两节点故障时, 基于图因子的部分重复码需要连接4个节点进行修复, 而FRSH码至多需连接3个节点进行修复, 可见在两节点故障时FRSH码具有显著优势.

3.2 修复带宽开销

在单节点故障的情况下, SRC需下载 $f$ 个数据块以完成修复, 而每个数据块的大小为 ${M / {fk}}$ , 因此SRC的带宽开销为 ${{(f + 1)M} / k}$ ; 由于RS码在单节点故障的情况下完成修复需下载整个原文件, 故RS码的带宽开销为原文件大小M; 而本文构造的FRSH码在单节点故障的情况下需要通过连接2个存活节点完成修复, 因此FRSH码的带宽开销为 ${{2M} / k}$ .

当两节点同时故障时, RS码与SRC的带宽开销均为M. FRSH码的带宽开销为 ${{3M} / k}$ .

假设原文件大小为M=1000 Mb, 存储节点数 $n = 11$ , SRC子文件数 $f = 3$ , RS码和SRC的原文件重构度为 $k = 8$ , FRSH码外部采用(11, 8)MDS编码. 当单节点故障时, RS码的带宽开销为1000 Mb, SRC的带宽开销为500 Mb, FRSH码的带宽开销为250 Mb; 当两个节点故障时, (11,8)RS码修复带宽开销为1000 Mb, SRC的带宽开销同样为1000 Mb, 为方便对比FRSH码的带宽开销取较大值 ${{3M} / k} = 375$ Mb. 如图8所示, 无论单节点还是两节点故障, FRSH码的修复带宽开销都相对较低.

3.3 构造算法运算复杂度

除去修复局部性与修复带宽开销这两种直观性能, 构造算法复杂度体现了算法在执行时的难易程度, 是衡量一个算法好坏的重要指标. 所谓运算复杂度, 即将算法写成程序在实际的计算机系统中运行时涉及的计算量. 本文构造的FRSH码构造时不需要任何计算量, 只需调节Harary图与其生成树的参数即可. 相较于可达到同等性能的FRC, 减少了大量的运算时间.

将基于Harary图生成树的FRSH与运用图因子分解构造的FRC^[17]在构造算法运算复杂度进行对比分析, 在文献[17]中, 构造算法时运用到了加法,乘法运算和基于一次方程上的运算共3种运算方式, 相较于本文仅需调整Harary图参数, 可知本文的构造算法运算复杂度更优.

4 结论与展望

针对部分重复码的有效修复问题, 本文基于Harary图生成树构造出了一种新型的部分重复码. 这种FRSH码在构造方面的优势在于参数选择范围较广且运算复杂度极低. 在性能方面, 实验结果表明, 相较于现有的RS码和SRC, FRSH码在修复带宽开销、修复局部性等方面得到了更低的开销, 且改善了修复效率, 并将故障节点的修复时间缩短; 又与可达到类似性能的图因子分解的部分重复码在运算复杂度方面进行比较, 得出本文的构造算法运算复杂度更优.