自适应可分解部分重复码的扩展构造

王甜甜,王汗青,孟 洁,余春雷,王晓峰

(1.海军航空大学 航空基础学院,山东 烟台 264000;2.四川文理学院 智能制造学院,四川 达州 635000)

0 引 言

现如今,海量数据仍迅速膨胀,针对大数据的可靠安全存储问题被广泛重视。大规模分布式存储系统成为当前存储海量数据的有效途径,因其具备可用性高、成本低、吞吐量高和可扩展等优势[1]。由于系统中经常发生存储节点故障的情形,为了使分布式存储系统提供可靠的存储服务,需要通过连接其他存活节点对故障节点进行修复。通常需要采取一定的冗余策略,以保证数据存储的有效性和可靠性。主流的冗余策略是复制(Replication)[2]和纠删码(Erasure Codes)[3]。复制策略的存储成本太大,在修复故障节点时纠删码的带宽开销较高。

针对复制策略和纠删码策略在数据存储和故障修复中存在的局限性,通过将“网络编码”的思路引入分布式存储系统中,Dimakis等人提出了再生码(Regenerating Codes,RC)[4],降低了修复带宽开销和节点存储开销[5]。根据存储—带宽开销权衡曲线上的最佳极值点,Rashmi等人提出了最小带宽再生(Minimum Bandwidth Regeneration,MBR)码和最小存储再生(Minimum Storage Regeneration,MSR)码[6]。但再生码需要连接较多存活节点来修复故障节点。为了降低修复故障节点时的修复局部性,Papailiopoulos等人提出了局部性修复编码(Locally Repairable Codes,LRC)[7],在局部修复组内对故障节点进行修复。结合RS码与简单的异或运算,Papailiopoulos提出了简单再生码(Simple Regenerating Codes,SRC)[8]。再生码和LRC需要通过大量运算来修复故障节点,其修复过程中的计算复杂度较高,导致修复时间较长[9]。

为了保证修复故障节点时具有较低修复带宽开销,同时进一步提高修复效率,Ramchandran等人提出了一种实现对故障节点进行精确无编码修复的MBR码——部分重复(Fractional Repetition,FR)码[10]。实际的分布式存储系统是一种动态的随机变化的环境,也就是说,存储节点故障和部分数据丢失等情况随时可能发生[11]。针对这一问题,朱兵提出了自适应FR码[11],以使FR码适用于动态分布式存储系统。采用自适应FR码的分布式存储系统中,在节点中部分数据丢失并无法修复的情况下,通过简单调整系统结构以满足FR码特性,无需重新配置存储系统[12]。随后,Oktay Olmez提出了可分解FR码[13-15],并提出了基于组合设计的构造方法。可分解FR码中每个平行类均存储原文件大小的数据量,在部分节点故障的情况下,剩余平行类中存活节点仍满足FR码特性。Su Yisheng结合自适应FR码与可分解FR码的特性,提出了自适应可分解FR码,并提出了基于仿射置换矩阵(Affine Permutation Matrices,APMs)与循环置换矩阵(Circulant Permutation Matrices,CPMs)的构造方法[16],有效适应了节点存储容量和数据块重复度在动态存储系统中的随机动态变化。为了使系统中存储节点数和节点存储容量易于扩展,朱兵提出了可扩展FR码的显式构造方法[17]。Krishna提出了具有非对称参数的广义部分重复(Generalized Fractional Repetition,GFR)码,并建立了GFR码与超图的对应关系[18]。

基于上述研究基础,该文在自适应可分解FR码原始构造方案的基础上,提出了利用超图实现自适应可分解FR码的扩展构造方法,实现FR码在动态分布式存储系统中的灵活扩展。当文件规模或分布式存储系统规模发生变化时,根据超图中边和顶点对应于FR码中节点和数据块的关系,通过增加或删除超图中对应的边和顶点,实现动态分布式存储系统中自适应可分解FR码的扩展构造。通过这种基于超图的扩展构造方法,能够扩展出给定参数范围内的所有自适应可分解FR码,该文列举出了存储节点数20以内自适应可分解FR码的所有参数。自适应可分解FR码与SRC和RS码相比,在修复局部性和修复带宽开销方面具有一定优势。

1 基础知识

1.1 自适应可分解FR码

在(n,k,d)分布式存储系统中,假定节点存储容量为α,从n个存储节点中至少连接任意k个存活节点即可重构原文件,单节点故障需要至少连接d个存活节点实现修复,则满足条件k≤d≤n-1,且d=α。

FR码[10]:在(n,k,d)分布式存储系统中,设定FR码C=(Ω,N)由n个子集组成的集合N={N1,…,Nn}表示,其中,每个子集均由符号集Ω={1,…,θ}中元素描述,且符号集Ω中元素的重复度均为ρ,该FR码亦可描述为(n,d,θ,ρ)FR码[19]。该(n,d,θ,ρ)FR码满足以下条件:

(1)子集Ni(i=1,…,n)的大小均为d;

(2)符号集Ω中每个元素均属于集合N中的ρ个子集;

(3)子集Ni和Nj(i≠j)最多包含符号集Ω中的一个元素;

(4)θρ=nd。

自适应FR码[11]:在FR码C=(Ω,N)中,如果∃S⊂Ω,且由非空子集N0S,N1S,…,Nn-1S组成的集合也是一个FR码C',则C为自适应FR码。

当存储系统中部分数据永久性故障而无法恢复时,原来的自适应FR码C通过简单调整得到新的FR码C',以适应新的分布式存储系统。

通过改变可分解FR码中的平行类数,即可改变数据块的重复度。由于每个平行类中的节点均存储全部数据块,因此重构原始文件可以通过下载任一平行类中的数据块实现,进而修复故障节点。当FR码中包含多个平行类时,即使删除该故障节点所在的平行类,其余节点仍满足FR码特性。

自适应可分解FR码同时满足自适应FR码和可分解FR码的特性,能够有效适应于动态分布式存储系统[15]。

1.2 超 图

超图[20]:对于离散集合H=(V,E),其中V=(v1,…,vn)是离散元素的有限集合,E=(E1,…,Em)是V中各非空子集的集合,则超图就是离散集合H=(V,E)。在超图中,顶点的集合为V,边的集合为E,任意非零数量的顶点连接成超图的边。

简单超图:超图的边集E=(E1,…,Em)中,如果满足Ei⊂Ej,则i=j,即任意两条边Ei、Ej没有包含关系,则该超图为简单超图。

线性超图:超图的边集E=(E1,…,Em)中,当i≠j时,|Ei∩Ej|≤1,即任意两条边Ei、Ej连接不超过一个共同顶点,则该超图为线性超图。

r-一致超图:超图的秩记为r(H)=maxj|Ej|,超图的下秩记为s(H)=minj|Ej|,当满足r(H)=s(H)时,超图H称为一致超图。每条边均连接r个顶点的超图,简记为r-一致超图。

t-正则超图:超图H中,连接顶点vi(i=1,…,n)的边数为顶点vi的度,凡所有顶点的度均相同的超图称为正则超图[21]。每个顶点均由t条边连接的超图,简记为t-正则超图。

(r,t)-超图:对于线性超图,如果所有的边均包含r个顶点,且所有顶点均存在于t条边中,则称为线性r-一致t-正则超图,简记为(r,t)-超图。

子超图:对于超图H=(V,E),顶点子集A⊆V,其子超图为HA=(A,{e∩A|e∈E∧e∩A≠∅})。在原超图的基础上去掉某些顶点后的超图,就是子超图。

部分超图:超图H=(V,E)中,边集E={ei|i∈Ie∧ei⊆V∧ei≠∅}的索引集为Ie,对于I⊂Ie,该超图的部分超图为HI=(V,{ei|i∈I})。

2 自适应可分解FR码的扩展构造

建立(d,ρ)-超图与(n,d,θ,ρ)自适应可分解FR码的对应关系,超图中边和顶点分别对应FR码中存储节点和数据块。通过对(d,ρ)-超图进行扩展,实现自适应可分解FR码在动态分布式存储系统中的扩展,而无需对系统进行重新配置。本节基于(d,ρ)-超图,从存储系统规模和存储文件规模变化这两个方面,对自适应可分解FR码进行扩展构造,使扩展后的FR码仍满足自适应和可分解特性。

2.1 存储系统规模变化

当存储系统规模发生变化时,通过改变存储节点数和数据块重复度,即可对原自适应可分解FR码进行扩展构造。

如果存储系统规模减小,即存储节点数n减小,假定节点存储容量d和存储文件规模(即数据块数θ)均不变,为满足FR码的存在条件(即θρ=nd),则需要减小数据块重复度ρ。因为FR码中平行类的存储节点与超图的染色边相对应,删除(d,ρ)-超图中对应染色边,就能实现向(d,ρ-1)-部分超图的扩展。根据(d,ρ-1)-部分超图中边和顶点对应于FR码中节点和数据块的关系,实现分布式存储系统规模变化时的扩展。

图1为(4,4)-超图,图2为对应的(16,4,16,4)自适应可分解FR码。当存储节点数减小为n=12时,为满足θρ=nd,则减小数据块重复度为ρ=3。在(4,4)-超图基础上,删除染色边{e13,e14,e15,e16},得到图3所示(4,3)-部分超图,对应得到图4所示(12,4,16,3)自适应可分解FR码。

图2 (16,4,16,4)自适应可分解FR码

图3 (4,3)-部分超图

图4 (12,4,16,3)自适应可分解FR码

2.2 存储文件规模变化

当存储文件规模发生变化时,通过改变数据块数和节点存储容量,即可对原自适应可分解FR码进行扩展构造。

如果存储文件规模减小,假定数据块大小不变,则数据块数θ减小,存储节点数n不变,为满足FR码的存在条件(即θρ=nd),保持数据块重复度ρ不变,则需要减小节点存储容量d。因为FR码的数据块与超图的顶点相对应,删除(d,ρ)-超图中对应顶点,就能实现向(d-1,ρ)-子超图的扩展。根据(d-1,ρ)-子超图中边和顶点对应于FR码中节点和数据块的关系,实现存储文件规模变化时的扩展。

在图4所示(12,4,16,3)自适应可分解FR码的基础上,当数据块数减小为θ=12时,为满足θρ=nd,则减小节点存储容量为d=3。在图3所示(4,3)-超图基础上,删除顶点{v13,v14,v15,v16},得到图5所示(3,3)-子超图,对应得到图6所示(12,3,12,3)自适应可分解FR码。

图5 (3,3)-子超图

图6 (12,3,12,3)自适应可分解FR码

2.3 自适应可分解FR码的参数范围

利用(d,ρ)-超图实现自适应可分解FR码的扩展,能够在给定参数范围内构造全部自适应可分解FR码。表1为自适应可分解FR码在存储节点数20个以内的全部(n,d,θ,ρ)参数。如表1所示,全部(n,d,θ,ρ)FR码均可通过基于(d,ρ)-超图的扩展实现。例如,针对存储节点数n=8,通过存储文件规模变化时的扩展方法,能够实现(8,2,8,2)自适应可分解FR码向(8,3,12,2)和(8,4,16,2)自适应可分解FR码的扩展。

表1 (n,d,θ,ρ)自适应可分解FR码的参数范围 (n≤20)

3 性能分析

分布式存储系统在修复故障节点时的两个重要性能是修复局部性和修复带宽开销。本节从这两个方面分析自适应可分解FR码的性能,并对比最常见的SRC和RS码,通过Matlab仿真给出这三种编码方式的性能对比。

3.1 修复局部性

在分布式存储系统中,假设原文件大小为M,存储节点数为n,重构原文件需要至少连接任意k个存活节点。(n,k)RS码中,只要故障节点数小于等于n-k,均需要连接k个存活节点的数据解码重构原文件,再编码恢复故障节点数据,则修复局部性为k。(n,k,f)SRC中,原文件由f个采用(n,k)RS编码的子文件组成,通过连接2f个存活节点能够修复单节点故障,则单节点故障的修复局部性为2f;当两节点同时故障时,需要连接k个存活节点解码重构原文件后进行故障修复,则两节点同时故障的修复局部性为k。(n,d,θ,ρ)自适应可分解FR码中,当单节点故障时,需要连接任一平行类的d个存活节点下载相应数据块,则修复局部性为d。当两节点同时故障时,若重复度ρ>2,通过任一平行类的min{n/ρ,2d}个存活节点下载相应数据块,则修复局部性为min{n/ρ,2d};若重复度ρ=2,且两个故障节点存储相同数据块,连接任意k个存活节点重构原文件进行故障修复,则修复局部性为k;若重复度ρ=2,且两个故障节点没有存储相同数据块,需要连接n/ρ或2d个存活节点,则修复局部性为n/ρ或2d。

设定(n,k,f)SRC和(n,k)RS码的存储节点数为n=12,重构原文件需要至少连接任意k=9个存活节点。SRC中原文件由f=3个子文件组成,每个子文件均采用(12,9)RS编码。为便于性能分析,设定(n,d,θ,ρ)自适应可分解FR码外部采用(12,9)MDS编码,其编码数据块的数目θ=12,数据块重复度ρ=3,因此节点存储容量为d=3。如图7所示,相比于(12,9,3)SRC和(12,9)RS码,外部采用(12,9)MDS编码的(12,3,12,3)自适应可分解FR码在修复局部性上具有较大优势。

图7 修复局部性

3.2 修复带宽开销

(n,k)RS码中,只要故障节点数小于等于n-k,均需要连接k个存活节点并分别下载M/k的数据量,则修复带宽开销为M。(n,k,f)SRC中,当单节点故障时,下载f个数据块并进行异或运算能够修复一个故障数据块,由于每个节点存储f+1个数据量为M/fk的数据块,则单节点故障的修复带宽开销为(f+1)M/k;当两节点同时故障时,同(n,k)RS码一样,修复带宽开销为M[22]。采用(θ,j)MDS编码的(n,d,θ,ρ)自适应可分解FR码,每个数据块的数据量为M/j,当单节点故障时,通过d个存活节点下载相应故障数据块即可,则单节点故障的修复带宽开销为Md/j。当两节点同时故障时,若重复度ρ>2,这两个故障节点最多存储一个相同数据块,则修复带宽开销为M(2d-1)/j或2Md/j;若重复度ρ=2,且两个故障节点存储相同数据块,需要重构原文件进行故障修复,则修复带宽开销为M;若重复度ρ=2,且两个故障节点不包含相同数据块,只需要从存活节点中下载相应故障数据,则修复带宽开销为2Md/j。

在3.1节(12,9,3)SRC、(12,9)RS码和(12,3,12,3)自适应可分解FR码的基础上,设定原始文件大小M=1 000 Mb。如图8所示,相比于(12,9,3)SRC和(12,9)RS码,外部采用(12,9)MDS编码的(12,3,12,3)自适应可分解FR码,在修复带宽开销上具有较大优势。

4 结束语

针对动态分布式存储系统中FR码的灵活扩展问题,提出一种利用超图实现自适应可分解FR码的扩展构造方法,能够实现当文件规模变化和存储系统规模变化时的扩展构造。具体地,建立(d,ρ)-超图与(n,d,θ,ρ)自适应可分解FR码的对应关系,在原FR码构造和原超图结构的基础上,通过增加或删除超图中边和顶点,实现对动态分布式存储系统中自适应可分解FR码的扩展构造。基于这种方法,能够扩展构造出给定参数范围内所有自适应可分解FR码。自适应可分解FR码相比于SRC和RS码,具有较优的修复局部性和修复带宽开销。