Source-linked AI summary
Fractional Repetition Codes for Repair in Distributed Storage Systems
Salim El Rouayheb, Kannan Ramchandran
TL;DR
Distributed storage systems need reliable repair despite node failures, but existing regenerating-code repairs can impose substantial survivor-node read and computation costs. The paper constructs exact MBR codes by concatenating an outer MDS code with an inner Fractional Repetition code, using regular graphs and Steiner systems. These constructions provide uncoded repair resilient to multiple failures and achieve storage capacity under random-access repair, while the table-based model motivates FR capacity with derived bounds.
Problem
Distributed storage systems require reliable repair despite unreliable nodes, while existing repair processes can require survivors to read all stored packets and compute linear combinations.
Method
The paper concatenates an outer MDS code with an inner Fractional Repetition code, constructing FR codes from regular graphs and Steiner systems.
Results
The constructed codes guarantee uncoded repair for multiple failures and achieve storage capacity under random-access repair.
Takeaways & Limitations
The table-based repair model yields the Fractional Repetition capacity concept, for which the paper derives bounds.
Abstract
from arXiv · showhide
We introduce a new class of exact Minimum-Bandwidth Regenerating (MBR) codes for distributed storage systems, characterized by a low-complexity uncoded repair process that can tolerate multiple node failures. These codes consist of the concatenation of two components: an outer MDS code followed by an inner repetition code. We refer to the inner code as a Fractional Repetition code since it consists of splitting the data of each node into several packets and storing multiple replicas of each on different nodes in the system. Our model for repair is table-based, and thus, differs from the random access model adopted in the literature. We present constructions of Fractional Repetition codes based on regular graphs and Steiner systems for a large set of system parameters. The resulting codes are guaranteed to achieve the storage capacity for random access repair. The considered model motivates a new definition of capacity for distributed storage systems, that we call Fractional Repetition capacity. We provide upper bounds on this capacity while a precise expression remains an open problem.
I. INTRODUCTION
Distributed storage systems combine redundancy with repair to preserve reliable access despite node failures. The paper proposes exact MBR codes with low-complexity uncoded repair, built from outer MDS and inner Fractional Repetition codes.
- Motivation: Distributed storage systems use redundancy and repair to preserve data reliability despite unreliable nodes and unexpected departures.Failures may arise from data-center hardware problems or peer-to-peer churning.
- System model: An MDS distributed storage system lets users recover the file from any k of n nodes, while repair contacts d survivor nodes.A replacement node stores data that maintains the MDS property.
- Related work: Prior regenerating-code work identified a storage-capacity and repair-bandwidth tradeoff, including minimum-bandwidth and minimum-storage regimes.The original model focused on functional repair, which preserves the MDS property without requiring the lost data to be reproduced exactly.
- Contribution: The paper constructs exact MBR codes whose replacement nodes recover lost data by downloading and storing one packet from each of d survivors.Uncoded repair requires each survivor to read only the needed packet and forward it without processing.
- Contribution: The construction concatenates an outer MDS code with an inner repetition code, called a Fractional Repetition code, that supports uncoded repair under multiple failures.Each node’s data is split into d packets, with each packet replicated across multiple system nodes.
- Constructions: Regular graphs provide FR-code constructions for single failures, while Steiner systems provide constructions for multiple failures.The paper also studies FR capacity motivated by its table-based repair model.
II. MOTIVATION AND MODEL
The model prioritizes minimum repair bandwidth and exact, uncoded repair because storage-node read/write bandwidth is a practical bottleneck. It defines the system parameters and contrasts the proposed repair requirements with functional repair and existing high-complexity processes.
- System parameters: A DSS is specified by (n, k, d), where users contact k of n nodes and repair contacts d survivor nodes, with d ≥ k.The system operates with k < n.
- Minimum-bandwidth regime: The minimum-bandwidth regime minimizes the total data downloaded during repair, so a replacement node downloads only the amount it stores.The focus reflects practical asymmetry in which bandwidth is more expensive than storage.
- Repair model: Symmetric repair requires a replacement node to download and store one equal-sized packet from each of its d contacted nodes.Under this model, d also equals the node storage capacity measured in packets.
- Repair requirements: Functional repair preserves the MDS property but may regenerate data different from the failed node’s data.Exact repair instead reproduces an exact copy and can support systematic data, lower protocol overhead, and data security.
- Uncoded repair: Existing constructions often require each survivor to read all d stored packets and compute a linear combination before forwarding one packet.The paper calls the lower-complexity alternative uncoded repair: reading one packet and forwarding it without processing.
III. EXAMPLES
The examples combine an outer MDS code with an inner Fractional Repetition code to achieve MBR capacity alongside exact, uncoded repair. The examples also show the trade-off between flexible repair and designs that support smaller repair degree or multiple failures.
- Example 1: The (5, 3, 4) construction concatenates a (10, 9) parity-check MDS code with a repetition code and achieves CMBR = 9.Each of 10 coded packets is placed across 5 nodes, with each packet replicated twice.
- Example 1: Any three nodes recover 9 distinct coded packets, allowing the outer MDS code to recover the 9-packet file.Any two nodes share exactly one packet, so contacting three nodes yields 9 distinct packets out of 10.
- Example 1: The first construction supports exact uncoded repair for one failure but requires d = n−1, so every survivor must be contacted.Its uncoded repair process also cannot tolerate multiple simultaneous failures.
- Example 2: The (7, 3, 3) construction uses an outer (7, 6) MDS code and a repetition code with each packet replicated on three nodes, tolerating up to two failures.The repetition pattern is derived from the Fano plane, whose seven lines correspond to storage nodes.
- Example 2: The Fano-plane construction achieves CMBR(7, 3, 3) = 6 because the worst-case choice of three nodes provides 6 distinct packets.Other three-node choices can provide all 7 packets, but the minimum determines system capacity.
- FR-code design: Fractional Repetition codes split each node’s content into d packets and place ρ replicas of every packet on different nodes.The examples use repetition degrees ρ = 2 and ρ = 3; repair in the second example follows a failure-dependent table rather than arbitrary survivor selection.
IV. FRACTIONAL REPETITION CODES WITH ρ = 2
For repetition degree ρ = 2, regular graphs yield Fractional Repetition codes whose uncoded repair tolerates one failure and achieves MBR capacity across feasible n and d.
- FR codes concatenate an outer MDS code with an inner repetition code, where each packet is replicated across distinct nodes.The repetition degree ρ determines the number of replicas, while the outer MDS code supports file recovery.
- Regular-graph constructions with ρ = 2 are universally good and achieve CMBR for all feasible n and d while supporting uncoded repair for a single failure.Each graph edge corresponds to one packet replica pair, so incident-edge storage gives repetition degree 2.
- FR code rate is the maximum number of distinct packets guaranteed to any user contacting k nodes.
- A universally good FR code has rate at least the DSS MBR capacity for every feasible k.
- For ρ = 2, nd must be even, and this condition is sufficient for constructing an FR code using a d-regular graph.The graph has n vertices, nd/2 indexed edges, and each node stores packets corresponding to its incident edges.
V. FRACTIONAL REPETITION CODES WITH ρ > 2
Because practical systems may require repetition degree above two, the paper develops Steiner-system-based FR constructions for ρ > 2, including the two parameterizations illustrated for S(2,3,9).
- Regular-graph constructions cannot generalize to the practically relevant case ρ > 2, motivating Steiner-system-based FR codes.
- Applying two constructions to S(2,3,9) yields either ρ = 4 with (n, d) = (12, 3) or ρ = 3 with (n, d) = (9, 4).
A. Steiner Systems
Steiner systems provide balanced combinatorial structures in which every t-point subset lies in exactly one block; the paper focuses on t = 2 to limit packet overlap.
- A Steiner system S(t, α, v) consists of α-element blocks over v points, with every t-point subset contained in exactly one block.
- In every Steiner system, each point belongs to the same number r of blocks.
- For S(2, α, v), focusing on t = 2 helps ensure that nodes share no more than one packet, supporting capacity achievability.
- The Fano plane is S(2, 3, 7), with r = 3 blocks through each point and b = 7 blocks overall.
- For sufficiently large v, S(2, α, v) exists when the stated congruence conditions on v, r, and α hold.
B. Code Constructions
The paper constructs universally good Fractional Repetition codes from Steiner systems, including two complementary constructions with different parameter relationships and repair degrees.
- Construction 2: Steiner-system Construction 2 uses blocks as FR-code nodes, yielding repetition degree ρ = (v−1)/(α−1), θ = v, n = v(v−1)/(α(α−1)), and d = α.Its pairwise block-intersection property limits shared packets, enabling capacity achievement for every k = 1, . . . , d.
- Construction 2: Construction 2 produces universally good FR codes that achieve CMBR for all k = 1, . . . , d.
- Construction 3: Construction 2 does not expose n and ρ directly in the Steiner-system parameters, motivating Construction 3 with d equal to a fraction of the survivor nodes.
- Construction 3: Construction 3 reverses the roles of blocks and points, making blocks packets and points storage nodes, so every two nodes share exactly one packet.
- Construction 3: Construction 3 also yields universally good FR codes.
- Existence conditions: Steiner-system existence is not guaranteed for arbitrary desired parameters, but for α = 2, . . . , 5 it is characterized by the stated integrality conditions.For repetition degrees ρ = 2, . . . , 5, Transpose codes exist if and only if n − 1 ≡ 0 mod ρ − 1 and n(n − 1) ≡ 0 mod ρ(ρ − 1).
VI. CAPACITY UNDER EXACT UNCODED REPAIR
The paper defines Fractional Repetition capacity for exact uncoded repair and shows that some FR codes exceed the conventional MBR capacity, while deriving upper bounds on the new capacity.
- Capacity exceeding CMBR: A repetition-degree-2 FR code for the (6, 3, 3) DSS gives R_C(3) = 7 > C_MBR = 6.Every user contacting three nodes observes at least seven distinct packets.
- Definition: Fractional Repetition capacity C_FR is the maximum file size a DSS with parameters (n, k, d) can store under exact and uncoded repair.The definition treats packets as atomic information units and requires nd ≡ 0 mod ρ for the FR code's existence condition.
- Upper bounds: The first upper bound on C_FR follows from averaging packet-set cardinalities across uniformly selected collections of k nodes.The observed packet set U_I is formed by the union of packets stored on the contacted nodes.
- Upper bounds: For the (7, 3, 3) DSS, the first bound gives R(3, 3) ≤ floor(6.2) = 6, making the Example 2 FR code optimal.
- Limitations: The averaging upper bound becomes loose for large n and k because FR capacity is defined as a worst-case measure.
- Upper bounds: A second upper bound defines C_FR through a recursively defined function g(k), and is tighter than the previous bound.The proof of this lemma is omitted from the paper because of space restrictions.
VII. CONCLUSION AND OPEN PROBLEMS
The paper introduces Fractional Repetition codes for exact MBR repair, combining replicated packets with an outer MDS code and supporting repair after multiple failures. It provides graph- and design-based constructions with random-access storage-capacity guarantees, while leaving broader existence and capacity questions open.
- VII. CONCLUSION AND OPEN PROBLEMS: An FR code splits each node’s data into packets and stores ρ replicas of every packet on distinct nodes.The outer MDS code ensures file recovery when a user contacts a sufficient number of storage nodes.
- VII. CONCLUSION AND OPEN PROBLEMS: FR codes guarantee uncoded repair for up to ρ −1 failures.This is the repair tolerance provided by repetition degree ρ.
- VII. CONCLUSION AND OPEN PROBLEMS: Regular-graph constructions cover all feasible single-failure parameters, while Steiner-system constructions address multiple failures.The paper also constructs Transpose codes in which repair contacts only a fraction of surviving nodes.
- VII. CONCLUSION AND OPEN PROBLEMS: All obtained codes achieve the storage capacity under random-access repair.The repair model is table-based, motivating the separate notion of Fractional Repetition capacity and corresponding bounds.
- VII. CONCLUSION AND OPEN PROBLEMS: For ρ > 2, FR-code existence is unknown for system parameters not covered by the constructions.A general expression for FR capacity and codes achieving it also remain open problems.