§38.5–38.6RAID-1: Mirroring … RAID-4: Parity

Striping (RAID-0) is fast and full-capacity but survives no failures. The redundant levels buy reliability back — each in a different way, at a different price. We measure them in the S (sequential) and R (random) units from the last section.

38.5 RAID Level 1: Mirroring

The simplest redundant design is mirroring mirroring RAID-1: keep two (or more) physical copies of every block on separate disks. Tolerates at least one disk failure (more, with luck); a read can use either copy, but every logical write must update all copies. Costs half the capacity (useful capacity (N·B)/2 at mirroring level 2). defined in ch. 38 — open in glossary (RAID-1): keep more than one copy of each block, each on a separate disk. With mirroring level 2 (two copies), a four-disk array holds two mirrored pairs and stripes across them — an arrangement called RAID-10 (mirror, then stripe):

Reading a block, the RAID has a choice — either copy will do. Writing a block, it has no choice: it must update both copies to preserve reliability. The two physical writes can proceed in parallel.

RAID-1 analysis.

• Capacity: expensive — with two copies, only half is useful: (N·B)/2.
• Reliability: good — tolerates any one disk failure for sure, and with luck up to N/2 (as long as no pair loses both members). In practice we count on surviving one.
• Performance: a single read has single-disk latency; a single write must wait for both physical writes, so its latency is the worse of the two (slightly above a single disk). For steady-state throughput: random reads are the best case — spread across all disks, N·R. Random writes are (N/2)·R (each logical write = two physical writes). Both sequential reads and writes are (N/2)·S — the write is obviously halved, but the read is the surprise below.

Why even sequential reads only reach (N/2)·S

You might expect a sequential read to hit full bandwidth — it only needs one copy of each block, so why not use every disk? The catch: to read blocks 0–7 you might send 0→Disk 0, 1→Disk 2, 2→Disk 1, 3→Disk 3, then 4→Disk 0, 5→Disk 2… Now look at what Disk 0 sees: block 0, then block 4 — it must rotate over the skipped block in between, delivering no data during that rotation. Each disk ends up giving only half its bandwidth, so the array delivers just (N/2)·S.

38.6 RAID Level 4: Saving Space With Parity

Mirroring’s 50% capacity tax is steep. Parity parity Redundancy computed with XOR across the data blocks of a stripe and stored in a parity block, so any one lost block can be reconstructed by XOR-ing the survivors. Cheaper than mirroring (one extra disk protects a whole group → (N−1)·B capacity) but slower on writes, since updating data means updating parity too. defined in ch. 38 — open in glossary -based RAID cuts the cost — at the price of write performance. RAID-4 devotes one disk to parity for each group it protects (here, five disks: four data + one parity). Each parity block holds the redundant information for its stripe — e.g. P1 is computed from blocks 4, 5, 6, 7:

How parity recovers a lost block

The parity function is just XOR. For a set of bits, XOR is 0 if there are an even number of 1s and 1 if odd — so every row (data plus parity) always holds an even number of 1s. That invariant is what lets us rebuild any one lost block from the survivors:

RAID-4 analysis.

• Capacity: one disk per group goes to parity → (N−1)·B. Much cheaper than mirroring.
• Reliability: tolerates exactly one disk failure (reconstruct it); lose two and the data is gone.
• Sequential reads: use all data disks → (N−1)·S.

Sequential writes get a break called the full-stripe write full-stripe write The efficient RAID-4/5 write: when a whole stripe's worth of data is written at once, the RAID computes the new parity directly by XOR-ing the new blocks and writes all data + parity in parallel — no read of old values needed. Sequential writes hit this fast path. defined in ch. 38 — open in glossary : when a whole stripe is written at once, the RAID computes the new parity directly from the new blocks (no reads needed) and writes all data + parity in parallel — so sequential writes also reach (N−1)·S.

The small-write problem

Random reads spread across the data disks → (N−1)·R. Random writes are where parity RAID hurts. Overwriting a single block means its parity block must change too. The efficient way is subtractive parity: read the old data and old parity, then

That is 4 physical I/Os per logical write — read old data, read old parity, write new data, write new parity. (The alternative, additive parity, reads all the other blocks in the stripe instead; better only in small arrays.)

Worse, look at where those I/Os land. Two small writes to blocks 4 and 13 (★) touch data on Disks 0 and 1 — which could go in parallel — but both must read-and-write their parity blocks P1 and P3 (✚), and all parity lives on Disk 4:

The lone parity disk is a bottleneck that serializes every write — this is the small-write problem small-write problem In parity RAID, a small random write must read-modify-write both the data block AND the parity block (4 I/Os via the subtractive method). In RAID-4 all parity lives on one disk, so that disk becomes a bottleneck serializing every write; small-random-write throughput is stuck at ~R/2 and does not scale with disks. defined in ch. 38 — open in glossary . Since that disk does two I/Os per logical write, RAID-4’s random-write throughput is stuck at R/2, and — unlike every other number here — it does not improve as you add disks. (Latency: a read is T, a write is ~2T for the two reads then two writes.) RAID-5 (next) fixes this by refusing to pin parity to one disk.