稀疏随机纠删码:一种大规模数据存储容灾方法

Sparse Random Erasure Code:a Fault Tolerance Scheme for Large-Scale Storage System

针对海量数据存储容灾系统中对扩展性、可靠性及高效性方面的需求,提出了一种高容灾可扩展且能够高概率译码恢复的高效大数据存储容灾算法。该算法利用等行重稀疏随机矩阵高概率行满秩的性质,用来实现数据高效可靠的存储容灾。首先,根据存储系统规模及容灾需求设置相应的编码参数;然后,采用等行重稀疏随机矩阵构造校验矩阵,并且产生相应的生成矩阵;最后,将数据文件分块编码到n个存储节点上,实现不同规模、不同容灾需求下的数据容灾存储,并通过设置合理的随机冗余,从而实现对译码成功率的控制。实验和理论分析表明:算法所提存储容灾技术可实现容灾能力不受素数或有限域大小的限制,而是根据存储规模及容灾需求灵活扩展;基于合理的随机冗余,译码成功率趋于1,实现了高可靠的数据容灾存储;在较大规模存储系统中,算法编译码速率是相应经典RS和CRS编码方案的2倍以上,并在较大码长下具有近似最大距离可分(MDS)的性质,可达到近似最优的存储空间利用率。

To meet the requirements for the scalability, reliability and high efficiency of data storage in large-scale storage system, a new kind of efficient storage fault-tolerance algorithm with flexible scalability and high probability of decoding is proposed, named sparse random erasure code（SREC）. The property of sparse random matrix with equal row weight is used in the algorithm. Firstly, the coding parameters are designed according to the scale of storage system and the requirement of fault tolerance; then, the parity check matrix and the corresponding generator matrix are constructed by using sparse random matrix; finally, the files are segmented into blocks and the parity blocks are created by encoding procedure, thus the data storage with different fault-tolerance requirements is realized. Meanwhile, by setting proper random redundancy, the probability of successful decoding is made controllable. Simulation results and theoretical analysis show that the proposed algorithm makes the fault-tolerance capability not have to be restricted by the prime or the size of finite field, and that based on the proper random redundancy, the successful decoding probability trends to 1, thus achieving the high reliability of data storage. Furthermore, the speeds of encoding and decoding are twice or more than those of classic RS and CRS algorithms, and when the code length is long enough, this algorithm has approximate optimal storage efficiency.