Saturday, October 8, 2011
2:50 PM

RAID Parity (From Wikipedia)

Many RAID levels employ an error protection scheme called "parity". Most use the simple XOR parity described in this section, but RAID 6 uses two separate parities based respectively on addition and multiplication in a particular Galois Field[7] or Reed-Solomon error correction. XOR parity calculation is a widely used method in information technology to provide fault tolerance in a given set of data.
In Boolean logic, there is an operation called exclusive or (XOR), meaning "one or the other, but not neither and not both." For example:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
The XOR operator is central to how parity data is created and used within an array. It is used both for the protection of data, as well as for the recovery of missing data.
As an example, consider a simple RAID made up of 6 drives (4 for data, 1 for parity, and 1 for use as a hot spare), where each drive has only a single byte worth of storage (a '-' represents a bit, the value of which doesn't matter at this point in the discussion):
Drive #1: -------- (Data)
Drive #2: -------- (Data)
Drive #3: -------- (Data)
Drive #4: -------- (Data)
Drive #5: -------- (Hot Spare)
Drive #6: -------- (Parity)
Let the following data be written to the data drives:
Drive #1: 00101010 (Data)
Drive #2: 10001110 (Data)
Drive #3: 11110111 (Data)
Drive #4: 10110101 (Data)
Drive #5: -------- (Hot Spare)
Drive #6: -------- (Parity)
Every time data is written to the data drives, a parity value is calculated in order to be able to recover from a data drive failure. To calculate the parity for this RAID, a bitwise XOR of each drive's data is calculated as follows, the result of which is the parity data:
00101010 XOR 10001110 XOR 11110111 XOR 10110101 = 11100110
The parity data 11100110 is then written to the dedicated parity drive:
Drive #1: 00101010 (Data)
Drive #2: 10001110 (Data)
Drive #3: 11110111 (Data)
Drive #4: 10110101 (Data)
Drive #5: -------- (Hot Spare)
Drive #6: 11100110 (Parity)
Suppose Drive #3 fails. In order to restore the contents of Drive #3, the same XOR calculation is performed using the data of all the remaining data drives and (as a substitute for Drive #3) the parity value (11100110) stored in Drive #6:
00101010 XOR 10001110 XOR 11100110 XOR 10110101 = 11110111
With the complete contents of Drive #3 recovered, the data is written to the hot spare, and the RAID can continue operating.
Drive #1: 00101010 (Data)
Drive #2: 10001110 (Data)
Drive #3: --Dead-- (Data)
Drive #4: 10110101 (Data)
Drive #5: 11110111 (Hot Spare)
Drive #6: 11100110 (Parity)
At this point the dead drive has to be replaced with a working one of the same size. Depending on the implementation, the new drive either takes over as a new hot spare drive and the old hot spare drive continues to act as a data drive of the array, or (as illustrated below) the original hot spare's contents are automatically copied to the new drive by the array controller, allowing the original hot spare to return to its original purpose as an emergency standby drive. The resulting array is identical to its pre-failure state:
Drive #1: 00101010 (Data)
Drive #2: 10001110 (Data)
Drive #3: 11110111 (Data)
Drive #4: 10110101 (Data)
Drive #5: -------- (Hot Spare)
Drive #6: 11100110 (Parity)
This same basic XOR principle applies to parity within RAID groups regardless of capacity or number of drives. As long as there are enough drives present to allow for an XOR calculation to take place, parity can be used to recover data from any single drive failure. (A minimum of three drives must be present in order for parity to be used for fault tolerance, because the XOR operator requires two operands, and a place to store the result).

Reference: http://en.wikipedia.org/wiki/RAID


0 comments:

Post a Comment