Storage

Parity

Error-correcting data stored across drives in RAID 5 and 6. Parity lets the array rebuild lost data from a failed drive, but calculating it imposes a write penalty on every update.

How XOR parity works

Parity in RAID is the XOR of the data blocks in a stripe. XOR gives 1 when an odd number of its inputs are 1, which makes it its own undo. Take two drives holding the bits 1010 and 0110. Their parity is 1100. If the second drive dies, XOR the first drive with the parity: 1010 and 1100 give 0110, the lost data.

The same trick works across any number of drives. The parity block is what all the data blocks XOR to, so any one missing block can be recomputed from the others plus the parity. That's also the limit. One parity block can rebuild one missing block per stripe, which is why RAID 5 survives one failed drive and no more.

Where the parity lives

RAID 4 keeps all the parity on one dedicated drive, and every write updates it, so that drive becomes a bottleneck. RAID 5 rotates the parity block from stripe to stripe so every drive takes a share. RAID 6 stores two parity blocks per stripe. The first is XOR. The second comes from a different code, typically Reed-Solomon, which lets the array solve for two missing blocks. ZFS offers the same idea as RAID-Z1, Z2 and Z3, with one, two or three parity blocks.

Parity costs space by the number of parity blocks, not by drive size. Take six 8 TB drives. Mirroring in RAID 10 leaves 24 TB, single parity leaves 40 TB, double parity leaves 32 TB and RAID-Z3's triple parity leaves 24 TB. A mirror spends 50% of the raw space on redundancy, and single parity spends 17%.

What parity costs

Parity makes writes harder. Changing a small block means reading the old data and the old parity, then computing the new parity as old parity XOR old data XOR new data, and writing both. That shortcut avoids reading the rest of the stripe, but it's still two reads and two writes for one small write. A write covering the whole stripe computes parity straight from the new data.

A crash can also leave data and parity out of step. If the power fails after the data block lands and before the parity block does, the stripe no longer adds up, and a later rebuild would produce wrong data from it. That's the write hole. Protected caches, journals and ZFS's design all exist to close it.

The biggest cost shows up in a rebuild, because recreating a lost drive means reading all the others. On four 8 TB drives that's 24 TB, and the chance of an unrecoverable read error in that much data is why double parity exists.

Parity guards against a drive dying. It doesn't guard against you deleting a file, because the delete updates the parity too.

Work it out yourselfOpen the RAID Calculator

Sources

Back to the glossary