Two disks down, still standing

RAIDZ1 buys back one dead disk with one equation: a parity column that is the XOR of the data, and a single line of algebra to recover whatever went missing. It ends on a cliffhanger. In a large array, replacing a failed disk means reading every surviving disk in full, for hours — and that sustained stress is precisely when a second disk, already old and already tired, tends to give up. Survive one and you've survived the easy case. RAIDZ2 wants to survive two.

The naive fix is the first thing anyone tries, and it fails instructively. This essay is about why it fails and what the real fix costs: a short trip into a finite field, GF(2⁸), where a second kind of "parity" becomes possible — one that is genuinely independent of the first. By the end you'll have the whole reconstruction written out, and a playground where you can kill any two of six disks and watch a 2×2 system over the field solve them.

Why a second XOR is worthless

Suppose we keep RAIDZ1's parity P = \bigoplus_i D_i and, hoping to survive a second failure, add another parity disk P_2. What should P_2 be? The tempting answer is "another XOR" — but XOR of what? Every subset you might XOR is built from the same bits with the same operation, and that's the trap.

Make it concrete. Say disks x and y both die. From the survivors you can recompute what the two parities should have summed to, giving you two equations in the two unknowns D_x, D_y:

\begin{aligned} D_x \oplus D_y &= P' \\ D_x \oplus D_y &= P_2' \end{aligned}

If P_2 was just another XOR of all data, its equation reduces to the same left-hand side D_x \oplus D_y. Two equations, one relation. Either they agree (and the second tells you nothing new) or they contradict (and you've detected corruption but still can't locate a value). In linear-algebra terms the coefficient matrix

\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}

is singular — its rows are identical, its determinant is zero — so the system has no unique solution no matter what the right-hand side is. To recover two unknowns you need two independent equations, which means the second parity must weight the disks differently from the first. And here's the rub: over the world of single bits, "mod 2", there's essentially only one nonzero weight — 1 — so you cannot make a second, differently-weighted sum. You have run out of numbers. The fix is to get more numbers, without giving up the property that made XOR so cheap and clean. That is exactly what a finite field is for.

A field where a byte is a number

We want a set of "numbers" with the algebra of a field — add, subtract, multiply, divide, with all the usual laws — but finite, so it fits in fixed-width storage, and built so that addition is still XOR (fast, and its own inverse). The construction that delivers this is \mathrm{GF}(2^8): the finite field with 256 elements, one for every possible byte.

The trick is to stop reading a byte as an integer 0–255 and start reading it as a polynomial over \mathrm{GF}(2) — the coefficients are the bits. The byte 0b00010011 becomes

x^4 + x^1 + x^0 \;=\; x^4 + x + 1.

Addition of two such polynomials adds coefficients mod 2 — i.e. XORs the bytes. No carries, and every element is its own additive inverse, exactly as before. So RAIDZ2 keeps RAIDZ1's first parity unchanged: P = \bigoplus_i D_i is addition in the field.

Multiplication is where the new numbers come from. Multiply the two polynomials the ordinary way (coefficients mod 2), and you may overflow past degree 7 — the product wants nine or more bits. To fold it back into a byte, reduce modulo a fixed irreducible polynomial of degree 8, one that can't be factored over \mathrm{GF}(2). RAIDZ2 uses the same primitive polynomial as AES's byte field,

m(x) \;=\; x^8 + x^4 + x^3 + x^2 + 1 \qquad (\texttt{0x11d}),

so that arithmetic stays inside the 256 bytes. Concretely, to multiply by x (the byte 0x02), shift the byte left one bit; if bit 7 was set — the product reached degree 8 — XOR with the low byte of m(x), 0x1d, to reduce. That shift-and-conditional-XOR is the entire multiply-by-2 routine, and it should feel familiar: it is the very same move as the \otimes\alpha tweak step in LUKS's XTS mode, just in an 8-bit field instead of a 128-bit one. Same trick, smaller field.

Two facts make this field the right tool:

• It's a genuine field. Because m(x) is irreducible, every nonzero byte has a multiplicative inverse (there's no way to factor your way to zero), so division exists — and division is what reconstruction will need.
• 0x02 is a generator. The element g = \texttt{0x02} (the polynomial x) is primitive: its powers g^0, g^1, g^2, \ldots, g^{254} run through all 255 nonzero bytes before repeating. So the sequence g^0, g^1, g^2, \ldots never repeats within an array's worth of disks, and — the point — the weights g^0, g^1, \ldots, g^{n-1} we're about to hand the disks are all distinct.

The two syndromes

Now RAIDZ2 defines two parity disks, and they differ in exactly the way that matters. For data disks D_0, \ldots, D_{n-1}:

P \;=\; \sum_{i} D_i, \qquad\qquad Q \;=\; \sum_{i} g^{\,i}\, D_i,

where all sums and products are in \mathrm{GF}(2^8) (so \sum is XOR, and g^i D_i is a field multiply). P weights every disk by 1; Q weights disk i by g^i — a different constant for each disk. That difference is everything. This is precisely the RAID-6 syndrome scheme H. Peter Anvin worked out for the Linux kernel, and RAIDZ2 uses the same idea.

Recovering two lost data disks. Suppose data disks x and y (with x < y) both die, and P and Q survive. From the disks you still have, recompute the two syndromes over the survivors and XOR them against the stored P, Q. What's left on each side is the contribution of exactly the two missing disks:

\begin{aligned} D_x \oplus D_y &= P' \\ g^{x} D_x \oplus g^{y} D_y &= Q' \end{aligned} \qquad\text{where}\quad \begin{aligned} P' &= P \oplus \!\!\bigoplus_{i \neq x,y}\!\! D_i \\ Q' &= Q \oplus \!\!\bigoplus_{i \neq x,y}\!\! g^{i} D_i \end{aligned}

This is a 2\times 2 linear system over the field, with coefficient matrix

A = \begin{pmatrix} 1 & 1 \\ g^{x} & g^{y} \end{pmatrix}, \qquad \det A = g^{y} \oplus g^{x}.

That's a Vandermonde matrix, and its determinant is the difference of the two weights. Because x \neq y and the powers of the generator are all distinct, g^x \neq g^y, so \det A = g^y \oplus g^x \neq 0 (subtraction is XOR; a nonzero field element). A nonzero determinant in a field means the matrix is invertible and the system has a unique solution — always, for any pair of lost disks. Contrast the singular all-ones matrix from the failed double-XOR: swapping the second row from (1,1) to (g^x, g^y) is the whole ballgame.

Solving it explicitly — Cramer's rule works verbatim in a field, with \oslash denoting division (multiply by the inverse):

D_x = \big(Q' \oplus g^{y} P'\big) \oslash \big(g^{x} \oplus g^{y}\big), \qquad D_y = P' \oplus D_x .

Read the top line slowly: g^y P' scales the first equation to match D_y's weight in the second, then XORing kills the D_y term (because g^y \oplus g^y = 0), leaving D_x times the determinant; one field division finishes it. Then D_y falls out of the simpler equation. Two disks, gone and restored, from two numbers per stripe.

The other cases fall out too. If one of the dead disks is a parity disk, it's easier, not harder: lose P (or Q) and one data disk D_x, and you first rebuild D_x from the surviving parity's single equation, then recompute the lost parity from the now-complete data. Lose both P and Q and all data is intact — just recompute them. The playground walks through each case and shows the actual field arithmetic.

Why not stack this forever?

If a second syndrome with weights g^i buys a second disk, why not a third with weights g^{2i}, a fourth with g^{3i}, and armor a pool against ten simultaneous failures? RAIDZ3 does take the third step, adding

R = \sum_i g^{\,2i} D_i,

and the three-disk recovery is a 3\times 3 Vandermonde solve. But it doesn't extend for free. As you add rows of the form (g^{ki}), keeping the whole system invertible for every possible choice of failed disks stops being automatic — the elegant "distinct powers of one generator" guarantee that makes the 2\times 2 and 3\times 3 cases clean needs more care, and real implementations pin down specific field constants and verify the sub-determinants rather than trusting a pattern. Anvin's paper documents exactly this bookkeeping for RAID-6, and it's why triple parity is roughly the practical ceiling in the wild: beyond it, the arithmetic to guarantee recoverability for all failure patterns grows faster than the benefit. Three is not a law of nature; it's where the cost curve bends.

The two ingredients, again

Step back and the design rhymes with RAIDZ1. There, one equation recovered one disk — but only once ZFS's checksums supplied the location of the failure, turning silent errors into erasures. Here it's the same contract, doubled: the checksums tell RAIDZ2 which two disks to distrust, and the field supplies the two independent equations needed to rebuild them. Locations from the checksum, values from the algebra. The finite field didn't add magic; it added exactly one thing the field of single bits couldn't provide — a second, honestly independent weighting — and that was the whole difference between surviving one death and surviving two.

Go take out two disks and watch the determinant stay nonzero.