Repair efficient erasure correcting codes for distributed storage systems
Siddhartha Kumar · Chalmers Publication Library (Chalmers University of Technology) · 2015
The current age of information technology is characterized by an ever increasing presence of digital data in the world.Digital data has become an integral part of our lives in the form of social networking, online streaming and accessing crucial data on the go.The huge amount of data generated needs to be stored in an inexpensive and reliable way.Distributed storage (DS) is a technology that stores data on a network of inexpensive storage devices, referred to as nodes, thereby lowering the cost of storage.However, such storage nodes are prone to failures, which leads to unavailability of the stored data.The ability to tolerate multiple node failures is defined as fault tolerance.The addition of redundancy in DS systems allows for the recovery of the lost data by guaranteeing fault tolerance.The easiest way to achieve this, is to replicate the data in a system, i.e., the data is copied over several nodes.However, replication schemes store data inefficiently.Hence, the storage industry has started moving towards erasure correcting codes (ECCs) that store data much more efficiently.Essentially, data in DS systems is available as long as the number of node failures does not exceed its limit of fault tolerance.When a node fails, to maintain the initial level of availability, another node needs to be populated with the lost data.This is referred to as repair.By using ECCs, one gains in storage efficiency but looses in repair performance, namely in such parameters as repair bandwidth and repair complexity.Therefore, in recent years, the research has been focused on designing ECCs for DS that perform repair efficiently.In this thesis, we present the construction of a new family of ECCs for DS that yield low repair bandwidth and low repair complexity for a single failed data node.In particular, we present a systematic construction based on two classes of parity symbols.The primary goal of the first class of symbols is to provide good erasure correcting capability, while the second class facilitates node repair, reducing the repair bandwidth and the repair complexity.Lastly, we compare the proposed codes with Minimum Disk I/O codes, Zigzag codes, piggyback codes and local reconstruction codes that are proposed in the literature.