Winter comes early in the north. The day the granary fills, the caravan must move the town’s whole winter store from this side of the mountain to the town on the far side, before the snows seal the road for good. There is only one road — the Pale Pass, a single thread of track hugging the cliff as it climbs. In deep winter an avalanche needs no warning; one push of the mountain’s hand can bury a wagon, horses and all. Which wagons it takes, no one can say. How many, no one can count.

The town’s inherited method was clumsy and dear: load every kind of grain twice, on two separate wagons, and pray the two wagons carrying the same thing were never buried together. But that meant hauling double the wagons, feeding double the horses, spending double the days on the pass — and the avalanche kept its own counsel. Let it happen to push both of a matched pair off the cliff at once, and that grain was simply gone. Winter rations were counted on fingers; every year the mayor fretted over the waste.

That year a new quartermaster arrived — lean, tall, forever tucking a ledger no one else could read under his arm. He said the grain need not be loaded twice.

He sorted the year’s store into ten “plain wagons,” each carrying something different, together making exactly one whole store — no more, no less. Beside those ten he prepared four “reserve wagons.” What went into a reserve was no copy of any single plain wagon. It was a blend: a scoop drawn from each of the ten plain wagons, mixed according to a recipe in his ledger.

Here was the crux: each of the four reserves used a different recipe. The first took one ladle of everything. The second took one ladle of the first grain, two of the second, three of the third — heavier as it went. The third and fourth followed still other proportions only he could keep straight. A hand asked, puzzled, “Blended together like that — how will you ever tell them apart again?” The quartermaster only said, “The recipes all differ. They come apart.”

The day the avalanche fell, its roar rolled down from the ridge. When the snow-dust settled and the caravan counted, three wagons were short — two plain, one reserve, buried in some drift no digging would find. The hands went white. But the quartermaster opened his ledger, wrote down the grain in the eleven wagons that reached town, fed the numbers into his recipes, and solved backward, step by step. What the surviving plain wagons held was plain enough already; what the two buried plain wagons should have held, and how much, he drew back out of the “blended clues” carried in the surviving reserves. Not an estimate, not a guess — an exact reconstruction of the original.

The hand was still shaken. “And if it had buried three reserves that day? Or three plain wagons side by side?” The quartermaster shook his head. “Any three, all the same. As long as ten wagons reach town — plain or reserve, it makes no difference — I can rebuild the whole store. One fewer and I cannot. Every wagon past ten is margin, freely won.”

At year’s end the mayor did the sum: against the old way of loading everything twice and doubling the whole train, he now carried just four extra reserves — the caravan grew by less than half a tenth — and lost not an ounce of the avalanche it could withstand. Only one cost he couldn’t hide from himself. In the old days, when a wagon was buried, an identical one still sat on the shelf; you fetched it and were done. Now, to replace a buried wagon, the quartermaster had to pass over all ten survivors and solve his recipes from end to end — what he saved on the road, he paid back in labor once the caravan reached town.

— By now you’ve probably recognized it: this is erasure coding.

What it is: Erasure coding is how distributed storage systems — Ceph, HDFS, S3’s erasure-coded storage classes, RAID 6 — trade lower storage overhead for fault tolerance. Original data is split into k data blocks, and an encoding scheme computes m additional parity blocks. A parity block is no copy of any single data block; it is a linear combination of all k data blocks — and each parity block uses different coefficients (typically drawn from a structure like a Vandermonde matrix). That the coefficients all differ is the whole point: it guarantees that the equations corresponding to any k of the n=k+m surviving blocks are linearly independent and invertible, so lost blocks can be reconstructed exactly by solving a linear system. This “any k will do” property is called MDS (Maximum Distance Separable), the core strength of Reed-Solomon codes — no matter which blocks are lost, as long as no more than m are gone, everything recovers. Compared to replication, which stores n full copies at n× overhead, erasure coding needs only (k+m)/k× the storage while tolerating any m simultaneous losses. The price: rebuild must read k surviving blocks and run a decode pass — read amplification and compute cost — which is why hot data often stays replicated and only cold data is converted to erasure coding.

Metaphor mapping

• One run over the pass → one write/encode operation
• The ten plain wagons, together exactly one whole store → the k data shards
• The four reserve wagons of blended grain → the m parity shards, linear combinations of the k data shards
• Each reserve using a different recipe → parity coefficients all differ (Vandermonde structure), making any k equations linearly independent
• The avalanche burying an unpredictable which and how-many → failures at any position, up to m blocks
• Any ten survivors sufficing to rebuild → reconstruction needs only surviving blocks ≥ k (the MDS property)
• Three reserves or three plain wagons, all recoverable alike → any ≤ m lost blocks recover, regardless of which
• Solving the recipes backward for the buried grain → decoding/rebuilding by solving a linear system
• Loading twice (old way) vs. four extra reserves → replication’s n× overhead vs. erasure coding’s (k+m)/k×
• Passing over all ten survivors to replace one wagon → rebuild’s read amplification and compute cost