Sidebar : XOR Operations

RAID Level 2 data reconstruction is based upon the use of XOR operations, so a good place to start our examination of an example of data reconstruction is by reviewing the exclusive OR (XOR) operation.

An XOR operation produces a true (1) result if either but not both variables are true, and generates a false (0) result if both variables have the same value or setting. This is indicated by the following table which indicates the application of an XOR operation to two variables.

X      Y      X XOR Y
0      0               0
0      1               1
1      0               1
1      1               0

Illustrating the use of an XOR operation to show how data can be reconstructed from n-1 operational drives, requires some drives to work with. So, let's assume there are three drives in our disk array labeled X, Y, and Z. Let's further assume that bit n recorded in block 1 on each drive had the values 1, 0, and 1, respectively. Then, X XOR Y results in a value of 1. If we XOR the intermediate result against the value of bit n in block 1 stored on drive Z, 1 XOR 1, we obtain a value of 0, which becomes the parity across the array for bit position n. The preceding sequence of operations is indicated below:

Generating Parity

Drive X      Drive Y        Drive Z       Parity
bit n            1                 0                   1
Ê          Â                    ,
XOR
1                 XOR          0

Let's assume drive X failed. Since X XOR Y yields an intermediary (I) result, which was XORed with Z's value of 1 to yield a parity value of 0, we can work backward to determine the value of bit position n in block 1 on drive X. That is, for I XOR Z to have a value of 0, the intermediate (I) result must have had a value of 1. Then, for X XOR Y to have a value of 1 when Y has a value of 0 requires X to have a value of 1. This is illustrated below:

Reconstructing information stored on a failed drive

Drive X       Drive Y      Drive Z       Parity
drive X inoperative X            0                1                 0
,
I is intermediate value           I   XOR   0
X   XOR  0    = 1
X      =    1

The preceding process would be continued to reconstruct the value of each bit on the failed drive.