RAID parity

[kavanagh_1]

Hi all, I have a reasonable understanding of RAID levels etc but I have never understood how the parity works. My problem is this, if we take RAID 3 as an example and using N + 1, where N is 4, we have 4 data disks and one parity disk. If any data disk was to fail it could be recovered from the parity disk and so from my understanding just 1 parity disk must hold all the information that is 4 data disks. How does it fit all that information into the 1 disk ?
Thanks in advance,
Matthew Kirk

[Paul R. Dittrich]

I like this oversimplified example.

-Assign numbers to every letter of the alphabet, with A=1 through Z=26

A piece of data striped across your N+1 raidset might look something like this:

D1 D2 D3 D4 Parity
D A ?? A 26

One disk (D3) is bad but the calculation is simple to do:

(4) + (1) + ?? + (1) = 26 so the missing number must be 20 which is letter T.

The idea is that any ONE disk can go bad but enough information exists to recreate the missing data.

[Mark van Silfhout]

That's correct the parity disk does not hold any user data, it just holds a parity number to recreate data if a disk goes down.
That's why performance will degrade when a disk goes down. If the parity disk would have a copy of the user data, performance would not be influenced (but then indeed it would not fit on one disk...)

Regards,

Mark

[Mladen Despic]

Let's say that each disk is a sequence of boxes, and each box contains either 0 or 1. For now, consider the box #1 on each of the four disks. These four boxes may contain something like

1 0 1 1

If one disk is lost, then only one of the four boxes
will be lost. How can you recover its contents?

The parity disk (in this case the fifth disk) keeps track
of the "parity" of this set of four bits. So, for the
above set, the parity is 1 because 1 + 0 + 1 + 1 is odd.
Should the contents of the boxes change to, say,

1 0 0 1

then the parity bit is updated to 0, since 1 + 0 + 0 + 1
is even.

Let's say that this parity bit is kept in "box #1" on the
parity disk. Now the contents of box #1 on all five disks
will be:

1 0 1 1 1

in the first case, and

1 0 0 1 0

in the second case. So, no matter what happens to
the data on the first four disks, when you add the bits
in box #1 on all 5 disks, the result is always even.

Now, if any of the four disks is lost, you can recover the contents of its box #1 simply by making sure that
the sum of the bits in box #1 on all 5 disks is even.
For example, if you lose the first disk and you see
the following in box #1 on 5 disks:

x 1 0 1 1

where x is the missing bit, then you know x had to be 1 because 1 + 1 + 0 + 1 + 1 is even (if x was 0, then 0 + 1 + 0 + 1 + 1 would be odd).

The same concept can be applied to box #2, box #3, etc.

To summarize:

The fifth disk, or the parity disk, does not contain any data from any of the four disks. It contains a (parity) bit of information for every 4 bits of information from the four disk (1 bit from each disk).

If one of the five disks is lost, then ALL FOUR remaining disks are used in the recovery process. The parity disk alone cannot recover anything. In fact if any 2 disks should fail, the recovery is impossible.

[Vincent Fleming]

So now you've got one oversimplified answer and one overcomplicated answer... how about a third (hopefully) somewhere inbetween:

The data is bytewise XORed in stripes to produce the parity. So, the first byte of parity is the XOR sum of the first byte of each data disk in the array:

d1 XOR d2 XOR d3 XOR d4 = P

One interesting property of XOR parity is that if you lose one of the data items, you can use the parity to reproduce it, as long as you have all the others... like this:

d3 = P XOR d1 XOR d2 XOR d4
d2 = P XOR d1 XOR d3 XOR d4
d1 = P XOR d2 XOR d3 XOR d4
d4 = P XOR d1 XOR d2 XOR d3

So, you can reproduce any piece of data from the remaining data and the parity.

This is also why yoy're in trouble if you lose two disks - you're missing a critical piece of data.

I hope this helps.