CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 3 of 6 · 3 min read

Parity

Think of a class of 30 pupils and a teacher who writes down the total of all their marks. If one pupil's mark is lost, the teacher subtracts the 29 known marks from the total and gets the lost one. The analogy stops in one place: a total of marks is a sum, while the parity of a disk is a bitwise XOR that has no carries.

In plain words: Parity is a block of redundancy that is the XOR of the data blocks of one stripe (one chunk from each data disk). XOR of two bits is 1 when they differ. A useful fact is that XOR is its own inverse: if P = A XOR B XOR C, then A = P XOR B XOR C. One parity block thus protects against the loss of any one block of the stripe, for the price of one disk and not of half. In RAID 4 the parity sits on one disk. In RAID 5 the parity block moves from disk to disk for each stripe, so that no disk takes all the parity writes. RAID 6 keeps two different parity blocks and survives any two failures, and costs two disks.

A worked example. One byte from each of three data disks is 0x01, 0x12 and 0x23. The parity byte is 0x01 XOR 0x12 XOR 0x23 = 0x13 XOR 0x23 = 0x30. If the second disk fails, its byte is recovered as 0x01 XOR 0x23 XOR 0x30 = 0x22 XOR 0x30 = 0x12. In a six-disk array of 4 TB disks, RAID 5 gives (6 - 1) x 4 = 20 TB, and RAID 6 gives (6 - 2) x 4 = 16 TB.

The key lines. The capacity of RAID 5 is (N - 1) times the disk size, and of RAID 6 is (N - 2) times, against N / 2 for mirrors. The more disks, the smaller the parity share. A rebuild after a failure reads all surviving disks completely. At 100 MB/s, a 4 TB disk takes 4,000,000 MB / 100 MB/s = 40,000 s, or 11.1 hours, and a second failure during that time loses the data of a RAID 5.

Parity (RAID)

Parity is a redundant block that is the bitwise XOR of the data blocks of one stripe. Any single missing block of the stripe can be recomputed as the XOR of all the other blocks, including the parity block.

Example: with data bytes 0x01, 0x12 and 0x23, the parity byte is 0x30, and a lost 0x12 is recomputed as 0x01 XOR 0x23 XOR 0x30.

Common mistake

RAID is not a backup. It protects against the failure of a disk, and it does nothing against a deleted file, a software bug, a virus or a fire. A deletion is copied to the mirror or the parity at once.

Check yourself: 1. What is the parity byte of 0x0F, 0xF0 and 0xFF? 2. Why does RAID 5 spread the parity over all disks? 3. How many disks may fail in RAID 6 without data loss?