A disk order that triples everything
A genome sequencing centre keeps the raw output of every run for ten years, because studies come back to old samples. The files are large, written once and rarely read, 1.2 PB in all, and the centre's storage cluster keeps three full copies of each in three different racks. So the archive occupies 3.6 PB of disk, and each year's 300 TB of new runs needs 900 TB of new disks. Three copies buy one thing: any two can be lost and the third still holds the file. The question before the next disk order is whether that has to cost two extra copies of every byte.
Rebuilding a piece from the others
Start small. Split a file into halves A and B, and store a third piece P, computed bit by bit as A XOR B. If A is 0110 and B is 1100, P is 1010. Lose A, and P XOR B gives 0110 back. Three half-size pieces take 1.5 times the original, and any one can be lost. That third piece is parity, the idea RAID 5 uses across the disks of one server.
Erasure coding generalises it. A (k, m) code cuts the data into k data fragments and computes m parity fragments from them, each the size of one data fragment. With a Reed-Solomon code, any k of the k + m fragments rebuild the data, so any m can be lost. Despite the name, it has nothing to do with deleting data (Deleting a person's data: erasure across every copy).
The centre picks a (6, 3) code, the shape of HDFS's default erasure-coding policy. A 600 MB run file becomes six 100 MB data fragments plus three 100 MB parity fragments: 900 MB on disk instead of 1,800 MB.
- Three full copies: 3 times the data on disk, any 2 losses survived.
- A (6, 3) code: (6 + 3) ÷ 6 = 1.5 times the data on disk, any 3 losses survived.
- Four full copies, to survive 3 losses by copying: 4 times.
The archive would shrink from 3.6 PB of disk to 1.8 PB and tolerate one more loss per file. A "loss" here means a fragment of the same file, and how losses arrive is the next problem.
Nine fragments, nine racks
The servers in a rack share a power feed and a switch, so when the rack goes, every fragment in it goes at once. Disks, hosts, racks and zones that fail together are failure domains, and the code sets the placement rule: to survive losing a whole domain, a file may keep at most m fragments in it. The centre has 12 racks and puts one fragment of each file per rack, so any three racks can go dark and every file can still be read.
Its first placement service balanced free space instead, and when three empty racks arrived it put three fragments of some files into rack 11. Then rack 11's switch failed, and the same afternoon a disk in rack 4 died. Files with three fragments in rack 11 and one on that disk had five reachable fragments, one short, and could not be read until the switch was replaced an hour later. Had rack 11's disks been destroyed rather than cut off, those files would be gone. The service now refuses a second fragment of a file in any rack, and the centre accepts what that costs: the new racks fill only as new runs arrive, while the old ones stay fuller for months, because moving old fragments across would compete with repairs for the network.
What a repair reads
A 16 TB disk in rack 2 fails, holding fragments of about 160,000 files (16 TB ÷ 100 MB). With full copies, repair reads 16 TB from surviving copies and writes it elsewhere. With the code there is no second copy of any fragment, so each one is rebuilt:
- The repair service finds, in the stripe map that records where each file's fragments sit, every file that had a fragment on the failed disk.
- For each file, it reads any six of the eight surviving fragments, 600 MB, from six other racks.
- It decodes the missing 100 MB fragment.
- It writes the fragment to a rack holding no fragment of that file and updates the stripe map.
The gateway writes six data and three parity fragments of each file, one per rack, and records where they went. When the disk in rack 2 fails, the repair service reads five data fragments and one parity fragment, decodes the lost one and writes it to rack 10.
Per lost byte, the code reads six where copying reads one: 96 TB across the network for this disk, against 16 TB. If repair may read at 2 GB/s without slowing researchers' reads, the rebuild takes 96,000 GB ÷ 2 GB/s = 48,000 seconds, about 13 hours; copying 16 TB would take about 2.
Those hours are the window of vulnerability: until its own fragment is rebuilt, each affected file has a margin of two losses instead of three, and it gets the third back when that fragment is written, not when the whole disk is done. With three copies, an affected file keeps a margin of one until its copy is remade; the whole disk takes about 2 hours that way, against about 13 with the code. Either way, the longer the repair, the more time a second and third failure have to land on the same files, so repair speed is part of durability.
Reading a file with a fragment missing
Storage systems normally use a code in systematic form: the data fragments are the file's own bytes, in order, and only parity is computed. A healthy read fetches the six data fragments and joins them, with no decoding. While rack 2's fragment is missing, a read of that file is a degraded read: the gateway fetches five data fragments and one parity fragment and decodes the missing 100 MB first. Decoding costs CPU and adds latency, which is fine for a file opened a few times a year.
It is not fine for small, busy files. Each run also has a quality report of a few kilobytes, opened whenever someone browses a study. Cut a 6 KB report into six fragments and every read touches six disks instead of one, every write touches nine, and the stripe map tracks nine locations, all to save one and a half copies of 6 KB. The centre keeps those on three copies. Many systems draw the same line, replicating small or frequently read objects and erasure-coding large, cold ones. Codes also suit data written once: with the Reed-Solomon code used here, changing bytes inside one data fragment means updating the corresponding parts of all three parity fragments too.
What eleven nines assumes
Amazon says S3 is designed for 99.999999999% durability, "eleven nines". Read as a yearly figure, that is about one chance in 100 billion of losing a given object in a year: for the centre's 2 million run files, one file every 50,000 years on average. A figure like that comes from a model of the code and the placement, and it depends on the failure rates, the correlations between failures and the repair times that model assumes. Failures or repair delays outside the model make it optimistic: a batch of disks with the same firmware fault, racks on one power feed, a repair service down for a week. The centre's own nines are only as good as its placement rule and its repair queue.
Durability is not availability: during the rack-11 outage the unreadable files had lost no byte, only access. Nor is it a backup. A delete, or a pipeline that overwrites a run with an empty file, is stored as durably as the original. Copies kept elsewhere, and copies nobody can alter, belong to Backups, high availability & disaster recovery. Copying a database to followers is a different job that shares the word, covered in Replication & read replicas.
Durability you can point to on your Grid
The Object Storage Service Challenge asks for "high durability via replication or erasure coding" and "automatic repair" when nodes fail. Make both visible: a path for large objects that writes k + m fragments, with the code and its overhead written on the storage node, and a replicated path for small ones; how many fragments each failure domain holds; and a repair worker, fed by node-failure events, with the repair read for one lost disk beside it. The simulation measures throughput and latency, not durability, so those numbers are yours to state. For buckets, keys and presigned URLs, the product side of the same store, read Object storage & blobs.