Is the 2nd parity bit in RAID 6 a simple calculation?

Question

I'm trying to understand how the 2nd parity bit or byte is set in RAID 6. I'm reading a paper by H. Peter Anvin, and it goes into Galois field algebra, which is somewhat new to me. Anyway, a rep from HP was trying to explain RAID 6 to me and she thought it was merely two XOR operations, one for the 1st parity bit and one for the 2nd. This doesn't make sense to me, but since I'm still working through the paper I don't know if it reduces to something simple for RAID 6 as opposed to RAID n. It looks to me like the 2nd parity bit is quite a bit more complicated than the XOR based 1st parity bit. Is that true?

Answer 1

The general case is indeed a bit complicated.

However, in the case of 4 disks you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store 4 bits redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store.

We can represent the scheme as 4 x 4 tables. The first 2 bits of our data determine the row and the last 2 bits of our data determine the column.

Disk 1: Just store the first 2 bits. That is:

00 00 00 00
01 01 01 01
10 10 10 10
11 11 11 11

Disk 2: Just store the last 2 bits. That is:

00 01 10 11
00 01 10 11
00 01 10 11
00 01 10 11

So far so good. Given disk 1 + disk 2, we can recover our original data: disk 1 tells us the row (the first 2 bits of the original data) and disk 2 tells us the column (the last 2 bits of the original data).

Disk 3: This is what we do on RAID5, just XOR the bits:

00 01 10 11
01 00 11 10
10 11 00 01
11 10 01 00

Again, everything is still fine. You can recover the original data using disk 1 + disk 3 or disk 2 + disk 3. A key observation is that the lookup table for disk 3 forms a Latin square: all elements of each row are distinct, and all elements of each column are distinct. For example, if you know the data on disk 1, you know the right row, and then you can use the data on disk 3 to recover the column. Conversely, if you know the data on disk 2, you know the right column, and then you can use the data on disk 3 to recover the row.

Disk 4: Here we can use the following lookup table:

00 01 10 11
10 11 00 01
11 10 01 00
01 00 11 10

Don't worry how it is constructed; we do not really care about that. The crucial properties are:

• The lookup tables of both disk 3 and disk 4 are Latin squares. Therefore if you know 1 + 3 or 1 + 4 or 2 + 3 or 2 + 4, you can recover both row and column (i.e., the original data).

• The lookup tables of disk 3 and disk 4 form orthogonal Latin squares, which makes it possible to recover the data if we only have disks 3 + 4.

Let's elaborate on the second point. By concatenating the lookup tables of disk 3 and disk 4, we get this matrix:

0000 0101 1010 1111
0110 0011 1100 1001
1011 1110 0001 0100
1101 1000 0111 0010

Now note that each 4-bit string occurs in this table exactly once. That is, if we know what is stored on disks 3 + 4, we know where we are on this table. We know both the row and the column, and hence we can recover the original data.

---

If you insist on seeing the connection to Galois fields, consider the field $F = GF(2^2)$. Label the elements of the field with $F = \{0,1,x,x+1\}$; these correspond to 2-bit strings ($0$ ≈ 00, $1$ ≈ 01, $x$ ≈ 10, $x+1$ ≈ 11). Now any 4-bit string can be encode as a pair $(a,b)$, where $a,b \in F$.

A pair $(a,b)$ is now stored as follows:

• Disk 1 stores $a$.
• Disk 2 stores $b$.
• Disk 3 stores $a+b$.
• Disk 4 stores $xa+b$.

Now given, for example, just $p = a+b$ and $q = xa+b$, you can solve $a$ and $b$. Using the rule $2 \equiv 0$, you can find

• $p + q = (xa+b) + (a+b) = (x+1)a + 2b \equiv (x+1)a$,
• $p + xq = (xa+b) + x(a+b) = 2xa + (x+1)b \equiv (x+1)b$.

Then divide by $x+1$ to get $a$ and $b$, etc. But in the end, this approach gives you precisely the same lookup tables as what was presented above.

Answer 2

The computation for $Q$ is definitely more difficult than the XOR computation needed for $P$ though it is in one sense the same kind of calculation: a polynomial evaluation.

Stripped of the detailed computational techniques described in the link, the idea is to regard the $n$ data bytes/drives $D_0$, $D_1, \ldots, D_{n-1}$ as the coefficients of a polynomial $D(x) = D_0 + D_1x + \cdots + D_{n-1}x^{n-1}$. Then,

$\qquad \begin{align*} P &= D(1) = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1}\\ Q &= D(\alpha) = D_0 \oplus D_1\cdot\alpha \oplus \cdots \oplus D_{n-1}\cdot\alpha^{n-1}\\ &= ((\cdots(D_{n-1}\cdot\alpha \oplus D_{n-2})\cdot\alpha \oplus \cdots \oplus D_1\cdot\alpha) \oplus D_0 \end{align*}$

where $\alpha$ is an element (denoted by $\{02\} = (00000010)$ in the paper cited by the OP) of the Galois field GF$(2^8)$ (also denoted $\mathbb F_{2^8}$) whose $256$ elements are the $256$ $8$-bit bytes, and the second line of the equation for $Q$ can be recognized as Horner's rule. Of course, the computation for $P = D(1)$ can also be thought of as using Horner's rule except that we are ignoring the multiplications by $1$ as NOPs and eliding all the parentheses in Horner's rule since they are unnecessary.

After the drives have been written,

• If either or both of $P$ and $Q$ fail, there is no problem; $P$ and $Q$ can be recomputed and stored on replacement drives.

• If the only failure is one data drive, say the $i$-th drive, then its contents can be recomputed since $$D_i = D_0 \oplus D_1 \oplus \cdots \oplus D_{i-1} \oplus D_{i+1} \oplus \cdots \oplus D_{n-1} \oplus P.$$

• If one data drive and $Q$ fails, the data drive can be recomputed as described above, and then $Q$ can be recomputed.

• What to do in the other cases: one data drive and $P$ failing or two data drives failing are more complicated to describe, but the methods can be understood more easily using the polynomial perspective described here. For example, if the $i$-th and $j$-th drives have failed, reconstruction is effectively the solution of the simultaneous equations: $$\begin{align*} D_i \oplus D_j &= P \oplus \sum_{k: k \neq i, j} D_k\\ \alpha^i\cdot D_i \oplus \alpha^j \cdot D_j &= Q \oplus \sum_{k: k \neq i, j} D_k\cdot\alpha^k. \end{align*}$$ where the right hand sides can be computed from the contents of the non-failed drives.

Answer 3

The three disk raid-6 is trivial: Just store the same information on disk 1, disk 2 and disk 3. Any two disks may fail and you can still recover the data. So a three disk raid-6 is basically just a three disk raid-1.

In the four disk case, there are two data "disks" (let's call them $A$ and $B$) and two parity "disks" (let's call them $P$ and $Q$). Furthermore, we have to operate on two bits from each disk at a time, so the minimum data item (whose parity generation is shown here) is four bits: Two bits on disk $A$ and two bits on disk $B$. This will generate two bits of parity $P$ and two more bits of parity $Q$. If we have more bits, we just repeat this scheme as needed.

The first parity $P$ is calculated normally, using a standard XOR ($⊕$) scheme:

$P = A ⊕ B$

For the second parity $Q$, we have to mangle one of the data items before we do the XOR, so that it becomes different from $P$:

$Q = A ⊕ B^*$

The mangled $B^*$ is calculated from $B$ as follows: The first bit of $B^*$ is the XOR of both bits from $B$, and the second bit of $B^*$ is a copy of the first bit of $B$:

$B^* = (B^*_1, B^*_2) = (B_1 ⊕ B_2, B_1)$

The above formula leads to the following table for the calculation of $B^*$ from $B$:

$00 \rightarrow 00$
$01 \rightarrow 10$
$10 \rightarrow 11$
$11 \rightarrow 01$

Note, that the value $00$ remains unchanged, when mangled, while the other values go through a cycle of three: $01 \rightarrow 10 \rightarrow 11 \rightarrow 01$.

Unmangling is rather straightforward: Because of the cyclic property, just repeat the mangling twice to do an unmangle. Or invert above formula for $B^*$, which leads to:

$B = (B^*_2, B^*_1 ⊕ B^*_2)$

So, unmangling is somewhat symmetrical to mangling.

Now comes the magic, that will later enable us recovery in the scenario, that the two data disks fail and only the parity disks survive: What happens, if $B$ and $B^*$ get XORed? Now, let's have a look:

$B ⊕ B^* = (B_1, B_2) ⊕ (B_1 ⊕ B_2, B_1) = (B_1 ⊕ B_1 ⊕ B_2, B_1 ⊕ B_2) = (B_2, B_1 ⊕ B_2)$

The nice result: XORing $B$ and $B^*$ is identical to performing an unmangle step on $B$. Thus $B$ can be recovered from $B ⊕ B^*$ by applying a mangle to it: $B = (B ⊕ B^*)^*$. And as $(B ⊕ B^*)$ is the result of XORing the two parity values $P$ and $Q$, recovery from the parity disks alone becomes possible.

Now, we have everything together: To store $A$ and $B$ on a RAID-6, we calculate first the mangled datum $B^*$, and then the standard parity $P$ from $A$ and $B$ and the mangled parity $Q$ from $A$ and $B^*$:

$B^* = (B_1 ⊕ B_2, B_1)$
$P = A ⊕ B$
$Q = A ⊕ B^*$

Recovery after failure of two disks is as follows:

• If $A$ and $B$ survive, just recompute $P$ and $Q$.
• If $A$ and $P$ survive, recover $B = P ⊕ A$, then recompute $Q$.
• If $B$ and $P$ survice, recover $A = P ⊕ B$, then recompute $Q$.
• If $A$ and $Q$ survive, recover $B^* = Q ⊕ A$, then recover $B$ from $B^*$ via an unmangle operation (or a double mangle), then recompute $P$.
• If $B$ and $Q$ survive, calculate the mangled $B^*$ from $B$, then recover $A = Q ⊕ B^*$, then recompute $P$.
• If $P$ and $Q$ survive, use the formula explained above $B = (P ⊕ Q)^*$, then recover $A = P ⊕ B$.

In the five disk case, there are three data disks $A$, $B$ and $C$ and again two parity disks $P$ and $Q$. The most notable difference is, that the mangle is performed twice on $C$, when calculating $Q$:

$P = A ⊕ B ⊕ C$
$Q = A ⊕ B^* ⊕ C^{**}$

Recovery in the five disk case follows the same principles as for the four disk case. In those cases, that two data disks and either $P$ or $Q$ survives, one has to take out two values from the parity instead of just one, and follow with the correct unmangle function in case of $Q$. For example, $C$ is recovered from $A$, $B$ and $Q$ as follows: $C = (Q ⊕ A ⊕ B^*)^*$.

The most tricky case is, if disks $A$, $P$ and $Q$ survive. Then $A$ is first XORed out of $P$ and $Q$, and then $(P ⊕ A)$ is mangled before XORing with $(Q ⊕ A)$. That maps out $B$ and leaves plain $C$:

$(P ⊕ A)^* ⊕ (Q ⊕ A) = (A ⊕ B ⊕ C ⊕ A)^* ⊕ (A ⊕ B^* ⊕ C^{**} ⊕ A) =$
$= (B ⊕ C)^* ⊕ (B^* ⊕ C^{**}) = (B^* ⊕ C^*) ⊕ (B^* ⊕ C^{**}) =$
$= B^* ⊕ C^* ⊕ B^* ⊕ C^{**} = B^* ⊕ B^* ⊕ C^* ⊕ C^{**} = (C ⊕ C^*)^* =$
$= (C^{**})^* = C^{***} = C$

For six or more disks, the principle remains the same, but the mangle operation needs to be replaced with one that has a longer cycle. This also requires the use of more bits. With four bits, a possible mangle op is:

$M^* = (M_1 ⊕ M_4, M_1, M_2, M_3)$

$0000$ is again mapped on $0000$, while all other values go through a 15-stage cycle: $0001 \rightarrow 1000 \rightarrow 1100 \rightarrow 1110 \rightarrow 1111 \rightarrow 0111 \rightarrow 1011 \rightarrow 0101 \rightarrow 1010 \rightarrow 1101 \rightarrow 0110 \rightarrow 0011 \rightarrow 1001 \rightarrow 0100 \rightarrow 0010 \rightarrow 0001$

With its 15-stage cycle, this mangle op can be used for up to 15 data disks and two parity disks. For the $P$ parity, all values are XORed together as is, and for $Q$, the first disks datum is not mangled, the second disks datum is mangled once, the third disks datum is mangled twice, and so on.

Answer 4

It looks pretty damned complicated to me.

Thus, in the formula above, the calculation of P is just the XOR of each stripe. This is because addition in any characteristic two finite field reduces to the XOR operation. The computation of Q is the XOR of a shifted version of each stripe.

(P being the first parity bit and Q being the second.)

So it sounds like the explanation you got is a valid high level description of the calculation, without getting into the mathematical theory and details that neither you or her (or me, or most anyone else) actually understand.