二元再生码在分布式存储系统的应用

The Application of Binary Regenerating Codes for Distributed Storage Systems

分布式存储系统以其高效的可扩展性和高可用性成为存储大数据的主要系统.为了提高可靠性,需要在分布式存储系统中引入冗余.因此如何最优化存储空间、最小化修复带宽和最小化计算复杂度是衡量冗余存储系统效率的关键问题.再生码存储是一类可以达到存储空间与网络修复带宽最佳折中的存储方法,但现有的再生码的构造方法有大量有限域的乘法运算,其高昂的计算复杂度成为用于分布式存储系统中的主要瓶颈.实验结果表明,在保留再生码优势的前提下,采用移位和异或运算取代有限域的乘法运算可以大幅度地降低计算复杂度.创新之处在于提出了二元再生码(binary regenerating codes,BRGC),并给出了构造二元再生码的两类最佳再生码,即最小带宽二元再生码和最小存储二元再生码的方法.通过评估和对比主流的RS码和基于矩阵乘法的再生码,发现BRGC在计算复杂度方面有着明显的优势,在实际海量数据的分布式存储系统中具备更好的应用价值.BRGC在修复和解码性能均优于柯西(Cauchy Reed-Solomon)码.

Distributed storage system(DFS)is the main system of providing storage for big data because of its efficient scalability and high availability. We need to induce redundancy to the distributed storage system to provide high reliability of system.Storage capacity,repair bandwidth and computational complexity optimization are the main considerations in distributed storage system. Regenerating code(RGC)is a class of storage codes that achieve the optimal trade-off between storage capacity and repair bandwidth.However,existing constructions of regenerating codes rely on expensive Product-matrix computational operations.The high complexity limits their applications in large-scale practical storage systems.The results of this paper show that it is possible to reserve the full potential feature of regenerating codes and bring low computational complexity.We propose a new class of regenerating codes,called BRGC(binary regenerating codes),and give two specific points(minimum-bandwidth and minimum-storage regenerating points)on the storage and repair bandwidth trade-off curve,using only binary addition and shift operations in the coding and repair processes.By comparing with the main RS code and Product-matrix RGC,we find BRGC has better applied value in practical DFS.The results of simulation show BRGC outperform Cauchy Reed-Solomon codes in repairing and decoding.