基于Petersen图的部分重复码

为对分布式存储系统的修复效率研究,提出一种基于Petersen图边染色的部分重复码设计。该设计利用Petersen图边染色进行构造,即先对Petersen图的边进行染色,标记出染色的不同边数,然后构造Petersen图中不同边色的链路,最后把每条链路视为部分重复码的存储节点,称为PECBFR码。理论分析指出,PECBFR码可以随机访问模式下的系统存储容量。此外,实验仿真结果显示,本文提出的基于Petersen图边染色的部分重复码构造算法,与分布式存储系统中的里所码以及简单再生码相比,在系统修复故障节点时,能够快速地修复故障节点,通过染色链路构造的部分重复码,在修复局部性、修复复杂度、修复带宽开销相较于分布式存储系统中的常见编码算法都有较大的性能提升。

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

针对分布式存储系统故障节点修复问题,提出一种部分重复(FR)码的构造算法。由Hadamard矩阵经过简单变换直接构造FR码。随后引入了分组思想,由8阶Hadamard矩阵构造分组FR码(HGFR),构造更加简洁直观,实现多故障节点在局部修复组内进行精确无编码修复。理论分析发现,与RS码和SRC简单再生码相比,设计的HGFR码在分布式存储系统节点发生故障时的修复局部性、修复复杂度和修复带宽开销都降低,且修复效率提高,减少了故障节点的修复时间。

基于差集矩阵的部分重复码构造

针对最小带宽再生码的有效修复问题,该文提出一种基于差集矩阵的部分重复(FR)码的构造算法。利用差集矩阵和克罗内克(Kronecker)和来构造正交排列,根据正交排列每一列取相同元素所在行作为节点的编码块,得到相应的FR码。构造的FR码可以划分成多个平行类,同时还能调整数据块的重复度和节点的存储容量。仿真结果表明,与传统的里德-所罗门(RS)码和简单再生码(SRC)相比,构造的FR码在修复复杂度、修复带宽开销和修复局部性方面具有更好的性能,修复选择度上虽然是基于表格的修复方案,但选择度依旧可以达到很高。

分布式存储系统中基于部分重复循环码的局部修复码构造

为了进一步优化分布式存储系统故障节点修复的磁盘I/O开销和修复局部性,提出一种基于部分重复循环码的局部修复码方法。首先构造部分重复循环码(FRCC);然后在此基础上划分局部修复组;最终得到相应的局部修复码,且局部修复组内故障节点可以通过相邻节点实现协作修复,以确保较低的磁盘I/O开销和修复局部性。性能分析以及实验仿真表明,采用基于部分重复循环码的局部修复码,单节点故障的修复局部性恒为2,并且可以快速实现多个故障节点的数据重构;与三副本复制策略、简单再生码以及基于传统FRC的局部修复码相比,基于部分重复循环码的局部修复码具有更低的修复带宽开销和修复局部性,修复效率更高。

基于混合型正交表构造部分重复码

考虑到分布式存储系统中数据的存储和节点修复,提出一种基于混合型正交表的异构部分重复(fractional repetition,FR)码构造算法,并证明了该异构FR码是一般好的一般部分重复(generalized fractional repetition,GFR)码。利用混合型正交表中的水平对构造关联矩阵,根据关联矩阵对数据块在存储节点进行存放。另外,利用分组的方法在混合型正交表的基础上构造分组部分重复码,可以在局部组内实现单故障节点的精确无编码修复,修复局部性为2或3,且能够对多个故障节点进行快速有效的修复。性能分析和实验仿真可知,所构造的分组FR码与RS码和简单再生码相比,在修复故障节点时具有较小的修复带宽开销和修复局部性,修复效率得到了提升。

基于可分组设计的部分重复码研究

针对最小带宽再生情形下的有效修复问题,提出了一种新型部分重复(FR,fractional repetition)码设计。该设计由外部最大距离可分(MDS,maximum distance separable)码和内部重复码组成,称为GDDBFR(group divisible design based FR)码,可以达到随机访问模式下的系统存储容量,并且能够在很大范围内选择构造参数。理论分析指出,尽管GDDBFR码采用基于表格的修复方式,但通常具有大量的节点修复选择方案。此外,实验结果表明,与传统的RS(Reed-Solomon)码和再生码相比,GDDBFR码可以显著地减少失效修复时间。

图因子分解的部分重复码构造

为了改善分布式存储系统的可靠性和修复效率,提出了一种基于图因子分解的部分重复(fractional repetition based on graph factorization,FRGF)码的构造算法。FRGF码能在大范围内选择构造参数和数据块的重复度,并且构造方法多样。与现有的里所(Read-Solomon,RS)码和简单再生码(simple regeneration codes,SRC)相比,FRGF码在修复局部性、修复复杂度及修复带宽等方面具有更低的开销,且修复效率高,显著减少了故障节点的修复时间。

图因子分解的故障节点快速修复

为了提高分布式存储系统中故障节点的修复效率,提出一种新的部分重复(fractional repetition,FR)码的构造算法.该算法利用完全图的因子分解进行构造,称为CGFBFR(complete graph factorization based FR)码.该算法首先对完全图进行因子分解,分解完成以后确定完全图的因子分解个数,根据需要存储数据块的重复度来选择完全图的因子个数,将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块,然后对选中因子图的边进行标记,标记的边当做分布式数据节点进行存储.最后根据选中的因子的顶点和边生成编码矩阵,在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储.实验仿真结果显示,本文提出的一种新的部分重复码构造算法,与分布式存储系统中的里所(reed-solomon,RS)码、简单再生码(simple regenerating codes,SRC)以及最新的循环可变部分重复(variable fractional repetition,VFR)码相比,在系统修复故障节点时,能够快速地修复故障节点,有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度,而且构造过程简单,同时可以灵活选择构造参数,广泛适用于分布式存储系统中.

异构部分重复码的构造

针对分布式存储系统部分重复(Fractional Repetition,FR)码大都是同构的问题,提出了基于Hadamard矩阵和基于[7,3,4]简单图形构造异构的FR码的两种新型构造设计算法,构造方法更加简洁.其中基于Hadamard矩阵构造存储容量异构的FR码可实现由同构经过简单变换为异构的编码方式;基于[7,3,4]简单图形构造可扩展异构FR码可实现扩展延伸.经过与RS码理论分析对比发现,设计的两种异构FR码的修复局部性、修复带宽开销进一步降低,且可以实现故障节点精确无编码修复,修复复杂度较低,修复效率较高,减少了修复故障节点的时间.

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

部分重复(Fractional Repetition,FR)码能够实现精确无编码修复,修复复杂度低且修复带宽成本小。在动态分布式存储系统中,要求FR码的节点存储开销和数据块重复度会随机动态变化。为了使FR码更灵活地适应动态分布式存储系统,该文提出利用超图实现自适应可分解FR码的扩展构造方法。具体地,建立超图中边和顶点与FR码中节点和数据块的对应关系,通过增加或删除超图中对应边和顶点,实现超图的扩展构造,进而得到存储系统规模和存储文件规模变化时自适应可分解FR码的扩展构造。基于这种方法,能够扩展构造出给定参数范围内所有自适应可分解FR码,列举了存储节点数20以内的所有参数。自适应可分解FR码与常见的简单再生码(Simple Regenerating Codes,SRC)和RS(Reed-Solomon)码相比,在修复局部性和修复带宽开销方面具有一定优势。

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

针对部分重复码的有效修复问题,本文基于Harary图生成树构造出了一种新型的部分重复(Fractional Repetition based on Spanning trees of Harary graph,FRSH)码.实验结果表明,相较于现有的里所(Read-Solomon,RS)码和简单再生码(Simple Regeneration Codes,SRC),FRSH码在修复带宽开销、修复局部性等方面得到了更低的开销,且改善了修复效率,并将故障节点的修复时间缩短.

基于节点共边的异构部分重复码构造

为了满足分布式存储系统的动态存储和异构存储,本文提出一种基于节点共边的异构部分重复码(heterogeneous fractional repetition codes based on node common edge,HFRC-NCE)的构造算法.具体地,将MDS码编码后的数据块分为冷数据块和热数据块,结合节点共边的特性,分别将冷数据块和热数据块复制不同的倍数存储到各个节点中,构造的异构部分重复码更加简单直观,可实现故障节点的精确无编码修复.理论分析表明,与基于完全图和部分正则图构造的部分重复码相比,基于节点共边的异构部分重复码虽然存储开销和修复带宽开销略大,但其节点修复选择度更高,节点存储数据容量更多样化,重构度更小.

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

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

二分图因子分解的部分重复码构造

为了提高分布式存储系统的可靠性和修复效率,提出一种基于二分图的部分重复码构造算法。实验结果表明,与里所码以及简单再生码相比,基于二分图的部分重复码具有灵活选择参数的特性以及显著的降低了分布式存储的修复局部性、修复带宽开销。

哈夫曼树的异构部分重复码构造

针对分布式存储系统中数据被访问频率的不同,提出一种基于哈夫曼树的可变重复度的异构部分重复(HVFR)码,将不同访问频率的数据块作为哈夫曼树带有确定权值的叶子节点,构造哈夫曼树并确定数据块的重复度,利用成对平衡设计构造异构部分的重复码,能够提高热数据的并行访问速度和系统存储效率.性能分析和实验结果表明,与里所码以及简单再生码相比,HVFR码可以显著减少故障节点的修复时间及修复局部性,提高热数据的并行访问速度,达到负载均衡,且计算复杂度低.