基于矩阵变换和可调节环的部分重复码构造①

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

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

随着大数据时代的到来,数据资源呈现出快速增长的趋势,数据的存储容量也随之不断增加.传统的数据存储系统已经不能适应当前海量数据存储,分布式存储系统逐渐成为主流存储方式.通过将海量数据分散的存储在多台互相独立物理设备上,分布式存储系统不仅很好的分担了存储负载,而且成本低廉,可扩展性能好,但是分布式存储系统中的这些物理存储设备容易发生故障,可造成大量数据丢失.因此,如何提高数据存储的可靠性就成为了分布式存储亟需解决的问题[1-3].

为保证数据存储时的高可靠性和高可用性,传统的分布式存储系统中生成冗余数据的策略通常有“复制”和“纠删码”策略[4,5].谷歌文件系统和Hadoop 系统运用了三副本复制策略,将原始数据块复制成三个副本然后存储在系统中来保证存储的可靠性,这样会导致存储开销过大；为了减小存储开销,在实际系统中引入纠删码的冗余策略,但该策略在修复故障节点时会带来巨大的带宽开销.针对上述问题,Dimakis 等将网络编码的思想运用到分布式存储中,提出了再生码的概念[6],有效减少了存储开销和修复带宽开销.目前对再生码的研究表明,主要表现在存储和带宽均衡曲线上的两个极值点,一个极值点对应最小存储再生码

MSRC (Minimum Storage Regenerating Code),另一个极值点对应最小带宽再生码MBRC (Minimum Bandwidth Regenerating Code).文献[7-9]给出了一些好的再生码的构造方法.

但是,再生码的缺陷在于,在进行故障节点修复时,需要大量基于有限域上的计算,计算复杂度高,修复局部性复杂.为解决上述问题,EI Rouayheb 和Ram chan dram 在MBRC 的研究基础上提出了一种新型码——部分重复码(Fractional Repetition Codes,FRC)[10],该码可以进行精确无编码有效的修复.一般意义上的FRC由两部分组成：外部的编码是最大距离可分码 (Maximum Distance Sparable,MDS)和内部是重复码,该码修复故障节点无需任何编码操作,可以很好地降低故障修复时所需的带宽和磁盘I/O 开销.目前对FRC 的研究主要有基于组合设计构造的FRC[11],基于图构造的FRC[12],基于偏序集构造的FRC[13],基于二分图构造的局部修复的FRC[14],这些构造算法复杂,并且大多只能构造同构的FRC,不能得到异构的FRC.

为此,本文提出了两种构造方法,一种是基于矩阵变换构造的异构FRC,该构造用于构造重复度为2,节点存储容量异构的FRC,该方法计算复杂度低,只需进行简单的异或运算就可得到节点存储容量异构的FRC,相比现有的运用正则图构造的同构FRC,该构造在节点存储容量上更符合现实的存储系统；另外,本文还提出了运用可调节环构造的FRC,该方法根据一定的存放规则能得到不同重复度的FRC,主要构造重复度 的情况,因为大部分对部分重复码的研究中重复度都是2 或3,同时该方法也可灵活的调节节点存储容量,即可得到节点存储容量同构的FRC 也可得到节点存储容量异构的FRC,可大范围选择参数,构造结构简单直观.同时本文上最大的应用价值在于能无编码的修复节点存储容量异构的分布式存储系统中的故障节点,应用前景好,具有很好的实用价值.

1 基础知识

目前研究表明,对MDS 码的研究已经十分成熟了,各种参数的MDS 码都可得到.所以对部分重复码的研究主要体现在内部重复码的构造上.FRC 实际上是复制倍数为ρ 的 θ 个数据块在节点上的一种排列组合,复制生成的数据块都分别存储在不同的系统节点上.内部的重复码可用 (n,k,d,θ,ρ,α)FRC 表示,其中n表示存储系统的节点数,θ表示存储在节点中的数据块个数,ρ表示数据块的复制次数,α表示每个节点的存储容量,d表示修复一个失效节点需连接的存活节点数,一般认为α=d.数学上的定义如下：

定义1[15].参数为(n,k,d)分布式存储系统的部分重复码C=(M,U),复制倍数为ρ,是指特定的n个子集的集合U={U1,U2,···,Un},每个子集的元素均来自于符号集M={1,2,···,θ}.并且节点存储容量同构的FRC 还需要满足下面条件：

1)每个子集的大小均为d；

2)M中的每一个元素都属于U中的子集,每个子集数大小为ρ；

3)同构的FRC 满足nα=ρθ.

定义2[16].(d1,d2,···,dm)正 则图G(V,E)是一个无向图,其中 |V|=n,V1,V2,···,Vm⊂V,并且Vi∩Vj=∅ .顶点Vi的度为di(1 ≤i≤m),若G(V,E)所有顶点的度都等于d,则该G(V,E)叫 作d-正则图,若G(V,E)顶点的度不相等分别为d1,d2,···,dm,则称该G(V,E)为(d1,d2,···,dm)-正则图,也叫部分正则图.

2 基于矩阵变换的异构部分重复码构造

本节运用矩阵变换的思想,结合部分正则图提出了一种新的节点存储容量异构的部分重复码,相比文献[10]和文献[16]中运用正则图和部分正则图构造的部分重复码,本构造能得到节点存储容量更加多样的FRC,和传统RS 码相比,在修复单节点故障时,修复局部性更好,修复复杂度更优,无需任何编码操作,计算复杂低.具体构造算法如下：

该构造主要用于构造节点存储容量异构的FRC,适用于分布式存储系统节点数n为奇数的情况,且构造的FRC 中数据块的重复度ρ 等于2；具体步骤如下：

步骤1.定义一个n阶的二进制循环置换矩阵Cn(d−1),其中n代 表节点数,d−1表示每个节点存储容量同时也表示矩阵中每一行1 的个数,且需满足的条件为d＞3,d为奇数；同时我们设定Cn(d−1)矩阵的第一行在数学上满足的表达式为：c(t)=t+t2+···+t(d−1)/2+tn−(d−1)/2+···+tn−1.

在矩阵的第一行确定后,矩阵后面的每一行依次向右移动一位,共移动n−1次,最后生成Cn(d−1)矩阵；

步骤2.为得到节点存储容量异构的FRC,在步骤1 的基础上引入矩阵Sn去 调节步骤1 中的Cn(d−1)矩阵,Sn矩 阵生成方法为：在(n−1)阶副对角线都为1,其他元素全为0 的方阵后面加一行0 和一列0,生成n×n阶的Sn矩阵；

步骤3.将步骤1 中的矩阵Cn(d−1)和步骤2 中的矩阵Sn进 行模2 运算,得到二进制矩阵P=Cn(d−1)+Sn(mod 2),矩阵P和部分正则图存在相关联的关系,用P=(mij)n×n,1 ≤i,j≤n表示部分正则图的关联矩阵,关联规则如下：

由上面关系可知,部分正则图的每一个顶点的度和矩阵的每一行中1 的个数是相等的,经过算法的验证,发现矩阵P的不同行中会出现有d,d−1,d−2个1 的情况,因此对应的部分正则图的度有d,d−1,d−2三种情况,记作(d,d−1,d−2)-部分正则图,也就对应着构造的FRC 的节点存储容量有d,d−1,d−2三种情况.

对构造的FRC 的故障节点修复进行分析可知,因为该FRC 的重复度 ρ=2,所以本构造能容忍单个节点出现故障,又由于异构FRC 的节点容量有d,d−1,d−2三种情况,所以分以下3 种情况讨论：

1)若存储容量为d的节点出现故障,那么只需要从另外的d个节点分别下载一个数据块即可直接修复；

2)若存储容量为d−1的节点出现故障,那么只需要从另外的d−1个节点分别下载一个数据块即可直接修复；

3)若存储容量为d−2的节点出现故障,那么只需要从另外的d−2个节点分别下载一个数据块即可直接修复.

当系统中出现故障节点,只需直接从其他存活的节点下载数据块修复,修复选择性高,无编码操作,计算复杂度低.根据上述构造算法给出如下具体实例.

例1.给定n=7,d=5,根据构造方法步骤1 得到矩阵C7(4),其中C7(4)是一个7 ×7的二进制矩阵且第一行表示为c(t)=t+t2+t5+t6,第一行确定后,后面的每一行依次向右移动一位,最后生成C7(4)矩阵,如下所示：

进一步运用矩阵S7调节矩阵C7(4),S7矩阵是在6 阶副对角线都为1,其他元素全为0 的矩阵后面加一行0 和一列0 生成的,如下所示：

得到S7矩 阵后,通过P=C7(4)+S7(mod 2)算得矩阵P,如下所示：

根据矩阵P能得到 (3,4,5)-部分正则图,即部分正则图的度有5,4,3 这三种情况,也就对应节点存储容量有5,4,3 三种情况,如图1所示.

若节点U1发生故障,需连接U2,U3,U7这3 个节点进行修复,即从U2,U3,U7这3 个节点下载1,6,7数据块进行修复,修复过程如图2所示.同理,其他节点发生故障也可用相同的方法进行修复.

图1 (3,4,5)-部分正则图和对应FRC 数据块存储结构图

图2 故障节点修复图

3 基于可调节环的FRC 构造

本节运用可调节环结构构造FRC,根据一定的存放规则去调节重复度的大小和节点存储容量,规则是将数据元素放入相邻的节点所在环的边之间,规定当每一个数据块依次放在两个相邻的节点之间时,此时FRC 的重复度为 ρ=2；当每一个数据块都放在3 个相邻的节点之间,此时FRC 的重复度为 ρ=3,同理可用相同的存放规则去调节重复度.由同构FRC 参数满足的条件nα=ρθ可知,当给定的参数满足该条件时,可得到同构的FRC,若该等式不成立,则可用可调节环构造节点存储容量异构的FRC,根据已有的对FRC 的研究中发现,大部分只考虑重复度为2,3 的情况,具体构造算法如下.

3.1 用可调节环去构造重复度ρ=2的FRC

假设系统中节点用U1,U2,···,Un表示,节点中的数据块用θ 表示,且[θ]={1,2,···,θ},将数据块按一定规则放入环中,即从节点U1开 始,将数据块1 放在U1和U2所在的边上,将数据块2 放在U2和U3所在的边上,数据块3 放到U3和U4所 在边上,以此类推,直到将θ 个数据块放完为止.

根据上述算法可以得到重复度 ρ=2的FRC.因为每一个数据块存在于相邻的2 个节点所在环的边上,每个数据块都会被两个节点所共有,即得到的是重复度 ρ=2 的FRC.若所给参数满足nα=ρθ,用可调节环可以构造节点存储容量同构的FRC,否则用可调节环可以构造节点存储容量异构的FRC.具体实例如下,其中,例2 给定的是用可调节环构造的重复度 ρ=2的同构FRC,例3 给定的是用可调节环构造的重复度ρ=2的异构FRC.

例2.给定n=6,θ=12,用可调节环去构造FRC,环结构和节点存储结构,如图3所示.

图3 可调节环结构和节点存储结构

由节点存储结构图可知该FRC 满足nα=ρθ,是同构的FRC,重复度ρ=2,节点储存容量为α=4,若节点U1故障,需要从U2下载数块1,7,从U6下载数据块6 和12 修复U1,其他节点故障也可用相同的修复方式进行修复,无需编码操作.

例3.给定n=8,θ=21,用可调节环去构造FRC,环结构和节点存储结构图,如图4.

图4 可调节环结构和节点存储结构图

由节点存储结构图可知,该FRC 不满足nα=ρθ,是异构的FRC,且重复度 ρ=2,节点存储容量有4,5,6 三种情况,可修复单节点故障,修复方式是直接从存活节点下载相应数据块进行修复.

3.2 用可调节环去构造重复度ρ=3的FRC

若分布式存储系统的节点用U1,U2,···,Un表示,θ表示存储在节点中的数据块,且[θ]={1,2,···,θ},将θ个数据块按一定的规则放入环中,即从U1节点开始,将数据块1 分别放到U1U2和U2U3所在的边上,将数据块2 分别放到U2U3和U3U4所在边上,数据块3 放到U3U4和U4U5所 在边上,以此类推,直到将θ 个数据块放完为止.

根据上述算法可得到重复度ρ=3的FRC.因为每一个数据块存在于相邻的3 个节点所在的环之间,即每个数据块都会被3 个节点共有,则得到的是重复度ρ=3的FRC.若所给参数满足nα=ρθ,用可调节环可以构造节点存储容量同构的FRC,否则可以构造节点存储容量异构的FRC.具体实例如下,其中,例4 给定的是用可调节环构造的重复度ρ=3的同构FRC,如图5所示,例5 给定的是用可调节环构造的重复度 ρ=3的异构FRC,如图6所示.

例4.给定θ=n=4,则用可调节环去构造FRC,结构如下.

由上面的可调节环结构图和节点存储图可知,构造得到的码是重复度 ρ=3,节点存储容量为3 的同构FRC.该FRC 的故障节点修复方式为,当U1发生故障,可以直接重U3中下载1,3 两个数据块,再从U2或U4中下载4 这个数据块；当U1和U2同时发生故障时,可以直接从U3和U4节点中下载数据块进行修复,修复方式简单,无需任何编码.

图5 可调节环结构和节点存储结构图

图6 可调节环结构和节点存储结构图

例5.给定 θ=16,n=8,用可调节环去构造FRC,结构如下.

由上面的可调节环结构图和节点存储图可知,构造得到的FRC 是重复度 ρ=3,节点存储容量异构的FRC,节点容量出现7,6,5 三种情况.该FRC 的故障节点修复方式为,直接从存活节点下载数据块,可最多修复两个故障节点.

4 性能分析

对本文提出的两种新的构造进行性能分析,主要与现有的FRC 对比分析,发现本文构造的FRC 在节点存储容量上具有异构的特点,修复局部性好,同时在构造算法运算复杂度低,可以大范围的选择参数,构造结构简单直观.

4.1 节点存储容量对比分析

对矩阵变换构造的异构FRC 和已有的用正则图和部分正则图构造的FRC 进行对比分析,主要分析节点存储容量,如表1.

表1 节点存储容量对比分析

表1只列举了部分情况,可以发现本文提出的基于矩阵构造的异构FRC 相比于正则图构造的FRC 在节点存储容量上是异构的,并且本文提出的构造方法在节点修复选择度上更优.

对基于可调节环构造的FRC 进行对比分析,相比于文献[10]提出的运用正则图构造的FRC 本构造在重复度上的选择性更灵活,正则图只能构造 ρ=2的同构FRC,用可环结构可以得到重复度多样的同构或异构的FRC,构造算法更简单直观.

4.2 参数选择对比分析

根据已有研究表明,大多数构造FRC 的方法都对参数有明显的限制,对比分析得本文提出的基于可调节环构造的FRC,在参数选择上更具有灵活性,对比分析结果,如表2.分析结果.表2中各参数含义解释如下：α是FRC 的节点存储容量,d表示修复单个节点时需要连接的节点数,一般意义上 α=d,ρ表示FRC 的数据重复度,θ表示系统中数据块,n表示系统中的节点数,q是 素数,h是Hadamard 矩阵的阶数.

4.3 修复局部性对比分析

修复局部性是指在修复故障节点时需要连接的存活节点数.当单节点出现故障时,运用正则图构造的FRC 需要连接的节点数为d,即修复局部性为d,运用基于矩阵变换构造的异构FRC 需要连接的节点数有d,d−1,d−2 三 种情况,即修复局部性为d,d−1,d−2三种情况,修复局部性更好.另外,当出现单节点故障时,(n,k)RS 码需要连接k个节点先恢复原始文件来修复出现故障的节点,修复局部性为k；基于矩阵变换构造的异构FRC 需要连接的节点数有d,d−1,d−2三种情况,修复局部性为d,d−1,d−2三种情况,又由于研究的FRC 都是d＜k,所以可知和(n,k)RS 对比,基于矩阵变换构造的异构FRC 具有更好的修复局部性.

表2 不同构造方法参数对比分析图

图7给定的实例是基于矩阵变换构造的异构FRC和(n,k)RS 码的在修复局部性方面的对比情况,当修复节点存储容量为d(d＜k)的节点时,可知基于矩阵变换构造的异构FRC 的修复局部性恒为d(d＜k),但RS 码的修复局部性与k(正整数)是一次线性关系.

图7 修复局部性与数据块k 的关系图

4.4 构造算法运算复杂度

衡量一个算法的优劣,通常需要考虑算法构造时涉及的运算复杂度,即将算法写成程序在实际的计算机系统中运行时,涉及的计算量.本文基于矩阵变换的异构FRC,由构造算法可知,构造一个异构的FRC 需要进行d−1次 加法运算和n2次模2 加运算；运用可调节环构造的FRC,构造时不需要任何计算量,只需在环上直接进行调节即可,相比于基于矩阵变换的异构FRC,用可调节环得到的FRC,在构造算法运算复杂度表现的更优.

将基于矩阵变换的异构FRC 和运用偏序集构造的FRC[10]在构造算法运算复杂度进行对比分析,在文献[10]中,构造算法时运用到了加法,乘法运算和基于集合上的运算,明显可知本文算法运算复杂度更低.

5 结论

考虑实际的分布式存储系统大多需要满足异构的特性.为此,本文提出了两种构造方法,一种是基于矩阵变换构造的异构FRC,该构造主要用于构造重复度为2,节点存储容量异构的FRC,相比用正则图构造的同构FRC,该构造更符合现实的存储系统；另外,本文还提出了运用可调节环构造的FRC,构造得到了重复度为2 或3 的FRC,该方法即可得到节点存储容量同构的FRC 也可得到节点存储容量异构的FRC.与现有的FRC 对比分析,发现本文构造的FRC 在节点存储容量上具有异构的特点,修复局部性好,同时在构造算法运算复杂度低,可以大范围的选择参数,构造结构简单直观.将来如何去构造更多样的异构FRC 是研究的热点.