Replication vs erasure coding: an interactive durability simulator

Storage systems protect data against disk failures in two ways. Replication keeps whole copies, usually three, on different disks. Erasure coding splits data into k fragments, computes m parity fragments, and can rebuild everything from any k of the k + m. Reed-Solomon RS(6, 3) survives any three lost disks, one more than three copies, using half the space. What it costs is repair: rebuilding one lost fragment means reading k others.

The playground compares five schemes for 10 petabytes of data. Change how often disks fail and how long a repair takes, and compare raw storage, durability and repair traffic.

How erasure coding works

1. Split each object, or a large block of objects, into k equal data fragments.
2. Encode m parity fragments from them. With one parity fragment it is simply the XOR of the data; Reed-Solomon codes produce any number using arithmetic over a finite field.
3. Spread the k + m fragments across different disks, servers and ideally racks or zones.
4. Read normally from the k data fragments; if some are missing, read any k of the survivors and decode.
5. Repair a lost fragment by reading k others and recomputing it.

Durability per byte of disk

Data is lost only if more than m of a stripe’s disks fail before repairs finish. Three copies tolerate two failures at 3× storage; RS(6, 3) tolerates three at 1.5×; RS(10, 4) tolerates four at 1.4×. With disks failing at 2% a year and a day to repair one, the playground puts three copies at about 9.7 nines of durability per stripe a year and RS(6, 3) at 11.8, for 15 PB of raw disk to store 10 PB instead of 30. Two copies, by contrast, manage under 6 nines: at that scale hundreds of stripes would be lost every year.

Repair time matters as much as the scheme, because a second failure only hurts while the first is being repaired. Stretch repairs from a day to a week and RS(6, 3) drops from 11.8 nines to about 9.2. Systems repair in parallel across many disks so a lost disk is rebuilt in minutes, not the hours it would take to copy it to one replacement.

The cost: repair traffic and degraded reads

Replacing a lost replica means copying one surviving copy: a 16 TB disk needs 16 TB read. Replacing a lost RS(6, 3) fragment means reading six fragments, 96 TB across the network for the same disk; RS(10, 4) reads 160 TB. Reads of data whose fragment is missing are slower too, since they must fetch and decode k others. Newer codes, such as the locally repairable codes used in Azure Storage, add local parity so most repairs read fewer fragments.

Where each is used

• Replication for hot, small or frequently updated data, where fast reads and cheap repairs matter more than space: databases, Kafka, the replicas behind a key-value store.
• Erasure coding for large, mostly cold, write-once data, where space dominates: object stores such as S3 and Azure Blob, HDFS with erasure-coding policies, backups and archives.
• Both: many systems write new data replicated and erasure-code it in the background once it cools.

The idea in code

# the simplest erasure code: one parity fragment, XOR of the data fragments (RAID 5's idea)
def encode(data: bytes, k: int) -> list[bytes]:
    size = -(-len(data) // k)
    frags = [data[i * size:(i + 1) * size].ljust(size, b"\0") for i in range(k)]
    parity = bytes(size)
    for f in frags:
        parity = bytes(a ^ b for a, b in zip(parity, f))
    return frags + [parity]                     # k + 1 fragments on k + 1 disks

def rebuild(frags: list[bytes | None]) -> list[bytes]:
    missing = frags.index(None)                 # survives any one lost fragment
    out = bytes(len(next(f for f in frags if f)))
    for f in frags:
        if f is not None:
            out = bytes(a ^ b for a, b in zip(out, f))
    frags[missing] = out
    return frags

# Reed-Solomon generalises this to m parity fragments surviving any m losses,
# using arithmetic over a finite field instead of plain XOR.

In a system design interview

When you store petabytes, say how it survives and what it costs: “Uploaded videos are written with three replicas so they can be served at once; after a day, a background job erasure-codes them with RS(6, 3) across three zones, which halves the disk bill and still survives losing a zone. Fragments are rebuilt in parallel from many disks, so a failed disk is repaired within an hour.” Expect the follow-ups: what happens to read latency when a fragment is missing, correlated failures, and how small objects are packed into large stripes.

Read the guide to object storage or distributed file systems, or watch a strong candidate design YouTube, where storage is the largest bill.

Questions people ask