XORing Elephants: Novel Erasure Codes for Big Data

By M. Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, A. Dimakis, Ramkumar Vadali, Scott Chen, Dhruba Borthakur. Proceedings of the VLDB Endowment, 2013

798 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/58b628792d3eb22a034a871ed3cf373afe591928

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Analyzing the download time of availability codes (2015, methodology): “It is worth noting that MTTDL of a 3-replication is typically considered as the performance objective while choosing an erasure code for a storage scheme [24, 48].”
A Solution to the Network Challenges of Data Recovery in Erasure-coded Distributed Storage Systems: A Study on the Facebook Warehouse Cluster (2013, background): “In [18, 19], a new class of codes called LRCs are proposed that reduce the disk and network bandwidth requirement during recovery.”
Private information retrieval in distributed storage systems using an arbitrary linear code (2016, background): “C4 is an LRC obtained from [12] and has a locality of 5.”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “Recently, codes have been extensively used for the storage layer to provide reliability by exploiting storage redundancy [4, 7, 9].”
Batch codes through dense graphs without short cycles (2014, methodology): “1: Graph representation GC for the [3, 8] code described in Example 1.”
Pocket: Elastic Ephemeral Storage for Serverless Analytics (2018, background): “Hence, it is common for storage systems to use fault-tolerance techniques such as replication and erasure codes [42, 66, 46].”
Availability Knob: Flexible User-Defined Availability in the Cloud (2016, neutral): “[55] mention an average of about 25 failed nodes, daily, in a 3000 node production cluster, which is noticeably higher than the previous record.”
f4: Facebook's Warm BLOB Storage System (2014, background): “XORing elephants [4] presents a new family of erasure codes that are more efficiently repairable.”
Locality and Availability in Distributed Storage (2014, background): “Some of these results have found their way into practice: codes with small locality were recently deployed in Azure production clusters [20], while others have been tested in Facebook clusters [6], [21].”
Locally Repairable Codes (2012, methodology): “The main properties that we exploit here are the following: entropy is oblivious to the encoding process (linear or nonlinear), it can accommodate different input or output symbol sizes, and different symbol representations (scalar or vector).”