基于循环矢量构造的精确修复MDS编码

为解决分布式存储系统节点精确修复的问题,构造了一类最小存储再生编码,该编码属于最大距离可分(MDS)删除码. 利用循环矢量构造生成矩阵,将冗余数据与系统数据混合存储,编码过程中所有的运算都属于伽罗华2域. 采用该编码的存储系统,在发生单节点故障时,精确修复的最小带宽为理论最小值,在系统正常工作时,能为单用户提供最大理论值的可用带宽. 与最小存储再生码和最小带宽再生码相比,编码矩阵简单,解码计算量较小,能提供较高的可用带宽.     

云存储系统中基于MSR码的局部性修复编码

为了提高分布式云存储系统的存储可靠性和故障节点修复效率,提出一种基于最小存储再生码的局部性修复编码方案. 具体地,构造适用于云存储的系统最小存储再生码,以此码为局部码构造局部性修复编码,确保最大距离可分性质和简单修复特性. 性能分析和仿真结果表明,该局部性修复编码方案可实现云存储系统中多个故障节点的快速修复,具有较低的修复局部性,相对于三副本复制方式和简单再生码,该局部性修复编码方案在存储开销和修复带宽开销方面的性能更优.     

基于Hadamard向量的新型(k+2,k)MSR码

在分布式存储系统中,再生码是一种能够最优修复节点丢失数据的编码策略.在存储空间有限的前提下,设计出一种高码率的最小存储再生码可以进一步提高存储空间的利用率.利用Hadamard向量设计出一种新型高码率最小存储再生码,实现最优精确修复所有系统节点数据.这种新的编码策略将Hadamard向量进行变型,同时改变了Hadamard向量放置在编码矩阵中的位置.与原有的(k+2,k)Hadamard MSR码策略不同,将编码矩阵中的Hadamard向量从主对角线位置移至非主对角线上时,能够减少修复过程中有限域上的运算次数.从而使这种新型再生码策略在能够精确修复系统节点数据的同时,进一步降低数据修复过程中的计算复杂度.     

非均匀故障保护的分组修复码构造

考虑到实际分布式存储系统中存在热度不同的文件,构造了一种基于非均匀故障保护的分组修复码（GRC-NFP）,可对热文件和高故障概率节点提供更高等级保护,并降低多故障节点修复的磁盘读取开销.在文件冷热分组后,用所存目标节点故障概率表征数据块故障概率,并排序,存入长度依次递增的多个数据分组,并生成组编码块.性能分析和实际系统部署结果表明,与里德-所罗门码和分组修复码相比,GRC-NFP可在存储开销较小的条件下拥有较高的容错能力和较低的修复局部性,并且使热文件能够受到更有效地保护.系统部署下较少的编码和故障修复时间进一步证明了GRC-NFP的可行性.     

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

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

基于非均匀循环编码的分组修复码构造

考虑到实际分布式存储系统中节点故障情况的多样性,该文提出一种基于非均匀循环编码的分组修复码(GRC-NCC),使高故障率节点得到更有效的保护.具体地,根据节点故障率对存储节点进行非均匀分组,将数据块依次存入长度递增的节点分组,再使用跨条带循环编码的思路生成组编码块和全局校验块.性能分析以及实验仿真表明,GRC-NCC虽...     

基于Hadamard矩阵的最优局部修复码构造

现有的局部修复码大多能满足最小距离最优的边界条件,但是在满足最小距离最优情况下构造维度最优的局部修复码还比较困难。针对上述问题,提出一种基于Hadamard矩阵的最优局部修复码的构造方法,通过对Hadamard矩阵进行扩展,构造局部修复码的校验矩阵,进而通过此校验矩阵构造最优局部修复码。首先,基于Hadamard矩阵构造局部修复码的校验矩阵,通过校验矩阵构造的局部修复码的最小距离可以达到最优最小距离界,但是其维度没有达到最优维度边界条件;为进一步提高维度,将校验矩阵中的关联矩阵0和1元素互换得到新的关联矩阵,通过和新的关联矩阵级联进行扩展,构造的扩展局部修复码不仅可以达到最小距离最优,且能达到维度最优的边界条件。与现有局部修复码相比,该构造的局部修复码是最小距离和维度最优的局部修复码,且其码率也更逼近局部修复码最优码率的边界。     

基于RBIBD的最优局部修复码构造

随着数据量的迅速增长,对存储海量数据的分布式存储系统的可靠性和有效性的要求日益增加。局部修复码(LRCs)具有良好的修复局部性,能够有效实现海量数据在分布式存储系统中的可靠高效存储,构造具有(r,t)局部性的局部修复码已经成为当前研究的热点。为此,提出了一种基于可分解均衡不完全区组设计(RBIBD)的最优局部修复码的构造方法,构造信息位具有(r,t)局部性的二元最优单校验LRCs。性能分析表明,构造的LRCs达到了最小距离最优边界,且在码率上表现得更优。     

分布式存储中新型分组piggybacking框架

随着互联网技术的快速发展，全球数据量爆炸式增长对分布式存储系统的可靠性和可用性提出了严峻的挑战。Piggybacking框架作为一种高效的数据容错技术成为近年来研究的热点。目前，绝大多数piggybacking框架均以牺牲子条带数和修复度的方式来降低修复带宽，导致修复失效节点过程中所节省的数据量通常无法有效地提升磁盘读取效率。针对上述情况，提出一种新型分组piggybacking框架，在保证较低修复带宽的同时，进一步降低了子条带数和信息节点修复度，从而提升分布式存储系统的输入/输出性能。该框架将校验节点分为两个部分，信息符号和校验符号分别按照一定规则分组后依次嵌入到对应的校验节点中，设计简单。通过这种设计，可以同时有效修复信息节点和校验节点，既减少了子条带数，又使其在校验节点个数较多时拥有较强的综合修复能力。与其他piggybacking框架相比，新型分组piggybacking框架能更好地权衡修复带宽、修复度与子条带数，适合在实际系统中应用。     

一种新的3容错扩展RAID码

随着存储系统规模的扩大,如何提高存储系统可靠性成为一个必须解决的问题. 目前的双容错独立冗余磁盘阵列(RAID)码已经无法满足存储系统可靠性要求. 在双容错行对角奇偶校验(RDP)码的基础上,提出了一种编码冗余率和纠错能力达到编码最优的新的扩展RDP-RAID码,可以允许任意3磁盘同时故障,并给出了一种基于二元矩阵变换的简单和直观的译码算法. 与STAT码和EEOD码相比,扩展RDP-RAID码的编译码复杂度、更新复杂度、存储效率的综合性能可达到最优,存储可靠性高.     

General reliability model of the non-MDS coded storage system

An open problem is how different configurations influence the reliability of a storage system using non-maximum distance separable codes as redundancy strategy.This paper proposes a repairable probability algorithm for solving data objects with non-maximum distance separable code encoding by considering the construction matrix of non-maximum distance separable codes.This algorithm exhaustively loses all possible combinations of several blocks and judges whether the matrix corresponding to each combination is reversible for calculating the probability of recoverability.We propose an analytical model based on the Markov chain to quantify the reliability of the non-maximum distance separable coded storage system.This model could quantify the impact of a series of design factors on the reliability of the storage system,such as the effect of non-maximum distance separable code configuration,the capacity of the storage system,the capacity of the object-based storage device nodes,the repair bandwidth,the mean time to data loss of the object-based storage device nodes and so on.Finally,the numerical analytical method is used to verify the correctness of the model and the influence of different factors on the reliability of the storage system.Our model enables system practitioners to decide the appropriate configuration based on their reliability requirements.     

Asymmetric spatially-coupled LDPC codes for burst erasure channels

The outstanding performance of Spatially-Coupled Low Density Parity Check(SC-LDPC) codes deteriorates due to burst erasures over the channels with memory. To improve the performance of SC-LDPC codes over burst erasure channels, an asymmetric spatial coupling structure is proposed where the variable nodes at the same position of the protograph are permitted to couple with check nodes with different coupling widths. According to the structural properties of the Asymmetric Spatially-Coupled LDPC (ASC-LDPC) codes, the characteristics of the stopping sets of the base matrices are analyzed. It is shown that the base matrix of an ASC-LDPC code possesses a longer span and a larger cardinality of the minimal stopping set than that of the conventional SC-LDPC code. Thus a longer single-burst erasure or more multiple-burst erasures can be corrected by ASC-LDPC codes. Simulation results show that the proposed asymmetric spatial coupling structure could improve the performance of SC-LDPC codes over both the single-burst erasure channels and multiple-burst erasure channels.     

阶数为素数幂的一类整循环矩阵

在循环哈达玛矩阵的研究中,引进了代数数论中的素理想分解方法,证明了阶数为４ｒ（ｒ＞１）的循环哈达玛矩阵是不存在的,并给出了全部４阶循环哈达玛矩阵．对于阶数为ｎ＝ｐｒ（ｐ为素数）且元素为整数和循环矩阵Ｈ,若满足ＨＨＴ＝ｎＩ,则Ｈ的结构可完全确定．这种Ｈ可视为有限域Ｆｐｒ上的矩阵,因而得到了Ｆｐｒ上一种正交码的构造．     

一类广义RA码的优化设计方法

由重复器、交织器、组合器和广义累加器组成的广义系统RA码,采用低密度奇偶校验码(LDPC码)的置信传播译码时,码性能受稀疏校验矩阵的小环影响大,而稀疏校验矩阵由编码器的结构决定。该文根据置信传播译码的无环要求,通过重复器、交织器、组合器和广义累加器的联合优化设计,给出了无4环的广义RA码的奇偶校验矩阵设计方法。研究结果显示,该方法实现简单,实用性强,设计的广义RA码编码增益大。