Fountain Codes for Fault Tolerance in Distributed Storage Systems

Abstract

Modern data storage systems are typically built using hard drives and other components that are prone to failure. The financial, operational and legal impact of data loss is usually quite high, particularly for owners of massive storage data-centers. Data loss prevention is therefore a critical aspect of storage system design. Techniques such as data replication are incapable of satisfying the cost and energy-efficiency required in a large-scale distributed storage system (DSS). Erasure codes for data storage are required to offer systematic encoding, low repair locality, low encoding/decoding complexity and low decoding/storage overhead. However, information theoretical bounds have shown that all these metrics might need to be carefully traded off with one another.

In this dissertation, analysis and design of Fountain codes for DSSs with respect to key performance requirements is performed. The first design proposed starts with a theoretical characterization of repair locality and system reliability for a Fountain coded system. The symbol repair locality probability as well as Data loss probability under BP decoding for a Fountain code are both derived. A multi-objective optimization (MOO) procedure is then used to determine degree distributions that achieve a good trade-off between repair locality, edge complexity and reliability. The second proposed solution offers a closed-form degree distribution using a modified truncated Poisson distribution (MTPD). The design is motivated by a careful study of the contributions from different encoding degrees towards the system performance. An analysis of the Fountain code probability of redundancy is used to determine the Poisson parameter.

Both proposed solutions come with approximately 10% additional decoding overhead compared to recent contributions based on algebraic codes. However, their design for implementation over a binary finite field and excellent repair capabilities make them quite attractive for implementation. Through simulations, we also show that their decoding overhead performance exhibits significant improvement over some existing Fountain code degree distributions in the literature. For instance, with the MTPD, we achieve a data loss probability closely approaching 10^-4, while other Fountain codes compared are about a factor of 10^2 higher.