RAID Parity Caliculation

The parity calculation is typically performed using a logical operation called "exclusive OR" or "XOR". As you may know, the "OR" logical operator is "true" (1) if either of its operands is true, and false (0) if neither is true. The exclusive OR operator is "true" if and only if one of its operands is true; it differs from "OR" in that if both operands are true, "XOR" is false. This truth table for the two operators will illustrate:




The interesting thing about "XOR" is that it is a logical operation that if performed twice in a row, "undoes itself". If you calculate "A XOR B" and then take that result and do another "XOR B" on it, you get back A, the value you started with. That is to say, "A XOR B XOR B = A". This property is exploited for parity calculation under RAID. If we have four data elements, D1, D2, D3 and D4, we can calculate the parity data, "DP" as "D1 XOR D2 XOR D3 XOR D4". Then, if we know any four of D1, D2, D3, D4 and DP, we can XOR those four together and it will yield the missing element.
Let's take an example to show how this works; you can do this yourself easily on a sheet of paper. Suppose we have the following four bytes of data: D1=10100101, D2=11110000, D3=00111100, and D4=10111001. We can "XOR" them together as follows, one step at a time:
D1 XOR D2 XOR D3 XOR D4
= ( (D1 XOR D2) XOR D3) XOR D4
= ( (10100101 XOR 11110000) XOR 00111100) XOR 10111001
= (01010101.XOR 00111100) XOR 10111001
= 01101001 XOR 10111001
= 11010000
So "11010000" becomes the parity byte, DP. Now let's say we store these five values on five hard disks, and hard disk #3, containing value "00111100", goes el-muncho. We can retrieve the missing byte simply by XOR'ing together the other three original data pieces, and the parity byte we calculated earlier, as so:
D1 XOR D2 XOR D4 XOR DP = D3
= ( (D1 XOR D2) XOR D4) XOR DP
= ( (10100101 XOR 11110000) XOR 10111001) XOR 11010000
= (01010101 XOR 10111001) XOR 11010000
= 11101100 XOR 11010000
= 00111100
= D3
Which is D3, the missing value.This operation can be done on any number of bits, incidentally; I just used eight bits for simplicity. It's also a very simple binary calculation--which is a good thing, because it has to be done for every bit stored in a parity-enabled RAID array.