Design of Exact Repair Regenerating Codes for Distributed Storage Systems

Abstract

The large volume of data generated by businesses, scientific research, web users, and other sources of information, requires systematic storage and maintenance mechanisms to ensure data integrity. Storage devices are prone to frequent failures due to various software and hardware issues. Distributed Storage Systems (DSS) enable reliable and efficient storage of data in the presence of node failures. In these systems, data is encoded in fragments spread across nodes and redundancy is introduced to improve the system’s reliability.Besides reliability, a storage system must be durable by having the capability of repairing the failed nodes. The repair process consists of downloading (part of) the content of a number of surviving nodes to reconstruct the content of the failed nodes. The conventional erasure codes suffer from high repair-bandwidth, the total size of data to be downloaded for the repair of each failed node. Regenerating codes are a class of erasure codes that have gained popularity in this context, due to their lower repair- bandwidth compared to erasure codes while providing the same level of fault tolerance. In this dissertation, a novel class of coding schemes for exact repair-regenerating is presented. The codes can trade between the repair bandwidth of nodes (number of downloaded symbols from each surviving node in a repair process) and the required stor- age overhead of the system. These codes work for general system parameters (n, k, d), which are the total number of nodes, the number of nodes suffice for data recovery, and the number of helper nodes in a repair process, respectively. The proposed construction offers a unified scheme to develop exact-repair regenerating codes for the entire trade-off. We conjecture that the new storage-vs.-bandwidth trade-off achieved by the proposed codes is optimum. Some other key features of this code include: the construction is linear; the required field size is only Θ(n); and the code parameters and in particular sub-packetization level is at most (d − k + 1)k; which is independent of the number of the parity nodes. Moreover, the proposed repair mechanism is helper-independent, that is the data sent from each helper only depends on the identity of the helper and failed nodes, but independent of the identity of other helper nodes participating in the repair process.