Replication vs erasure coding

The problem: 2 PB of archives, kept safe, cheaply

Snip's archived click history (09.04 How object storage works) has grown to 2 PB. Disks fail all the time at that scale: with tens of thousands of drives, several die every week. The archive must survive that, and survive losing a whole rack or data centre. Keeping three full copies would mean buying 6 PB of disk to store 2 PB.

Replication: whole copies

Store each piece of data on three machines, in different racks or zones. Lose any two and the third still has everything.

• Overhead: 200% (3 bytes stored per byte of data).
• Reads: any one copy answers, so reads are simple and fast.
• Repair: copy the data from a surviving replica. Cheap and quick.

That's ideal for hot data: frequently read, latency-sensitive, small.

Erasure coding: pieces plus parity

Split the data into k data pieces, compute m parity pieces from them, and store all k + m on different machines. The code is designed so that any k of the k + m pieces rebuild the original. Lose up to m pieces and nothing is lost.

The simplest example is one parity piece made by XOR, as in RAID 5:

export function parity(shards: Buffer[]): Buffer {
  const p = Buffer.alloc(shards[0].length);
  for (const s of shards) for (let i = 0; i < p.length; i++) p[i] ^= s[i];
  return p;
}

/** Any one missing shard is the XOR of all the others, parity included. */
export const rebuildMissing = (survivors: Buffer[]) => parity(survivors);

Tested with three 8-byte shards ("Snip cli", "ck histo", "ry 2026!"): XOR of the parity and two survivors rebuilt the missing middle shard exactly. XOR tolerates one loss; Reed-Solomon codes generalise it to any m.

RS(10, 4) survives more failures than triple replication while storing less than half as many bytes. For 2 PB of archive, that's 2.8 PB of disk instead of 6.

What erasure coding costs

• Repair is expensive. Rebuilding one lost piece means reading k others across the network, and computing. With RS(10, 4), losing one 1 GB piece costs 10 GB of reads. Replication's repair reads 1 GB.
• Reads can be slower. A whole-object read gathers k pieces from k machines; if one is slow or gone, the reader must fetch a parity piece and decode (03.12 Tail latency and why p99 matters).
• Small objects don't split well. Splitting a 5 KB object into 14 pieces is silly, so systems erasure-code large stripes or volumes made of many objects (09.04 How object storage works).
• Placement matters. All k + m pieces must be on independent failure domains, or one rack failure takes out several.

Hot, warm, cold

Most large storage systems use both: replicate hot data, and erasure-code data once it cools down. Facebook moved older, less-requested photos and videos from Haystack (replicated) to f4, an erasure-coded system for "warm" data, cutting the effective copies stored per byte from 3.6 to 2.8, or 2.1 with a cross-datacenter scheme.

Snip does the same with click history: the current month lives in the replicated LSM cluster (09.03 The LSM write and read path), three copies; monthly archives go to object storage, which erasure-codes them.

Recap

Interview questions