基于Harary图生成树的部分重复码构造①

张鑫楠,沈克勤,孙 伟,何亚锦

(长安大学 信息工程学院,西安 710061)

目前,将海量数据存储在分布式存储系统中的不同存储节点上的数据存储方式已在实际系统中得到了广泛应用,如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 图是一种正则图,定义为Hk,m,其中k为每个节点所邻接的节点个数,即顶点的度;m为顶点个数.根据k和m的取值,可分为3 种情况构造Harary 图.

(1)k是偶数

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

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

设k=2r+1,则H2r+1,m构 造如下:首先构造出H2r,m,为满足k=2r+1,还需添加一些边:这些边连接了每个顶点i与顶点连接完即可得到H2r+1,m.

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

设k=2r+1,此时的H2r+1,m构造如下:首先构造出H2r,m,为满足k=2r+1,需要添加一些边:这些边连接了顶点0与顶点和再将每个顶点i连到顶点如此连接即可完成构造.

图1所示是构造的k=4,m=8的Harary 图H4,8.

1.2 生成树的基础知识

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

图1 Harary 图H4,8

图2 完全图K8和它的生成树T1

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

步骤1.画出边(1,v+1)和(1,m-v+1),v=1,2,…,

步骤2.令p=+1,j=,画出边(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为基于H4,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.

图3 基于H4,8的生成树

图4 离心率参考图

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

2.1 构造方法

ρ的FRSH 码的构造算法,具体步骤如算法1.

基于Harary 图生成树与离心率,给出重复度为

算法1.基于Harary 图生成树的部分重复码构造1)给定一个Harary 图的设计参数k和m,其中k为每个节点所连接的节点个数,即节点的度,m为顶点个数,m>0.本文暂且只考虑k为偶数的情况.2)根据给出的设计参数k和m 构造Harary 图.3)选定Harary 图上任一顶点作为顶点1,并从顶点1 开始给Harary图的顶点顺时针编号,每个顶点存储与其编号相同的数据块.4)由构造的Harary 图以顶点1为起始顶点构造生成树.n(n≥1)5)对得到的生成树的顶点按离心率分组,将第一个生成树G的顶点按离心率分为组,分组后每组顶点的离心率相同,并将各组顶点按编号从小到大的顺序分别写入n个节点中,得到第一组节点.ρ(ρ≥1)ρ−1 n∗(ρ−1)6)按照所需构造部分重复码的重复度 更换起始顶点,重复步骤4)和步骤5)再得到个生成树,并将它们的顶点按离心率分组后分别写入个新的节点中.

M=(ms,t)1≤s≤nρ,1≤t≤m 7)由生成树顶点按离心率的分组得到关联矩阵 ().关联矩阵构造公式如下(vt 代表生成树中的任一顶点,es 代表任一离心率取值):ms,t=■■■■■■■■■1,若vt与es相关联0,其它情况d ρ ρ再将生成树的关联矩阵等价为FR 码的关联矩阵,关联矩阵的行向量对应FR 码的存储节点,列向量对应FR 码的编码块.行向量的重表示表示节点存储容量,列向量的重表示编码块重复度.由此即可得到重复度为的FR 码.

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

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

图5 H 4,11和它的生成树

将图5(b)中给出的生成树的顶点按离心率分组,相同离心率顶点对应的数据块写入同一分组.为满足重复度 ρ=3,需重复步骤4)和步骤5),分别以顶点3和顶点5为起始顶点再得到第2个生成树和第3个生成树(此处图略).进一步将第2个生成树和第3个生成树的顶点存储数据按离心率分组,构造关联矩阵M.以图5(b)中的生成树为例,本例中所有生成树顶点的离心率es共有n=3个取值:e1=3、e2=4、e3=5.图5(b)中顶点2、3、4、5的离心率都为e1=3,即v2、v3、v4、v5与e1相关联,故有m1,2=m1,3=m1,4=m1,5=1,以此类推便得到关联矩阵M.

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

图6 FR 码

2.2 故障节点修复

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

(1)当单个节点失效时,新生节点从存活平行类中下载失效节点对应数据块,即可完成修复.如节点N1故障时,损坏的数据块2、3、4、5 可从剩余两个平行类N4、N5、N6或N7、N8、N9中下载.这里选择连接存活节点N4、N9并分别下载4、5、2、3,即可修复故障节点N1.

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

(3)当多个节点同时出现故障,且多个故障节点所包含的数据块个数d≥αmin+αmax时,需连接n−1或n个不同节点即可完成故障节点修复.同样先考虑图6中的节点N4和N5发生故障,此时故障节点N4和N5包含d=7个数据块,满足d≥αmin+αmax.为修复故障节点N4和N5需要从n−1=2个存活节点中下载对应数据块,这里选择存活节点N1和N7,并分别从N1和N7下载数据块3、4、5和6、7、8、9,即可修复故障节点N4和N5.另当N2和N7发生故障时,此时故障节点N2和N7包含d=7个数据块,同样满足d≥αmin+αmax.而此时修复N2和N7需连接n=3个存活节点N4、N5和N6,并分别下载6、7、8、9和1 便可修复N2和N7.

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

3 性能分析

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

表1 几种编码方案的性能分析

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 码.

图7 修复局部性

另与基于图因子构造的部分重复码相比,在单节点故障时两种部分重复码都需要连接两个节点进行修复;在两节点故障时,基于图因子的部分重复码需要连接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 码的修复带宽开销都相对较低.

图8 修复带宽开销对比

3.3 构造算法运算复杂度

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

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

4 结论与展望

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