Replication vs erasure coding: same safety, a third the cost

Splitting an immutable object into k data plus m parity fragments lets any k of the k+m fragments rebuild it — tolerating m losses at ~1.2x storage instead of the 3x that plain triple-replication spends to tolerate only 2.

Previously

Now that an object is a sealed, never-changing blob, we can store it durably — and the cheapest safe way is to split it, not to copy it.

Scene 05

Replication vs erasure coding: same safety, a third the cost

Watch
Try it
Predict
Capture

What to watch for

The sealed object feeds the encoder and comes out as 17 data fragments plus 3 small extra fragments computed from them. The lever kills three fragments; the survivors still rebuild the original byte-for-byte. Watch the two readouts: storage overhead and durability.

On the left, the sealed immutable object from the previous scene.
An encoder in the center splits it two ways: as 3 identical whole copies (replication), or as k data fragments plus m parity fragments (erasure coding).
A 'kill fragments' lever greys tiles out one at a time; while at least k survive, a reconstruct animation reads any k of them and rebuilds the original blob.
Two readouts move in opposite directions: storage overhead and durability nines.

Implementation

Highlighted lines are the ones running in the diagram right now.

Encoder.encode

split the sealed object once into k data + m parity

1def encode(blob, k, m):
2    data = split_into(blob, k)        # k data fragments
3    # parity = matrix-multiply over GF(2^8)
4    parity = rs_encode(data, m)        # m parity fragments
5    fragments = data + parity          # k + m total
6    # immutable: computed once, never re-touched
7    for f in fragments:
8        node = pick_failure_domain(f)
9        node.write(f)
10    index.commit(key, locations(fragments))

Storage.read

the GET path — and the degraded read when fragments are dead

1def read(key):
2    locs = index.lookup(key)
3    alive = [f for f in locs if f.up]
4    if len(alive) < k:
5        raise Unrecoverable     # fewer than k survive
6    if all_data_present(alive):
7        return concat(data_fragments(alive))
8    # degraded read: rebuild from ANY k survivors
9    k_subset = alive[:k]
10    return rs_decode(k_subset)  # inverse-matrix solve

Layout.cost

the trade every layout makes: bytes stored vs losses tolerated

1def cost(scheme, k, m):
2    if scheme == 'replicate':
3        copies = m + 1
4        overhead = copies          # 1 byte stored per copy
5        tolerated = copies - 1     # lose all-but-one
6    else:  # erasure
7        overhead = (k + m) / k     # thin parity, not copies
8        tolerated = m              # lose any m of k+m
9    return overhead, tolerated

Sources

Where this sits in Build an S3-style distributed object store

Scene 05 of 12, in the Keep it alive act — Erasure coding, placement, the two planes, and repair.. Split into k+m fragments — any k rebuild it — tolerating m losses at ~1.4× instead of 3× replication.

Up next. Splitting into k+m fragments tolerates m losses only if those losses are independent — but real disks fail together, so where you put the fragments decides whether the math is true.

All 12 scenes in Build an S3-style distributed object store · Every curriculum

Built with Arqly

Every scene in Build an S3-style distributed object store builds on the one before it.All 12 Build an S3-style distributed object store scenes