Disks, SSDs & Disk Scheduling

Think of the memory hierarchy as a set of shelves, each one bigger and slower than the one above it. At the top the CPU registers and caches answer in about a nanosecond; main memory answers in roughly a hundred. Then comes a cliff. A read that misses memory and has to reach a spinning hard disk can take around ten milliseconds — and ten milliseconds is not "a bit slower", it is on the order of a hundred thousand times slower than RAM. A solid-state drive narrows the gap enormously, to tens or hundreds of microseconds, but it is still an order of magnitude or two below memory.

To feel the scale, borrow the old trick of turning nanoseconds into human time. If a CPU cache hit were one second, a main-memory access would be a couple of minutes, an SSD read would be a day or two, and a single seek on a hard disk would be the better part of a year. That is the mountain the OS is climbing every time your program touches persistent storage, and it explains almost everything the storage stack does.

• ▸Storage is where the memory hierarchy bottoms out: huge capacity, permanence, and brutal latency compared to RAM.
• ▸Because a device is so slow, the CPU must never simply sit and wait for it — the OS overlaps I/O with other work (this is why we schedule).
• ▸Because a device is so slow, the OS caches aggressively in RAM (the page cache) so most reads never reach the disk at all.
• ▸Because a device is so slow, the *order* in which pending requests are served can change total time dramatically — the heart of this chapter.

A hard disk drive is one of the last pieces of fast-moving mechanical engineering left in a modern computer. Inside the sealed case, one or more rigid platters coated in magnetic material spin at a constant speed — commonly 7200 revolutions per minute in a desktop drive. A read/write head floats a fraction of a micron above each surface on the end of an arm, and the arm pivots in and out to reach different distances from the centre. Data is stored by magnetising tiny regions of the surface as the platter rushes past the head.

Platter

A rigid magnetic disk that spins; a drive stacks several, usually with a head on each surface.

Track

One concentric ring of data on a platter surface; the head reads a whole track as the platter rotates under it.

Sector

The smallest addressable chunk on a track — historically 512 bytes, now typically 4 KB (the physical unit of I/O).

Cylinder

The set of same-radius tracks across all platters, reachable without moving the arm — cheap to access together.

Head & arm

The read/write element and the actuator that pivots it to the right track; moving it is the slow, mechanical part.

The reason a hard disk is slow is that reaching a specific sector is a three-part physical dance, and two of those parts involve waiting for mass to move. First the arm must swing until the head sits over the right track: that is the seek time, and it is the killer — a few milliseconds for a full-width swing, because you are physically accelerating and stopping a mechanical arm. Second, even once the head is on the right track, you must wait for the platter to rotate until the sector you want comes around under the head: that is rotational latency, and on a 7200 RPM drive one full rotation takes about 8.3 ms, so on average you wait half of that, roughly 4 ms. Only then comes the third part, transfer time — actually streaming the bytes off the surface — which is comparatively quick.

Put numbers on it. A drive that streams sequentially at 150 MB/s can read a megabyte in well under 10 ms once the head is in place. But if you ask it for 256 scattered 4 KB blocks, each one costs a seek plus half a rotation before any bytes flow — call it 8 ms of pure waiting per request, over 2 seconds of nothing but arm-swinging and spinning for the same one megabyte of data. The disk was never "reading" for most of that time; it was waiting for metal to arrive. This single asymmetry is why the OS works so hard to turn random access into sequential access, and why the next few sections exist at all.

How does software name a particular sector? The original scheme, CHS, addressed a sector by its physical coordinates: which Cylinder, which Head (that is, which platter surface), and which Sector around the track. It was honest about the geometry, and that was exactly its problem — software had to know the drive’s physical shape, and real shapes stopped being uniform once manufacturers packed more sectors onto the longer outer tracks than the short inner ones.

Modern drives hide all of that behind Logical Block Addressing. LBA presents the entire disk as one long, flat array of fixed-size blocks numbered 0, 1, 2, up to N. The operating system asks for "block 4,192,043" and the drive’s own controller translates that number into whatever physical cylinder, head, and sector currently holds it. The geometry becomes the drive’s private business; the OS just sees a numbered array.

CHS (Cylinder–Head–Sector)

The old physical address triple; exposed the drive’s real geometry and did not survive variable track sizes.

LBA (Logical Block Addressing)

The modern scheme: the disk is one flat array of numbered blocks; the drive maps each number to real hardware.

Block / logical block

The fixed-size unit the OS reads and writes (512 B historically, 4 KB on modern drives); the atom of disk I/O.

This flat, numbered array is one of the most important abstractions in the whole storage stack, because it is the surface that everything above builds on. The file system does not think in platters and heads; it thinks "this file occupies blocks 812, 813, 814, and 990". Whether those blocks live on a spinning HDD, an SSD, a RAID array, or a network volume, the interface is identical: read block N, write block N. That uniformity is exactly why the same file system code runs unchanged across wildly different hardware — and it is the abstraction the next three chapters on file systems assume from the first line.

When several processes have I/O outstanding, the OS holds a queue of pending block requests for each drive. Because seek time dominates on an HDD, the *order* in which it services that queue changes the total arm travel — and therefore the total time — enormously. Disk scheduling is the policy that picks the order. We will use one running example throughout: a drive with cylinders 0 to 199, the head currently resting at cylinder 53, and a queue of requests for cylinders 98, 183, 37, 122, 14, 124, 65, 67.

FCFS

First-come, first-served: service requests in arrival order. Perfectly fair, but the arm can whipsaw across the disk.

SSTF

Shortest-seek-time-first: always serve the nearest pending cylinder. Fast on average, but can starve far-away requests.

SCAN (elevator)

The arm sweeps in one direction serving everything in its path, reaches the end, then sweeps back — like a lift.

C-SCAN

Circular SCAN: sweep one way, then jump straight back to the start and sweep the same way again — more uniform waits.

LOOK / C-LOOK

Practical SCAN/C-SCAN that reverse at the last *request* instead of travelling to the physical end of the disk.

Queue: 98, 183, 37, 122, 14, 124, 65, 67

FCFS  (arrival order)
  53→98→183→37→122→14→124→65→67
   45 +85 +146+ 85+108+110+ 59+ 2   = 640

SSTF  (always nearest pending)
  53→65→67→37→14→98→122→124→183
   12 + 2 +30 +23 +84 +24 +  2+ 59  = 236

SCAN  (elevator: sweep up to 199, then back down)
  up:   53→65→67→98→122→124→183→199   = 146
  down: 199→37→14                     = 185
  total                               = 331

For reference, on the same queue:
  LOOK   (up to 183, then back to 14)        = 299
  C-SCAN (up to 199, wrap to 0, up to 37)    = 382
  C-LOOK (up to 183, jump to 14, up to 37)   = 322

Read the arithmetic and the trade-offs jump out. FCFS is scrupulously fair but travels 640 cylinders because it obeys arrival order blindly — 183 then 37 alone throws the arm most of the way across the disk and back. SSTF cuts that to 236 by always grabbing the closest request, which is why greedy nearest-first feels so fast. But SSTF has a dark side: if requests keep arriving near the head, a request stranded out at cylinder 14 can wait indefinitely — that is starvation.

SCAN, the elevator algorithm, is the classic answer to starvation. Like a lift that finishes going up before it comes down, the arm sweeps in one direction serving every request it passes, then reverses. No request waits longer than two full sweeps, so nothing starves, and the total (331 here) sits comfortably between FCFS and SSTF. The refinements are small but real: C-SCAN sweeps only one way and jumps back to the start, which makes waiting times more uniform across the disk (a plain SCAN slightly favours the middle); and LOOK and C-LOOK simply refuse to trudge out to cylinder 0 or 199 when the last real request is at 14 or 183 — which is why LOOK’s 299 beats SCAN’s 331 on the same queue. Real systems have long used LOOK-family policies rather than textbook SCAN.

A solid-state drive throws away the platters and the arm entirely and stores bits in NAND flash memory cells. With no mass to move, the whole seek-and-rotate cost model of the previous sections evaporates: any location is reachable in roughly the same tens of microseconds, and random reads become nearly as cheap as sequential ones. That alone is why SSDs feel transformative. But flash comes with its own hard constraint that shapes everything about how the drive behaves — and it is not the one people expect.

Flash is organised into pages (the unit you read and write, typically 4–16 KB) grouped into much larger erase blocks (often hundreds of pages). The awkward rule is this: you can read any page freely, and you can write a page — but only if it is already erased, and you cannot erase a single page. Erasing happens only a whole block at a time. So flash cannot overwrite data in place the way a disk sector can. To change one page inside a full block, the drive must write the new version somewhere already-erased and mark the old copy dead, later reclaiming whole blocks in bulk.

Page

The unit flash reads and writes — a few KB. You can write a page only if it is currently erased.

Erase block

A large group of pages; erasing is only possible for a whole block at once — the root of flash’s complexity.

FTL (Flash Translation Layer)

Firmware inside the SSD that maps logical block numbers to physical pages, hiding erase-before-write from the OS.

Wear levelling

Spreading writes across all blocks so no cell wears out early — flash cells survive only a limited number of erases.

Garbage collection

Background work that consolidates still-live pages and erases blocks full of dead data to reclaim free space.

TRIM

A command letting the OS tell the SSD which blocks a deleted file no longer needs, so GC can skip copying dead data.

The Flash Translation Layer is the firmware that makes all of this invisible. It keeps a map from logical block numbers (the flat LBA array the OS still thinks it is talking to) to the physical pages that currently hold them. When you "overwrite" block 900, the FTL quietly writes the new data to a fresh erased page and repoints the map, so the OS never sees the erase-before-write rule at all. On top of that mapping the FTL does two more essential jobs: wear levelling, which deliberately spreads writes so that hot data does not burn out one block while others sit idle (flash cells die after a finite number of erases), and garbage collection, which in the background gathers the still-live pages out of mostly-dead blocks and erases those blocks to refill the free pool.

This is why the two directions are so asymmetric on an SSD. A read is a simple map lookup and a page fetch — fast and uniform. A write may trigger a cascade: find an erased page, update the map, and eventually cause garbage collection to copy live pages and erase blocks elsewhere. That hidden copying means the drive can physically write more bytes than you asked it to — write amplification — which both slows sustained writes and consumes the finite erase budget faster. TRIM helps by letting the OS tell the drive "this block belongs to a file I deleted", so garbage collection does not waste effort preserving data nobody wants.

The arrival of SSDs quietly demoted one of the proudest ideas in this chapter. The elevator algorithms exist to minimise arm travel — but an SSD has no arm. Reordering requests by logical block number no longer shortens any physical path, because "nearby" block numbers are not physically nearer on flash. So on an SSD, the elaborate seek-minimising schedulers buy almost nothing, and the CPU time spent sorting the queue can even cost more than it saves. What the OS wants from a fast SSD is mostly to get out of the way.

Linux reflects this directly in its I/O schedulers. For a spinning disk you still want a seek-aware, fairness-aware policy — mq-deadline (which bounds how long any request can wait) or BFQ (which shares bandwidth fairly between processes and keeps the desktop responsive). For a fast NVMe SSD the common choice is literally none: submit requests straight to the device and let the drive’s own parallelism sort it out.

That parallelism is the other big shift. Old drives sat behind a single request queue — one arm, one thing at a time. A modern NVMe SSD has many independent flash channels and is built for deep, parallel request queues, so Linux moved to a multi-queue block layer (blk-mq) with a queue per CPU feeding the device. The bottleneck is no longer "when does the arm get there"; it is "keep enough requests in flight to saturate the flash". Scheduling for throughput now means concurrency, not ordering.

• ▸On HDDs, request ordering (SCAN/LOOK, mq-deadline, BFQ) still matters a great deal — seek time is real.
• ▸On SSDs, ordering barely helps; the "none" scheduler plus deep parallel queues (blk-mq / NVMe) is usually best.
• ▸Partition and file-system alignment to the SSD’s erase-block/page size avoids splitting one logical write across two physical blocks (which doubles the erase work).
• ▸Either way, the biggest win is still upstream in the OS: the page cache serving reads from RAM so the device is never asked at all.

A single drive is one point of failure and one source of bandwidth. RAID — a Redundant Array of Independent Disks — combines several physical drives into one logical volume to buy speed, safety, or both. Two primitives do all the work. Striping spreads consecutive blocks across drives so several can be read or written at once, multiplying bandwidth. Mirroring keeps identical copies on more than one drive so that if one dies the data survives. Parity is the clever compromise: store extra check information so the array can rebuild a lost drive’s contents without paying for a full second copy.

RAID 0 (striping)

Blocks striped across drives for maximum speed and full capacity — but zero redundancy; one drive lost loses everything.

RAID 1 (mirroring)

Every block written to two drives. Survives a drive failure and reads fast, at the cost of half your capacity.

RAID 5 (striping + parity)

Data plus a rotating parity block across three or more drives; survives any one failure with only one drive’s worth of overhead.

RAID 10 (1+0)

Mirrored pairs, then striped across them: the speed of striping with the safety of mirroring — the priciest common choice.

The point is not to memorise level numbers but to see the axis they sit on: performance versus redundancy versus cost, pick your balance. RAID 0 is pure performance and pure risk. RAID 1 is pure safety at double the disks. RAID 5 tries to have both cheaply and mostly succeeds, though rebuilding a failed drive is slow and stresses the survivors. RAID 10 is what databases often run on when they can afford it. And a caution that outlives every level: RAID protects against a drive dying, not against a bad deploy deleting your data — RAID is not a backup.

Everything in this chapter converges on one rule you will use for the rest of your career: sequential access beats random access, and it beats it by a lot. On an HDD it is the difference between one seek and a thousand; on an SSD it is the difference between clean large writes and a storm of small ones that inflate garbage collection and write amplification. This is why serious data systems bend over backwards to turn random writes into sequential ones.

• ▸A write-ahead log (WAL) appends every change to the end of one file before touching the real data — turning random updates into a sequential append, and giving crash recovery for free. Postgres, MySQL/InnoDB, and SQLite all do this.
• ▸Log-structured merge trees (LSM), behind Cassandra, RocksDB, and LevelDB, buffer writes in memory and flush them as large sequential runs, then merge in the background — random writes become sequential batches.
• ▸Databases align their page size to the device block size (commonly 4 KB or a multiple) so one logical page is one physical I/O, never a torn write across two blocks.
• ▸On SSDs, over-writing in place still means erase-later work under the hood, so append-only and copy-on-write designs are gentle on the flash as well as fast.

When storage is the suspect, measure before you guess — and on Linux the first tool is iostat. It shows per-device throughput, how long requests are waiting, and how busy each device is, which tells you at a glance whether a slow service is actually I/O-bound and, if so, on which device.

$ iostat -x 1
Device      r/s      w/s    rkB/s     wkB/s   r_await  w_await   aqu-sz  %util
nvme0n1   120.0   3400.0   4800.0  210000.0     0.08     0.42     1.40   18.3
sda        15.0    240.0    600.0    9800.0     6.20    14.80     3.90   98.6

Read that the way you would in an incident. The NVMe drive is barely breathing: 18% utilised, sub-millisecond waits, moving 200-plus MB/s of writes without strain. The spinning sda is pinned at 98.6% utilisation with a queue backing up and write waits of nearly 15 ms — that disk is the bottleneck, and no amount of CPU or memory tuning will help until the workload moves off it or its random writes are turned sequential. The high %util and await, not the throughput number, are the tells; a fast device can be saturated at a low MB/s if the access pattern is punishing it.