Repair Traffic in Erasure-Coded Sets and What Regenerating Codes Change

A replicated store rebuilds a lost copy by reading one surviving copy. An erasure-coded store rebuilds a lost fragment by reading k fragments and decoding. That is the price of the space saving, and it is paid on the network, in the background, precisely when the cluster is already degraded. The size of the price is not a detail of implementation; it follows from the code’s structure, and changing it requires changing the code.

The bound on what a rebuild must read

Consider a k-of-n code. A lost fragment is a linear combination of the k data fragments. To compute it, a decoder needs k independent equations, which means k surviving fragments. The lost one is unknown, so any k of the remaining n-1 will do, and the reconstruction is a matrix inversion applied to k fragments of size S/k each, where S is the object size.

The information-theoretic view: the object has S bytes of entropy. Each surviving fragment carries S/k bytes. Reconstructing the lost fragment requires gathering enough information to determine the whole object, which requires at least S bytes, so at least k fragments. Any scheme that reads fewer than k fragments cannot have enough information unless the fragments carry redundancy relative to each other, which is exactly the opening that regenerating codes exploit.

The reading of k fragments to rebuild one is therefore optimal for a code that stores the object as k independent data fragments plus parity, and it is not optimal in general. The distinction is the whole subject of repair-efficient coding: a code whose fragments are not independent can be repaired by reading fewer than S bytes in total.

What the repair actually does

The mechanics of a rebuild in a distributed store: a coordinator identifies the lost fragment’s stripe, contacts the nodes holding the surviving fragments, streams k fragments to a repair target, inverts the appropriate k-by-k submatrix, multiplies, and writes the result. The submatrix depends on which fragments survived, so the inverse cannot be precomputed for all cases unless the number of failure patterns is small; implementations precompute a few common patterns or invert on demand.

The cost has three components, and only one of them is the read volume. The first is the read itself: k × S/k = S bytes for an object of size S, which is k times the size of the fragment being rebuilt. The second is the decode: $O(k^3)$ field operations for a dense matrix inverse, or $O(k^2)$ with structured matrices, plus $O(k \cdot S/k)$ multiplications for the actual reconstruction. The third is the write of the rebuilt fragment, S/k bytes. On a per-byte basis, the read dominates.

The aggregate picture is worse than the per-object picture. A device that fails in a cluster holding T bytes across D devices was carrying roughly T/D bytes, and each of those bytes is rebuilt by reading k bytes spread over k sources, so the repair pulls roughly k × T/D bytes across the network. On a cluster where the failed device held a proportional share, that is k times the failed device’s contents arriving as a burst while the cluster is one device short. This is why repair is rate-limited, and why the rate limit is a durability parameter: the slower the repair, the longer the cluster sits at reduced redundancy, which is the degraded window.

Local parity: paying in space to cut the read set

The simplest structural fix is to break the stripe into groups. A code with a local parity fragment per group computes parity over a small subset of the data fragments, and the global parity over all of them. A single lost data fragment is then recoverable from its group alone, reading only the group’s data fragments plus the local parity, a much smaller set than k.

The cost is space. Local parity fragments occupy capacity that would otherwise be global parity, so the code tolerates fewer simultaneous failures for the same space overhead, or costs more space for the same tolerance. The classic trade is a code that tolerates two simultaneous failures globally but recovers any single failure with a local read: it uses more parity than a plain 2-parity code, and in exchange its single-failure repair reads a fraction of the stripe.

The failure mode of local parity is a second failure inside the same group before the first is repaired. The local parity has already been consumed to repair the first, and the group is now unprotected; recovery of the second failure must fall back to the global parity path, which reads the whole stripe. The probability of that sequence depends on the group size and the repair rate, which is why group size is chosen with the failure rate in mind rather than being as small as possible.

Regenerating codes and the storage-bandwidth trade-off

The read amplification can be stated as arithmetic. For each configuration, the space cost is the ratio of stored fragments to data fragments, and the repair cost is the number of fragments read to rebuild one.

def layout(name, k, m):
    """Space overhead and repair reads for a stripe of k data + m parity."""
    return {
        "layout": name,
        "stored_per_byte": (k + m) / k,
        "reads_per_repaired_fragment": k,      # Reed-Solomon: any k of n
        "failures_tolerated": m,
    }

for name, k, m in [("10-of-14", 10, 4), ("6-of-9", 6, 3), ("3x replication", 1, 2)]:
    # Replication is the k = 1 case: one fragment read, two extra copies.
    print(layout(name, k, m))

The last row shows why the comparison is not apples to apples: replication has no decode step and no matrix inversion, so its repair reads fewer fragments, at three times the space.

The deeper result is that repair bandwidth and storage overhead are not independent knobs but points on a curve. The Dimakis et al. result describes a trade-off between the total stored bytes and the bytes read to repair one failure, parameterised by how many fragments the repairer contacts and how many bytes it downloads from each.

The intuition is that a fragment need not be repaired from k whole fragments; it can be repaired from d fragments, each contributing fewer bytes, provided the code is constructed so that partial information from many fragments is sufficient. The extreme point of the curve minimises repair bandwidth and requires the most storage; the other extreme minimises storage and requires the full k fragments. Reed-Solomon sits at the minimum-storage extreme.

Two families sit at or near the bandwidth extreme. Regenerating codes derived from network coding achieve the bound at the cost of fragments that are not simple linear combinations of the original data, so a read of the object is not a simple decode of k fragments and a partial repair needs carefully constructed coefficients. Locally repairable codes achieve a practical point with simple XOR arithmetic, at the cost of the space overhead described above.

The engineering reason Reed-Solomon remains dominant despite the bound is that its arithmetic is simple, its decode is well understood, and its repair can be done by any node with any k fragments without special structure. The bandwidth-optimal codes trade those properties for a constant-factor saving in repair traffic, and the constant depends on k: for small k, the saving is small, and for large k the construction’s complexity grows. A cluster with k = 10 gains little; one with k = 30 has more to gain and more to lose in complexity.

Rotating the repair target

A cheaper lever than changing the code is changing where the rebuild reads from. A repair that streams k fragments from k distinct nodes places the read load on k nodes, each of which serves one fragment. Spreading the reads over more nodes, reading sub-fragments from more than k sources, reduces the per-node load and the time to complete, without changing the total bytes. This is the difference between minimising bytes and minimising completion time, and a cluster whose bottleneck is per-node bandwidth rather than total bandwidth prefers the latter.

The complementary lever is to place the repair target where the data already is. A rebuild that reads k fragments and writes one should choose the target node such that the reads are spread across racks in proportion to available bandwidth, not such that the target is the first node with free space. This is a placement decision layered over the code, and it is where most of the practical tuning happens, because the code’s read amplification is fixed while the placement of the reads is not.

What repair traffic does to the rest of the cluster

Repair competes with foreground traffic for the same links, and the competition is not neutral: repair is bulk, foreground is latency-sensitive, and a link that is 90 percent utilised by repair has a queue that delays every foreground packet. The standard mitigation is priority or rate limiting at the transport, and the consequence is that repair takes longer than the network could deliver, which lengthens the degraded window and lowers durability.

This is the loop that makes erasure-coded clusters hard to size. Faster repair shortens the window and improves durability but steals bandwidth from the workload; slower repair protects latency and leaves the cluster exposed. The knob is a policy decision that trades a latency target against a durability target, and it has to be chosen with the code’s read amplification in mind, because a code with k = 20 multiplies every repair’s cost by twenty and therefore needs either twenty times the repair bandwidth or twenty times the repair duration for the same durability.

The interaction with quorum acknowledgement closes the loop. A store that acknowledges a write after W replicas have it is vulnerable only during the window between a failure and the completion of repair; a store that acknowledges earlier is vulnerable from the moment of acknowledgement. Repair traffic is the mechanism that closes that window, which makes it a correctness component rather than a maintenance chore.