A New Class Of Regenerating Codes In Distributed Stotage Systems And Research On Its Decoding Algorithm

In recent years, "BIG DATA" is regarded as a more and more important research field by the Internet industry and academia. The biggest challenge in this field is how to store and deal with it. The Distributed Storage Systems, in past three decades, hava played a significant role in data storage and processing. The distributed storage systems can help to keep balance between the storage cost, the repair bandwidth and the repair complexity. Erasure Codes and Replication Codes are the two traditional repair schemes that are widely used in distributed storage system. With an (n, k) erasure code, the original k data blocks are encoded into n blocks and the whole coded data blocks are stored by n storage nodes. When a node fails, it needs to connect to any arbitrary k out of the n-1 surviving nodes and download the whole data blocks to repair the failed node. Apparently, with the erasure codes, it needs a small amount of extra storage but complex operations to repair the failed node. Compared with Erasure Codes, the Replication Codes have a nice performance in terms of repair bandwidth and computational overhead.After Network Coding was intergrated into Distributed Storage Systems, Dimakis et.al proposed the conception of Regenerating Codes. With Regenerating Codes, the data can not only be transferred on each node, but also can be operated. From 2010 to date, different kinds of MBR (Minimum Bandwidth Regenerating) codes, MSR (Minimum Bandwidth Regenerating) codes and LRC (Locally Repairable Codes) were proposed, and each of them had their own strengths. The Product Matrix construction for regenerating codes, proposed by Rashmi et. al, is widely used because there is no constraint of the constructing parameters. Moreover, Yang proposed a repair and recovery scheme called In-place algorithm for shift-based codes. With In-place algorithm, it needs only Xor operations to repair a failed node or recover the original data blocks. Hence, the computational complexity was reduced greatly.The bandwidth of aforementioned Product Matrix MBR codes and BASIC codes was optimal, but the Data I/O was not. In this paper, a new class of product matrix MBR codes is proposed. With the new codes, it has the optimal I/O property and can simultaneously maintain all the original properties (advantages) of product matrix codes. What’s more, a novel algorithm is proposed for shift-based codes in this paper. With the proposed algorithm, the time of decoding is reduced by half.