Thursday, May 21, 2009

Raid 5 and XOR

RAID 5 functionality is based on the logical operator xor (exclusive or). So let's dvelve into the wonderful world of xor. Xor is a bitwise operator that returns a 1 (true) if only one of the input bits is a 1. This is the resulting truth table:
1 xor 0 = 1
1 xor 1 = 0
0 xor 1 = 1
0 xor 0 = 0

What makes raid 5 work is that xor have the following interesting property:
If
A xor B = X
then
A xor X = B

And this works with any number of inputs:
X = A xor B xor C xor D xor E
A = X xor B xor C xor D xor E
B = A xor X xor C xor D xor E
C = A xor B xor X xor D xor E
D = A xor B xor C xor X xor E
E = A xor B xor C xor D xor X

Simply exchange the letter of the data that you want back by replacing that with the x. In a raid array, the x would be the parity drive. This is why you only loose one disc worth of storage space in a raid 5 setup, no matter how many hard drives you put in.

No comments: