Erasure coding vs replication: the actual tradeoff behind cheap storage

Every storage system that has to survive a disk or a node dying makes the same decision at its core: how much extra data do you write, up front, to be able to reconstruct what you lose later. The simplest answer is replication — keep two or three full copies on different machines. It’s easy to reason about and easy to implement, and it’s also the most expensive answer available, because the cost scales linearly with how many failures you want to survive. Three copies means 3x the storage bill, forever, for every byte you store.

Erasure coding answers the same question with a different trade. Instead of duplicating the whole file, it splits the file into pieces, computes extra “parity” pieces from those originals using finite-field math, and stores originals plus parity spread across machines. The guarantee is the same shape — survive some number of failures — but the storage overhead is a fraction of what replication needs. The cost moves from disk to CPU: reconstructing a lost piece means running matrix arithmetic instead of just copying a spare.

The overhead numbers, concretely

A Reed-Solomon scheme is described by two numbers: k, the number of original data chunks, and n, the total number of chunks stored (data plus parity). Any k of the n chunks are enough to reconstruct the whole file, which means the scheme tolerates the loss of any n - k chunks.

SecStore, a small erasure-coded object store, implements this over GF(2^8) in coordinator/erasure_coding.py. Its default topology and the numbers that come out of it:

At k=2, n=3 you tolerate one failure for 1.5x the original size, half the cost of triple replication for the same single-failure guarantee. At k=4, n=7 you tolerate three failures — better than triple replication’s one — for less storage than triple replication costs. That second row is the part that makes erasure coding worth the complexity: it isn’t just cheaper for the same guarantee, it can give you a stronger guarantee for less money than the naive approach gives you for a weaker one.

The catch is real, though. n is capped at 15 and k at 10 in encode() (“For performance, max k=10, max n=15”), and the field itself caps n at 256, since GF(2^8) only has 256 distinct elements and every chunk index needs a unique one for the reconstruction matrix to stay invertible.¹ Replication doesn’t have this ceiling — you can keep adding copies as cheaply, or expensively, as you like. Erasure coding buys its storage efficiency at the cost of a scheme that gets mathematically harder to scale past a modest number of chunks.

Where the CPU cost actually goes

The arithmetic underneath Reed-Solomon runs over GF(2^8), a finite field where addition is XOR and multiplication needs log/exp lookup tables built from a primitive polynomial:

# coordinator/erasure_coding.py
def _precompute_tables(self):
    x = 1
    for i in range(255):
        self.gf_exp[i] = x
        self.gf_log[x] = i
        x <<= 1
        if x & 0x100:
            x ^= 0x11D  # primitive polynomial
    for i in range(255, 512):
        self.gf_exp[i] = self.gf_exp[i - 255]

def gf_mul(self, a, b):
    if a == 0 or b == 0: return 0
    return self.gf_exp[self.gf_log[a] + self.gf_log[b]]

Encoding a file means building a Vandermonde matrix over this field, converting it to systematic form so the top k rows are an identity matrix, and multiplying it against the k data chunks to produce the n - k parity chunks. Decoding, when everything is healthy, is nearly free — if the surviving fragments are exactly the original k data chunks, the code just concatenates them back together:

# coordinator/erasure_coding.py
def decode(self, fragments: dict, k: int, n: int, original_size: int, padding_len: int):
    indices = sorted(fragments.keys())[:k]
    if indices == list(range(k)):
        combined = b"".join([fragments[i] for i in indices])
        return combined[:len(combined) - padding_len]
    # otherwise: invert the submatrix for whichever fragments survived
    ...

The expensive path, inverting a k x k matrix over GF(2^8) via Gaussian elimination, only runs when an actual data chunk is missing and has to be rebuilt from parity. That asymmetry is worth noticing: erasure coding’s CPU cost isn’t paid on every read, it’s paid specifically on the reconstruction path, which only fires when something has already gone wrong. Replication has no equivalent cost on that path at all — a healthy replica is just a healthy replica, no math required — which is the other half of the trade you’re making by choosing parity over copies.

The trade only holds if the pieces you read back are the right ones

Erasure coding’s math has no way to detect that its own inputs are wrong. If one node was offline during a write and comes back later holding a fragment from an older version of the file, and a read combines that stale fragment with fresh ones from other nodes, the reconstruction math still runs and still produces output. It just isn’t the right output, and nothing in the decode step signals that.

Guarding against that isn’t part of the coding scheme; it’s a property the surrounding system has to add on top. SecStore does it by giving every upload a fresh version ID and recording a SHA-256 hash per chunk against that version at write time, then re-verifying each chunk’s hash before it’s allowed into the reconstruction:

# coordinator/main.py — download_file()
for i, r in enumerate(results):
    if isinstance(r, Exception) or r.status_code != 200 or get_hash(r.content) != meta_list[i]["hash"]:
        missing.append(idx_list[i])
    else:
        retrieved[idx_list[i]] = r.content

if len(retrieved) < k:
    raise HTTPException(status_code=500, detail="Not enough valid fragments to reconstruct file.")

A hash mismatch, whatever caused it, routes that chunk into missing instead of retrieved. The decoder only ever sees chunks that verified against the specific version being reconstructed. If fewer than k verified chunks are left, the request fails loudly instead of quietly returning a plausible-looking but wrong file.

The general point holds for any scheme that reconstructs data from partial pieces, not just this one: splitting a file into fragments introduces a failure mode that a whole-copy replica never had, mismatched fragments from different points in time. Any system that gets the storage savings of erasure coding also has to build the bookkeeping that replication got for free.