The idea: store more points of the same polynomial

Disks fail. Keeping three full copies of every file survives two failures, but it triples the storage. Erasure coding does better: it splits the data into k data shards, computes n − k parity shards, and puts the n shards on n different disks. Any k of them are enough to get everything back. Reed–Solomon is the classic way to build such a code. The page uses k = 3 and n = 5: 3 data shards, 2 parity shards, any 2 disks may fail.

The data values 2, 5 and 10 are the points (1, 2), (2, 5) and (3, 10). They lie on P(x) = x² + 1 mod 11, which also gives the parity points (4, 6) and (5, 4). The five shards D1, D2, D3, P1, P2 go to five disks; any three of them give P(x) back.
Data and parity are five points of one parabola, so any three of them pin it down again.

Data as points on a polynomial

Read the 3 data values as points: d1 at x = 1, d2 at x = 2, d3 at x = 3. Two points fix a line; three points fix a parabola, a polynomial P(x) = a + bx + cx2 of degree at most 2. In general k points fix exactly one polynomial of degree ≤ k − 1.

The parity shards are just more points of that same polynomial: P(4) and P(5). For the data 2, 5, 10 the polynomial is P(x) = x2 + 1, so P(4) = 17 and P(5) = 26. In mod-11 arithmetic these become 6 and 4 (Demo: encode 3 data shards into 5). Data 1, 2, 3 lie on the line P(x) = x, and the parity simply continues it with 4 and 5 (Demo: data on a line, parity continues it). The data shards keep their values unchanged; a code like this is called systematic, so reading needs no decoding while all disks are healthy.

Why mod a prime

With ordinary numbers, P(5) could be huge, or a fraction, and would not fit in the same space as a data value. So all the arithmetic is done mod 11: add, subtract or multiply as usual, then keep the remainder after dividing by 11. Every result is a whole number from 0 to 10, the same size as the data.

Division also works, because 11 is prime. Dividing by b means multiplying by its inverse b−1, the number with b·b−1 ≡ 1. For example 6−1 = 2, since 6·2 = 12 ≡ 1. Every number from 1 to 10 has one (the table sits in the canvas; the Euclidean algorithm finds inverses for big moduli). Numbers mod a prime form a finite field, GF(11), and polynomials there behave just like the ones from school: k points still fix exactly one of degree < k. Real systems use the field GF(28) with 256 elements, so that each symbol is one byte.

Recovery by Lagrange interpolation

When disks fail, take any 3 surviving shards. Their points fix P again, and evaluating P at a lost x gives the lost value. The direct recipe is Lagrange interpolation. For each known point (xi, yi) build a weight

Li(t) = Πj≠i (t − xj) / (xi − xj)

It is 1 at its own point and 0 at the others. Then P(t) = Σ yi·Li(t). If D2 is lost, the survivors (1, 2), (3, 10), (4, 6) give the weights 4, 1, 7 at t = 2, and 2·4 + 10·1 + 6·7 = 60 ≡ 5: D2 is back (Demo: lose a data shard, recover it). Encoding is the same computation, from the 3 data points to x = 4 and 5.

Left: three surviving points (1, 2), (3, 10), (4, 6) allow only one parabola, which gives D2 = 5 and P2 = 4. Right: with only two points (3, 10) and (4, 6), two different parabolas both pass through them and give different values at x = 1, 2 and 5.
Three points allow one parabola; two points allow eleven, one for every guess of a third value.

How many failures

With n − k parity shards, any n − k lost shards can be rebuilt, data or parity (Demo: lose two shards (RAID-6), recover both and Demo: lose both parity shards, compute them again). One more is fatal: with only 2 points left, every guess for a third value gives a different parabola that fits the survivors (Demo: lose three shards: too many). No code can do better: a code that always survives the loss of any n − k shards is called maximum distance separable (MDS), and Reed–Solomon is one.

schemedisks for 3 disks of datastorage overheadsurvives
no redundancy31×0 failures
3 copies (replication)93×any 2 failures
Reed–Solomon k = 3, n = 551.67×any 2 failures

The price is work on repair: rebuilding one shard reads k others instead of one copy, and costs CPU for the field arithmetic.

Where it is used

  • RAID-6 keeps two parity blocks per stripe: P is a plain XOR, Q is a Reed–Solomon syndrome over GF(28). Any two disks may fail.
  • Object storage: HDFS erasure coding ships policies such as RS-6-3 (6 data + 3 parity, 1.5× overhead instead of 3×); Backblaze spreads each file over 17 data + 3 parity shards; Amazon S3, Azure Storage and Ceph also split objects into erasure-coded shards across disks and data centres.
  • QR codes add Reed–Solomon codewords; levels L, M, Q, H can restore about 7%, 15%, 25% and 30% of a damaged code.
  • CDs, DVDs and deep-space links: CDs use two interleaved Reed–Solomon codes against scratches; Voyager and the CCSDS standard use RS(255, 223).

How shards get spread over machines is the subject of Partitioning vs Sharding.

Erasures vs errors

The page shows erasures: the system knows which shard is missing, because the disk is dead. That is the easy case, and 2 parity shards fix 2 erasures. An error is a shard that is present but wrong, and nobody knows which one. Reed–Solomon can fix those too, but finding where they are costs parity: 2 parity symbols per wrong symbol (decoders such as Berlekamp–Welch and Berlekamp–Massey). A CRC only detects that something is wrong; storage systems often keep a checksum per shard so a corrupted shard becomes a known erasure.

What the page leaves out

The page uses the tiny field GF(11), values 0 to 10 and fixed sample data. Real codes use GF(28) with table-driven multiplication, shards of megabytes (each byte position is its own small code), encoding with a Vandermonde or Cauchy matrix instead of Lagrange, error correction with syndromes, and repair-friendly variants such as local reconstruction codes (LRC). It also skips how parity is updated when a single data shard changes. Polynomial arithmetic itself is on Polynomial Division.