S3-like object store

Why are we paying for 123 terabytes to keep 41?

Two years after the first recipe video (lesson 5.4), cooks upload about 13.7 TB a year, originals and renditions together. The data team wants three years kept, for training new cooks and for disputes about what a dish should look like: 41.1 TB.

Most of it is cold. A video is watched for a few weeks, then almost never. So the old videos move off the CDN-backed bucket into a cheaper archive the business runs itself: storage servers rented in three separate halls of a data centre, fifteen disks in all, five per hall.

The archive is configured the way lesson 3.1 taught: every video stored three times, one copy per hall, so a whole hall can burn down and nothing is lost.

Now read the hardware order the way an accountant would. The archive holds 41.1 TB. The disks ordered come to 123.3 TB. Two thirds of that disk holds spare copies of videos that almost nobody watches. The spare copies are what lets the archive survive losing a hall, so deleting them is not an option. Does protecting the data have to cost three times its size?

Think about how you might protect a recipe book without copying it three times: keep a little extra information from which any lost part can be worked out again. Data can be stored the same way. It survives more failures than three copies do, using half the disk. It has a different cost, and an archive has to decide whether it can afford that cost.

Parts and sums: the erasure code

Erasure code

A way to store an object as k data fragments plus m parity fragments so that any k of the k + m pieces are enough to rebuild it. It survives m lost pieces and uses (k + m) / k times the space.

For example: k = 6, m = 3: nine fragments of one sixth each. Disk used: 9 / 6 = 1.5 times the data, against 3 times for three copies; it survives any three losses, against two for three copies.

The simplest erasure code needs no algebra. With one parity fragment (m = 1), the parity is the XOR of the k data fragments, byte by byte. Because x XOR x = 0, XORing the parity with every surviving fragment leaves exactly the missing one. That is RAID 5. Reed-Solomon generalises it to m independent parities, so m simultaneous losses can be repaired.

Which videos get coded?

The disk column argues for coding everything. The repair column, read by whoever has to restore a video when a cook asks for it, argues against.

Each case is right for different data, so let the age of a video decide: what is new and hot is copied, what is old and cold is coded. That is also the split f4 makes at Facebook, where Haystack keeps hot photos and f4 holds “warm” ones at a lower replication factor.

What to remember

1. An erasure code stores k data and m parity fragments; any k rebuild the object. Disk is (k + m) / k of the data, and any m losses are survived.
2. XOR is the one-parity case; Reed-Solomon gives m independent parities.
3. The cost moves to repair and degraded reads: rebuilding one fragment reads k. Small objects must be packed into volumes first.
4. Place fragments so no failure domain (disk, machine, hall) holds more than m of them, or the code’s promise does not hold.

Keep full copies of data that is read often, erasure-code data that is rarely read, and plan for the extra reads that repair needs.

In the real world

The simulator places fragments by counting and rebuilds with XOR. Real systems do Reed-Solomon arithmetic in a finite field (often with hardware support), spread fragments over racks and zones with explicit rules, rebuild one lost disk from many disks in parallel so repair finishes in hours, and scrub data in the background to find silent corruption before a second failure makes it fatal.

The numbers in real deployments follow the same arithmetic you used: Backblaze’s 17 + 3 costs 3 / 17 = 17.6% extra; f4’s (10,4) is 1.4 times the data before its cross-datacenter XOR.