Parity

Parity is one extra block per stripe, computed from the stripe's data blocks by XOR. If any one block of the stripe is lost, it can be recomputed from the others. This protects the stripe at the cost of one block instead of a full copy of the data. RAID 6 adds a second extra block, called Q, computed with a different formula: with two extra blocks, the stripe survives two lost blocks.

The XOR arithmetic

XOR, written ⊕, adds bits without carry: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 1 = 0. XOR has one property that makes it useful as redundancy: a value XORed in twice cancels out. So any one term of an XOR sum can be recovered by XORing all the others. With data blocks D₀, D₁, D₂ and parity P over a stripe:

P  = D₀ ⊕ D₁ ⊕ D₂                  parity: the XOR of the data blocks

D₁ = D₀ ⊕ D₂ ⊕ P                   any one block is the XOR of all the others

example, one byte per block
D₀ = 1100 0101
D₁ = 0011 1010
D₂ = 1111 0000
P  = 0000 1111                     recompute D₁: D₀ ⊕ D₂ ⊕ P = 0011 1010  ✓

Parity is computed over the blocks of one stripe, so it exists only under striping; the chunk entry says how many bytes a full stripe holds.

If the disk that holds D₁ fails, the raid engine answers every read of D₁ by reading the rest of its stripe and XORing the blocks: the array is then in degraded mode. When the disk is replaced, the engine runs the same computation over every stripe and writes D₁ back: this is the rebuild.

Placement of the parity block

The 1988 RAID paper defines the fourth level with one check disk per group, holding the parity of every stripe. It works, and it has one bottleneck: "every write must read and write the check disk", so the whole array can only complete writes as fast as that one disk. The fifth level keeps the same parity but spreads it: "the final level RAID distributes the data and check information across all the disks — including the check disks". Linux md says the same in its own words: RAID 4 is "a RAID0 array with an extra device for storing parity", the last of the devices; in RAID 5 "the parity blocks for each stripe, instead of being on a single device, are distributed across all devices", which "allows more parallelism when writing" and when reading.

The placement algorithm determines which disk holds the parity of stripe k. Linux md's default, left-symmetric, puts the parity on the last disk for stripe 0 and moves it one disk to the left every stripe, with the data starting just right of it; in raid5.c this is the line pd_idx = data_disks - sector_div(stripe2, raid_disks). Every disk then carries the same share of parity and of data, and no disk is the check disk.

Parity updates

Whenever a data block changes, the parity of its stripe must change with it. The paper gives the rule and its cost:

new parity = (old data ⊕ new data) ⊕ old parity

a small write, on two disks:     read old data      read old parity
                                 write new data     write new parity
                                 → 4 operations for one logical write

That is the small-write problem, and the four operations are the write penalty of single parity. There is a second way: read the data blocks the write does not touch, and compute the parity fresh. raid5.c counts both for every stripe it is about to write, rmw (blocks to read for a read-modify-write) and rcw (blocks to read for a reconstruct-write), and takes the cheaper. A write that covers the whole stripe has nothing left to read: rcw is zero, the parity is computed from what is being written, and the penalty disappears. For this reason, writes aligned to whole stripes make parity cheap. The file system's stripe_width option exists for this: it lets the block allocator avoid a read-modify-write of the parity.

The two writes of that rule are separate disk operations, and a power cut between them leaves a stripe whose parity no longer matches its data. The XOR arithmetic cannot detect the mismatch, and a rebuild uses the wrong parity as if it were right. This is the write hole, and it is why a parity array needs either a raid engine whose write cache survives power loss, or a journal or a partial parity log on the disks.

Single and double parity

One parity block recovers one missing block. To survive two failures a stripe needs a second block that is not another XOR (two XORs of the same blocks carry the same information). RAID 6 computes two syndromes, in H. Peter Anvin's description for the Linux implementation:

P = D₀ + D₁ + D₂ + … + Dₙ₋₁                        ordinary XOR parity
Q = g⁰·D₀ + g¹·D₁ + g²·D₂ + … + gⁿ⁻¹·Dₙ₋₁         a Reed-Solomon code

where the arithmetic is that of the Galois field GF(2⁸) and g is a generator of it. With one data disk lost, P recovers it as in RAID 5; with two lost, the two equations are solved together. "RAID-6 supports losing any two drives." The cost is two blocks per stripe, and a write that touches one data block must update both: six operations instead of four. The field has 255 non-zero elements, so a stripe can hold at most 255 data disks.

Windows Storage Spaces offers the same two shapes as single parity and dual parity spaces, described as "data is striped across multiple drives with parity information for fault tolerance".