PaperlayerView exact revision on arXiv

Source-linked AI summary

XORing Elephants: Novel Erasure Codes for Big Data

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

arXiv:1301.3791v1cs.ITcs.DCcs.NI

TL;DR

Large-scale storage systems need redundancy without replication’s high storage overhead, yet Reed-Solomon codes make repairs expensive. The paper introduces locally repairable codes, proves their locality optimal, and implements them in HDFS. Experiments report approximately 2× lower repair disk I/O and network traffic, while faster repairs provide higher reliability at a 14% storage increase.

  • Problem

    Large storage systems seek lower-overhead redundancy, but Reed-Solomon codes have high repair costs and replication has very large storage overhead.

  • Method

    The paper introduces Locally Repairable Codes, proves their locality information-theoretically optimal, and implements them in HDFS-Xorbas.

  • Results

    Approximately 2× lower repair disk I/O and network traffic than production Reed-Solomon codes is achieved with 14% more storage.

  • Takeaways & Limitations

    LRCs provide an intermediate storage-reliability operating point with significantly smaller repair costs and practical relevance when network bandwidth is the bottleneck.

  • Takeaways & Limitations

    A detailed study of availability tradeoffs for coded storage systems remains future research.

Abstract

from arXiv · show

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.

1. INTRODUCTION

Distributed storage is moving from replication toward erasure coding to reduce storage overhead, but Reed-Solomon codes impose costly repairs. The paper introduces locally repairable codes that reduce repair costs while trading some storage efficiency for locality and reliability.

  • Motivation: Replication can impose 200% storage overhead, motivating erasure coding for large-scale archival data.Facebook and others use Reed-Solomon codes to introduce redundancy while saving storage.
  • Existing Codes: RS (10,4) tolerates any 4 block failures with 40% storage overhead, achieving the minimum storage overhead for that reliability level.Each stripe contains 10 data blocks and 4 parity blocks.
  • Repair Problem: A single lost block can require Reed-Solomon repair to transfer and reconstruct 10 blocks, creating a 10× repair bandwidth and disk-I/O overhead.Information-theoretic results motivate codes that repair failures using substantially less network bandwidth.
  • Contributions: Locally Repairable Codes reduce network bandwidth and disk I/O for single-block repair, with analytically optimal locality.The paper presents randomized and explicit constructions starting from generalized Reed-Solomon parities.
  • Evaluation: 2× lower repair disk I/O and network traffic is achieved experimentally, at the cost of 14% more storage than Reed-Solomon codes.The added storage is information-theoretically optimal for the obtained locality.
  • Reliability: Faster repairs improve availability and yield 2 more zeros in MTTDL than RS (10,4) and 5 more zeros than 3-replication under a simple Markov model.The evaluation uses HDFS-Xorbas and compares it with Reed-Solomon-based HDFS-RAID.

2. THEORETICAL CONTRIBUTIONS

The paper develops Locally Repairable Codes that trade a small loss in distance for much lower repair locality, while achieving an information-theoretically optimal locality–distance tradeoff. An HDFS-Xorbas construction adds local parities to Reed-Solomon coding so single-block failures can be repaired from fewer blocks.

  • Locality–distance tradeoff: MDS codes cannot achieve locality smaller than k, making optimal fault tolerance expensive to repair.Any k coded blocks can reconstruct the file, but repairing one block may require accessing k others.
  • Locality–distance tradeoff: LRCs provide logarithmic locality while retaining distance asymptotically equal to that of MDS codes.The construction uses locality r = log(k), with distance approaching the MDS distance as k grows.
  • Code construction: The codes are constructed by grouping MDS-encoded blocks into logarithmic-sized sets and combining them into low-degree parity blocks.The paper proves optimal distance for the chosen locality through a universal information-theoretic tradeoff.
  • LRC implemented in Xorbas: Xorbas starts with 10 data blocks and 4 Reed-Solomon parities, then adds local parities so a single failure can be repaired using only 5 other blocks.The local parity construction is layered on top of the production (10,4) Reed-Solomon code.
  • LRC implemented in Xorbas: An alignment equation among three local parities allows one parity to remain implied rather than stored.This reduces the storage cost introduced by adding local parities, although the scheme still requires extra storage relative to Reed-Solomon.
  • LRC implemented in Xorbas: The implemented code has maximum distance d = 5 for locality r = 5 and blocklength n = 16.For the HDFS-RAID Reed-Solomon code, choosing all local-parity coefficients as ci = 1 permits simple XOR operations.

3. SYSTEM DESCRIPTION

HDFS-Xorbas modifies HDFS-RAID to support locally repairable codes while remaining compatible with existing Reed-Solomon files. Its light decoder repairs suitable failures from five blocks using simple XOR, falling back to a heavy decoder for harder cases.

  • HDFS-RAID: HDFS-RAID stores Reed-Solomon parity files and uses RaidNode and BlockFixer processes for encoding, maintenance, and repair.ErasureCode implements the underlying RS encoding and decoding for stripes of 10 data blocks and 4 parity blocks.
  • HDFS-Xorbas: HDFS-Xorbas extends HDFS-RAID with LRC support by modifying ErasureCode, RaidNode, and BlockFixer.The resulting system is distinguished from the original implementation as HDFS-RS.
  • HDFS-Xorbas: Xorbas preserves backwards compatibility and can convert RS-encoded files incrementally by adding local XOR parities.The deployed LRCs are designed as extension codes of Facebook’s (10,4) Reed-Solomon code.
  • Encoding: Each stripe contains 10 data blocks, 4 Reed-Solomon parities, and 2 local XOR parities, for 16 total blocks.Parity computation is distributed through MapReduce, and blocks are placed across DataNodes according to Hadoop’s block-placement policy.
  • Decoding: Xorbas uses a light decoder for single-block failures and a heavy decoder when light decoding cannot obtain the required blocks.The light decoder reads five required blocks in parallel and performs a simple XOR.
  • Decoding: For single failures, Xorbas accesses fewer blocks than HDFS-RS, and many double failures are also locally repairable when they affect different local XOR groups.HDFS-RS currently opens streams to all 13 other blocks, though a more efficient implementation could reduce this to 10.

4. RELIABILITY ANALYSIS

The analysis compares replication, Reed-Solomon, and LRC reliability using Markov models under stated Facebook-cluster assumptions. It evaluates how failure tolerance and repair speed affect MTTDL, while noting an availability tradeoff requiring further study.

  • Reliability model: MTTDL increases with greater failure tolerance and faster repairs, the two factors used to compare the storage schemes.The analysis models their interplay rather than treating reliability as determined by storage efficiency alone.
  • Scheme comparison: Under the Markov model, replication repairs fastest but tolerates fewer failures, whereas LRC repairs faster than RS while both coded schemes tolerate more failures.Replication has three states, while both (10,4)-RS and (10,6,5)-LRC lose data after five block erasures.
  • Evaluation assumptions: The evaluation assumes 3000 disk nodes, 30PB of data, four-year node MTTF, 256MB blocks, and a 1Gbps cross-rack repair limit.These parameters are based on Facebook cluster measurements and warehouse defaults.
  • Reliability results: 2 more zeros in MTTDL distinguish Xorbas LRC (10,6,5) from (10,4) Reed-Solomon under the evaluated model.The analysis reports that LRC’s higher repair speed compensates for its additional storage in reliability.
  • Availability: A detailed study of availability tradeoffs for coded storage systems remains future work, despite LRC’s faster degraded reads.Replication can serve another copy immediately after one block loss, whereas coded schemes wait for repair.

5. EVALUATION

The evaluation compares HDFS-Xorbas with HDFS-RS across EC2 and Facebook environments, measuring repair I/O, network traffic, duration, and workload impact. Xorbas consistently reduces repair cost and time, while workload benefits depend on scheduler configuration.

  • Evaluation methodology: The experiments evaluate HDFS-Xorbas against HDFS-RS using HDFS Bytes Read, Network Traffic, and Repair Duration.HDFS Bytes Read measures data read by repair jobs, Network Traffic measures repair data transferred, and Repair Duration spans the first repair job launch to the last completion.
  • EC2 results: 41%−52% of RS’s data was read by Xorbas to reconstruct the same number of lost blocks, yielding an estimated 2× reduction in blocks read per lost block.The estimated averages were 11.5 blocks read per lost block for HDFS-RS and 5.8 for HDFS-Xorbas.
  • EC2 results: Xorbas finished repairs 25% to 45% faster than HDFS-RS across the experiments.Repair duration was measured from the launch of the first block-fixing job to termination of the last one.
  • Scaling implication: Because network bandwidth was not fully saturated in these experiments, larger-scale repairs may widen Xorbas’s recovery-time advantage as network bottlenecks emerge.The paper reports network saturation as a typical bottleneck for large-scale MapReduce tasks and expects it to delay RS repairs more than LRC repairs.
  • Repair under workload: Under workload, missing blocks added 9 minutes for LRC and 23 minutes for RS, but the benefit depended critically on Hadoop FairScheduler configuration.The experiments used WordCount jobs with missing-block and all-blocks-available scenarios; unfavorable scheduling can increase delays or cause jobs to fail if repairs exceed a threshold.
  • Facebook cluster results: In the Facebook cluster experiment, Xorbas still reduced data read and repair duration despite losing more blocks than RS by more than its storage overhead.Network Traffic was unavailable in this experiment, and the dataset was not representative of Facebook production data.

6. RELATED WORK

Prior work established repair-bandwidth bounds and explored exact repair, but practical high-rate constructions remained incomplete. This paper’s approach uses locality to reduce both repair traffic and disk I/O while characterizing an information-theoretic tradeoff.

  • High-rate exact-repair codes remained incompletely understood, with no practical construction known to the authors.
  • Many repair-efficient codes reduced network traffic at the cost of higher disk I/O, whose necessity was unknown.
  • Locality measures the number of blocks needed to reconstruct a lost block, and the introduced codes match its information-theoretic bound.
  • The main construction combines optimal locality with Reed-Solomon global parities through implied parities and explicit parity alignment.

7. CONCLUSIONS

The paper introduces Locally Repairable Codes as a practical storage-system operating point. Its implementation reduces repair costs substantially while accepting a modest storage increase, with potential relevance to archival and bandwidth-constrained systems.

  • LRCs provide significantly smaller repair disk I/O and network-bandwidth requirements with marginally suboptimal storage.
  • 2× disk I/O and network reduction was observed in implementation experiments for 14% more storage.
  • Large LRCs could offer high fault tolerance and small storage overhead for purely archival clusters.
  • Local repairs could allow spinning disks to be powered down because few disks are required for single-block repairs.
  • LRCs create a practically relevant operating point especially when network bandwidth is the main performance bottleneck.

A. DISTANCE AND LOCALITY THROUGH ENTROPY

This section formulates code distance and locality through entropy, yielding definitions that apply to linear and nonlinear codes. The entropy framework supports universal information-theoretic bounds on codes with locality.

  • The entropy-based characterization of code distance applies universally to linear and nonlinear code designs.
  • An encoding map takes k file blocks as input and outputs n coded blocks, defining a (k, n−k) code.
  • Code distance is the minimum number of block erasures that leaves the remaining blocks with entropy below the file size.
  • A block has locality r when it is a function of r other coded variables that can reconstruct it.
  • The entropy formulation enables universal information-theoretic bounds on code distance for codes with locality.

B. INFORMATION THEORETIC LIMITS OF LOCALITY AND DISTANCE

The section derives information-theoretic limits linking locality and minimum distance by constructing large low-entropy sets of coded blocks. It shows that non-overlapping repair groups attain the resulting distance bound, and that linear codes can achieve it.

  • The analysis seeks the largest coded-block set S whose entropy is below the file size, thereby deriving an upper bound on minimum distance.
  • Each coded block belongs to a repair group of size r+1 consisting of the block and the r blocks that generate it.
  • The joint entropy of one repair group is at most the entropy of r file blocks.
  • The proof builds S incrementally, tracking changes in cardinality and entropy until the set remains just below file entropy.
  • Non-overlapping (r+1)-groups are optimal for code distance, and linear codes suffice to achieve the information-theoretic bound.

C. ACHIEVABILITY OF THE BOUND

The paper proves achievability of the locality–distance bound by modeling repair groups and decoding requirements in a locality-aware information flow graph. Feasible multicast sessions then yield codes meeting the bound, including explicit existence results.

  • Information flow graph: A locality-aware information flow graph augments standard network models with dependency subgraphs for repair groups of size r + 1.Its capacities and cut-set bound are determined by k, n − k, r, and d.
  • Information flow graph: Data Collectors must receive enough coded-block flow to reconstruct the file, equivalently requiring source–DC cuts of at least the file size M.The graph represents file blocks as sources, coded blocks as intermediate nodes, and Data Collectors as decoding sinks.
  • Cut-set achievability: A minimum source–DC cut of at least M holds when d satisfies the stated distance bound, establishing sufficient entropy for decoding.Lemma 2 verifies this cut condition for G(k, n − k, r, d).
  • Cut-set achievability: A feasible multicast session on G(k, n − k, r, d) implies a (k, n − k) code with locality r and distance d.Thus, the network construction translates multicast feasibility into an erasure-code existence result.
  • Explicit constructions: RLNC achieves the cut-set bound, yielding codes that attain the distance bound; deterministic multicast constructions can alternatively produce explicit linear codes.The deterministic construction is described as polynomial-time in the number of destinations and network parameters.
  • Explicit constructions: There exists a linear code with locality r and length n, for (r + 1)|n, attaining the stated distance expression; setting r = log(k) recovers Theorem 1.Deleting one coded block from each non-overlapping repair group leaves an MDS code under the stated construction relationship.

D. AN EXPLICIT LRC USING REED-SOLOMON PARITIES

The paper constructs an explicit locality code by adding XOR parities to a Reed–Solomon code and proves that the resulting length-16 code has locality 5 and optimal distance 5.

  • Construction: Reed–Solomon codes provide the MDS precode because every relevant square submatrix of the parity-check matrix is full-rank, giving distance d = n − k + 1.The parity-check matrix is defined over an extended binary field with field order q = 2^m ≥ n.
  • Construction: The construction starts from a (14, 10)-Reed–Solomon generator matrix and adds two simple parities over separate groups of five coded blocks.The resulting code is designed to provide local repair while retaining the Reed–Solomon foundation.
  • Systematic form: A full-rank row transformation converts the constructed code into systematic form without changing its distance or locality properties.The transformation makes the first ten coordinates the file blocks while preserving the code’s structural guarantees.
  • Guarantees: The resulting length-16 code has locality 5 for every coded block and optimal distance d = 5.The distance upper bound follows from the entropy constraints imposed by repair groups, matching the construction’s achieved distance.
  • Local repair: All coded blocks can be repaired from five other coded blocks using the added XOR parities and interference alignment.The proof uses parity relations and the generator-matrix identity to repair both the initial and parity blocks.
Loading 1301.3791v1…