§38.1–38.4Interface And RAID Internals … RAID-0: Striping

When we use a disk we sometimes wish it were faster (I/O is often the system bottleneck), sometimes bigger (data keeps growing), and sometimes more reliable (a dead disk with no backup means data gone for good). What if one technique could give us all three?

That technique is the Redundant Array of Inexpensive Disks (RAID) RAID Redundant Array of Inexpensive (or Independent) Disks: a technique that ties several disks into one logical disk to gain capacity, performance (parallelism), and/or reliability (redundancy). It presents the same block interface as a single disk, so it works transparently — you can swap a disk for a RAID without changing any software above it. defined in ch. 38 — open in glossary — coined in the late 1980s by Patterson, Gibson, and Katz at Berkeley. A RAID uses several disks in concert to build one disk that is faster (parallelism), bigger (capacity), and more reliable (redundancy lets it survive a disk failure and keep running as if nothing were wrong).

38.1 Interface And RAID Internals

The magic is that a RAID does all this transparently. From the file system’s point of view a RAID looks exactly like a single disk: a linear array of blocks you read and write. Internally it is a complex beast — but the software above never has to know.

A RAID is essentially a specialized computer: a microcontroller running firmware, DRAM to buffer blocks, sometimes non-volatile RAM to hold writes safely, and sometimes dedicated logic to compute parity. When a file system issues one logical I/O, the RAID figures out which disk(s) to touch and issues one or more physical I/Os. A mirrored RAID, for instance, turns every logical write into two physical writes.

38.2 Fault Model

To compare RAID designs we need a fault model — which failures a RAID is meant to survive. We start with the simplest: the fail-stop fail-stop fault model The simple RAID failure assumption: a disk is either working (all blocks readable/writable) or failed (permanently, wholly lost), and a failure is immediately and reliably detected. It deliberately ignores 'silent' faults like corruption and latent sector errors (deferred to the data-integrity chapter). defined in ch. 38 — open in glossary model. A disk is in exactly one of two states — working (every block readable and writable) or failed (permanently, wholly lost) — and critically, a failure is detected immediately (the controller knows at once when a disk dies).

This deliberately ignores harder, “silent” faults — disk corruption, or a single unreadable block on an otherwise-working disk (a latent sector error). Those are more realistic but much harder; we defer them to the data-integrity chapter and assume fail-stop for now.

38.3 How To Evaluate A RAID

We judge every RAID design along three axes:

• Capacity — given N disks of B blocks each, how many useful blocks do clients get? No redundancy gives N·B; mirroring (two copies) gives (N·B)/2; parity schemes land in between.
• Reliability — how many disk failures can the design tolerate (under the fail-stop model)?
• Performance — workload-dependent, so we first need workloads to reason about.

We consider two workloads workload The collective description of the processes/jobs running in a system; the more you know about it, the better your policy. defined in ch. 7 — open in glossary . A sequential workload reads/writes large contiguous regions (e.g. 1 MB starting at block x); the disk spends almost all its time transferring, at S MB/s. A random workload issues many small requests to scattered locations; the disk spends almost all its time seeking and rotating, at R MB/s. Because positioning dominates small requests, S ≫ R.

How different are S and R? Take a disk with a 7 ms average seek, 3 ms average rotation, and a 50 MB/s transfer rate. For a 10 MB sequential transfer we spend 7 + 3 ms positioning and 200 ms transferring:

Nearly the full 50 MB/s — the positioning cost is amortized away. For a 10 KB random transfer, positioning is unchanged but the transfer takes only ~0.195 ms:

So S/R ≈ 48 — sequential is roughly fifty times faster. Hold onto S and R; every RAID level below is scored in these units.

38.4 RAID Level 0: Striping

The first RAID level RAID level A named RAID design choosing a specific point in the capacity/reliability/performance trade-off space: RAID-0 (striping, no redundancy), RAID-1 (mirroring), RAID-4 (dedicated-parity), RAID-5 (rotated-parity). The 'level' naming comes from the 1988 Patterson/Gibson/Katz paper. defined in ch. 38 — open in glossary is not really a RAID at all — it has no redundancy — but striping striping RAID-0: spread the array's blocks round-robin across all disks with no redundancy. Perfect capacity (N·B) and best-case performance (all disks in parallel), but zero reliability — any one disk failure loses data. Serves as the performance/capacity upper bound for the other levels. defined in ch. 38 — open in glossary (RAID-0) is the performance and capacity upper bound, so it is worth understanding first. The idea: spread the array’s blocks across the disks in round-robin order. The blocks in one row form a stripe stripe The set of blocks at the same position across all disks of a striped array (one 'row'). Related: the chunk size sets how many consecutive blocks land on one disk before moving to the next. defined in ch. 38 — open in glossary ; the chunk size chunk size How many consecutive logical blocks a RAID places on one disk before moving to the next. Small chunks boost single-file parallelism but raise positioning time (max over all disks touched); large chunks reduce intra-file parallelism but lower positioning cost. Tuning it needs workload knowledge. defined in ch. 38 — open in glossary sets how many blocks land on a disk before moving to the next.

The mapping problem

Every RAID must solve the mapping problem mapping problem Given a logical block address, how does the RAID compute which physical disk and offset hold it? For simple striping with a one-block chunk it is just Disk = A % N, Offset = A / N (integer arithmetic). defined in ch. 38 — open in glossary : translate a logical block into a physical (disk, offset). For simple striping it is just two integer operations:

(integer arithmetic — 14 / 4 = 3, not 3.5). The last step of the walkthrough above traces block 14 → Disk 2, offset 3.

Evaluating RAID-0

Striping is the easy case on all three axes, and gives the numbers every other level is compared against:

• Capacity: perfect. All N·B blocks are useful — nothing is spent on redundancy.
• Reliability: zero — perfect in the bad way. There is no redundancy, so the loss of any single disk loses data.
• Performance: excellent. A single-block request has the latency of one disk (RAID-0 just forwards it). Steady-state throughput uses every disk in parallel: N · S for sequential, N · R for random.

These N·S / N·R figures are both the simplest to compute and the ceiling for the redundant levels ahead — mirroring (ch38.5) and parity (RAID-4/5) buy reliability by giving some of this performance and capacity back.