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.
|