Concepedia

XORing elephants

Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros G. Dimakis, Ramkumar Vadali, Scott Chen, Dhruba Borthakur

Proceedings of the VLDB Endowment · 2013 · 689 citations · 30 references

DOI

TL;DR

Distributed storage systems for large clusters typically rely on replication, but erasure codes such as Reed‑Solomon reduce storage overhead at the cost of high repair traffic, a trade‑off deemed unavoidable for high efficiency and reliability. The paper proposes a solution to eliminate this high repair cost. The authors design a novel family of efficiently repairable erasure codes, implement them in Hadoop HDFS, and benchmark them against the existing Reed‑Solomon module. Analytically the codes attain the optimal locality‑distance trade‑off, and experimentally they cut repair disk I/O and network traffic by about two‑fold, add only 14 % extra storage, and achieve reliability orders of magnitude higher than replication.

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 2× 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.