PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Coding for Distributed Storage Systems

Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, Kannan Ramchandran

arXiv:0803.0632v1cs.NIcs.ITmath.IT

TL;DR

Repairing an erasure-coded fragment by reconstructing the full object can require transferring the whole object, motivating a way to reduce repair traffic. The paper introduces regenerating codes and characterizes the storage–repair-bandwidth tradeoff; for the (4,2) example, 1.5Mb is the information-theoretic minimum.

  • Problem

    Repairing a coded fragment by reconstructing the whole object takes M bits of traffic to create a fragment of size M/k, raising the question of whether that repair overhead can be reduced.

    Source: §I · pp. 1–2

  • Method

    The paper introduces regenerating codes, which let surviving nodes send functions of stored data, and uses information-flow graphs to characterize feasible storage and repair-bandwidth tradeoffs.

    Source: §I · p. 2, A. Information Flow Graph · p. 4

  • Results

    For the (4,2) example, 1.5Mb is the information-theoretic minimum repair bandwidth, and codes can achieve every point on the optimal storage–bandwidth tradeoff.

    Source: §I · p. 2

  • Takeaways & Limitations

    Allowing each storage node slightly more than M/k bits can significantly reduce repair bandwidth.

    Source: §I · p. 2

    Practical implementation issues remain, including deterministic designs over small finite fields, coefficient-storage overhead, and node dynamics.

    Source: §V · p. 9

Abstract

from arXiv · show

Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a node failure is for a new node to download subsets of data stored at a number of surviving nodes, reconstruct a lost coded block using the downloaded data, and store it at the new node. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to download \emph{functions} of the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.

I. INTRODUCTION

Distributed storage relies on redundancy, but repairing coded fragments can require transferring the entire data object. The paper introduces regenerating codes that reduce repair traffic and characterizes the tradeoff between storage and repair bandwidth.

A. Erasure codes

  • Erasure coding stores n coded pieces from k file pieces so any k pieces recover the file, offering better storage efficiency than replication.The paper focuses on adding repair bandwidth to the redundancy–reliability tradeoff.Source: §I · p. 1, A. Erasure codes · p. 3

I. INTRODUCTION

  • Repairing a coded fragment by reconstructing the whole object requires M bits of traffic to create a fragment of size M/k.The paper challenges the belief that this k-factor repair overhead is unavoidable.Source: §I · pp. 1–2
  • Regenerating codes let surviving nodes send functions of their stored data, enabling repair without communicating the whole object.For the (4,2) example, 1.5Mb is the information-theoretic minimum repair bandwidth.Source: §I · p. 2, Figure 2 · p. 2, B. Network Coding · p. 3
  • The paper characterizes an optimal tradeoff between storage and repair bandwidth and gives codes that achieve every point on it.The tradeoff is characterized using maximum-flow arguments on an information flow graph.Source: §I · p. 2
  • Minimum-storage regenerating codes preserve MDS storage, while minimum-bandwidth regenerating codes minimize repair bandwidth.Allowing each node slightly more than M/k bits can significantly reduce repair bandwidth.Source: §I · p. 2

B. Network Coding

  • Network coding allows intermediate nodes to encode received data, while this paper adds repair bandwidth and ongoing maintenance to that network-coding picture.Regenerating-code nodes form smaller parity packets that carry enough novel information to generate a replacement fragment without reconstructing the whole object.Source: B. Network Coding · p. 3

C. Distributed storage systems

Prior work compared erasure coding with replication and proposed a Hybrid repair strategy; the analysis models storage, repair, and reconstruction through an evolving information flow graph.

C. Distributed storage systems

  • Rodrigues and Liskov’s Hybrid strategy uses one replica-holding node to repair coded fragments, with added architectural complexity and a possible delay if that replica is lost.Prior studies found erasure codes’ storage benefits could be outweighed by bandwidth costs in high-churn settings; their conclusions varied with churn.Source: C. Distributed storage systems · p. 3

III. ANALYSIS

  • The information flow graph represents data communication, limited node storage, and paths to data collectors as a directed graph.Storage is represented by input and output nodes connected by an edge whose capacity equals the data stored at that node.Source: §III · p. 3, A. Information Flow Graph · p. 3

A. Information Flow Graph

  • As nodes fail and join, the graph changes: newcomers download from active storage nodes, and data collectors connect to active nodes to reconstruct the file.The capacity of each newcomer’s incoming edge represents the amount downloaded from its corresponding active node.Source: A. Information Flow Graph · pp. 3–4
  • In the illustrated example, the minimum cut is 1 + 2β, so each of three helpers must send at least 0.5 Mb for 2 Mb reconstruction.A cut’s capacity is the sum of the capacities of its edges; the minimum cut is the smallest such separating cut.Source: A. Information Flow Graph · p. 4

B. Storage-Bandwidth Tradeoff

The paper characterizes feasible storage and repair-bandwidth pairs using information-flow graphs, then examines the minimum-storage and minimum-bandwidth endpoints of the tradeoff.

B. Storage-Bandwidth Tradeoff

  • For the (4, 2, 3, 1 Mb, 1.5 Mb) example, the point is feasible, while standard erasure coding requires 2 Mb of repair bandwidth.The optimal tradeoff curves are shown for k=5, n=10 and k=10, n=15, with d=n−1.Source: B. Storage-Bandwidth Tradeoff · p. 4, Figure 4 · p. 5
  • A tuple is feasible when a code exists for its storage and repair bandwidth; the threshold α* is achievable or exceeded, while lower storage is impossible.Linear network codes suffice at every feasible point.Source: B. Storage-Bandwidth Tradeoff · p. 4
  • Minimum cuts across the information-flow graphs characterize repair feasibility, and network-coding results establish achievability when the graphs have sufficient connectivity.The analysis minimizes storage subject to a sufficient flow constraint.Source: B. Storage-Bandwidth Tradeoff · p. 4

C. Special Cases: Minimum-Storage Regenerating (MSR) Codes and Minimum-Bandwidth Regenerating (MBR) Codes

  • MSR codes retain MDS reliability–redundancy performance while improving repair bandwidth, which can fall further when newcomers contact more than k nodes.For (n, k)=(14, 7), contacting all 13 other nodes requires downloading 13M/49 to generate a fragment of size M/7.Source: C. Special Cases: Minimum-Storage… · p. 6
  • MBR codes minimize repair bandwidth, and their storage size α equals the total downloaded bandwidth γ, avoiding bandwidth expansion.The paper identifies MSR and MBR codes with the minimum-storage and minimum-bandwidth endpoints, respectively.Source: C. Special Cases: Minimum-Storage… · pp. 4, 6

IV. EVALUATION

The evaluation compares regenerating codes with other redundancy strategies using trace-informed analytical modeling. It focuses on file availability, distinguishing transient outages from permanent data loss.

IV. EVALUATION

  • The evaluation follows the methodology of, using an analytical model with parameters estimated from real-system node-availability traces.The model is intended to capture average maintenance bandwidth and file availability, while simplifying real storage systems.Source: §IV · p. 6

A. Node dynamics and objectives

  • The evaluation considers reliability, bandwidth, and disk space, and distinguishes permanent failures that lose stored data from transient failures that preserve it.A node is available when its data can be retrieved across the network.Source: §IV · p. 6, A. Node dynamics and objectives · p. 6
  • The reported reliability measure is file unavailability—the fraction of time a file cannot be reconstructed from currently available nodes—not durability.Durability concerns whether data has been lost to permanent failures, even if it might become available later.Source: A. Node dynamics and objectives · p. 6

B. Model

The model estimates average maintenance bandwidth and file availability under assumptions about permanent failures and transient outages. It compares replication, erasure-code strategies, and regenerating-code variants.

B. Model

  • The simplified model follows with minor changes, counts bandwidth costs from permanent failures only, and computes probabilities directly rather than using binomial approximations.It is intended to enable direct comparison with and precise calculation of rare-event probabilities.Source: B. Model · p. 6
  • The model assumes a fraction f of data-holding nodes fail permanently per unit time and independent node availability probability a at any given time.Permanent failures trigger repair transfers; transient failures make stored data temporarily unavailable without losing it.Source: B. Model · p. 6
  • Across schemes, expected repair bandwidth generally equals f times storage replaced; replication, ideal erasure coding, and Hybrid coding are compared at matched redundancy.The Hybrid strategy combines one full replica with erasure-coded packets; its unavailability depends on both the replica and the coded packets being unavailable.Source: B. Model · p. 6
  • For MSR codes, δMSR measures transfer overhead relative to fragment size; the stated maintenance transfer is f·R·M·δMSR bytes per unit time.The cited expression assumes the favorable case in which a newcomer connects to d=n−1 nodes.Source: B. Model · pp. 6–7
  • For MBR codes, expected maintenance transfer is f·M·n·δMBR bytes per unit time, with δMBR defined as transfer relative to ideal fragment size.The total stored amount is M·n·δMBR bytes.Source: B. Model · p. 7

C. Estimating f and a

The evaluation estimates node failure and availability rates from four system traces, then compares storage strategies across availability and maintenance bandwidth. At four nines of availability, the reported MSR and MBR comparisons with Hybrid show different bandwidth and storage tradeoffs.

C. Estimating f and a

  • The authors estimate failure rate f and availability a from four varied traces, using a one-day timeout to identify permanent failures and averaging availability among nodes not so classified.The traces cover PlanetLab, Microsoft PCs, Skype superpeers, and Gnutella peers.Source: C. Estimating f and a · p. 7
  • The estimates may be biased by timeout handling, node selection, and omitted transfer time, though the authors consider relative strategy comparisons unlikely to be affected.Source: C. Estimating f and a · p. 7

D. Quantitative results

  • At k = 14, the relative performance of the strategies is similar to that at k = 7.Source: D. Quantitative results · p. 7
  • At unavailability 0.0001, MSR uses about 44% more bandwidth and 28% less storage than Hybrid, while MBR uses about 3.7% less of both.Both also have somewhat better unavailability than Hybrid (.000059 vs. 0.00018).Source: D. Quantitative results · p. 7
  • MSR maintenance bandwidth initially decreases as redundancy R rises, because reduced overhead more than offsets additional data to maintain at small R.Source: D. Quantitative results · p. 7
  • The minimizing n is one of the two integers closest to the optimum, whose redundancy factor approaches 2 as k→∞.Source: D. Quantitative results · p. 8

E. Qualitative comparison

Regenerating codes offer storage and repair-bandwidth tradeoffs with scheme-specific architectural and read costs; workload affects which design is useful, while practical implementation issues remain.

E. Qualitative comparison

  • Against Hybrid, minimum-storage regenerating codes offer slightly lower maintenance bandwidth and storage, with a simpler architecture requiring only one redundancy type.Hybrid’s replica node must read the whole object and compute encoded fragments, which can make disk I/O a repair bottleneck.Source: 1) Comparison with Hybrid · p. 8

1) Comparison with Hybrid:

  • MBR requires n−1 nodes rather than Hybrid’s one to construct a new packet or reconstruct the file; fewer contacts increase maintenance bandwidth.Source: 1) Comparison with Hybrid · p. 8
  • Against Hybrid, MSR uses somewhat less storage but more maintenance bandwidth; newcomers and data collectors must connect to multiple nodes.Source: 1) Comparison with Hybrid · p. 9
  • MBR increases total read traffic by roughly 30% at R=2, k=7 or 13% at R=4, potentially unacceptable for frequent reads and small k.Source: 1) Comparison with Hybrid · p. 9
  • Regenerating codes address the architectural complexity Rodrigues et al. identified for erasure coding, which may broaden coding’s applicability.Their other concern was minimal maintenance-bandwidth improvement in more stable environments.Source: 1) Comparison with Hybrid · p. 9

V. CONCLUSIONS

  • The flow-graph framework characterizes the storage–repair-bandwidth tradeoff, and regenerating codes can achieve points on its feasible region.The conclusion notes that practical implementation issues remain, including finite-field designs, CPU and disk I/O effects, and packet integrity and security.Source: §V · p. 9
  • For large, infrequently read archival files, MBR’s symmetric design may beat Hybrid; where storage matters, MSR codes may be useful.The conclusion also notes that high reliability can favor MBR over simple replication.Source: §V · p. 9

VI. APPENDIX

The appendix uses information-flow graph cuts to characterize recoverability and show when codes can attain the cut bound. It then invokes network-coding results to establish code existence under a bounded number of failures and repairs.

VI. APPENDIX

  • A data collector cannot reconstruct the file when its source-to-collector minimum cut is smaller than M.The proof uses a cut-set bound to show that the collector retains nonzero uncertainty about the file.Source: §VI · p. 10
  • When every collector's minimum cut is at least M, a linear network code over a sufficiently large finite field lets all collectors recover the file.Randomized network coding can make recovery probability arbitrarily high by increasing the field size.Source: §VI · p. 10
  • Enumerating all failure-and-repair patterns and collectors yields a valid code achieving the necessary cut bound when the number of failures and repairs is bounded.A separate paper gives deterministic constructions tolerating infinitely many failures and repairs under a bounded active-node population.Source: §VI · p. 11
  • A graph G* matches the cut bound with equality when k newcomers each connect to the preceding d nodes and the collector connects to the last k newcomers.This construction is used to prove the bound is tight.Source: §VI · p. 11
  • When the stated condition is satisfied, every graph in G(n, k, d, α, β) has enough flow from the source to each data collector.There exists an information flow graph G* in G(n, k, d, α, β) where this bound is matched with equality.Source: §VI · p. 11
  • For fixed repair bandwidth γ, the minimum storage threshold α*(d, γ) is piecewise linear, and increasing d improves the storage–repair bandwidth tradeoff.The optimization fixes d and γ and minimizes α.Source: §VI · p. 12
Loading 0803.0632v1…