RAID Parity Calculation using XOR Operation
Using XOR Redundancy on RAID Hard Drives
Many variants of RAID (Redundant Array of Inexpensive Disks) arrays calculate parity to provide a redundancy against failure. The amount of redundancy available in a RAID array varies according to the particular RAID level used.
RAID levels that use parity include:
- RAID 3
- RAID 4
- RAID 5
- RAID 6
There are other RAID levels that make use of parity in one way or another, as well as RAID systems that use other redundancy methods. These other RAID levels will not be discussed here.
Parity Creation
A very simple Boolean operation is used at the binary level to create RAID parity. This operation is the Exclusive Disjunction operation also known as Exclusive OR (XOR, EOR herein XOR). Using XOR raw binary data is passed through an operation that results in a binary result, which can be used for redundancy and error correction. The truth table for calculating XOR parity is shown below:
As you can see above the calculated value when the Value 1 XOR Value 2 is equal to 1 if and only if one of the Disk’s binary bits is equal to 1. Should the value of two of the disks be equal 0, 0 or 1, 1 then the result has to be 0.
There does not exist a single recognised symbol of the XOR operation, various symbols are used within different applications, for the purpose of this article when the operation is used it shall take the following form: value a XOR value b.
So what happens if a disk other than the parity disk fails? Well as the results in the table show the missing disks value is equal to the XOR of the remaining data disk and the parity bit.
What if more disks are thrown into the equation, well, thanks to the simplicity of this system results are still easily calculated with little overhead. For this particular example we will use 4 sets of 4 bits (or a nibble in techy speak) that will represent four bits of data on four different RAID member disks.
- Disk 1 =1111
- Disk 2 =1110
- Disk 3 =1100
- Disk 4 =1000
If we work on the first bit of disks 1 – 4:
1 XOR 1 XOR 1 XOR 1 which can also be displayed as:
((1 XOR 1) XOR 1) XOR 1 n
(0 XOR 1) XOR 1
1 XOR 1n
= 0
If we then run this operation on the remaining bits within the nibble we achieve a Parity nibble of 0101 as shown in the table below:
The calculation process is also displayed below:
1111 XOR 1110 XOR 1100 XOR 1000
((1111 XOR 1110) XOR 1100) XOR 1000
(0001 XOR 1100) XOR 1000
1101 XOR 1000
= 0101
RAID 3 Parity Implementation
RAID 3 requires a minimum of 3 physical storage mediums. The data stored on the array is then striped across two of the devices at the byte level (usually ? 1024 bytes) whilst the third device is used as a dedicated parity device. RAID 3 can provide a redundancy against a single disk failure (n-1).
RAID 4 Parity Implementation
RAID 4 = Where a single disk is reserved as a Parity disk and data is striped across the remaining disks at the block level (block size varies dependent on implementation and preference) Fault Tolerance = Total number of disks -1
RAID 5 Parity Implementation
RAID 5 = Where Parity is distributed in a regular fashion across all of the member disks in the array. Distributed Parity removes the bottleneck created by using a single dedicated Parity Disk.Fault Tolerance = Total number of disks -1
The actual way that parity is rotated through the disks can vary dependant on the specific software or controller used to create and manage the array. It is however common for the default stripe size to be equal to 64KB with the first block of parity calculated on the final member that is configured logically within the array. The Parity block then tends to skip back a disk to the previous logically configured member of the array.
Please Note:
Many vendors use many different methods of RAID 5 organisation; also particular applications may require different settings in order to achieve maximum efficiency. Please contact your software/hardware vendor for more information on the way in which your own RAID 5 array may be set up.