Reed-Solomon Codes: The k-of-n Arithmetic and Its Repair Cost

Replication spends capacity to buy survival. An erasure code spends computation to buy the same survival for less capacity, and the price is paid later, in the repair path. The Reed-Solomon family is the oldest and most widely used construction for this trade, and its arithmetic is small enough to state completely: a polynomial over a finite field, evaluated at n points, of which any k suffice to recover it.

The object becomes a polynomial

Split an object into k fragments of equal size. Treat the fragments as coefficients of a polynomial of degree $k-1$ over a finite field, and evaluate that polynomial at n distinct points. The n evaluations are the encoded fragments. The original k coefficients are recoverable from any k of the evaluations by polynomial interpolation, because a degree $k-1$ polynomial is uniquely determined by its values at k points. The other n-k fragments carry no information the k do not, but they make the object survivable: any k of the n fragments reconstruct it, so the code tolerates the loss of any m = n-k fragments.

The field matters. The coefficients are fragments, which are byte strings, and a fragment is not a field element unless the field’s elements are the size of a fragment. Two choices are common. A field of $2^8$ elements treats each fragment as a sequence of bytes and encodes byte position by byte position, which is what RAID-6 implementations do for the two-parity case. A field of $2^{16}$ or wider treats a fragment as a sequence of 16-bit or 32-bit words, and the arithmetic operates on words. Larger fields allow longer codes but cost more per operation; the standard practical choice for storage is $2^8$ with byte-wise operation, because it maps onto ordinary memory and can be vectorised.

Arithmetic in $GF(2^8)$ is not the integer arithmetic of the same name. Addition is XOR. Multiplication is carry-less polynomial multiplication modulo an irreducible polynomial of degree 8. The AES polynomial $x^8 + x^4 + x^3 + x + 1$, written 0x11b, is the usual choice, with 0x11d used in RAID implementations. Every non-zero element has a multiplicative inverse, which is what makes the encoding matrix invertible for any k rows.

# GF(2^8) multiply via log/antilog tables; generator 2, reducing polynomial 0x11d.
EXP = [0] * 512
LOG = [0] * 256
x = 1
for i in range(255):
    EXP[i] = x
    LOG[x] = i
    x <<= 1
    if x & 0x100:
        x ^= 0x11d
for i in range(255, 512):
    EXP[i] = EXP[i - 255]

def gmul(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return EXP[LOG[a] + LOG[b]]   # log domain turns multiply into add

Encoding is then a matrix multiplication over the field: the k data fragments form a vector, an n-by-k matrix produces the n encoded fragments, and the first k rows of the matrix are the identity so that the data fragments appear unchanged among the outputs. This is the systematic form, and it matters for the read path: a healthy read of the object needs only the k data fragments, with no decoding at all.

Reconstruction is a matrix inversion

Recovery takes any k of the n fragments, extracts the corresponding k rows of the encoding matrix, inverts the resulting k-by-k matrix, and multiplies. If the k fragments are the data fragments themselves, the matrix is the identity and no work is done, which is why the common case of a healthy read costs nothing beyond reading k fragments. If some data fragments are missing, the matrix is a mix of identity rows and parity rows, and the inversion is real work: $O(k^3)$ field operations for a dense inversion, or $O(k^2)$ for the structured matrices used by systematic codes when the structure is exploited.

The inverse must exist for every possible choice of k surviving fragments, and that is the property the encoding matrix has to guarantee. A Vandermonde matrix, with rows of consecutive powers of distinct evaluation points, has the property that every square submatrix is invertible, which is exactly the requirement. The naive Vandermonde construction is not systematic, so implementations convert it by row operations into a systematic form, and the conversion must preserve the “every square submatrix invertible” property; a careless conversion produces a matrix that is invertible in the healthy case and singular for some specific loss pattern, which fails only when a particular pair of fragments is lost. Plank’s tutorial and its correction document the subtlety, which is worth knowing because the bug is invisible until the exact failure pattern occurs.

The overhead arithmetic

A 10-of-14 code stores 1.4 bytes per byte of data, against 3 for triple replication. Its space overhead is 40 percent against 200 percent, and its failure tolerance is four fragment losses against two. On those two axes it dominates replication for any workload where the repair path can afford the reads.

The repair path is where the cost appears. Rebuilding one lost fragment under replication means reading one surviving copy: 1x. Under a 10-of-14 code, the straightforward reconstruction reads ten fragments to rebuild one: 10x. Since a cluster’s background traffic is dominated by repair after failures and by scrubbing, this amplification is the operational cost of the space saving, and it is why erasure-coded clusters are typically designed with more cross-node bandwidth per stored byte than replicated ones.

The read path has a subtler cost. A healthy read touches k fragments rather than one, so the per-object latency is the maximum of k node latencies rather than one node’s, and the tail of the latency distribution widens with k. A code with k = 10 has a read latency determined by the slowest of ten nodes; the probability that at least one of ten nodes is slow is roughly ten times the probability that one is. This is the argument for keeping k small in latency-sensitive deployments and for reading only as many fragments as the object’s size requires. A small object stored with k = 10 reads ten small fragments, each of which carries per-request overhead.

Partial writes and the read-modify-write penalty

A full-stripe write computes all n fragments from k data fragments in one pass, which is cheap. A partial write, updating a few bytes inside one fragment, cannot do that, because the parity depends on the whole data vector. The two strategies are the classic ones from RAID. Read-modify-write reads the old data fragment and the old parity fragments, applies the delta, and writes the new data and parity: three fragments touched for a two-parity code, but a small read and a small write. Reconstruct- write reads the other k-1 data fragments, recomputes the parity from scratch, and writes the new data plus all parity: k+m fragments touched, mostly reads.

Which is cheaper depends on the size of the update relative to the fragment. A 4 KiB update inside a 1 MiB fragment makes read-modify-write obviously better, because it touches 4 KiB plus parity deltas rather than 10 MiB of reconstruction. An update that spans most of a fragment makes reconstruction competitive and avoids the read-before-write dependency. The pathological case for read-modify-write is a small random overwrite on a code with many parity fragments, because each parity fragment needs its own read and write, and the parity updates are serialised against the same data fragment’s lock.

The mitigation used by most object stores is to avoid partial writes entirely: objects are immutable once written, and an update is a new object with a new identifier. That removes the read-modify-write path from the design and leaves only the full-stripe case, which is why erasure-coded object stores tend to be append-only at the storage layer even when the interface above them allows overwrites.

Where the code stops helping

An erasure code protects against fragment loss, not against correlated loss that removes more than m fragments at once, and not against a fault that corrupts rather than removes. A code cannot detect which fragment is wrong; it can only reconstruct from a set it believes is correct. If a fragment is silently corrupted and the checksum layer does not catch it, decoding produces a wrong object with no error indication. Every practical erasure-coded store therefore pairs the code with per-fragment checksums, and treats a checksum failure as a fragment loss, which converts a corruption into an erasure, a strictly easier problem, since the position of an erasure is known and the position of an error is not. That pairing is the reason checksum verification during repair is part of the code’s specification rather than an independent feature.

The second limit is the field’s code length. A $GF(2^8)$ code has at most 255 evaluation points, so k + m cannot exceed 255 with byte-sized elements. Practical systems stay far below that, typically with k between 4 and 20 and m between 2 and 6, because the repair amplification grows with k while the space saving grows only like (k+m)/k. The marginal gain from raising k flattens quickly: going from 10-of-14 to 20-of-26 reduces overhead from 1.4 to 1.3 but doubles the repair read amplification.

The third limit is that the code treats every fragment as equally important and every loss as equally likely, which is false. A fragment on a host that is about to be decommissioned is more likely to be lost than one on a healthy host, and a scheme that accounts for that, biasing placement or choosing which parity to compute first, is a placement policy question layered above the code, not a property of it.