随机二元扩展码:一种适用于分布式存储系统的编码

Random Binary Extensive Code(RBEC):An Efficient Code for Distributed Storage System

随着分布式存储系统的存储容量快速增长,备份容灾存储效率低的缺陷日益明显,基于纠删码的容灾方法越来越受到重视.然而,应用于存储系统的纠删码研究起步较晚,可供选用的码类少,并且大多数属于通信领域的编码方法,不能很好满足存储领域的特殊需求.该文将提出一种新颖的存储编码方法,称为随机二元扩展码(Random Binary Extensive Code,RBEC),为数据容灾存储系统提供一种新的选择.RBEC是一种基于异或运算的系统码,编码矩阵由一个单位阵和一个随机阵构成,采取自底向上的设计模式,通过控制随机矩阵中各个元素生成,达到码字整体上高性能.相比其他传统码类,RBEC参数具有动态调整能力,其编码矩阵的行列可以自由伸缩.进而,存储系统可根据应用需求的变化,动态调整码率和纠删能力.对于(k,δ,t)参数RBEC码,该文给出了容任意t删除错的成功译码概率下界及其证明,并指出通过增加δ值可使译码概率下界无限趋近1(100%).为了提高译码效率,该文进一步给出了一种简化译码矩阵规模的方法.最后介绍了RBEC在分布式存储系统的应用.

With the rapid growth of the capacity of distributed storage system, the defect of low storage efficiency for replication fault tolerance has become more and more obvious. In this context, erasure code for fault tolerance has attracted much attention in recent years. However, the research of erasure code applied in storage system starts relatively late and the existing types are too less. Furthermore, most of them are used in the communication field but can＇t satisfy the special requirement of storage field. In this paper, we present a novel code called Random Binary Extensive Code （RBEC）, which provides a new option for fault tolerance storage system. The RBEC is a kind of XOR-based systematic code, in which the generator matrix consists of an identity matrix and a random matrix. The bottom-up design model has been utilized in the design of the RBEC. Overall high performance can be achieved by controlling the generation of each element in the random matrix. In contrast to traditional codes, the RBEC has the ability of dynamically adjusting parameters, and the rows and columns of generator matrix can be scaled freely. Therefore, storage system can dynamically adjust the rate and the tolerance ability when the application requirements changed. For the （k,δ, t） RBEC, our work demonstrates and then gives the probability lower bound of successfully decoding in tolerating any t erasure errors, whose value can tend to 1 （100%） infinitely by increasing the value of 8. In order to further improve decoding efficiency, we also propose a method to minimize the size of decoding matrix. Finally, we introduce the application of the RBEC in distributed storage system.