RAID Parity
Patterson, Gibson and Katz argued in 1988 that an array of cheap disks could be more reliable than one expensive one, which sounds backwards until you see what the extra disk holds. Not a copy. One exclusive or of the corresponding bytes across the group, which is their own description of it. Throw any single disk away and it comes back exactly, and this page rebuilds it and compares byte for byte rather than telling you it would.
A whole disk is gone and XOR still knows every byte
1 Four disks, and one more that holds no copy of anything
Four disks of data, eight bytes each so the arithmetic fits on a screen, and one more disk holding a single exclusive or of the corresponding bytes across them.
2 Lose one, and what is left of the arithmetic
Throw a disk away. Not its contents corrupted, not a bad sector: the whole disk, gone, the way the paper means it.
3 Rebuild it, and compare byte for byte
Rebuild it. The operation is the same one that made the parity in the first place, which is the surprising part: exclusive or is its own inverse, so nothing here is a special recovery routine. The underlined bytes below were computed rather than read, and they are compared against what was actually on the disk.
4 Lose two, and what single parity cannot do
Now lose a second one. Single parity is one equation, and two missing disks are two unknowns; one equation cannot solve for two. Press a second disk above and this page refuses rather than returning something plausible, which is the honest half of the scheme and the reason RAID 6 exists.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it. The rebuild claim is checked over every disk of two hundred different groups, not over one.
| claim | held | measured |
|---|---|---|
| Any one data disk in a group can be rebuilt exactly, byte for byte | yes | 800 of 800 rebuilds were byte-identical to the disk that was lost |
| And the parity disk itself is rebuilt by the same operation | yes | recomputing parity from the data reproduces it exactly |
| Two lost disks in one group cannot be rebuilt, and the page refuses rather than guesses | yes | two disks in one group leave two unknowns and one equation, and one equation cannot solve for two unknowns. Single parity reconstructs one disk, not any two. |
| Computing parity and rebuilding from it are the same operation | yes | checked on all 65,536 byte pairs |
What is real here, and what is not
The parity disk holds no copy of any disk
It is worth being clear about this because the scheme reads like duplication and is not. The parity disk holds one exclusive or of the corresponding bytes across the group, which is the paper's own sentence. Four data disks and one parity disk is five disks of storage holding four disks of data, where mirroring would need eight.
The rebuild is compared, not asserted
The page does not say the disk would come back. It throws one away, rebuilds it from the survivors and the parity, and compares the result against what was there byte for byte. Every check on this page does that over hundreds of groups and every disk in each of them, and prints how many rebuilds were byte-identical out of how many were tried.
Computing parity and rebuilding from it are the same operation
That is the surprise and it is why the parity disk is not special: exclusive or is its own inverse, so the operation that made the parity is the operation that recovers a lost disk from it. The page checks that property over all 65,536 byte pairs rather than stating it.
Two lost disks is where it stops, and the page shows that
Single parity is one equation. Two missing disks are two unknowns, and one equation cannot solve for two unknowns, so the group is gone. A page that only demonstrated the recovery would be selling something. This one lets you lose a second disk and refuses, and says why rather than returning a plausible answer.
The disks here are eight bytes, and a real one is not
Eight bytes to a stripe unit so the arithmetic fits on a screen and you can read the exclusive or yourself. Nothing about the property depends on the size. What is NOT modelled is everything that makes RAID hard in practice: the read-modify-write cost of a small write, where the parity lands (this is level 4, one dedicated parity disk, not level 5's rotation), rebuild time on a real disk, or a second failure arriving during a rebuild, which is how these arrays actually die.
The reliability arithmetic is the paper's and is not on this page
The paper's other famous result is that the mean time to failure of an array is the mean time to failure of one disk divided by the number of disks, which is why redundancy was needed at all. That is a different argument from this one and the page does not restate it.
No sound
Nothing here has a duration.
Sources
- David A. Patterson, Garth Gibson and Randy H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), University of California Berkeley report UCB/CSD-87-391, published at SIGMOD in June 1988. Read for this page: that each parity bit is a single exclusive or of the corresponding data bits in a group, and the definition of a group.
- Logical Art, the studio this belongs to.