Xorbas Hadoop Project Page

Xorbas is our Hadoop version that implements a new set of regenerating codes called Locally Repairable Codes (LRC). The source code is available here. It is built on top of Facebook's Hadoop system running HDFS-RAID, and thus can support Reed Solomon and XOR codes in addition to LRCs.

Paper Title

XORing Elephants: Novel Erasure Codes for Big Data

Authors:

• Maheswaran Sathiamoorthy, University of Southern California
• Megasthenis Asteris, University of Texas at Austin
• Dimitris Papailiopoulos, University of Texas at Austin
• Alexandros G. Dimakis, University of Texas at Austin
• Ramkumar Vadali, Facebook
• Scott Chen, Facebook
• Dhruba Borthakur, Facebook

Abstract:

Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability.

This paper shows how to overcome this limitation. We present a novel family of erasure codes that are efficiently repairable and offer higher reliability compared to Reed-Solomon codes. We show analytically that our codes are optimal on a recently identified tradeoff between locality and minimum distance.

We implement our new codes in Hadoop HDFS and compare to a currently deployed HDFS module that uses Reed-Solomon codes. Our modified HDFS implementation shows a reduction of approximately 2x on the repair disk I/O and repair network traffic. The disadvantage of the new coding scheme is that it requires 14% more storage compared to Reed-Solomon codes, an overhead shown to be information theoretically optimal to obtain locality. Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.

BibTex

@article{XorbasVLDB,
    title={XORing Elephants: Novel Erasure Codes for Big Data},
    author={Sathiamoorthy, M. and Asteris, M. and Papailiopoulos, D. and Dimakis, A. G. and Vadali, R. and Chen, S. and Borthakur, D.},
    journal={Proceedings of the VLDB Endowment (to appear)},
    year={2013},
    publisher={VLDB Endowment}
}

Download the Paper.

Tech Report (arXiv).

Video on `Erasure Codes for Large Scale Distributed Storage` by Prof Alex Dimakis

Note:

1. The paper is set to appear in 39th International Conference on Very Large Data Bases (VLDB) 2013, Italy.

2. Part of this work was completed when Megasthenis Asteris, Dimitris Papailiopoulos and Alexandros G. Dimakis were with the University of Southern California

3. Supported by NSF Award CCF-1055099 and research gifts by Google and Microsoft Research.