PaperlayerView exact revision on arXiv

Source-linked AI summary

Erasure Coding for Distributed Storage: An Overview

S. B. Balaji, M. Nikhil Krishnan, Myna Vajha, Vinayak Ramkumar, Birenjith Sasidharan, P. Vijay Kumar

arXiv:1806.04437v1cs.IT

TL;DR

Distributed storage needs redundancy for reliability while limiting storage overhead and the network cost of repairing failed nodes. This survey synthesizes regenerating codes, locally recoverable codes, improved Reed–Solomon repair, and related bounds and constructions. It covers repair-bandwidth and repair-degree objectives, regenerating-code tradeoffs, and low-sub-packetization questions for Reed–Solomon codes.

  • Problem

    Reliable distributed storage must balance storage overhead with efficient failed-node repair, including repair bandwidth, helper-node access, and repair degree.

  • Method

    The paper surveys regenerating and locally recoverable codes, Reed–Solomon repair techniques, and associated constructions, bounds, and evaluations.

  • Results

    The survey organizes recent developments around repair bandwidth, repair degree, Reed–Solomon repair, and bounds including optimal or achievable code constructions.

  • Takeaways & Limitations

    The reviewed results provide multiple coding approaches for reducing repair costs while preserving distributed-storage recovery properties.

Abstract

from arXiv · show

In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code. This survey provides an overview of the efforts in this direction that have taken place over the past decade.

I. INTRODUCTION

This survey examines erasure coding for reliable, storage-efficient data-center storage, emphasizing the practical challenge of repairing failed nodes. It reviews regenerating and locally recoverable codes, improved Reed–Solomon repair, and the network-coding foundations of repair and file-size bounds.

  • Motivation: Distributed storage uses redundancy for reliability, but minimizing storage overhead and repairing failed nodes efficiently are central design challenges.The survey considers data-center systems storing tens or hundreds of petabytes.
  • Motivation: A Facebook warehouse cluster experienced a median of 50 unavailable nodes and 180TB of daily cross-rack repair traffic; conventional [n, k] Reed–Solomon repair downloads k times the failed node’s data.The reported deployment used an [n = 14, k = 10] Reed–Solomon code, and 98.08% of cases had exactly one missing block per stripe.
  • Survey scope: Regenerating codes minimize repair bandwidth, locally recoverable codes minimize repair degree, and new techniques improve Reed–Solomon repair.The survey organizes these developments alongside related code classes and tradeoffs.
  • Regenerating codes: A regenerating code lets any k nodes recover the file and repairs a failed node by contacting d helpers, downloading β symbols from each, and reconstructing α symbols.Exact repair restores the failed node’s contents, whereas functional repair only preserves the regenerating-code properties.
  • Bounds: Network-coding arguments yield a cut-based upper bound on file size, achievable with linear network coding for sufficiently large finite fields.The survey notes that the resulting functional-repair file-size bound is independent of n.

B. Storage-Repair Bandwidth Tradeoff

The storage-repair bandwidth tradeoff contains multiple optimal storage and repair-bandwidth points, with MSR minimizing storage and MBR minimizing repair bandwidth. The section describes regenerating-code properties, practical repair distinctions, and representative MBR constructions.

  • Different pairs (α, β) can achieve the storage-repair tradeoff equality, representing alternative storage-overhead and normalized-repair-bandwidth optima.The smallest permissible α gives the MSR endpoint, while the smallest permissible β gives the other endpoint.
  • MSR codes use α = B/k and β = α/(d−k+1), whereas MBR codes occupy the opposite endpoint of the tradeoff.MSR codes are identified with the minimum-storage point; the supplied passage introduces MBR as the minimum-bandwidth point.
  • MSR codes are vector MDS codes, while exact-repair variants preserve node contents over time and are generally easier to implement than functional-repair codes.The MDS characterization follows from B = kα and the Singleton-bound argument.
  • A regenerating code supports data collection from k nodes and repairs a failed node by contacting d helpers, downloading β symbols from each, and reconstructing the replacement node.The repair process pools dβ symbols to recreate the failed node's α stored components.
  • MBR repair downloads exactly α symbols, the minimum possible, and RBT repair requires no computation at helper or replacement nodes.An RBT code is therefore also an HBT code, while HBT MBR codes do not exist when d < n−1.
  • The polygonal MBR construction uses a complete graph and an underlying scalar MDS code, but requires O(n^2) field size; the PM construction reduces this to O(n).The PM construction applies for all feasible k ≤ d ≤ n−1 with β = 1.

C. Other Work

The survey reviews MBR and MSR construction advances, including field-size, update-complexity, sub-packetization, and optimal-access questions. It highlights explicit high-rate MSR constructions while identifying unresolved lower bounds and construction goals.

  • MBR codes: MBR research includes constructions with least-possible update complexity within the PM framework and extensions addressing repair and error-correction properties.The PM framework provides MBR codes for feasible parameters with O(n) field-size requirements.
  • MSR codes: MSR codes are attractive because their storage overhead can be made arbitrarily small, they are MDS codes, and they remain challenging to construct.These motivations explain the extensive attention given to MSR codes among regenerating codes.
  • MSR codes: A central MSR construction goal is to combine high rate, low sub-packetization, small field size, arbitrary repair degree, and optimal access.Earlier constructions often trade among these properties or rely on non-explicit MDS proofs.
  • MSR codes: Ye and Barg provide an explicit high-rate optimal-access MSR construction with α = r⌈n/r⌉, field size no larger than r⌈n/r⌉, and d = n−1.Related constructions use pairwise coupling or transform scalar MDS codes into MSR codes.
  • MSR codes: Lower-bound work establishes optimal sub-packetization for several earlier constructions and links minimum-sub-packetization optimal-access codes to coupled-layer structure.The survey also reports constructions achieving the lower bound for selected repair degrees.
  • Open problems: Open problems include finding a tight sub-packetization lower bound with matching constructions and explicit optimal-access MSR codes for every (n, k, d).The survey separately identifies determining the smallest possible MBR field size as an open problem.

B. Constructions of MSR Codes

The survey presents multiple MSR-code constructions, including product-matrix and coupled-layer approaches, and describes how their algebraic structure supports node repair and data collection. These constructions target different parameter regimes and repair properties, including multiple-node and adaptive repair.

  • Product-Matrix Construction: Product-matrix constructions organize message symbols in a matrix and obtain codewords through an encoding matrix, with repair and data collection derived from matrix properties.The described framework uses an encoding matrix Ψ and symmetric message matrices, while linear independence supports recovery.
  • Coupled Layer Code: Coupled-layer codes first layer MDS codewords into an uncoupled data cube, then apply a pairwise-forward transform to obtain the coupled code.The construction is specified for (n, k, d = n−1), with α = st and β = st−1, and can be extended by shortening.
  • Coupled Layer Code: The coupled-layer repair contacts every surviving node, which sends symbols indexed by the failed node’s coordinates; the resulting equations recover the replacement node.The repair equations retain the failed node’s unknown symbols and solve them using a known value κ∗.
  • Ye-Barg Codes: Ye-Barg codes provide explicit MSR constructions for any parameter set (n, k, d) and are also optimal for repairing multiple nodes.Their multiple-node repair achieves the stated lower bound in the centralized repair setting.
  • Adaptive Repair: MSR constructions may support adaptive repair, allowing a failed node to be repaired from any d nodes for d between k and n−1.Each helper sends α/(d−k+1) symbols under the stated adaptive-repair rule.

V. ON THE STORAGE-REPAIR BANDWIDTH TRADEOFF UNDER EXACT REPAIR

Under exact repair, the storage-repair bandwidth tradeoff is more restrictive than the functional-repair tradeoff: interior points are generally unattainable, except near the endpoints and MSR point. Layered constructions and later bounds characterize parts of the achievable region and its separation from functional repair.

  • Non-existence of ER Codes: Exact-repair codes cannot attain interior points of the functional-repair tradeoff, except at the MBR point and in a small region near the MSR point.This non-existence result is stated for codes whose storage and repair-bandwidth values lie on the interior of the functional-repair tradeoff.
  • Proof Strategy: The cut-set bound expresses file size as B ≤ min B_m, while equality requires maximum entropy that conflicts with entropy limits on rows of the repair matrix.This contradiction establishes the stated non-existence result.
  • Scope of the Result: The theorem does not exclude exact-repair codes that approach the functional-repair tradeoff asymptotically as file size B tends to infinity.Thus, the finite-parameter non-existence result leaves asymptotic approaches unresolved.

B. The S-RB Tradeoff for (4, 3, 3)

For (n, k, d) = (4, 3, 3), the exact-repair storage–repair-bandwidth tradeoff is characterized by bounds and constructions, with a strict separation from functional repair away from specified endpoints and regions.

  • Outer bounds: For (n, k, d) = (4, 3, 3), Tian identified an additional inequality that helps characterize the achievable normalized storage–repair-bandwidth region.The inequality 4ᾱ + 3β̄ ≥ 1 was found using ITIP.
  • Achievable interior points: Layering MDS codes produces regenerating codes with file sizes in the interior of the storage–repair-bandwidth tradeoff.The canonical layered construction operates between the MSR and MBR points and can be extended to k < d.
  • Exact versus functional repair: The exact-repair tradeoff remains separated from the functional-repair tradeoff even as file size grows without bound.A positive gap δ < β was established for every (n, k, d).
  • Exact versus functional repair: For k ≥ 3, exact repair is strictly separated from functional repair except at the MSR and MBR endpoints and a region surrounding MSR.The separation follows from entropy bounds on repair-matrix subsets.
  • Characterization results: For n, k = 3, d = n − 1, improved layered codes achieve the best-known outer bound and characterize the exact-repair tradeoff.The same bound characterizes certain interior points when k = 4.
  • Open problems: The exact-repair tradeoff remains open for general (n, k, d) in both linear and nonlinear settings.

VI. VARIATIONS ON THE THEME OF REGENERATING CODES

Regenerating-code research extends repair models, relaxes optimality requirements, and develops constructions that trade repair bandwidth, sub-packetization, and helper-node behavior.

  • Cooperative repair: Cooperative repair lets multiple replacement nodes exchange data during a two-phase repair process.Each new node first downloads from surviving helpers and then exchanges repair data with other new nodes.
  • Cooperative repair: Explicit minimum-bandwidth cooperative regenerating-code constructions exist for all parameters, while minimum-storage constructions are comparatively rare.
  • Cooperative repair: Partial cooperative repair interpolates between independent single-node repair and full cooperative repair through a parameter controlling exchanges among replacement nodes.When s = t it becomes single-loss repair; when s = 1 it becomes cooperative repair.
  • Bandwidth-efficient MDS repair: Piggybacking and related vector MDS constructions reduce repair bandwidth relative to conventional Reed–Solomon repair without requiring MSR sub-packetization.These codes are not MSR but offer repair savings while keeping α small.
  • ϵ-MSR codes: The ϵ-MSR framework permits sub-packetization logarithmic in n at the cost of a multiplicative repair-bandwidth factor of (1 + ϵ).The framework transforms an MSR code into an ϵ-MSR code and is motivated by the large sub-packetization of MSR codes.
  • ϵ-MSR codes: A construction based on a base MSR code and an outer code yields an ϵ-MSR code whose parameter ϵ depends on the outer code's relative distance.The resulting code is obtained through a block-matrix parity-check construction.

C. Fractional Repetition Codes

Fractional repetition codes use replicated symbols and a fixed helper set to simplify repair, while related regenerating-code work addresses security, errors, and locality.

  • FR-code model: Fractional repetition codes associate n nodes, reconstruction threshold k, sub-packetization α, and replication degree ρ with replicated code symbols.Their file size is evaluated through the maximum rank contribution obtainable from admissible node collections.
  • Repair by transfer: An FR code requires one fixed set of d = α helper nodes for repair-by-transfer, and replication ensures that set remains available after up to ρ − 1 node failures.
  • Example: For n = 7, k = 3, d = 3, ρ = 3, the Fano-plane FR code has RC(k) = 6 and supports repair-by-transfer after up to two node failures.
  • Security: Secure regenerating-code models distinguish passive eavesdroppers, active omniscient adversaries, and active limited-knowledge adversaries.The models differ in which nodes can be read and modified.
  • Security: Explicit secure MBR and low-rate MSR constructions achieve the passive-eavesdropper upper bound when ℓ2 = 0, while secure MSR codes provide lower bounds for ℓ2 > 0.
  • Locality: Locally recoverable-code theory provides minimum-distance bounds, and pyramid and Tamo–Barg constructions achieve the relevant Singleton-type bound for broad parameter classes.

B. Constructions

Locality constructions reorganize or evaluate polynomials so that symbols can be recovered from small repair groups while retaining optimal minimum-distance guarantees.

  • Pyramid Code Construction: Pyramid codes reorganize the generator matrix of an [n − (δ − 1), k] MDS code to construct codes with (r, δ) information-symbol locality.The resulting code preserves the MDS minimum-distance value and meets the locality distance bound.
  • The Tamo-Barg Construction: The Tamo–Barg construction provides locally recoverable codes with all-symbol locality by evaluating structured polynomials over partitioned field subsets.A good polynomial is constant on each local group, enabling local recovery.
  • The Tamo-Barg Construction: The Tamo–Barg codes achieve the minimum-distance bound for (r, δ) all-symbol locality with δ = 2.Each local code is supported on one of the partition subsets Ai.
  • The Tamo-Barg Construction: For multiplicative subgroup constructions, g(x) = x^(r + 1) is constant on every coset and can serve as a good polynomial.
  • The Tamo-Barg Construction: Locality constructions achieving the Singleton bound are also available with field size O(n) for selected parameter ranges.

C. Alphabet-Size Dependent Bounds on Code Rate

Alphabet-size-dependent bounds refine dimension, minimum-distance, and asymptotic-rate limits for locally recoverable codes, with shortening as a recurring technique. The literature also supplies constructions approaching or attaining several bounds.

  • Dimension bounds: The dimension bound applies to linear and nonlinear locally recoverable codes and remains valid regardless of the finite-field size.A tighter alphabet-size-aware theorem is also given for nonlinear codes.
  • Dimension bounds: Shortening an LR code produces a shorter code with unchanged minimum distance, allowing classical bounds to be lifted to the original code.The approach was introduced in and subsequently reused in later work.
  • Binary and cyclic codes: Binary LR-code dimension bounds use Hamming-bound and linear-programming techniques, with the tightest known bounds reported for disjoint local-code supports.Comparisons among several dimension bounds appear in Table III.
  • Asymptotic rate: A Gilbert–Varshamov-type lower bound is available for asymptotic LR-code rate, while algebraic-geometric constructions improve it for selected parameter ranges.Some constructions also achieve the displayed lower bound.

D. Small-Alphabet Constructions

Small-alphabet constructions realize locality together with distance or maximal-recoverability properties, often by carefully designing generator or parity-check matrices. These constructions expose trade-offs involving dimension, field size, and explicitness.

  • Binary constructions: Binary constructions achieve several LR dimension bounds, while optimal information- and all-symbol-locality constructions are known for selected minimum distances.The reported cases include dmin = 4, dmin = 6, and larger-distance constructions with restricted locality.
  • Cyclic LR codes: Cyclic LR codes can be built by selecting generator-polynomial zeros that impose both a BCH distance guarantee and periodic local parity checks.The construction uses g(x) = lcm{g1(x), g2(x)} and combines distance and locality constraints.
  • Cyclic LR codes: The example obtains a [15, 8] code with dmin ≥4 and r = 4, while introducing locality reduces code dimension.The dimension loss equals the degree contribution associated with the locality polynomial.
  • Maximal Recoverable codes: Maximal Recoverable codes recover every erasure pattern not ruled out by their prescribed linearity constraints, including locality constraints.Their additional parity checks can require an extension field when the base field is too small.
  • Maximal Recoverable codes: MR-code existence follows from choosing additional parity checks so that determinant products are nonzero, although explicit constructions may require large fields.Linearized-polynomial constructions remain generally exponential in field size.

A. Various Classes of Multiple-Erasure LR Codes

Multiple-erasure LR codes differ in whether erased symbols are recovered sequentially, in parallel, or through multiple recovery sets. These choices trade recovery flexibility and parallelism against storage overhead and helper participation.

  • Sequential and parallel recovery: Sequential-recovery LR codes recover up to t erased symbols in an ordering where each symbol uses at most r unerased helpers that avoid later erasures.The erased symbols are repaired successively using their corresponding recovery relations.
  • Sequential and parallel recovery: Parallel-recovery LR codes require every recovery set to avoid all erased symbols, enabling simultaneous repair but generally increasing storage overhead.A helper symbol may participate in repairing more than one erased symbol.
  • Availability: Availability codes provide t recovery sets for each single erased symbol, and therefore form a subclass of parallel-recovery LR codes.Information-symbol availability restricts the disjoint recovery sets to symbols in an information set, unlike all-symbol availability.
  • Cooperative recovery: Codes with cooperative recovery minimize the average number of unerased symbols contacted per erased symbol rather than enforcing exactly r helpers for every symbol.They are also parallel-recovery codes, but their locality parameter can be substantially larger.
  • Constructions and bounds: Availability-code constructions include product codes, Wang et al.’s parity-check construction, and direct sums of Simplex codes.The Wang construction improves rate over the product code and also has smaller block length.
  • Constructions and bounds: Rate and minimum-distance bounds constrain availability codes, while stricter bounds apply to strict-availability codes as locality increases.Strict availability requires uniform parity-check row and column weights, and the cited bound becomes tighter than an earlier bound as r increases for fixed t.

3) Bounds on Minimum Distance:

Minimum-distance analyses for availability and sequential-recovery LR codes use shortening, generalized Hamming weights, and alphabet-size-dependent bounds. Sequential recovery also has a precisely characterized rate in important cases, with matching constructions and structural constraints.

  • Availability-code distance bounds: The cited availability-code distance bounds include alphabet-size-dependent versions and bounds that are reported as tighter than earlier alternatives.These results apply to information-symbol availability and therefore also to all-symbol availability.
  • Availability-code distance bounds: Shortening-based and minimum-support-weight methods produce upper bounds on minimum distance for availability codes.The minimum-support sequence upper-bounds generalized Hamming weights of the dual code and feeds into the resulting distance bound.
  • Availability-code distance bounds: The calculation of ρ(r, t) for t = 1 was not explicitly stated in, although it is described as well known.The same source also gives an improved upper bound for strict-availability codes.
  • Sequential recovery: The maximum rate of sequential-recovery LR codes is precisely determined for t = 2 and t = 3 by tight upper bounds with matching constructions.The rate bound also proves a conjecture on the maximum achievable rate of sequential-recovery LR codes.
  • Sequential recovery: A binary code attaining the sequential-recovery rate bound must have a sparse staircase parity-check structure and can be based on a tree-like graph with girth at least t + 1.The graph has degree r + 1 for most nodes, with edges representing code symbols and nodes representing parity checks.
  • Sequential recovery: For certain block lengths, rate-bound-achieving constructions correspond to Moore graphs, which exist only for selected t values when r ≥ 2.The listed values are t ∈ {2, 3, 4, 5, 7, 11}.
  • Sequential recovery: The comparison in Fig. 16 suggests that sequential-recovery codes offer a significant rate advantage over availability codes for t = 10.The figure compares the tight sequential-recovery bound with the availability-code upper bound.

3) Achievability Results on Asymptotic Rate:

The survey presents asymptotic-rate bounds for locally recoverable codes, including a GV-type bound and an improved bound in a specific parameter range. It also motivates hierarchical locality as a way to handle different erasure patterns with different repair scopes.

  • Asymptotic-rate bounds: A GV-type bound is derived for codes with (r, δ) locality and fractional minimum distance ∆.The bound is presented in the cited work as an asymptotic-rate result.
  • Asymptotic-rate bounds: A second lower bound improves the GV-type bound when r + δ −1 = √q in some parameter range.This bound is expressed in terms of Rq(r, δ, ∆).
  • Hierarchical locality: Hierarchical locality uses multiple tiers so frequent single erasures can use short local codes while multiple erasures access a larger middle code.The discussion focuses on two tiers: local and middle codes.
  • Hierarchical locality: A hierarchical-locality code can be characterized by local and middle dimensions at most r1 and r2 and minimum distances at least δ1 and δ2.These parameters appear in the stated theorem for a linear code with hierarchical locality.
  • Open problems: The survey identifies maximum minimum distance, field size, rate, and dimension for locality variants as open questions.The listed questions include codes with availability, cooperative locality, and multiple erasures.

IX. LOCALLY REGENERATING CODES

Locally regenerating codes combine locality with regenerating-code mechanisms to reduce both repair bandwidth and repair degree. The survey describes their locality definitions, distance bounds, and constructions using MSR or MBR local codes.

  • Overview: Locally regenerating codes seek simultaneously low repair bandwidth and low repair degree by using regenerating local codes.They were introduced independently in two cited works and can be viewed as locally recoverable codes with regenerating local codes.
  • Locality definitions: Vector-code locality specifies local sets of size at most r + δ −1 whose restricted codes have minimum distance at least δ.The definitions distinguish information-symbol locality, all-symbol locality, and disjoint locality.
  • URA locality: URA locality requires local vector codes to have identical rank profiles, enabling a minimum-distance bound dmin(C) ≤ n − P^(inv)(K) + 1.The rank profile is defined through accumulated ranks of thick-column restrictions.
  • Constructions: Minimum-distance-optimal LRG codes can be constructed with MSR or MBR local codes using the Tamo-Barg construction of optimal scalar locally recoverable codes.An example uses local MBR codes with parameters n = 15, K = 20, dmin = 5, and α = 4.
  • Constructions: For an MSR-local construction, stacking α independent Tamo-Barg layers and applying pairwise forward transforms yields an LRG code with local MSR regeneration.The resulting code is minimum-distance optimal when dTB ≤ 2(nℓ−r + 1).

X. REPAIRING RS CODES

The survey explains how scalar Reed-Solomon repair can be improved by viewing symbols over a subfield and downloading subfield symbols from surviving nodes. It also reviews optimality results, extensions, and practical implementations.

  • Motivation: Conventional repair of an [n, k] scalar MDS code downloads k times the failed node’s stored data, whereas subfield-based repair can reduce bandwidth.For a [16, 8] RS code over F24, the example reduces repair traffic from 32 bits to 15 bits.
  • Subfield repair: A scalar MDS code over Fq can be represented over a subfield B, with the extension degree t serving as its sub-packetization level.The survey notes that traditional RS code lengths correspond to logarithmic sub-packetization in code length, while some bounds require exponential sub-packetization for fixed r.
  • Repair schemes: Linear repair schemes are characterized through subsets of dual-code codewords whose evaluations support reconstruction of each failed coordinate.Trace operations over B convert downloaded subfield symbols into the traces needed to recover the failed Fq symbol.
  • Repair schemes: For suitable GRS parameters, each failed code symbol can be repaired by downloading one B-symbol from each of the other n−1 nodes.The construction is optimal when A = Fq and n −k = pt−1.
  • Extensions and systems: Later work extends RS repair to broader parameters, lower sub-packetization, multiple erasures, and simultaneous optimal bandwidth points.The survey also reviews implementations and evaluations of locally recoverable, MDS-array, and MSR-based systems.
Loading 1806.04437v1…