RAID and Redundant Storage

A RAID array presents N physical disks to the operating system as one (or a few) logical volumes. The controller — implemented in hardware, firmware, or a software layer inside the OS — decides how to lay data across the physical disks and, in redundant levels, how to compute and store extra recovery information. From the file system's point of view, sitting atop the abstractions of Disk Structure and Geometry, a RAID volume just looks like a bigger, faster, or more durable disk; the striping, mirroring, and parity machinery is invisible above the block-device interface. Three primitive techniques combine to form the standard RAID levels. Striping divides a logical block address space into fixed-size chunks called stripe units, distributing consecutive stripe units round-robin across disks so that a large sequential access touches many disks in parallel — this is pure performance engineering with no redundancy. Mirroring stores an identical copy of every block on two (or more) disks, so a request can be served by either copy and a disk's failure loses no data, at the cost of doubling (or more) the physical capacity needed. Parity computes a checksum block — the bitwise XOR of corresponding blocks across a set of data disks — and stores it on a dedicated or rotating parity disk, so that if any single disk in the set fails, its content can be reconstructed by XOR-ing the survivors together. The key mathematical fact underlying parity RAID is that XOR is its own inverse: for blocks $D_1, \dots, D_k$ with parity $P = D_1 \oplus D_2 \oplus \cdots \oplus D_k$, losing any single $D_i$ can be recovered as

because XOR-ing a value with itself cancels it (`x ⊕ x = 0`) and XOR-ing with 0 is the identity. This single identity is the entire engine behind RAID 4, RAID 5, and (with a second, independent parity function) RAID 6.

RAID 0 — Striping, no redundancy

Data is divided into stripe units of size S and written round-robin across N disks. Logical block b maps to disk `b mod N`, offset `b div N` (in units of S). There is no parity and no duplication, so RAID 0 maximizes usable capacity ($N$ disks of capacity $C$ give $N \cdot C$ usable) and throughput (up to $N\times$ parallel bandwidth on large sequential transfers), but any single disk failure destroys the entire array, since every stripe unit is unique.

RAID 1 — Mirroring

Every logical block is written identically to two physical disks. Usable capacity is $C$ (half of $2C$ raw), but the array survives the loss of either disk in a mirrored pair, and reads can be load-balanced across both copies for roughly $2\times$ read throughput. Many systems generalize this to $N$-way mirroring or combine it with striping (RAID 10 / RAID 01) to get both parallelism and redundancy.

RAID 4 — Dedicated parity disk

$N$ disks hold data, one additional disk holds parity, where stripe $i$'s parity block is the XOR of the data blocks in stripe $i$ across all $N$ data disks. Usable capacity is $N \cdot C$ out of $(N+1)\cdot C$ raw. The dedicated parity disk becomes a bottleneck: every write to any data disk also requires an update to the same parity disk, serializing all writes through one drive.

RAID 5 — Rotating parity

RAID 5 fixes RAID 4's bottleneck by rotating which physical disk holds the parity block, stripe by stripe, so parity load is spread evenly across all $N+1$ disks. Usable capacity is identical to RAID 4: $N \cdot C$ out of $(N+1)\cdot C$ raw, tolerating exactly one disk failure.

RAID 6 — Double parity

RAID 6 stores two independent parity blocks per stripe (commonly one XOR parity and one Reed–Solomon-style "Q" parity over a Galois field), tolerating any two simultaneous disk failures. Usable capacity is $N \cdot C$ out of $(N+2)\cdot C$ raw. The following pseudocode captures the essential read/write/rebuild logic shared by parity-based RAID (4/5); RAID 6 is the natural extension with a second parity function. ``` // N data disks (0..N-1) indexed logically; parity disk index rotates per stripe for RAID 5, // is fixed (disk N) for RAID 4. function PARITY_DISK(stripe_index): if scheme == RAID4: return N // always the same physical disk else: // RAID5 return stripe_index mod (N + 1) // rotates function WRITE_BLOCK(stripe_index, data_disk, new_data): p_disk = PARITY_DISK(stripe_index) old_data = READ(data_disk, stripe_index) old_parity = READ(p_disk, stripe_index) new_parity = old_parity XOR old_data XOR new_data // update parity incrementally WRITE(data_disk, stripe_index, new_data) WRITE(p_disk, stripe_index, new_parity) // total I/O: 2 reads + 2 writes = 4 disk operations (the "RAID-5 write penalty") function READ_BLOCK(stripe_index, data_disk): if disk_is_healthy(data_disk): return READ(data_disk, stripe_index) else: // reconstruct from all surviving disks in the stripe (data + parity) result = 0 for each disk d in stripe_index's disk set, d != data_disk: result = result XOR READ(d, stripe_index) return result function REBUILD_FAILED_DISK(failed_disk, spare_disk): for stripe_index = 0 to LAST_STRIPE: recovered = READ_BLOCK(stripe_index, failed_disk) // uses XOR reconstruction path WRITE(spare_disk, stripe_index, recovered) mark spare_disk as healthy // cost: one full sequential read of every surviving disk, one full write of the spare ``` The small-write penalty is the crux of RAID 5's performance story: a single logical block write costs four physical I/Os (read old data, read old parity, write new data, write new parity), rather than the one I/O a plain disk write would cost. Large, full-stripe writes avoid this by computing parity directly from the new data across the whole stripe rather than reading old contents first — an optimization called a full-stripe write.

Capacity. With $N$ data disks of capacity $C$ each:

• RAID 0: usable $= N C$ (no overhead).
• RAID 1 (2-way mirror over $N$ pairs): usable $= N C$ out of $2NC$ raw, i.e., 50% efficiency independent of $N$.
• RAID 4/5: usable $= N C$ out of $(N+1)C$ raw; efficiency $\to 100\%$ as $N \to \infty$, but fault tolerance stays fixed at one disk.
• RAID 6: usable $= N C$ out of $(N+2)C$ raw; same asymptotic trend, tolerating two disk failures.

Throughput. For large sequential I/O, striping across $N$ (or $N{+}k$) disks yields up to $N\times$ (or $(N{+}k)\times$) the single-disk bandwidth, since independent disks transfer in parallel — this is the entire motivation for RAID 0 and a major side benefit of RAID 4/5/6/10. For small random writes, the picture differs sharply:

• RAID 0/1: one write costs 1 I/O (RAID 0) or 2 I/Os (mirrored write to both copies, RAID 1), each parallelizable, so latency stays near single-disk latency.
• RAID 4/5: a partial-stripe write costs 4 physical I/Os — read old data, read old parity, write new data, write new parity — because parity must be recomputed incrementally via

This is the small-write penalty, and it is the dominant reason parity RAID underperforms mirroring on write-heavy random workloads such as OLTP databases.

• RAID 6: analogous reasoning gives 6 physical I/Os per small write (two parities to read and rewrite instead of one).
• A full-stripe write (all $N$ data blocks of a stripe overwritten together) avoids reading old data entirely: parity is computed directly as the XOR of the $N$ new blocks, costing $N + 1$ (or $N+2$) I/Os for a whole stripe rather than $4N$ (or $6N$) — a large win for sequential or batched workloads, which is why log-structured and copy-on-write file systems pair well with parity RAID.

Correctness of parity reconstruction. The claim to verify: given $N$ data blocks $D_1,\dots,D_N$ and parity $P = D_1 \oplus \cdots \oplus D_N$, if any single $D_i$ is lost, it is uniquely recoverable from the rest plus $P$. Proof. XOR over bit vectors of fixed length forms an abelian group where every element is its own inverse ($x \oplus x = 0$) and $0$ is the identity ($x \oplus 0 = x$). XOR-ing $P$ with all surviving blocks:

Each $D_j$ for $j \neq i$ appears exactly twice (once from $P$'s definition, once from the explicit XOR) and cancels, leaving exactly $D_i$. This holds for any single missing operand, which is precisely why RAID 4/5 tolerate exactly one failed disk per stripe — losing two disks removes two distinct unknowns from one equation, which is underdetermined and unrecoverable with single parity.

Why RAID 6 tolerates two failures. RAID 6 adds a second, algebraically independent parity function $Q$ (typically a weighted sum in a Galois field $GF(2^8)$, using distinct nonzero coefficients per disk). With two independent linear equations,

losing any two blocks $D_i, D_j$ leaves a $2\times2$ linear system in the two unknowns that is solvable exactly when the coefficient matrix is invertible — which the Reed–Solomon-style coefficient choice guarantees for all disk-index pairs. This is the same reasoning as [Reed–Solomon error-correcting codes]: two independent syndromes let you localize and solve for two erasures.

Rebuild time and the reliability trap. Rebuilding a failed disk in RAID 5 requires reading every surviving disk in full to reconstruct the lost data via the parity identity, then writing the spare. Rebuild time scales with disk capacity and is bounded below by sequential-read bandwidth: for a $T$-terabyte drive at sustained rate $R$ MB/s, rebuild takes roughly $T / R$ (hours, for modern multi-terabyte drives). During this window, the array runs in a degraded state with zero remaining redundancy (RAID 5) — a second failure or even an unrecoverable read error on any surviving disk during rebuild causes data loss. As drive capacities have grown far faster than sustained transfer rates, rebuild windows have stretched from minutes to many hours, making this a first-order reliability concern, not a footnote — the practical reason RAID 6 (tolerating a failure during rebuild) and RAID 10 (rebuild is a fast single-disk copy, not an $N$-disk XOR scan) have displaced plain RAID 5 in most modern deployments.

Honesty about trade-offs. RAID is not a backup: it protects against disk hardware failure, not against accidental deletion, file system corruption, ransomware, or a controller bug that writes bad data to all disks simultaneously. RAID also does not protect against silent data corruption (bit rot) unless paired with checksumming file systems (e.g., ZFS, Btrfs) that can detect which copy is corrupt — plain RAID 5/6 parity alone can detect a mismatch but cannot always tell which of $N{+}1$ disks is the culprit without an extra checksum per block.

Consider a RAID 5 array with $N = 3$ data disks plus 1 rotating parity disk, storing one stripe of 8-bit blocks:

Step 1 — compute parity at write time: ``` D0 1101 0011 D1 XOR 0110 1010 -------------------- = 1011 1001 D2 XOR 1011 0100 -------------------- P = 0000 1101 ``` So parity `P = 0000 1101` is stored on Disk 3 for this stripe. Step 2 — Disk 1 fails. The array is now degraded; any read targeting Disk 1's blocks must reconstruct on the fly using `READ_BLOCK` from the pseudocode above: ``` recovered = D0 XOR D2 XOR P ``` Compute: ``` D0 1101 0011 D2 XOR 1011 0100 -------------------- = 0110 0111 P XOR 0000 1101 -------------------- recovered = 0110 1010 ``` This matches `D1 = 0110 1010` exactly — the reconstruction is correct, confirming the group-cancellation argument from the correctness section with real bits. Step 3 — a write arrives for `D0` while Disk 1 is still failed, changing `D0` to `1111 0000`. In a healthy array this would cost 4 I/Os (read old `D0`, read old `P`, write new `D0`, write new `P`); in degraded mode the controller must instead reconstruct the current logical value of every block in the stripe from survivors, apply the update, and recompute parity directly from all logical values — a strictly more expensive degraded write, illustrating why performance craters further during rebuild, on top of the lost redundancy. Step 4 — rebuild. A spare disk replaces failed Disk 1. For every stripe in the array, the controller performs exactly the reconstruction of Step 2, then writes the result to the spare. For an array with $M$ stripes, this is $O(M)$ full-stripe reads across all surviving disks plus $O(M)$ writes to the spare — i.e., a complete sequential scan of the array's logical capacity, which is why rebuild time tracks disk size, not just array size.

RAID emerged from a simple economic and reliability insight at UC Berkeley: cheap, small disks connected redundantly could out-perform and out-cost expensive mainframe-class drives, provided the redundancy math was sound.

RAID underlies nearly every layer of durable storage infrastructure. Database servers use RAID 10 for write-heavy transactional workloads where the 4x small-write penalty of RAID 5 is unacceptable. Large-scale file servers and NAS appliances default to RAID 5 or RAID 6 to balance capacity against fault tolerance for mostly-read workloads. Cloud object storage systems (the logical descendants of RAID's ideas) generalize parity across whole machines rather than disks — erasure coding schemes in systems like distributed object stores are direct mathematical generalizations of RAID 6's dual-parity idea to tolerate multiple node failures across a data center. Hardware RAID controllers with battery-backed write caches, software RAID implementations built into operating system kernels, and checksummed file systems that layer integrity verification atop RAID's fault tolerance are all direct engineering descendants of the ideas developed here. The same striping-versus-redundancy trade-off reasoning reappears whenever engineers design any distributed, fault-tolerant storage system, making RAID the essential mental model before studying replication and erasure coding at data-center scale.

Ask the tutor: How would erasure coding across an entire data center generalize the RAID 6 dual-parity idea to survive multiple machine failures?