Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 38, Arpaci-Dusseau & Arpaci-Dusseau

Redundant Arrays of Inexpensive Disks (RAID)

A single disk is often too slow, too small, or too fragile. RAID [P+88] combines multiple disks into one transparent big disk — faster, larger, and (with redundancy) more reliable — without rewriting the host OS.

Crux: how to build a large, fast, reliable disk? What are the trade-offs?

Transparency enables deployment

Swap a SCSI disk for a SCSI RAID and nothing above changes. Deployability made RAID succeed.

Internals & fault model

A RAID presents a linear block array. Each logical I/O becomes one or more physical I/Os (level-dependent). Hardware RAIDs are mini-computers: MCU, DRAM, sometimes NVRAM and parity ASICs.

Fail-stop for this chapter: a disk works or is permanently lost, and failure is detectable. (Silent corruption / latent sector errors come later.)

Evaluate every design on capacity, reliability, and performance (latency of one request vs steady-state bandwidth under sequential vs random workloads; single-disk rates S ≫ R).

RAID-0: Striping

Round-robin chunks across disks (a stripe = one row). Mapping (chunk = 1 block): Disk = A % N, Offset = A / N. Larger chunk size trades intra-file parallelism for fewer seeks.

	RAID-0
Capacity	`N · B`
Reliability	0 failures
Seq / rand throughput	`N · S` / `N · R`

Upper bound on speed and space — no redundancy.

RAID-1: Mirroring

Keep two copies on different disks (layouts: RAID-10 vs RAID-01). Reads may pick either copy; writes must update both (in parallel).

	RAID-1 (mirror=2)
Capacity	`(N · B) / 2`
Reliability	1 for sure (up to `N/2` if lucky)
Seq R/W	≈ `(N/2) · S`
Random read	`N · R`
Random write	`(N/2) · R`

Consistent update

Crash mid multi-disk write can leave mirrors inconsistent. Log intent (often in NVRAM) then apply [DAA05].

RAID-4: Fixed parity

One parity disk per stripe; P = XOR of data blocks. Rebuild a lost disk by XORing the survivors. Capacity (N−1)·B; tolerates 1 failure.

Full-stripe write: compute P, write all data + P in parallel → (N−1)·S
Small write (subtractive): P_new = (C_old ⊕ C_new) ⊕ P_old → 2 reads + 2 writes. Parity disk bottleneck → ~R/2 (does not scale with N)

Quiz

Rank the sequence

1 / 1

Order the steps of a RAID-4 subtractive small write (top = first).

OrderDrag the handle to rearrange — top should be first.

1Write the new parity block
2Write the new data block
3Compute new parity: (C_old XOR C_new) XOR P_old
4Read the old data block and old parity block

Drag items into the correct order (or use ↑↓), then check.

RAID-5: Rotated parity

Same math as RAID-4, but parity rotates across disks → small writes can proceed in parallel across stripes → ~(N/4) · R. Dominates RAID-4 in the market (except workloads that are only huge writes).

Comparison (simplified)

	Cap	Faults	Seq	Rand read	Rand write
0	`N·B`	0	`N·S`	`N·R`	`N·R`
1	`N·B/2`	1+	`N/2·S`	`N·R`	`N/2·R`
4	`(N−1)·B`	1	`(N−1)·S`	`(N−1)·R`	`R/2`
5	`(N−1)·B`	1	`(N−1)·S`	`N·R`	`N/4·R`

Pick: speed only → 0; random I/O + reliability → 1; capacity + reliability → 5 (pay on small writes).

Interactive

Try: why RAID · levels 0/1 · parity 4/5 · which to pick.

Check your understanding

Quiz

RAID

1 / 6

RAID’s transparency means…

Pick an answer to see if you are right.

Coding challenges

Homework lab: raid.py

Use the OSTEP raid homework (raid.py).

Lab

Homework: file-raid / raid.py

0/4 started

Loading lab…

Summary

Goal	Lean toward
Max speed, no redundancy	RAID-0
Random I/O + simple reliability	RAID-1
Capacity + 1-disk tolerance	RAID-5 (watch small writes)

Also exists: RAID-6 / multi-fault codes, hot spares, reconstruction, software RAID, richer fault models [B+08].

Previous: Hard Disk Drives

Next: Files and Directories — the UNIX FS API.

Internals & fault model​

RAID-0: Striping​

RAID-1: Mirroring​

RAID-4: Fixed parity​

RAID-5: Rotated parity​

Comparison (simplified)​

Interactive​

Check your understanding​

Coding challenges​

Homework lab: raid.py​