"Locally Repairable Codes: Novel Erasure Codes for Big Data"

Dimitris Papailiopoulos
Communication Sciences Institute
Department of Electrical Engineering
University of Southern California
505 EEB, 3740 McClintock Ave.,
Los Angeles, CA 90089-2560

Abstract:

Currently, most distributed storage systems for large clusters use erasure codes to efficiently provide high reliability for archival storage applications. However, off-the-shelf erasure codes suffer from large costs during the repair of lost nodes: repairing node failures requires a large disk I/O, a great number of disk accesses, and heavy network traffic. In this talk, we present codes that are optimized for the metric of repair locality, which corresponds to the the number of disk accesses required during a node repair.

We characterize an information theoretic trade-off à la Singleton bound, that binds together locality, code distance, and storage cost per node. We introduce locally repairable codes (LRCs) which achieve the points of this tradeoff. The achievability proof uses a novel "locality aware" flow graph gadget which leads to a randomized code construction. Then, we present a HadoopDFS implementation of an explicit LRC and compare it to the default Reed-Solomon encoded HDFS. Our experimental evaluation indicates a reduction of approximately 2x on the repair disk I/O and repair network traffic.

Biography:

Dimitris S. Papailiopoulos received the Diploma and M.Sc. degrees in electronic and computer engineering from the Technical University of Crete, Greece, in 2007 and 2009, respectively. Since 2009, he has been a graduate student with the Department of Electrical Engineering, University of Southern California, where he is currently working toward the Ph.D. degree. His research interests are in the areas of coding theory, communications, and signal processing, with an emphasis on storage codes for big data, interference alignment methods, and large-scale sparse principal component analysis.