Disks, SSDs and disk scheduling

Why it matters

A Postgres instance on a spinning disk serves about 150 random reads a second; on an NVMe drive, several hundred thousand. An SSD at 97 percent full crawls on writes for reasons the file system cannot see. The I/O scheduling and buffering lesson covers the page cache, writeback and the block layer; this lesson is the device below them.

The idea

Memory versus storage

Main memory (DRAM) is volatile, byte-addressed and fast: around 100 ns per access, at a few dollars per GB. Secondary storage is persistent, addressed in blocks (512-byte or 4 KB sectors, so one byte costs a whole block) and far slower: tens of microseconds for flash, milliseconds for a disk. In exchange it costs 1 to 2 cents per GB on hard disks and 5 to 10 cents on SSDs.

How a hard disk serves a request

A hard disk spins several platters at 7,200 rpm. Each surface holds concentric tracks of sectors; the tracks at one radius across all surfaces form a cylinder. A request pays seek time to reach the cylinder (3 to 10 ms), rotational latency until the sector passes under the head (half a rotation, 4.17 ms at 7,200 rpm) and transfer time for the bytes (20 µs for 4 KB at 200 MB/s). A random 4 KB read therefore costs about 8 ms, 100 to 200 per second, while sequential reads skip the first two steps and stream at 150 to 250 MB/s. That 100× gap is why append-only logs exist.

Inside an SSD

An SSD stores bits in NAND flash, read and written in pages of 4 to 16 KB. A page cannot be overwritten in place: it must be erased first, and erasure works only on erase blocks of hundreds of pages. The controller's flash translation layer (FTL) hides this by mapping each logical block address to whichever physical page holds it now; an overwrite goes to a fresh page, the old one becomes stale, and garbage collection later copies live pages out of mostly stale blocks and erases them. That copying is write amplification: several flash writes per host write, climbing steeply as the drive fills, which is why full SSDs get slow and drives keep spare capacity (over-provisioning). TRIM (discard, run weekly by fstrim) tells the drive which blocks the file system has freed, so the FTL stops copying dead data. Wear levelling spreads erases across blocks, since a cell survives only a few thousand erases. So random reads are cheap, random small writes cost erases and garbage collection, and the drive prefers large sequential writes.

NVMe

SATA offered one queue 32 deep, built for a single disk head. NVMe attaches flash to PCIe with up to 65,535 queues of 65,536 commands each, one per core in practice. A drive reaches its rated million IOPS only with many requests in flight; one thread issuing synchronous reads sees perhaps 10,000.

Disk scheduling algorithms

With several requests waiting on a hard disk, service order changes total arm movement. The classic example: requests for cylinders 98, 183, 37, 122, 14, 124, 65, 67, head at cylinder 53, cylinders 0 to 199.

1. 1

   FCFS

   Serve in arrival order; the arm swings across the whole disk.
2. 2

   SSTF

   Shortest seek time first: serve the closest pending cylinder. Far requests can starve.
3. 3

   SCAN

   The elevator: sweep to one end serving everything on the way, then reverse.
4. 4

   C-SCAN

   Sweep one way only, then jump back to the start, so waiting time is uniform.
5. 5

   LOOK and C-LOOK

   The same sweeps, but turn at the last pending request rather than the physical end.

Elevators were the disk default for decades. An SSD has no geometry, so seek ordering is wasted; what remains is merging, bounding latency and fair sharing.

Linux I/O schedulers today

The multi-queue block layer ships four schedulers, chosen per device in /sys/block/<dev>/queue/scheduler. none passes requests through. mq-deadline keeps requests sorted by sector with a deadline (500 ms for reads, 5 s for writes) after which a request jumps the queue: LOOK with a fairness bound. BFQ shares device time fairly between processes, good for desktops and slow disks. kyber targets latency on fast devices. For NVMe, none or mq-deadline is right: the drive has thousands of queue slots and its own scheduler, so host sorting only adds latency; cgroup I/O limits handle fairness between containers, and hard disks still gain from mq-deadline.

Trade-offs

Hard disks give the cheapest capacity, fine for sequential workloads and terrible for random ones. SSDs make random reads cheap but hide a write-and-erase machine; past about 90 percent full, or under small random writes, latency spikes follow. Host scheduling pays on disks and costs on NVMe, which wants parallelism.

In an interview

Say which device your numbers assume: "On the gp3 volume we get 3,000 IOPS, so a random read costs about a millisecond with queueing; the hot index has to fit in memory." On the classic algorithms: "SSTF minimises movement but can starve the far end; LOOK bounds waiting, which is why mq-deadline adds a deadline to a sorted queue."