Source-linked AI summary
Simple Regenerating Codes: Network Coding for Cloud Storage
Dimitris S. Papailiopoulos, Jianqiang Luo, Alexandros G. Dimakis, Cheng Huang, Jin Li
TL;DR
Distributed storage needs codes that tolerate failures while making exact repair simple, inexpensive, and storage-efficient. The paper introduces Simple Regenerating Codes that combine MDS codes with XOR parities and evaluates them against replication and Reed-Solomon codes. SRCs provide constant-node repair, high rates, and competitive cloud-storage performance, while trading off degraded-read performance in one reported comparison.
Problem
Existing practical efficiently repairable constructions had data rates bounded by 1/2, motivating codes that combine high rates with simple exact repair.
Method
SRCs combine outer MDS codes for fault tolerance with simple locally decodable parities and structured chunk placement for exact repair.
Results
SRCs require a constant number of repair nodes independent of (n, k), and a (50, 46, 2)-SRC uses approximately half the storage of 3-way replication with approximately 60% worse degraded-read performance.
Takeaways & Limitations
SRCs add feasible points to the distributed-storage tradeoff space by combining good performance, higher data reliability, and lower storage cost than 3-way replication.
Abstract
from arXiv · showhide
Network codes designed specifically for distributed storage systems have the potential to provide dramatically higher storage efficiency for the same availability. One main challenge in the design of such codes is the exact repair problem: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. One of the main open problems in this emerging area has been the design of simple coding schemes that allow exact and low cost repair of failed nodes and have high data rates. In particular, all prior known explicit constructions have data rates bounded by 1/2. In this paper we introduce the first family of distributed storage codes that have simple look-up repair and can achieve arbitrarily high rates. Our constructions are very simple to implement and perform exact repair by simple XORing of packets. We experimentally evaluate the proposed codes in a realistic cloud storage simulator and show significant benefits in both performance and reliability compared to replication and standard Reed-Solomon codes.
I. INTRODUCTION
Distributed storage codes must preserve encoded data after failures while balancing reliability, storage efficiency, and repair cost. SRCs address this challenge with simple exact repair, high rates, and a construction that combines MDS coding with XOR-based parities.
- Motivation: Large-scale storage systems require regular failure recovery and tolerance of multiple failures without the storage cost of many replicas.Erasure coding provides high failure tolerance with lower storage overhead than replication.
- Repair challenge: Exact repair requires a newcomer to access existing nodes and reproduce the failed node’s encoded contents while preserving redundancy.The repair process uses in-network combinations of coded packets.
- Prior limitations: No prior practical efficiently repairable constructions achieved data rates above 1/2, while cloud storage may be constrained by disk-I/O overhead from contacting repair nodes.Repair bandwidth is well studied, but the paper emphasizes the number of disks involved in rebuilding.
- Contribution: SRCs provide simple look-up repair, arbitrarily high rates, exact repair through packet combinations, small disk-I/O, and minimal repair computation.The construction is designed for simple implementation while retaining fault tolerance.
- Code properties: An (n, k, f)-SRC tolerates n−k erasures, stores a fraction (f+1)/(fk) of the file per node, and repairs a lost node using d = 2f disk accesses.Repairing one coded chunk accesses f disks and reads one chunk from each; the stated rate is R = f/(f+1).
- Example: For the (4, 2, 2)-SRC, two nodes recover the file through outer MDS codes, while lost chunks are reconstructed by downloading and XORing two other chunks.The parity chunks are not needed for reconstruction, whereas the outer MDS codes are not used during repair.
- Trade-off: The separation of MDS-based fault tolerance from parity-based repair makes the construction suboptimal, but its storage loss is asymptotically negligible and its repair-bandwidth overhead logarithmic.The codes combine outer MDS codes and simple parities, assigning different roles to reliability and repair.
A. The f = 2 Case: degree 2 parities
The degree-2 SRC construction independently MDS-encodes two file parts, forms aligned XOR parities, and circularly places the resulting chunks across storage nodes. This placement enables exact repair while preserving erasure tolerance.
- Encoding: For f = 2, the file is split into two parts and each part is independently encoded with an (n, k) MDS code.The two encoded vectors, x and y, each have length n.
- Parity formation: The construction forms each parity chunk as s_l = x_l + y_l, producing 3n chunks from the two n-chunk coded vectors and their parity vector.Each parity combines coded chunks with the same index.
- Chunk placement: Each storage node stores one x chunk, one y chunk, and one parity chunk whose subscripts are all different.The distinct-subscript requirement supports the repair-oriented placement.
- Chunk placement: Circular placement assigns the 3n chunks across n nodes, with modular index addition defining the arrangement.The resulting coded array is the general placement scheme for the construction.
- Placement property: For n ≥ 2, the three chunks stored at each node do not share a subscript.This property follows from the circular placement.
C. Erasure Resiliency and Effective Coding Rate
The (n, k, 2)-SRC preserves tolerance of any n−k erasures while achieving a rate approaching 2/3 for fixed erasure tolerance. Generalizing chunk multiplicity and parity degree yields arbitrarily high rates.
- Erasure resiliency: The (n, k, 2)-SRC tolerates any combination of n−k erasures.This reliability is inherited from the underlying outer MDS codes, which allow file recovery from any k nodes.
- Effective coding rate: The (n, k, 2)-SRC has effective coding rate bounded by 2/3.The rate is computed as useful file information divided by total stored data.
- Effective coding rate: For fixed erasure tolerance n−k = m, the SRC rate can approach 2/3.The construction reaches this limit asymptotically as the system size grows for fixed m.
- Generalization: Increasing chunks per node and parity degree from 2 to f generalizes the construction to arbitrarily high rates.These generalized constructions are developed in the subsequent section.
D. Repairing Lost Chunks
The SRC repairs lost chunks and nodes using a small, fixed set of disk accesses, chunk reads, and downloads. Its circular chunk placement enables simple exact repair, with failure only possible when n ≤ 2.
- Repair mechanism: Circular chunk placement enables repair using a small, fixed neighborhood of disks.Each lost chunk is reconstructed from two available chunks, including parity sums that are combined by addition or subtraction.
- Repairing lost chunks: A lost chunk in the (n, k, 2)-SRC costs 2 repair-bandwidth units, 2 chunk reads, and 2 disk accesses.The cost is stated as a fraction 1/k of the file size for repair bandwidth and chunk reads.
- Repairing lost nodes: A lost node costs 6 repair-bandwidth units and 6 chunk reads, with disk accesses bounded by min(n−1, 4).The accessed disks for node i are {i ⊖2, i ⊖1, i ⊕1, i ⊕2}.
- Repair boundary: The repair construction fails only when n ≤ 2.This condition concerns retrieval of one of the packets used to regenerate lost information.
- Generalization: The general (n, k, f)-SRC extends the construction while retaining tolerance of any n−k node erasures.Its coding rate is given as f/(f+1) · k/n.
III. SRC: THE GENERAL CONSTRUCTION
The general SRC combines parallel outer MDS pre-codes with circularly placed parity chunks, providing erasure resilience, high rate, and simple repair. Its coding rate is a fraction f/(f+1) of the corresponding MDS code rate and approaches the MDS rate as f increases.
- Construction: The (n, k, f)-SRC uses f parallel identical outer MDS pre-codes and one parity vector generated from the f encoded parts.The resulting chunks are circularly placed across n storage nodes.
- Construction: Each storage node holds f coded chunks and one parity-sum chunk, yielding (f+1)n chunks placed across n nodes.The placement avoids repeated subscripts within a node, enabling repair.
- Erasure resilience and rate: The (n, k, f)-SRC tolerates any combination of n−k node erasures and has coding rate (f/(f+1))·(k/n).Any k nodes contain enough distinct coded chunks for reconstruction through the outer MDS codes.
- Erasure resilience and rate: SRCs attain an f/(f+1) fraction of the coding rate of an (n, k) MDS code while retaining simple, low-cost node repair.The construction separates fault tolerance and repair responsibilities between outer MDS codes and simple parities.
- Rate comparison: As f increases, the effective coding rate of a (20, 16, f)-SRC approaches that of a (20, 16) MDS code.Both codes tolerate four failures in the comparison.
B. Repairing Lost Elements
SRC repair reconstructs lost chunks through simple look-up access and additions, with costs controlled by f rather than necessarily by k. Single-node repair requires 2f disk accesses when 2f≤n−1, otherwise n−1.
- Lost-chunk repair: A single chunk repair costs M/k in repair bandwidth, chunk reads, and disk accesses when each node stores α_SRC=(f+1)M/k.The repair reconstructs a parity-sum chunk by accessing the f nodes containing the required coded chunks.
- Lost-chunk repair: To repair a lost chunk, the newcomer accesses f specified nodes and downloads chunks with the same subscript as the lost chunk.The repair sets are determined by the circular placement of chunks.
- Comparison with regenerating codes: SRC disk accesses are a design parameter set by choosing f and can be orders less than k.The comparison considers MSR and MBR codes connecting to d={k,n−1} remaining nodes.
C. Asymptotics of the SRC and links to MDS codes
The asymptotic analysis examines SRCs with f growing logarithmically in k and compares their repair costs with MSR codes. SRCs incur only logarithmic repair overhead while retaining asymptotically negligible coding-rate loss and XOR-based repair.
- Asymptotic setting: The asymptotic comparison fixes the coding rate R=k/n while allowing the parity degree f to grow as a function of k.The supplied analysis introduces this regime before selecting f=log(k).
- Asymptotic repair: With f=log(k), repairing one SRC node costs γ_SRC=(log(k)+1)M/k and uses d_SRC=2log(k) disk accesses.This choice makes the repair degree grow logarithmically with k.
- Links to MDS codes: Compared with repair-optimal MSR codes, SRCs with f=log(k) have asymptotically negligible coding-rate loss and logarithmic repair-bandwidth overhead.They simultaneously retain simple XOR repair and logarithmic-in-k disk accesses.
IV. SIMULATIONS
The paper evaluates SRCs in a realistic cloud storage simulator, testing f=2 and comparing the codes with replication and Reed–Solomon codes.
- Simulation setup: SRCs were evaluated in a realistic cloud storage simulator against replication and Reed–Solomon codes.The experiments used f=2, which provides the most efficient repair but relatively high storage overhead.
- Scope: The evaluation leaves other choices of f and their associated tradeoffs for future work.The paper specifically identifies the tradeoff between repair efficiency and storage overhead as unexplored experimentally.
A. Simulator Introduction
The simulator models a Hadoop-like cloud storage architecture with machines, fixed-size chunks, redundancy sets, and detailed repair processes. It is designed to capture component and chunk-level behavior during data recovery.
- Cloud Storage Architecture: The modeled architecture uses a master server and many data storage servers, similar to GFS and Hadoop.The system targets large-scale storage where frequent failures make fault tolerance and availability critical.
- Data Organization: Data is partitioned into fixed-size chunks, grouped into redundancy sets, and protected through replication or erasure coding.The modeled chunk size is 64MB, and lost chunks can be reconstructed from surviving chunks.
- Simulation Model: A discrete-event simulator models machines, chunks, and detailed repair processes to analyze data-recovery performance.The simulator tracks each repair process rather than only aggregate system behavior.
B. Simulator Validation
The simulator was calibrated against real Hadoop repair behavior and then used to compare SRC with replication and Reed-Solomon codes. SRC reduced storage cost while retaining substantially better repair behavior than Reed-Solomon, with degraded-read performance below replication.
- Simulator Validation: The simulator was validated against a 16-machine Hadoop experiment connected by a 1Gb/s network using measured chunk repair times.The validation compared repair-time distributions from real Hadoop and simulation.
- Simulator Validation: The simulated and real Hadoop repair results match very well, particularly below the 95th percentile.The authors conclude that the simulator can precisely simulate Hadoop’s data-repair process.
- Storage Cost Analysis: At (50, 46), SRC has normalized storage cost 0.54 versus 0.36 for Reed-Solomon, while requiring approximately half the storage of 3-way replication.SRC storage cost can decrease further with larger f, but repair becomes slower.
- Repair Performance: SRC repair throughput remains constant across (n, k), whereas Reed-Solomon performance worsens as n grows.Replication has the best repair performance, SRC follows, and Reed-Solomon performs worst because repair accesses more data.
- Degraded Read Performance: SRC degraded-read performance is higher than repair performance for the same (n, k), but reaches approximately 60% of 3-way replication’s performance.The degraded-read performance trend is similar to the repair-performance trend for all three codes.
F. Data Reliability Analysis
The reliability analysis uses a disk-failure Markov model and compares SRC with replication and Reed-Solomon codes. SRC remains substantially more reliable, including at high rates, while the analysis notes assumptions about independent disk failures and unverified correlated-failure benefits.
- Reliability Model: The reliability model assumes failures occur only at disks and are uncorrelated.The authors expect correlated failures to further benefit SRC because its data is spread across more nodes, but leave this for future verification.
- Reliability Model: The analysis assumes a 5-year disk MTTF, 1PB of stored data, and repair times of 15 minutes for replication and 30 minutes for SRC.For Reed-Solomon codes, repair time depends on k.
- Reliability Results: SRCs are several orders of magnitude more reliable than 3-way replication even for the high-rate (50, 46) configuration.The analysis attributes this reliability benefit to SRC’s high repair speed.
- Code Properties: SRC combines MDS codes with locally decodable parities to provide high fault tolerance, asymptotically optimal storage, and efficient repair.The number of contacted nodes can be made a small constant independent of n and k.
- System-Level Comparison: For (50, 46, 2), SRC uses approximately half the storage of 3-way replication, has approximately 60% worse degraded-read performance, and provides approximately four more zeros of data reliability.The comparison identifies a storage, performance, and reliability trade-off at high code rates.
- Conclusion: The authors conclude that SRCs add feasible points to the distributed-storage trade-off space at lower storage cost and higher data reliability than 3-way replication.They describe the investigation as preliminary and suggest SRCs may be attractive for real cloud storage systems.