异构部分重复码的构造①

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

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

近些年,随着信息技术和大数据产业的发展,数据量激增,传统集中存储设备已无法满足海量数据存储要求.分布式存储系统(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].满足:HnHnT=nIn>;Hn是一个n阶方阵其由1 或−1 构成,In是一个n阶单位矩阵,称Hn为n阶Hadamard 矩阵.

Hadamard 矩阵具有如下性质:

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

(2)若Hn是n阶Hadamard 矩阵,需要满足n是4的倍数(n＞2).

本文所需的Hadamard 矩阵均为标准型,即Hn的第1 行和第1 列全是1.

1.2 部分重复码

定义2[13].FR 码.给定一个部分重复码C=(∂,M),其中参数为(n,k,d),将重复度设为ρ(即编码数据块复制ρ倍),特定地,M={M1,···,Mn}为n个子集的集合,Mi(1 ＜=i＜=n)中的每一个元素都属于集合∂={1,···,θ}.

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

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

2)∂中每一个元素分别存在于M的ρ个子集中.

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

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

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

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

步骤1.首先采用(n,k)MDS 编码(n≥k)对原始文件进行编码,得到n个编码数据块c1,···,ck−1,ck,ck+1,···,cn,其中包括k个原始数据块和n−k个校验数据块[6];

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

矩阵Jn+1中 元素全为1,Hn+1为标准Hadamard 矩阵,得到的K′n+1(n≥k)是一个0-1 矩阵,将K′n+1的第一行和第一列同时删去得到所需矩阵Kn;

步骤3.将矩阵Kn中第j列出现的第(j+1)mod个1 改为0 得到新的矩阵Kn1,然后计算式(1):

其中,j=1,2···,n,i表示第i个FR 节点,aij表示矩阵第i行第j列的值.其中表示异构FR 码的存储节点,将矩阵Kn1中第i行中全部的1 所分别对应的列数提取出来,即可得到一个节点Ni存储的数据块,得到节点存储容量不同的异构FR 码.

具体的,选取一个12 阶的Hadamard 矩阵如图1所示,对其按步骤2 操作得到11 阶矩阵K11如图2所示,每一列的第个1 改为0 得到新的矩阵K111如图3所示.随后节点对应矩阵的行,而不同的编码块对应于矩阵的列.所以我们得到了存储容量不同的异构的FR 码,每个节点的存储结构如图4所示,其节点的存储容量d=3,4,5,编码块的重复度 ρ=4.

图1 12 阶Hadamard 矩阵

图2 K11 矩阵

图3 K111 矩阵

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

图4 存储容量异构的FR 码节点存储结构图

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

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

步骤1.首先采用(n,k)M DS 编码(n≥k)对原始文件进行编码,得到n个编码数据块c1,···,ck−1,ck,ck+1,···,cn,其中包括k个原始数据块和n−k个校验数据块[6];

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

图5 [7,3,4]简单代码图形

步骤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个存储节点Ni,共有n个 存储节点(i=I,II,···,n);将与存储节点直接相连的数据块当作该存储节点存放的数据块,即可得到存储容量和重复度异构的FR 码.

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

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

图6 图形结构

图7 FR 码节点存储结构图

图8 扩展图形结构

可以看出共有6 个存储节点.存储节点N1和N5的存储容量是5,存储节点N3和N4的存储容量是7,并且重复度 ρ为2 或3的一个异构的FR 码.

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

4 性能分析

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

4.1 修复带宽开销

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

图9 修复带宽开销对比

采用基于[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 码的修复局部性、修复带宽开销进一步降低,性能进一步提高.