Sven Erik Matzen

Software Architect | Cloud & Security Expert | AI-enabled Solutions

Eleven Nines: Erasure Coding, Reed-Solomon, and How the Cloud Makes Data Practically Unlosable

🎧 Listen to this article

Cloud Computing · 2026-08-07

EU label: fully AI-generated content Fully AI-generated article (no prior review).

The Hook: The Disk That Is Allowed to Die

There is a number on the product pages of the major cloud storage services that arrives so matter-of-factly you barely read it: 99.999999999 percent. Eleven nines. Amazon states it for S3, and other providers promise something similar. Translated into words it means: if you store ten million objects, you should statistically expect to lose one of them every ten thousand years. Put differently, a single object has an expected lifetime that exceeds the entire duration of human civilization by orders of magnitude.

That is an astonishing claim, because it is made on a foundation that is anything but reliable. Hard drives die. They die constantly, in every data center, every day. A single magnetic disk has an annual failure rate of a few percent; in a storage system with hundreds of thousands of drives, one fails practically every hour. Servers crash, power supplies burn out, whole racks lose power, and occasionally an entire building goes offline. Building a system out of nothing but unreliable components that preserves its data with eleven nines is a bit like trying to build a clockwork that keeps time to the millisecond out of a handful of notoriously unpunctual people.

The naive road there is old and simple: make copies. Store every datum not once but three times, on three different drives in three different racks. If one fails, two remain. This works — and for years it was the de facto standard, for instance in the original Hadoop Distributed File System with its replication factor of three. But it comes at a brutal price: for every useful byte you pay three bytes. Two thirds of your expensive, power-hungry, cooled storage infrastructure holds pure redundancy. At the data volumes of modern cloud providers — S3 now manages hundreds of trillions of objects — that is not a footnote but a cost factor that decides over billions.

There is a more elegant road, and it comes from a 1960 mathematical paper, long before there was cloud storage, hard drives in their present form, or the internet. It is called erasure coding, and its best-known representative is the Reed-Solomon code. Its idea is as counterintuitive as it is beautiful: you can add redundancy without copying data — by computing mathematical "checksums" from the data, constructed so that from any sufficient subset of all the fragments the whole can be reconstructed. Instead of three complete copies, an overhead of maybe fifty, thirty, or even eighteen percent is enough in the end to reach the same or better fault tolerance.

For someone like Sven — Senior AI Engineer with one foot in cloud architecture and one in IT security — erasure coding is a model example of how a deep mathematical result translates directly into hard operating costs and into a firm availability guarantee. This article takes you along the full route: from the question of what "durability" even means, through the astonishingly simple core idea, the mathematics of Reed-Solomon codes and their history, to the real pain point of practice — repair — and the clever codes invented specifically to address it.

Part 1: Two Terms That Are Constantly Confused — Durability and Availability

Before we get to the mechanics, it is worth sharply separating two properties that are perpetually muddled in marketing and everyday conversation, even though they mean entirely different things.

The first is durability. It answers the question: is my datum even still there — today, in ten years, after arbitrarily many hardware failures? Durability concerns permanent, unrecoverable loss. A datum that is lost is gone forever; no waiting brings it back. S3's eleven nines are a durability guarantee.

The second is availability. It answers the question: can I access my datum at this very moment? A datum can be stored perfectly safely and yet be temporarily unreachable — because the server holding it is rebooting, because a network link is disrupted, or because an entire availability zone is briefly offline. Availability is typically stated in fewer nines: four nines (99.99 percent) already means roughly one hour of downtime per year.

The distinction is more than academic. Durability and availability place different demands on the system, and a good storage design optimizes each separately. Erasure coding is primarily a tool for durability — it ensures that data survives failures. That the data is also reachable at all times is a second property, bought with geographic distribution, caching, and fast repair. We will see that precisely at this seam — achieving durability cheaply without ruining availability and repair costs — lie the most interesting engineering decisions.

How does one even arrive at a number like eleven nines? In simplified form: you model the annual failure probability of a single storage fragment, you know how many fragments must fail simultaneously for a datum to be irrecoverably lost, and you know how quickly the system replaces (repairs) a failed fragment before the next one fails. From the interplay of these three quantities — failure rate, number of tolerable simultaneous failures, and repair speed — durability emerges. Erasure coding acts on the second quantity (it dramatically raises the number of tolerable failures per stored byte), and repair speed is the reason the "local" codes covered later were invented.

Part 2: The Core Idea — Redundancy Without a Copy

Let us begin with a picture that requires no higher mathematics and yet hits the core.

Suppose you have two numbers, a and b, and want to store them so as to survive the loss of one arbitrary storage medium. The copy approach: store a and b twice each, on four media. Overhead: 100 percent. The erasure approach: store a on medium 1, b on medium 2, and their sum p = a + b on medium 3. Now three values sit on three media, overhead only 50 percent. If any single medium fails, you can recompute the missing value from the remaining two: if a is missing, then a = p − b; if b is missing, then b = p − a; if p is missing, it does not matter anyway, since a and b are still there. A single "parity symbol" protects two data symbols against one arbitrary failure.

That is, at its core, the principle of RAID-5 and, spelled out, of every erasure code. Generalized it reads: you take k data fragments, compute m parity fragments from them, and store all n = k + m fragments on n different failure domains (drives, servers, racks, data centers). The decisive claim that a good code satisfies is astonishingly strong:

From any k of the n fragments, the original datum can be fully reconstructed.

That is: the system tolerates the simultaneous loss of up to m fragments — no matter which m they are. A code with this property is called an MDS code (Maximum Distance Separable). It is optimal in a precise sense: with m parity fragments you can tolerate at most m failures (this is the so-called Singleton bound), and an MDS code reaches this maximum. Reed-Solomon codes are MDS. Nothing is wasted: each individual parity fragment buys you exactly one more tolerable failure.

Work out what this means. A code with k = 6 data and m = 3 parity fragments (n = 9) has a storage overhead of 9/6 = 1.5 — that is, 50 percent extra — and survives three simultaneous failures. Triple replication has 200 percent overhead and likewise survives "only" two failures (with three lost copies the datum is gone). So the erasure code is simultaneously leaner and more fault-tolerant. Facebook's HDFS uses RS(10,4): ten data, four parity, overhead 1.4, survives four arbitrary failures. Backblaze stores in its "Vaults" with 17+3: seventeen data, three parity, overhead only about 1.18, survives three failures. You can see the tuning knob: the larger you choose k relative to m, the lower the overhead — but the greater the "spread" over which a datum is distributed, with consequences for repair that we will come to.

The obvious question is: how do you compute the parity fragments so that the MDS property is guaranteed to hold — so that truly every subset of k fragments suffices, not just some? The simple sum above is not enough once you want more than one parity fragment (two simple sums would be linearly dependent and would not protect against two failures). This is where the mathematics of Reed and Solomon comes in.

Part 3: The Mathematics of Reed-Solomon Codes

Data as a Polynomial

The original viewpoint of Irving Reed and Gustave Solomon from 1960 is of compelling clarity. Interpret your k data symbols d₀, d₁, …, d_{k-1} as the coefficients of a polynomial of degree k−1:

P(x) = d₀ + d₁·x + d₂·x² + … + d_{k-1}·x^{k-1}

Such a polynomial is uniquely determined by k coefficients — and, here is the twist, equally uniquely by its values at k distinct points. This is the ancient theorem of polynomial interpolation: through k points in general position passes exactly one polynomial of degree k−1. Through two points passes exactly one line (degree 1), through three points exactly one parabola (degree 2), and so on.

Now comes the encoding: evaluate the polynomial not at k but at n distinct points (x = 0, 1, 2, …, n−1). This yields n symbols — the encoded fragments. Because the polynomial has only degree k−1, it is already fully determined by any k of these n values. So if you lose up to m = n−k of the values, you can uniquely interpolate the polynomial from the remaining k and read off from it all the original coefficients — your data. That is exactly the MDS property, and here it follows inevitably from a theorem of algebra: n evaluations of a polynomial of degree k−1, and any k of them reconstruct it. Repair is interpolation.

Why Finite Fields — GF(2⁸)

One detail is what makes the whole thing practical in the first place. If you computed with ordinary real numbers, the evaluations P(x) for large x would grow astronomically large, the rounding errors would become unmanageable, and symbols would not be handy bytes. Reed and Solomon therefore do not compute in the real numbers but in a finite field, also called a Galois field (after the young French mathematician Évariste Galois, who died early).

A finite field is a finite set of elements in which you can add, subtract, multiply, and divide as usual and in which all the familiar arithmetic laws hold — except that the result never leaves the set. For storage systems the field of choice is GF(2⁸), the Galois field with 256 elements. The reason is convenience: every element can be represented as a single byte. A data symbol is a byte, a fragment is a sequence of bytes, and the entire coding is byte-wise arithmetic.

The arithmetic in GF(2⁸) is delightfully alien. Addition is simply the bitwise XOR of two bytes — lightning fast, and every element is its own negative (a + a = 0), so that addition and subtraction coincide. Multiplication is polynomial multiplication of the bit patterns modulo a fixed "primitive" polynomial of degree eight; for GF(2⁸) this is usually x⁸ + x⁴ + x³ + x² + 1 (hexadecimal 0x11D). In practice it is realized via small log/antilog tables or special CPU instructions. All that matters is: in GF(2⁸) all the field axioms hold, so polynomial interpolation works exactly as it did in school — only exactly, without rounding, and with bytes as numbers.

The Vandermonde Matrix and Systematic Codes

In practice the encoding is rarely formulated as polynomial evaluation but as a matrix-vector multiplication, which amounts to the same thing and is more convenient on modern hardware. You pack the k data symbols into a vector d and multiply it by a fixed generator matrix G of size n × k:

c = G · d

If for G you choose a Vandermonde matrix (whose rows are the powers 1, xᵢ, xᵢ², … of the n evaluation points), it is guaranteed that any k rows of G are linearly independent — and that is again the MDS property: from any k of the n encoded values, d can be recovered by solving a linear system of equations (inverting the corresponding k × k submatrix).

One practical trick deserves mention: the systematic code. You choose G (via a simple transformation) so that the first k encoded fragments are identical to the original data and only the remaining m fragments contain "genuine" parity data. The advantage is enormous: as long as all data fragments are present (the normal case), you need not decode anything at all to read — you simply read the data directly. The expensive interpolation only occurs when a data fragment is actually missing and must be reconstructed from the parity fragments. Almost all production systems — from RAID-6 through HDFS to Backblaze's open-source Reed-Solomon library, which uses a systematic Vandermonde construction — work systematically.

Let us summarize the chain: data are the coefficients of a polynomial; encoding is evaluation at n points (or, equivalently, multiplication by a Vandermonde matrix); the computation is byte-wise in the Galois field GF(2⁸); and because any k evaluations uniquely determine a polynomial of degree k−1, any k of n fragments suffice for full recovery. That is the whole magic — a theorem about polynomials, translated into operational reliability.

Part 4: From the Stars to the Cloud — A Brief History

Reed and Solomon published their paper "Polynomial Codes over Certain Finite Fields" in 1960 in the Journal of the Society for Industrial and Applied Mathematics. Their motive was not storage space but error-prone transmission: noisy radio channels in which individual symbols arrive corrupted. Remarkably, their code at first remained something of a mathematical curiosity — an efficient decoding procedure (the Berlekamp-Massey algorithm) was only found years later and was what made practical use possible at all.

After that, Reed-Solomon conquered nearly all of technology almost unnoticed. The Voyager probes beamed their images from the outer solar system to Earth with Reed-Solomon protection starting in the late 1970s. The compact disc and later the DVD owe to it the fact that a scratch on the medium does not destroy the music — the code fills the gap from the redundancy. QR codes contain Reed-Solomon redundancy and therefore remain readable even when part of the pattern is covered or damaged. DSL and digital television rely on it too. The 1960 paper belongs to those rare theoretical works whose applications practically every human being touches dozens of times a day without suspecting it.

Into the storage world the code arrived by a detour. The RAID systems of the 1980s and 1990s began with simple XOR parity (RAID-5, one tolerated drive failure). As disks grew larger and rebuild times longer — and with them the danger that during a repair a second drive dies — RAID-6 introduced a second, independent parity symbol, and for this second symbol you need exactly the Reed-Solomon arithmetic over a Galois field. RAID-6 tolerates two simultaneous failures.

The real leap came with the distributed storage systems of the cloud era. Amazon S3 launched in 2006 and was one of the first large-scale commercial services to rely on redundancy across many machines and locations. Google, Facebook, and Microsoft in the following years built enormous storage systems in which triple replication was increasingly replaced by erasure coding for cost reasons. A visible milestone in the open-source world was HDFS-EC: with Hadoop 3.0 (2017), native Reed-Solomon erasure coding entered the Hadoop ecosystem and cut the storage overhead of "cold" data from 200 percent (triple replication) to roughly 40 to 50 percent at the same or better fault tolerance. The current state of research is documented in a 2025 survey in ACM Transactions on Storage that summarizes the past, present, and future of erasure coding for storage systems.

Part 5: The Sore Point — Repair

Up to here erasure coding sounds like a pure win: same safety, less storage. But there is a price, and it reveals itself not when storing but when repairing. This is precisely where the most exciting engineering of the last fifteen years lies.

Why Repair Is Expensive

With triple replication, repair is trivial. If a copy fails, you simply copy one of the two remaining ones to a new drive — you read exactly as much data as you recover, and from a single source. With a Reed-Solomon code it is different and far more unpleasant: to reconstruct a single lost fragment of an RS(k,m) code, you must read k other fragments in full, transport them over the network to a machine, and compute the interpolation there. With RS(10,4) this means: to replace 1 fragment you read 10. The repair traffic is a multiple of the repaired data volume.

Why is that bad? Because repair is not the exception but the permanent state. In a large cluster something is always failing somewhere, and the system repairs continuously in the background. This "repair traffic" consumes network bandwidth and disk I/O, which are then missing for the actual useful work. At Facebook it was observed that the repair of Reed-Solomon-encoded data made up a substantial share of the cluster-internal network traffic — a real, measurable operating cost item. Moreover, expensive repair lengthens the window in which the system is vulnerable: as long as a fragment is missing, the buffer against the next failure is smaller. Slow repair directly undermines durability.

So there is a fundamental trade-off: large k lowers the storage overhead but makes repair more expensive (you have to read more fragments). This is one of those balancings that recur perpetually in distributed storage systems — you cannot pick storage, repair bandwidth, and fault tolerance all three to taste at once.

Local Reconstruction Codes — Microsoft's Answer

The cleverest way out is to give up the classical MDS property just a little in order to make the typical repair — the failure of a single fragment, by far the most common case — drastically cheaper. That is exactly what Local Reconstruction Codes (LRC) achieve, presented by Cheng Huang and colleagues at Microsoft in a Best-Paper-award-winning paper at USENIX ATC 2012, which forms the basis of the erasure coding layer of Windows Azure Storage.

The idea: alongside the global parity fragments that protect all the data, you introduce additional local parities, each of which secures only a group of the data fragments. Concretely, the LRC(12,2,2) described in the paper splits the twelve data fragments into two groups of six, computes one local parity for each group, plus two global parities — sixteen fragments in total, overhead 16/12 ≈ 1.33. If a single data fragment now fails, you no longer have to reconstruct it from twelve but only from the six fragments of its local group. The repair traffic for the most common case is halved. The price: an LRC is no longer a pure MDS code — it cannot tolerate every conceivable combination of failures in its size class, but is constructed so that it catches all "realistic" failure patterns (every triple combination and the vast majority of quadruple combinations) while conceding the rare, pathological patterns. For operations this is an excellent trade: low storage overhead and cheap repair, bought with a wafer-thin, statistically negligible loss of fault tolerance.

Facebook's "warm" BLOB storage system f4, described at OSDI 2014, pursues a related strategy with Reed-Solomon and geographic distribution to hold rarely changed but not cold data space-efficiently yet fault-tolerantly. Both systems show the same pattern: the pure, mathematically optimal code is seldom what ends up running in production; it gets tailored around the practical constraints — repair bandwidth, data-center topology, access patterns.

Regenerating Codes — the Theoretical Limit

In parallel to engineering practice, information theory has surveyed the repair problem fundamentally. In an influential paper, Alexandros Dimakis and colleagues introduced regenerating codes in 2010. Their starting point was a surprising result: to repair a lost fragment you need not download k whole fragments — it suffices to fetch a smaller piece from more nodes each. Using methods from network coding they derived a fundamental bound for the trade-off between storage per node and repair bandwidth, and identified two extreme operating points: minimum storage (MSR codes, as lean as MDS but with optimized repair) and minimum repair bandwidth (MBR codes). This work founded an entire research field and provides the theoretical foundation against which practical codes such as LRC can be measured. I am of the opinion that precisely this interplay — a deep impossibility/optimality result on the one side, pragmatic, operationally driven constructions on the other — makes erasure coding one of the most instructive fields of applied computer science.

Part 6: The Practice — How Eleven Nines Actually Come About

Let us return to the opening number. How exactly does a real service like S3 achieve its eleven nines? Erasure coding is a necessary but not the only ingredient. Several layers come together.

Geographic distribution. A code whose n fragments all sit in the same rack or even on the same server protects only against drive failures, not against the fire of a building. Large services therefore deliberately spread the fragments across multiple availability zones — physically separated data centers with independent power and cooling. Amazon describes S3 as designed to survive the simultaneous loss of data in two facilities. The erasure code then ensures that even the failure of an entire zone costs only a portion of the fragments — few enough that the remaining ones suffice for reconstruction.

Checksums and scrubbing. Hard drives fail not only loudly (the drive disappears) but also silently: a byte flips without the disk reporting it — so-called silent data corruption or bit rot. Against this the system stores a checksum for each fragment and continuously reads all data in the background, verifies the checksums, and proactively replaces corrupt fragments from the redundancy, long before they are needed. This scrubbing (also anti-entropy or background auditing) is the quiet, permanent labor that prevents unnoticed errors from accumulating until, in an emergency, the redundancy no longer suffices.

Fast, automatic repair. As seen in the previous part, repair speed is a direct factor in the durability calculation. The faster a failed fragment is replaced, the shorter the window of heightened vulnerability. This is why the systems invest so much in cheap (local) repair.

The concrete figures illustrate the gain. Backblaze has publicly documented its approach and even open-sourced a Reed-Solomon library: in a "Vault," each file is split into 17 data fragments, augmented with 3 parity fragments, and distributed over 20 drives in 20 different servers. The system survives the simultaneous failure of any three of these twenty drives, at a storage overhead of only about 18 percent — compared with 200 percent for triple replication. In exactly this number lies the economic reason why erasure coding has conquered the world's large-scale storage: at exabyte holdings, the difference between 1.18-fold and 3-fold physical storage is the difference between one and several data centers full of hard drives.

An honest picture includes the limits. Erasure coding is not free. First, the compute load: encoding and — above all — decoding cost CPU cycles (Galois-field arithmetic), which is why erasure coding is preferably used for "warm" to "cold" data that is rarely written and need not be read in microseconds; hot, latency-critical data often remains replicated. Second, the repair bandwidth already discussed. Third, a disadvantage for small objects: splitting a datum into k fragments only pays off if those fragments have a sensible size; for many tiny objects, management overhead arises, which is why systems often first aggregate small objects into large blocks before encoding. And fourth, the higher read latency in the failure case: if a data fragment is missing, reconstruction is required, which is slower than simply reading an intact copy. As so often in storage engineering, it is a matter of balancing storage space, compute effort, latency, and fault tolerance — you cannot win all corners at once.

The Central Takeaway

The core idea of erasure coding can be captured in one sentence: redundancy need not be a copy. Instead of dumbly multiplying data, you can embed it in a mathematical fabric from which the whole can be recovered from any sufficient subset — and that at a fraction of the storage price. Reed-Solomon codes have done this since 1960 with a single deep principle: data is a polynomial, and a polynomial of degree k−1 is uniquely determined by any k of its values.

But the real, transferable lesson lies in the second half of the story. The mathematically optimal code (pure MDS Reed-Solomon) is seldom the one that ends up in production. Only the confrontation with the practical constraints — how expensive is repair, how is the data center laid out topologically, which failure patterns are realistic and which negligible — leads to the codes that actually carry billions of objects: Local Reconstruction Codes, which trade a bit of theoretical optimality for cheap repair. For Sven's work — whether in cloud architecture or security design — that is the truly valuable stance: to design a system not only against normal operation but explicitly against failure and, one level deeper, against the cost of recovery after failure. The question is never merely "How do I protect the datum?" but "What does it cost me if I have to repair it — and how often will I do that?"

A Question to Reflect On

Erasure coding buys dramatic storage savings with expensive repair, and the cleverest real systems give up a sliver of mathematical optimality to make the most common failure case cheap. Where in your own systems do you implicitly optimize for the rare catastrophe, even though the actual operating costs sit in the frequent small case — and would you, like the LRC inventors, deliberately trade a trace of theoretical cleanliness for a tangible gain in everyday operation?

Cross-References in the Vault

Sources

Note: This article reflects the verifiable, scientifically established state of knowledge. Where personal assessments enter, they are marked with "I am of the opinion that ..."

← All articles