9. Storage Systems

Every abstraction built so far — processes, address spaces, pages evicted to a backing store — eventually rests on a device that remembers things after the power goes out, and that device is thousands to millions of times slower than RAM. This chapter opens up secondary storage: the physical structure of rotating disks and flash, the algorithms the kernel uses to order requests, and the redundancy schemes that turn unreliable devices into storage you can trust. It matters because storage is where most systems actually spend their time waiting, and because the right mental model for a hard disk is almost exactly the wrong one for an SSD.

<a id="91-secondary-storage-structure"></a>

9.1 Secondary Storage Structure

This section covers the hardware the operating system must drive: how a magnetic disk turns a linear block number into a mechanical operation, how flash differs so profoundly that it needs a translation layer of its own, how devices attach to the machine, and what "formatting" a disk actually writes.

Magnetic Disk Geometry

Theory

A hard disk drive is the last mechanical component in a modern computer, and nearly everything odd about disk performance follows from that single fact. Understanding its geometry is not nostalgia: it explains why disk scheduling algorithms exist, why file systems try to keep related blocks close together, and why the performance model of an SSD had to be rebuilt from scratch.

The physical construction is a stack of rigid platters coated in magnetic material, spinning together on one spindle at a constant rate — 5,400, 7,200, 10,000, or 15,000 revolutions per minute. Each platter surface is read by its own head, and all the heads are mounted on a single arm assembly that moves in and out as one unit. That last detail is important: the heads cannot be positioned independently, so at any instant all of them sit over the same radius.

The surface is organised into concentric rings called tracks, each divided into sectors — the smallest unit the device can read or write, historically 512 bytes and now typically 4,096 bytes. The set of tracks at the same radius across all surfaces forms a cylinder, which is the natural unit of locality: data in one cylinder is reachable by switching heads electronically, with no arm movement at all.

Three delays compose every disk access, and they differ by orders of magnitude:

1. Seek time — moving the arm to the correct cylinder. Mechanical, and the dominant cost: typically 3–12 ms average, with a short "track-to-track" seek near 0.5 ms.
2. Rotational latency — waiting for the desired sector to rotate under the head. On average, half a revolution. At 7,200 RPM a revolution takes 60/7200 s = 8.33 ms, so average latency is about 4.17 ms.
3. Transfer time — the actual data movement, once the head is in the right place. Fast: at 200 MB/s, a 4 KB sector takes about 20 microseconds.

Compare the numbers. Positioning costs milliseconds; transfer costs microseconds. A random 4 KB read spends roughly 99.8% of its time getting ready to read. This single asymmetry is the origin of nearly every storage optimisation ever devised: read ahead, batch, order requests to reduce arm motion, and above all prefer sequential access.

Because outer tracks are physically longer than inner ones, modern drives use zone bit recording: outer zones hold more sectors per track than inner zones. A consequence is that sequential throughput is genuinely higher at the start of a disk (outer edge) than at the end, often by a factor of two.

The old CHS addressing scheme (cylinder, head, sector) exposed this geometry to software. It is gone. Drives now present logical block addressing (LBA): a flat array of blocks numbered 0 to N-1, which the drive maps internally to physical locations. LBA is a mercy — geometry varies by zone and bad sectors get remapped — but it also means the OS can only approximate physical locality. The one reliable heuristic that survives is that nearby LBAs are usually nearby physically.

The analogy is a vinyl record player where the needle must be lifted and repositioned by hand. Moving the arm to another groove is slow; waiting for the right part of the groove to come around is slow; reading once you are there is instant. If you had a hundred snippets to play, you would sort them by groove position rather than take them in the order requested — which is exactly what Section 9.2 is about.

Example

   HARD DISK GEOMETRY (side view and top view)

   SIDE VIEW                              TOP VIEW OF ONE SURFACE
                                            ______________
    ====================  platter 0        /   ________   \
    --> head 0                            |   /  ____  \   |
    ====================  platter 1       |  |  / __ \  |  |   <- track
    --> head 1                            |  | | |  | | |  |
    ====================  platter 2       |  | | |()| | |  |   <- spindle
    --> head 2                            |  |  \ __ /  |  |
         |                                |   \  ____  /   |
     ARM ASSEMBLY (all heads move          \   ________   /
     together, one radius at a time)        \______________/

                                          A track is cut into SECTORS:
   CYLINDER = the same track number         [ s0 ][ s1 ][ s2 ][ s3 ]...
   on every surface. Reachable by
   switching heads: NO seek needed.

   THE THREE DELAYS, TO SCALE (7,200 RPM drive, 4 KB read)

   seek        |###################################|  ~4.0 ms   (mechanical)
   rotation    |#################################|    ~4.17 ms  (mechanical)
   transfer    |#|                                     ~0.02 ms  (electronic)
                                                       --------
                                              total    ~8.2 ms

   Positioning is ~99.8% of a random 4 KB read.

# Modelling a disk access, and the sequential-vs-random gulf.

RPM              = 7200
AVG_SEEK_MS      = 4.0                    # average arm movement
TRACK_SEEK_MS    = 0.5                    # adjacent cylinder
TRANSFER_MB_S    = 200.0

rotation_ms      = 60_000 / RPM           # 8.33 ms for one full revolution
avg_rot_ms       = rotation_ms / 2        # on average, half a turn: 4.17 ms

def access_ms(bytes_read, seek_ms):
    transfer_ms = (bytes_read / (TRANSFER_MB_S * 1e6)) * 1000
    return seek_ms + avg_rot_ms + transfer_ms

# 1,000 random 4 KB reads: full seek + half rotation, every time.
random_total = 1000 * access_ms(4096, AVG_SEEK_MS)

# 1,000 sequential 4 KB blocks = one 4 MB read: pay positioning ONCE.
seq_total = access_ms(4096 * 1000, AVG_SEEK_MS)

print(f"random     : {random_total:8.1f} ms")   # random     :   8187.1 ms
print(f"sequential : {seq_total:8.1f} ms")      # sequential :     28.6 ms
print(f"ratio      : {random_total/seq_total:8.1f}x")  # ratio  :    285.8x

# Effective throughput tells the same story from the other side.
print(f"random  MB/s: {4096*1000/1e6 / (random_total/1000):.2f}")  # ~0.50 MB/s
print(f"seq     MB/s: {4096*1000/1e6 / (seq_total/1000):.2f}")     # ~143 MB/s

# Inspect real geometry and behaviour (Linux).
lsblk -o NAME,ROTA,SIZE,PHY-SEC,LOG-SEC,MODEL
# ROTA=1 means rotational (HDD); PHY-SEC 4096 with LOG-SEC 512 is "512e"

sudo hdparm -I /dev/sda | grep -Ei 'rotation|sector|model'
sudo smartctl -a /dev/sda | grep -Ei 'rotation rate|sector size'

# Sequential vs random, measured rather than assumed.
sudo hdparm -t /dev/sda                    # sequential read throughput
sudo fio --name=rand --filename=/dev/sda --rw=randread --bs=4k \
         --direct=1 --runtime=10 --time_based --readonly
# An HDD gives ~100-200 IOPS here; an SSD gives 100,000+. Same command.

Key takeaways

• A disk access costs seek time plus rotational latency plus transfer time; the first two are mechanical and dominate everything else.
• Average rotational latency is half a revolution: 60,000/RPM/2 milliseconds (4.17 ms at 7,200 RPM).
• A cylinder is the set of same-radius tracks across all surfaces; staying inside one cylinder avoids seeking entirely.
• Sequential access can beat random access by two orders of magnitude on the same drive — the difference is positioning, not bandwidth.
• Drives expose flat LBA rather than CHS, so software can only approximate physical locality; the surviving rule is that nearby LBAs are usually nearby.
• Zone bit recording puts more sectors on outer tracks, making the outer edge of a disk measurably faster.

🧪 Practice

1. A 10,000 RPM drive has 5 ms average seek and transfers at 150 MB/s. Compute the average time for a random 4 KB read, and for a sequential 1 MB read.
2. A workload issues 200 random 8 KB reads per second to a 7,200 RPM drive with 4 ms average seek. Is the drive keeping up? Show the arithmetic, then state what has to change if it is not.
3. Interview-style: "Why does copying one 1 GB file take far less time than copying 250,000 4 KB files totalling 1 GB, on the same disk?" Hint: count how many times positioning is paid in each case, and add metadata updates per file.

Solid-State Drives

Theory

A solid-state drive stores bits as trapped charge in floating-gate transistors. There is nothing to move, so the seek and rotation terms of the previous topic simply vanish — a random read costs the same as a sequential one, roughly 50–100 microseconds on SATA and 20–80 microseconds on NVMe. If that were the whole story, SSDs would be "disks, but fast" and this topic would be one paragraph.

It is not the whole story, because NAND flash has three constraints that no rotating disk ever had.

First: the read/write/erase asymmetry. Flash is organised into pages (typically 4–16 KB) grouped into blocks (typically 128–512 pages, so a few megabytes). You can read a page. You can program (write) a page, but only if it is currently erased. You cannot overwrite a page in place — and erasure works only at whole-block granularity. So changing 4 KB inside a full block means: read the block elsewhere, erase it, rewrite it. This "read-modify-erase-write" asymmetry is the central awkwardness of flash, and it is what the Flash Translation Layer (next topic) exists to hide.

Second: wear. Each erase damages the oxide layer slightly. A block tolerates a finite number of program/erase (P/E) cycles before it stops holding charge reliably. The count depends on how many bits are packed into a cell:

Type	Bits/cell	Voltage levels	Typical P/E cycles	Character
SLC	1	2	50,000–100,000	Fast, durable, expensive
MLC	2	4	3,000–10,000	Balanced, now mostly enterprise
TLC	3	8	1,000–3,000	The consumer mainstream
QLC	4	16	100–1,000	Cheap, dense, slow writes, read-heavy use

More bits per cell means more voltage levels to distinguish in the same physical window, which makes reads slower, writes much slower, and endurance worse. This is a density-versus-everything-else trade, and it is why a cheap large SSD can be slower at sustained writes than a hard disk once its cache is exhausted.

Third: asymmetric and variable latency. A read takes tens of microseconds; a program takes hundreds; an erase takes milliseconds. Because erases are triggered by background garbage collection, a write can occasionally be stuck behind one, which is why SSD latency distributions have a long tail even though their averages are excellent. Tail latency, not average latency, is what wakes people at night.

Against these constraints, flash offers something rotating media never could: internal parallelism. A drive contains many dies across several channels, all of which can be busy at once. A single outstanding request uses a small fraction of the device. Getting an SSD's advertised IOPS requires many concurrent requests — queue depth is a first-class performance parameter, which was never true of a single-armed disk.

The analogy is a whiteboard divided into panels, written in permanent marker. Reading any panel is instant. Writing on a blank area is quick. But changing one word means erasing an entire panel — and each panel survives only so many wipes before it goes grey and stops taking ink.

Example

   NAND FLASH ORGANISATION AND THE THREE OPERATIONS

   DIE
    +--------------------------------------------------+
    |  BLOCK 0 (erase unit, ~4 MB)                      |
    |   +--------+--------+--------+ ... +--------+     |
    |   | page 0 | page 1 | page 2 |     | page N |     |  page = read/program
    |   | 16 KB  | 16 KB  | 16 KB  |     | 16 KB  |     |         unit
    |   +--------+--------+--------+ ... +--------+     |
    |  BLOCK 1 ...                                      |
    +--------------------------------------------------+

   OPERATION    GRANULARITY     TYPICAL TIME    NOTES
   read         page            25-100 us       cheap, repeatable
   program      page            200-1500 us     only onto an ERASED page
   erase        BLOCK           2-10 ms         resets a few MB at once

   WHY IN-PLACE OVERWRITE IS IMPOSSIBLE

   want: change 4 KB inside a full block
     naive:  read whole block -> erase block (ms!) -> rewrite whole block
             = megabytes of work and one P/E cycle for a 4 KB change
     real:   write the new data to a fresh erased page ELSEWHERE and
             remap the address. (This is the FTL -- see the next topic.)

   PARALLELISM: ONE REQUEST USES ALMOST NONE OF THE DEVICE

   channel 0 -> [die][die]      queue depth 1  : one die busy, ~7% utilised
   channel 1 -> [die][die]      queue depth 32 : most dies busy
   channel 2 -> [die][die]      => IOPS scale with CONCURRENCY, not clock
   channel 3 -> [die][die]

# Endurance arithmetic: how long does a TLC drive actually last?

CAPACITY_GB      = 1000
PE_CYCLES        = 1500        # TLC
WRITE_AMP        = 2.5         # host writes vs actual flash writes (see FTL)
HOST_WRITES_GB_D = 40          # a fairly heavy desktop workload

total_flash_writes_gb = CAPACITY_GB * PE_CYCLES        # ideal, perfect wear levelling
effective_host_gb     = total_flash_writes_gb / WRITE_AMP
days                  = effective_host_gb / HOST_WRITES_GB_D

print(f"endurance (TBW): {effective_host_gb/1000:.0f} TB")   # 600 TB
print(f"lifetime       : {days/365:.1f} years")              # 41.1 years

# The same drive under a write-heavy database workload:
for gb_per_day in (40, 200, 1000):
    print(gb_per_day, "GB/day ->",
          round(effective_host_gb / gb_per_day / 365, 1), "years")
# 40 GB/day -> 41.1 years | 200 -> 8.2 years | 1000 -> 1.6 years
# Wear is a workload property, not a drive property.

# What the drive says about its own wear and geometry.
sudo smartctl -a /dev/nvme0n1 | grep -Ei 'percentage used|data units written|available spare'
# Percentage Used: 3%          <- fraction of rated P/E cycles consumed
# Data Units Written: 41,203,551  (x 512,000 bytes)

sudo nvme id-ns /dev/nvme0n1 -H | grep -i 'lba format'   # sector size in use

# Queue depth is the parameter that matters on flash. Same drive, two depths:
sudo fio --name=qd1  --filename=/dev/nvme0n1 --rw=randread --bs=4k \
         --iodepth=1  --direct=1 --runtime=10 --time_based --readonly
sudo fio --name=qd64 --filename=/dev/nvme0n1 --rw=randread --bs=4k \
         --iodepth=64 --direct=1 --runtime=10 --time_based --readonly
# Typical: ~15,000 IOPS at QD1 vs ~600,000 IOPS at QD64. The device did not
# get faster -- you finally used more than one die at a time.

Key takeaways

• SSDs have no seek or rotational delay, so random and sequential reads cost nearly the same; the disk-era intuition about locality mostly evaporates.
• Flash reads and programs at page granularity but erases only at block granularity, so in-place overwrite is impossible.
• Erase blocks wear out; endurance falls sharply as bits-per-cell rises (SLC to QLC), and QLC drives can be slower than an HDD at sustained writes.
• Latency is asymmetric — read microseconds, program hundreds of microseconds, erase milliseconds — which produces a long tail even with excellent averages.
• Performance comes from internal parallelism across channels and dies, so achieving rated IOPS requires deep queues, not faster individual requests.

🧪 Practice

1. A 512 GB TLC drive is rated at 1,000 P/E cycles with a write amplification of 3. Compute its total bytes written and its expected lifetime under 100 GB/day of host writes.
2. Explain why a benchmark that issues one 4 KB read at a time reports roughly 5% of an NVMe drive's advertised IOPS, and what to change in the benchmark.
3. Interview-style: "A QLC SSD writes at 1.5 GB/s for twenty seconds and then collapses to 80 MB/s for the rest of a large copy. What is happening?" Hint: think about what the fast region is made of, how big it is, and what has to happen before it can be reused.

NVM and Flash Translation Layer

Theory

The previous topic ended with a problem: flash cannot be overwritten in place, but every operating system, file system, and application on earth assumes block N can be rewritten whenever they like. Something has to reconcile the two. That something is the Flash Translation Layer (FTL) — firmware running on the drive's own controller, with its own CPU and DRAM, which presents a perfect, infinitely-rewritable array of logical blocks on top of hardware that offers nothing of the sort.

The FTL's core trick is indirection. It keeps a mapping table from logical block address to physical flash page. A write never modifies the old page; it programs a fresh, already-erased page somewhere convenient, updates the map, and marks the old page invalid. This turns every random write into a sequential append into whatever erase block is currently open — which is precisely the access pattern flash likes.

That trick creates a new problem: invalid pages accumulate, and the drive eventually runs out of erased blocks. Garbage collection solves it. The FTL picks a victim block with many invalid pages, copies the still-valid pages out to a fresh block, and erases the victim. Note what just happened: writing user data caused additional internal writes. The ratio is write amplification:

write amplification = bytes written to flash / bytes written by the host

Write amplification is the single most important number in SSD behaviour. It is near 1.0 for large sequential writes, and can exceed 5 for small random writes on a nearly full drive — which simultaneously multiplies wear and destroys sustained throughput. Two things reduce it: over-provisioning (hidden spare capacity, usually 7–28%, that guarantees erased blocks are always available) and keeping the drive from being filled to the brim, which is the same thing done voluntarily.

The FTL also handles wear levelling. Left alone, a filesystem that rewrites the same metadata block would destroy a handful of erase blocks while the rest stayed pristine. Wear levelling spreads erases evenly, migrating even cold, never-modified data occasionally so its blocks can take their turn. And it manages bad block retirement, pulling failed blocks out of service and replacing them from the spare pool.

One last piece is needed, and it must come from the OS. When a file is deleted, the file system stops caring about those blocks — but the drive has no idea. It will keep dutifully copying that dead data during garbage collection forever. The TRIM command (DISCARD in Linux, DEALLOCATE in NVMe) tells the drive "these LBAs no longer contain anything I want," letting the FTL mark those pages invalid immediately. Without TRIM, a drive's write amplification climbs steadily over its life and performance degrades permanently.

Alongside NAND sits a newer category: non-volatile memory (NVM) that is byte-addressable and sits on the memory bus rather than a storage bus. It blurs the storage/memory boundary — persistence at near-DRAM latency, accessed with load and store instructions rather than a block driver, which forces filesystems and databases to rethink durability primitives entirely (clwb, sfence, and persistent-memory-aware allocation instead of write and fsync). Intel's Optane was the commercial flagship and has been discontinued, but the programming model — DAX-mapped persistent memory — remains the reference design for the category, and CXL-attached memory is bringing the same questions back.

The analogy for the FTL is a librarian in a library where books cannot be edited. To "update" a book, she prints a corrected copy, shelves it in the next free slot, and rewrites the catalogue entry; the old copy is left to be recycled later. Occasionally she consolidates a shelf full of superseded copies to free it. The catalogue is the mapping table, the recycling is garbage collection, and if nobody ever tells her a book has been formally withdrawn, she will keep moving dead copies around forever — that is what TRIM prevents.

Example

   FTL INDIRECTION: A WRITE NEVER OVERWRITES

   Host: write LBA 42 (new contents)

   BEFORE                                AFTER
   map: 42 -> P100                       map: 42 -> P307
   block A: [P100 valid  ]               block A: [P100 INVALID]  <- garbage
            [P101 valid  ]                        [P101 valid  ]
   block B: [P307 ERASED ]               block B: [P307 valid  ]  <- new data
            [P308 ERASED ]                        [P308 ERASED ]

   Random host writes become a SEQUENTIAL append into the open block.

   GARBAGE COLLECTION AND WRITE AMPLIFICATION

   victim block: [ V ][ I ][ V ][ I ][ I ][ V ][ I ][ I ]   V=valid I=invalid
                   3 valid pages, 5 invalid

   1. copy the 3 valid pages to a fresh block   -> 3 extra page writes
   2. erase the victim (one P/E cycle)          -> 8 pages now free
   net gain: 5 free pages, at a cost of 3 internal writes

   host wrote 5 pages worth of new data, flash wrote 5 + 3 = 8
   write amplification = 8 / 5 = 1.6

   HOW FULLNESS DESTROYS THIS

   drive 50% full : victims are mostly invalid -> WA ~1.1  (fast)
   drive 95% full : victims are mostly valid   -> WA ~5.0  (slow, wears out)

   WITHOUT TRIM, DELETED DATA IS STILL "VALID" TO THE DRIVE
   fs deletes file -> blocks free to the OS, still V to the FTL
   -> GC keeps copying dead pages forever -> WA climbs, perf never recovers

# A minimal FTL: out-of-place writes, invalidation, garbage collection, and
# the write amplification that falls out of them.

PAGES_PER_BLOCK = 8

class FTL:
    def __init__(self, blocks):
        self.n     = blocks
        self.data  = [[None]  * PAGES_PER_BLOCK for _ in range(blocks)]
        self.valid = [[False] * PAGES_PER_BLOCK for _ in range(blocks)]
        self.free  = list(range(blocks))       # erased blocks, ready to program
        self.open, self.ptr = self.free.pop(), 0    # the currently open block
        self.map   = {}                        # LBA -> (block, page)
        self.host_writes = self.flash_writes = self.erases = 0

    def _program(self, lba):
        if self.ptr == PAGES_PER_BLOCK:        # open block is full
            while not self.free:               # no erased block? make one
                self._collect()
            self.open, self.ptr = self.free.pop(), 0
        b, p = self.open, self.ptr
        self.data[b][p], self.valid[b][p] = lba, True
        self.map[lba] = (b, p)
        self.flash_writes += 1                 # every PHYSICAL page write counts
        self.ptr += 1

    def write(self, lba):
        self.host_writes += 1
        if lba in self.map:                    # invalidate the OLD location --
            ob, op = self.map[lba]             # never overwrite it in place
            self.valid[ob][op] = False
        self._program(lba)                     # append to the open block

    def trim(self, lba):                       # the OS says: this is dead
        if lba in self.map:
            b, p = self.map.pop(lba)
            self.valid[b][p] = False           # GC will never relocate it again

    def _collect(self):
        # Greedy victim selection: the block with the fewest surviving pages.
        cands  = [b for b in range(self.n) if b != self.open and b not in self.free]
        victim = min(cands, key=lambda b: sum(self.valid[b]))
        surv   = [self.data[victim][p] for p in range(PAGES_PER_BLOCK)
                  if self.valid[victim][p]]
        self.data[victim]  = [None]  * PAGES_PER_BLOCK
        self.valid[victim] = [False] * PAGES_PER_BLOCK
        self.erases += 1
        self.free.append(victim)
        for lba in surv:                       # relocation: the cost of GC.
            self._program(lba)                 # THESE are the extra writes.

import random
for live in (40, 80, 100, 112):                # live LBAs out of 128 page slots
    random.seed(7)
    ftl = FTL(blocks=16)
    for _ in range(4000):
        ftl.write(random.randrange(live))      # uniform random overwrites
    print(f"{live/128:4.0%} full -> host {ftl.host_writes}, "
          f"flash {ftl.flash_writes:5}, erases {ftl.erases:4}, "
          f"WA {ftl.flash_writes/ftl.host_writes:.2f}")

# 31% full -> host 4000, flash  4028, erases  498, WA 1.01
# 62% full -> host 4000, flash  6763, erases  967, WA 1.69
# 78% full -> host 4000, flash  9699, erases 1265, WA 2.42
# 88% full -> host 4000, flash 14126, erases 1777, WA 3.53
#
# The host issued the SAME 4,000 writes every time. Only free space changed.
# On a roomy drive the victim block is nearly all invalid, so an erase is
# almost pure profit; on a full one the victim is mostly valid, so freeing a
# page costs several relocations. This is why leaving an SSD unpartitioned at
# the end -- or simply not filling it -- measurably improves both speed and
# lifetime, and why TRIM matters: every trimmed page is one GC never copies.

# Is TRIM actually reaching the device?
lsblk --discard                 # non-zero DISC-GRAN/DISC-MAX = discard supported
sudo fstrim -av                 # trim all mounted filesystems now
systemctl status fstrim.timer   # the weekly batch job most distros ship

# Continuous discard is the alternative, but it adds a command per delete:
grep discard /etc/fstab         # prefer the timer unless latency demands otherwise

# Over-provisioning by leaving a partition gap: give the FTL room to work.
sudo nvme id-ctrl /dev/nvme0 | grep -i tnvmcap   # total capacity vs usable

# Persistent memory, when present, appears as a DAX device rather than a disk:
ls /dev/pmem* 2>/dev/null
ndctl list -u 2>/dev/null       # namespaces, modes (fsdax, devdax, sector)

Key takeaways

• The FTL hides flash's no-overwrite rule behind a logical-to-physical map, turning every host write into an out-of-place append and invalidating the old page.
• Garbage collection reclaims blocks by relocating surviving pages, and the resulting extra writes are quantified as write amplification.
• Write amplification rises sharply as the drive fills; over-provisioning and free space are the direct remedies.
• Wear levelling spreads erases across all blocks, including migrating cold data so its blocks take a turn.
• TRIM/DISCARD is the OS's only way to tell the drive that deleted blocks are dead; without it, GC keeps relocating garbage and performance decays permanently.
• Byte-addressable persistent memory sits on the memory bus and replaces the block-device model with load/store plus explicit cache-flush instructions.

🧪 Practice

1. A GC victim block holds 64 pages, 48 of them valid. Compute the pages relocated, the pages freed, and the write amplification if the host had written the 16 invalidated pages.
2. Explain why a freshly formatted SSD benchmarks faster than the same drive after six months of heavy use, and name two things that restore most of the difference.
3. Interview-style: "Why does an SSD get slower as it fills up, when a hard disk mostly does not?" Hint: ask what garbage collection must copy when almost every candidate block is full of valid data.

Disk Attachment Methods

Theory

A storage device is useless until the CPU can talk to it, and the path between them determines bandwidth, latency, distance, and who else can share the device. Attachment methods split into three families that differ in one crucial respect: what unit is transferred over the wire — blocks or files.

Host-attached storage puts the device on a local bus, and the OS speaks a block protocol to it directly.

Interface	Protocol	Typical bandwidth	Queues x depth	Where it is used
SATA	AHCI/ATA	6 Gb/s (~550 MB/s)	1 x 32 (NCQ)	Consumer HDD and SSD
SAS	SCSI	12–24 Gb/s	1 x 254	Enterprise disks, expanders, dual-port
NVMe	NVMe over PCIe	4–16 GB/s (PCIe 4/5 x4)	64K x 64K	Modern SSDs
USB/Thunderbolt	UAS / NVMe	0.5–5 GB/s	varies	External drives

The interesting row is NVMe, and the reason is not raw bandwidth. AHCI was designed for a device with one arm, so it offers one command queue of 32 entries — perfectly adequate for a mechanism that can only be in one place at a time, and catastrophically inadequate for a chip with dozens of parallel dies. NVMe provides up to 65,535 queues of 65,535 commands, so each CPU core can own a queue and submit without any cross-core locking. The protocol change, not the wire, is what unlocked flash.

Network-attached storage (NAS) exports a file system over an ordinary IP network using NFS or SMB. The client sends "open this path, read these bytes"; the server owns the on-disk layout and enforces access control. Because the unit is a file, multiple clients can share the same tree safely, which is why NAS is the natural fit for home directories and shared documents.

Storage-area networks (SAN) export raw blocks over a dedicated fabric — Fibre Channel, iSCSI (SCSI over TCP/IP), or NVMe-over-Fabrics. The client sees what looks like a local disk and puts its own file system on it. Blocks are faster and lower-level, but a plain file system cannot be mounted read-write by two hosts at once without corrupting itself; sharing requires a cluster file system or a volume manager that arbitrates.

The distinction is worth stating plainly because it is the most common confusion in the area:

	NAS	SAN
Unit exported	Files and directories	Raw blocks (LUNs)
Protocol	NFS, SMB	Fibre Channel, iSCSI, NVMe-oF
Who owns the file system	The server	The client
Network	Shared Ethernet/IP	Usually a dedicated fabric
Natural sharing	Many clients, same tree	One client per volume (unless clustered)
Typical use	Home directories, media, shared docs	Databases, VM images, low-latency workloads

Cloud object storage (S3 and its imitators) is a fourth category that fits neither: the unit is a whole immutable object addressed by key over HTTP, with no partial overwrite and no POSIX semantics — enormously scalable and durable, but not something you can put a file system on and expect to behave.

Example

   THREE ATTACHMENT MODELS

   HOST-ATTACHED                 NAS (file-level)          SAN (block-level)

   +---------+                   +--------+                +--------+
   |  HOST   |                   | client |                | client |
   | +-----+ |                   +---|----+                +---|----+
   | | FS  | |                       | "read /home/a.txt"      | "read LBA 8192"
   | +--|--+ |                       | NFS / SMB               | FC / iSCSI
   | +--v--+ |                   ====|==== IP net          ====|==== fabric
   | |block| |                       |                         |
   | | drv | |                   +---v----+                +---v----+
   +---|-----+                   | server |                | array  |
       | SATA/SAS/PCIe           | +----+ |                | (raw   |
   +---v-----+                   | | FS | |  <- server     |  LUNs) |  <- CLIENT
   |  DRIVE  |                   | +----+ |     owns the   +--------+     owns
   +---------+                   +--------+     filesystem                the FS

   WHY NVMe REPLACED AHCI: IT IS THE QUEUE MODEL, NOT THE CABLE

   AHCI / SATA                        NVMe
   core0 --\                          core0 -> [queue 0 ]--\
   core1 ---> [ ONE queue, 32 ] -> HDD core1 -> [queue 1 ]---> SSD (many dies)
   core2 --/    contended lock        core2 -> [queue 2 ]--/
                                      up to 65,535 queues x 65,535 entries
   fine for one arm                   matches a device with internal parallelism

# What is attached, and how (Linux).
lsblk -o NAME,TRAN,ROTA,SIZE,MODEL      # TRAN = sata | sas | nvme | usb
ls /sys/class/nvme/nvme0/               # NVMe controller attributes
nvme list                               # namespaces, firmware, capacity

# How many queues does the NVMe device actually expose to this host?
ls /sys/block/nvme0n1/mq/ | wc -l       # one hardware queue per CPU, typically
cat /sys/block/sda/device/queue_depth   # SATA/SAS: 32 or 254

# iSCSI: attaching a remote LUN so it appears as a LOCAL block device.
sudo iscsiadm -m discovery -t sendtargets -p 10.0.0.20
sudo iscsiadm -m node -T iqn.2026-01.com.example:vol1 -p 10.0.0.20 --login
lsblk                                   # the LUN now shows up as e.g. /dev/sdb
# Note: you must still create a filesystem on it -- the CLIENT owns the FS.

# NFS: attaching a remote FILE SYSTEM. No mkfs, ever -- the server owns it.
sudo mount -t nfs 10.0.0.30:/export/home /mnt/home
mount | grep nfs

Key takeaways

• Host-attached buses (SATA, SAS, NVMe) carry block commands to a local device; the distinguishing feature of NVMe is its many deep queues, which match flash's internal parallelism.
• AHCI's single 32-entry queue was sized for a one-armed mechanism and became the bottleneck for SSDs.
• NAS exports files over IP (NFS, SMB); the server owns the file system, so many clients can share a tree safely.
• SAN exports raw blocks over a fabric (FC, iSCSI, NVMe-oF); the client owns the file system, so a volume normally belongs to one host unless a cluster file system arbitrates.
• Object storage is a third model — whole immutable objects by key over HTTP — with no POSIX semantics and no partial overwrite.

🧪 Practice

1. Draw the request path for reading 4 KB from (a) a local NVMe SSD, (b) an NFS mount, (c) an iSCSI LUN. Mark on each where the file system logic runs.
2. Two servers mount the same iSCSI LUN read-write with ext4 and both write. Predict the outcome and explain the mechanism, then name two ways to make the sharing safe.
3. Interview-style: "We swapped SATA SSDs for NVMe SSDs with the same NAND and random-read IOPS went up 8x. The wire bandwidth only doubled. Explain." Hint: count the command queues on each side and think about what limits concurrency, not throughput.

Disk Formatting and Partitioning

Theory

A brand-new drive is not usable storage; it is an array of cells with no agreed structure. Three distinct steps stand between it and a mounted file system, and they are routinely conflated even though they happen at different layers and different times.

Low-level (physical) formatting divides the medium into sectors the controller can address. Each sector gets a header (identifying information), a data area, and a trailer holding an error-correcting code computed over the data. On every read, the controller recomputes the ECC and compares; small errors are corrected silently, larger ones are reported as a read failure. This step is done at the factory on modern drives — the sector layout is intertwined with servo information that a user-level "format" cannot rewrite. What tools like hdparm --security-erase or nvme format do is different: they discard data and reset mappings, not re-lay the physical geometry.

Partitioning carves the logical block space into independent regions so different file systems (or an OS and its swap area) can coexist. The partition table lives in the first sectors and comes in two schemes:

	MBR	GPT
Introduced	1983	~2000 (part of UEFI)
Max disk size	2 TB (32-bit LBA x 512 B)	8 ZB (64-bit LBA)
Primary partitions	4 (more via extended/logical)	128+ by default
Integrity	None	CRC32 on header and entries
Redundancy	Single copy at LBA 0	Backup table at the end of the disk
Identification	1-byte type code	128-bit type and unique GUIDs

GPT wins on every axis and keeps a "protective MBR" in sector 0 so that MBR-only tools see one large unknown partition rather than empty space they might overwrite.

Logical formatting is creating a file system — writing superblocks, inode tables, free-space maps, and a root directory into a partition. This is mkfs, and it is the step that decides block size, inode density, and journalling behaviour (Chapter 10 covers what these structures do).

Two special regions matter to boot and reliability. The boot block is a fixed location the firmware reads to start the system: on BIOS/MBR machines, code in sector 0 chains to a boot loader; on UEFI/GPT machines, firmware instead reads a FAT-formatted EFI System Partition and executes a .efi file — a much saner arrangement, since the loader is an ordinary file. And bad block management handles sectors that fail over time. Drives keep a pool of spare sectors and perform sector sparing (remap the bad LBA to a spare) or sector slipping (shift the affected range by one to preserve sequential layout). All of this is invisible above the block layer, which is why a growing "reallocated sector count" in SMART data is the clearest early warning a disk gives before it dies.

The analogy is preparing a blank notebook: ruling the pages into lines is low-level formatting (done by the manufacturer), dividing the notebook into sections with tabs is partitioning, and writing a table of contents and index conventions for a section is logical formatting.

Example

   FROM RAW DEVICE TO MOUNTED FILE SYSTEM

   raw medium
     |  low-level format (FACTORY): sectors = [header][ data ][ ECC ]
     v
   LBA 0 .. N-1  (a flat array of addressable blocks)
     |  partitioning: write a GPT
     v
   +--------+------------------+---------------------------+-----------+
   | LBA 0  | GPT header +     |  partition 1  partition 2 | backup    |
   |protect.| entry array      |  (ESP, FAT)   (root, ext4)| GPT (end) |
   |  MBR   | CRC32 protected  |                           |           |
   +--------+------------------+---------------------------+-----------+
     |  logical format (mkfs) per partition
     v
   superblock | inode table | block bitmap | data blocks | root dir
     |  mount
     v
   /dev/sda2 mounted at /

   BAD SECTOR HANDLING (invisible above the block layer)

   sparing:   LBA 900 fails -> remapped to a spare far away
              [897][898][899][ X ][901]      ... [spare -> holds 900]
              sequential reads now SEEK to fetch block 900

   slipping:  shift the range by one so order is preserved
              [897][898][899][ X ][900][901]...   (contents move down one)
              costs a rewrite, keeps sequential layout intact

# 1. Inspect what is already there before touching anything.
sudo parted -l                     # partition tables and types
sudo gdisk -l /dev/sdb             # GPT detail, including the backup table
sudo blkid                         # filesystem UUIDs and types

# 2. Partition with GPT.
sudo parted /dev/sdb --script mklabel gpt
sudo parted /dev/sdb --script mkpart ESP fat32 1MiB 513MiB
sudo parted /dev/sdb --script set 1 esp on
sudo parted /dev/sdb --script mkpart root ext4 513MiB 100%
# Start at 1MiB, not sector 63: alignment to 4 KB physical sectors and to the
# SSD erase block avoids every write becoming a read-modify-write.

# 3. Logical format: create file systems.
sudo mkfs.fat -F32 /dev/sdb1
sudo mkfs.ext4 -b 4096 /dev/sdb2   # -b picks the filesystem block size
sudo tune2fs -l /dev/sdb2 | head -20

# 4. Mount, persistently and by UUID (device names are not stable).
sudo mount /dev/sdb2 /mnt
blkid /dev/sdb2                    # copy the UUID into /etc/fstab

# 5. Bad blocks: the early-warning signal.
sudo smartctl -A /dev/sda | grep -Ei 'reallocated|pending|uncorrectable'
# Reallocated_Sector_Ct  0  -> healthy
# Current_Pending_Sector 8  -> sectors failing reads, not yet remapped: BACK UP

Key takeaways

• Low-level formatting creates sectors with headers and ECC and is done at the factory; user-visible "format" commands do not re-lay physical geometry.
• Partitioning divides the LBA space; GPT supersedes MBR with 64-bit addressing, CRC-protected tables, a backup copy, and GUID identification.
• Logical formatting (mkfs) writes the file system's own metadata into a partition and sets parameters like block size.
• Booting reads a fixed boot block on BIOS/MBR systems, or an ordinary .efi file on a FAT-formatted EFI System Partition under UEFI.
• Bad sectors are handled below the OS by sparing or slipping from a spare pool; rising reallocated and pending sector counts are the clearest pre-failure warning.
• Partition alignment matters on 4 KB-sector drives and SSDs, because a misaligned partition turns every write into a read-modify-write.

🧪 Practice

1. List the three formatting/partitioning steps for a new drive, say who performs each, and name one parameter fixed by each step.
2. A 4 TB disk shows only 2 TB of usable space after partitioning. Diagnose the cause and give the fix.
3. Interview-style: "A disk reports 200 reallocated sectors but passes its SMART self-test. Do you replace it?" Hint: consider what reallocation implies about the medium's trend, what the spare pool is finite in, and the cost asymmetry between replacing early and restoring from backup.

<a id="92-disk-scheduling"></a>

9.2 Disk Scheduling

Because positioning dominates the cost of a mechanical disk access, the order in which pending requests are served changes total service time by a factor of three or more. This section works through the classic algorithms on one shared example, then asks what survives when the arm disappears.

Every topic below uses the same scenario, so the numbers can be compared directly:

   Disk cylinders : 0 .. 199
   Head starts at : 53
   Pending queue  : 98, 183, 37, 122, 14, 124, 65, 67

FCFS Disk Scheduling

Theory

First-Come, First-Served serves requests in arrival order. It is the null hypothesis of disk scheduling: no reordering, no cleverness, no policy at all beyond a plain queue.

Its virtues are real and easy to undervalue. It is trivially correct, it never starves anybody (every request is served after exactly the requests ahead of it), and it preserves the order the application asked for — which occasionally matters for workloads that depend on issue order for their own reasons. Its per-request latency is also perfectly predictable in terms of queue position.

Its vice is that it ignores the one fact that dominates cost. Consecutive requests in arrival order have no relation to each other's cylinder, so the arm swings back and forth across the platter — 98 out, 183 further out, 37 all the way in, 122 back out again. Each swing is a full seek that a different ordering could have avoided. On our example the head travels 640 cylinders; the best of the algorithms in this section does the same work in 208.

The intuition to carry forward: FCFS optimises fairness in time while completely ignoring cost in space. Every other algorithm in this section trades some of the former for a lot of the latter, and the interesting question is always how much fairness the trade costs.

FCFS is not merely a straw man, though. It is the right answer whenever seek cost is zero or near zero — which is exactly the situation on flash, where Linux's none scheduler is essentially FCFS and is the recommended default for NVMe. The algorithm did not get better; the hardware assumption it depends on became true.

Example

   FCFS: head 53, queue 98, 183, 37, 122, 14, 124, 65, 67

   0        14      37    53   65 67      98        122 124        183   199
   |--------|-------|-----|----|--|-------|---------|---|----------|-----|
                          (1)-------------> 98                    (2)
                          53 -> 98  = 45
        (3)<--------------------------------------------------- 183
                          98 -> 183 = 85
            37 <------------------------------------------------ (4)
                          183 -> 37 = 146
             (5)--------------------------> 122
                          37 -> 122 = 85
        14 <------------------------------- (6)
                          122 -> 14 = 108
             (7)------------------------------> 124
                          14 -> 124 = 110
              65 <---------------------------- (8)
                          124 -> 65 = 59
              (9)-> 67
                          65 -> 67  = 2
                                      ---
                          TOTAL       640 cylinders

   The arm crosses the whole platter FOUR times. Three of those crossings
   are pure waste: the cylinders were passed over and had to be revisited.

# All six algorithms share this harness; each returns a service ORDER.
QUEUE, HEAD, MIN_CYL, MAX_CYL = [98, 183, 37, 122, 14, 124, 65, 67], 53, 0, 199

def head_movement(order, start=HEAD):
    total, cur = 0, start
    for cyl in order:
        total += abs(cyl - cur)      # seek distance, in cylinders
        cur = cyl
    return total

def fcfs(queue, head):
    return list(queue)               # the entire algorithm: no reordering

order = fcfs(QUEUE, HEAD)
print(order)                         # [98, 183, 37, 122, 14, 124, 65, 67]
print(head_movement(order))          # 640

# What that costs in real time on a 7,200 RPM drive.
SEEK_PER_CYL_MS, AVG_ROT_MS = 0.02, 4.17
print(f"{head_movement(order)*SEEK_PER_CYL_MS + len(order)*AVG_ROT_MS:.1f} ms")
# 46.2 ms  -- of which 12.8 ms is seeking that reordering could remove

# FCFS-equivalent scheduling on Linux is called 'none' (formerly 'noop').
cat /sys/block/nvme0n1/queue/scheduler
# [none] mq-deadline kyber bfq     <- the default for NVMe, and correct there

# Force it, then observe. On an HDD this is usually a mistake; on flash it is not.
echo none | sudo tee /sys/block/sda/queue/scheduler
iostat -x 2 5                       # watch r_await/w_await and aqu-sz

Key takeaways

• FCFS serves requests in arrival order, guaranteeing no starvation and giving the simplest possible implementation.
• It ignores seek cost entirely, so the arm may cross the platter repeatedly; on the standard example it moves 640 cylinders against 208 for LOOK.
• Its worst case appears when consecutive requests alternate between the inner and outer edges of the disk.
• FCFS is the correct policy when positioning cost is near zero — Linux's none scheduler for NVMe is exactly this.

🧪 Practice

1. With the head at 100 and the queue 55, 58, 39, 18, 90, 160, 150, 38, 184, compute the total head movement under FCFS.
2. Construct an 8-request queue on a 0–199 disk that maximises FCFS head movement, and give the total.
3. Interview-style: "Linux ships none as the default scheduler for NVMe devices. Isn't that just FCFS, which every textbook calls the worst option?" Hint: ask which cost the textbook ranking is measuring, and whether that cost still exists on the device in question.

SSTF

Theory

Shortest Seek Time First applies the obvious greedy idea: from wherever the head is now, serve the pending request whose cylinder is closest. It is the disk analogue of Shortest-Job-First from Chapter 4, and it inherits both that algorithm's strength and its characteristic flaw.

The strength is a large, immediate improvement. On our example SSTF cuts head movement from 640 to 236 cylinders — a 63% reduction obtained by a single line of logic. Real workloads have spatial locality (a file's blocks cluster, a database's index pages cluster), so choosing the nearest pending request tends to keep the arm within a neighbourhood where it is already doing useful work.

The flaw is starvation. Greedy choice has no memory of how long anything has waited. If requests keep arriving near the head's current position — which is exactly what a busy process doing localised I/O produces — a request at cylinder 183 can wait indefinitely while the arm services an endless stream of nearby work. This is not a rare pathology; a single sequential reader can trivially generate it, and the starved request belongs to some other process that appears, from the outside, to have hung.

There is a second, subtler point worth internalising: SSTF is not optimal, only greedy. Minimising the next seek does not minimise the total. On our example, starting toward 65 and 67 before doubling back to 37 and 14 costs 236, whereas sweeping inward first and then outward costs 208 — SSTF's very first decision (go to 65, the nearest at distance 12, rather than 37 at distance 16) is what makes it lose. Greedy algorithms buy simplicity, not optimality.

Finally, the name is a slight lie. "Shortest seek time" is approximated by shortest seek distance, because the OS knows LBAs, not the drive's true internal geometry, remapped sectors, or rotational position. A drive's own firmware can do better — modern drives reorder internally using rotational position sorting, knowing exactly where the platter is — which is part of why elaborate OS-side scheduling has been steadily de-emphasised.

Example

   SSTF: head 53, queue 98, 183, 37, 122, 14, 124, 65, 67

   step  head   candidates (distance)                     choose   moved
   1     53     65(12) 67(14) 37(16) 14(39) 98(45) ...    65       12
   2     65     67(2)  37(28) 14(51) 98(33) ...           67        2
   3     67     37(30) 14(53) 98(31) 122(55) ...          37       30
   4     37     14(23) 98(61) 122(85) ...                 14       23
   5     14     98(84) 122(108) 124(110) 183(169)         98       84   <-- the
   6     98     122(24) 124(26) 183(85)                   122      24    long
   7     122    124(2) 183(61)                            124       2    jump
   8     124    183(59)                                   183      59
                                                          TOTAL   236

   THE GREEDY MISTAKE, VISIBLE IN STEP 1

   SSTF : 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> ...        = 236
   LOOK : 53 -> 37 -> 14 -------> 65 -> 67 -> 98 -> ...  = 208
          taking the SLIGHTLY WORSE first step (16 vs 12) avoids
          re-crossing the 14..67 span later.

   STARVATION

   arm working here                                 waiting since t=0
        v v v                                             v
   |----[####]------------------------------------------[183]--------|
        new requests keep arriving in this cluster
        -> the arm never has a reason to leave -> 183 waits forever

def sstf(queue, head):
    pending, cur, order = list(queue), head, []
    while pending:
        # Greedy: nearest pending cylinder, measured in LBA distance.
        nearest = min(pending, key=lambda c: abs(c - cur))
        pending.remove(nearest)
        order.append(nearest)
        cur = nearest                     # no memory of anyone's waiting time
    return order

order = sstf(QUEUE, HEAD)
print(order)                # [65, 67, 37, 14, 98, 122, 124, 183]
print(head_movement(order)) # 236   (vs 640 for FCFS: a 63% reduction)

# Demonstrating starvation: a localised reader keeps issuing nearby requests.
def starvation_demo(head, far_request, rounds):
    cur, passed_over, served_far = head, 0, 0
    for _ in range(rounds):
        # A sequential reader ping-pongs between two adjacent cylinders, so
        # there is ALWAYS a pending request two cylinders away from the head.
        nearby = 55 if cur == 53 else 53
        if abs(nearby - cur) < abs(far_request - cur):
            cur = nearby                  # greedy: the near one always wins
            passed_over += 1
        else:
            cur = far_request
            served_far += 1
    return passed_over, served_far

print(starvation_demo(head=53, far_request=183, rounds=1000))
# (1000, 0) -- the request at cylinder 183 was passed over every single round
# and never served. Nothing in SSTF records that it has been waiting.

Key takeaways

• SSTF greedily serves the closest pending request, cutting head movement from 640 to 236 on the standard example.
• It can starve distant requests indefinitely, because a stream of nearby arrivals gives the arm no reason to travel.
• It is greedy, not optimal: minimising the next seek does not minimise the total, and LOOK beats it (208) on the same queue.
• Seek distance only approximates seek time, since the OS cannot see real geometry or rotational position.
• The starvation problem is what motivates the sweeping algorithms that follow.

🧪 Practice

1. Head at 100, queue 55, 58, 39, 18, 90, 160, 150, 38, 184: give the SSTF service order and total head movement.
2. Build a 5-request queue and a head position where SSTF's total exceeds the optimal ordering's total, and show both numbers.
3. Interview-style: "SSTF and SJF share a flaw. Name it, and explain why the fix used for SJF (ageing) is awkward for a disk arm." Hint: ageing changes which request is chosen, but the cost of choosing a far request is paid in mechanical movement, not in a scheduler decision.

SCAN and C-SCAN

Theory

The starvation in SSTF comes from letting the arm change direction freely in pursuit of whatever is nearest. SCAN removes that freedom: the arm moves steadily in one direction, servicing every request it passes, until it reaches the end of the disk; then it reverses and sweeps back. Because of the resemblance, SCAN is universally called the elevator algorithm — a lift travelling to the top floor picks up everyone going that way rather than jumping between the nearest waiting passengers.

The guarantee this buys is a bound on waiting time. A request can be missed by the current sweep, but it will certainly be served on the next one, because the arm systematically visits every cylinder. Worst-case wait is two sweeps, and no request can be passed over indefinitely. Trading greedy optimality for a bound is the same move the scheduler chapter made when it replaced SJF with round-robin.

On our example, sweeping toward 0 first, SCAN serves 37, 14, continues to cylinder 0, reverses, and then serves 65, 67, 98, 122, 124, 183 — a total of 236 cylinders, coincidentally the same as SSTF here, but without the starvation risk. (Direction matters: sweeping outward first from 53 costs 331 on this queue. Textbook comparisons always fix a direction, and yours should say which.)

SCAN has one unfairness of its own, and it is geometric. Consider a cylinder just behind the arm as it passes: it waits almost a full round trip. A cylinder just ahead waits almost nothing. Worse, the middle cylinders get visited twice as often as the edges, because the arm passes through the middle on both legs of every round trip while reaching each edge only once. The service rate is therefore not uniform across the disk.

C-SCAN (Circular SCAN) fixes exactly this. It services requests in one direction only; on reaching the end, it returns immediately to the beginning without servicing anything on the way back, and starts again. Treating the disk as a circular list makes waiting time uniform: every cylinder is visited exactly once per cycle, so the expected wait is the same everywhere. The cost is one full-disk repositioning per cycle — which is cheap on a real drive, since a single long seek is far less than proportionally expensive compared to many short ones. C-SCAN costs 382 cylinders on our example, but delivers a much tighter variance, and variance is what users actually perceive.

The general lesson is one that recurs throughout systems: SCAN optimises the average, C-SCAN optimises the distribution. Choosing between them means deciding whether you are being judged on throughput or on the ninety-ninth percentile.

Example

   SCAN ("elevator"), head 53, moving TOWARD 0 first

   0        14      37    53   65 67      98        122 124        183   199
   |--------|-------|-----|----|--|-------|---------|---|----------|-----|
   <========|=======|=====|                                              leg 1
      served: 37, 14, then continue to cylinder 0 (the END, even though
      no request is there -- that is what distinguishes SCAN from LOOK)
   |========|=======|=====|====|==|=======|=========|===|==========|>     leg 2
      served: 65, 67, 98, 122, 124, 183

   53->37 =16, 37->14 =23, 14->0 =14, 0->183 =183          TOTAL = 236

   C-SCAN, head 53, servicing only in the OUTWARD direction

   |--------|-------|-----|----|--|-------|---------|---|----------|-----|
                          |====|==|=======|=========|===|==========|====>  serve
                             65 67  98      122     124    183     199
   <=======================================================================
        immediate return to 0, SERVICING NOTHING on the way back
   |========|>                                                            serve
     14, 37

   53->199 =146, 199->0 =199 (return, no service), 0->37 =37  TOTAL = 382

   WHY C-SCAN COSTS MORE BUT FEELS FAIRER

   SCAN   : middle cylinders are crossed TWICE per round trip,
            edge cylinders ONCE -> service rate varies by position;
            a cylinder just behind the arm waits a full round trip.
   C-SCAN : every cylinder is visited exactly ONCE per cycle
            -> uniform expected wait, much lower variance.

def scan(queue, head, min_cyl=MIN_CYL, max_cyl=MAX_CYL, direction="down"):
    below = sorted(c for c in queue if c < head)
    above = sorted(c for c in queue if c >= head)
    if direction == "down":
        # Sweep inward, touch the end of the disk, then sweep outward.
        return list(reversed(below)) + [min_cyl] + above
    return above + [max_cyl] + list(reversed(below))

def c_scan(queue, head, min_cyl=MIN_CYL, max_cyl=MAX_CYL):
    below = sorted(c for c in queue if c < head)
    above = sorted(c for c in queue if c >= head)
    # Serve outward to the edge, jump back to 0 servicing nothing, resume.
    return above + [max_cyl, min_cyl] + below

s = scan(QUEUE, HEAD)
print(s, head_movement(s))      # [37, 14, 0, 65, 67, 98, 122, 124, 183] 236
c = c_scan(QUEUE, HEAD)
print(c, head_movement(c))      # [65, 67, 98, 122, 124, 183, 199, 0, 14, 37] 382

# Direction is not a detail: the same queue, swept outward first.
print(head_movement(scan(QUEUE, HEAD, direction="up")))   # 331

# The fairness claim, made quantitative: how far the arm has travelled by the
# time each REAL request is served (the edge stops 0 and 199 are not requests).
def worst_wait(order):
    cur, waits, travelled = HEAD, [], 0
    for cyl in order:
        travelled += abs(cyl - cur); cur = cyl
        if cyl in set(QUEUE):                # skip the sentinel edge stops
            waits.append(travelled)
    return max(waits), round(sum(waits) / len(waits), 1)

print("SCAN   worst/avg:", worst_wait(s))    # (236, 129.0)
print("C-SCAN worst/avg:", worst_wait(c))    # (382, 135.2)
# C-SCAN's average is worse; what improves is uniformity across POSITIONS --
# no cylinder is systematically visited more often than any other.

Key takeaways

• SCAN (the elevator algorithm) sweeps the arm to one end servicing everything it passes, then reverses, bounding worst-case wait at two sweeps.
• SCAN's flaw is non-uniform service: middle cylinders are crossed twice per round trip and a request just behind the arm waits a full trip.
• C-SCAN services in one direction only and returns to the start without servicing, making expected wait uniform across all cylinders.
• On the standard example SCAN costs 236 and C-SCAN 382, but C-SCAN's waiting-time variance is far lower.
• SCAN optimises the average; C-SCAN optimises the distribution — pick according to whether throughput or tail latency is the target.
• The initial sweep direction changes the totals, so any comparison must state it.

🧪 Practice

1. Head at 100 on a 0–199 disk, queue 55, 58, 39, 18, 90, 160, 150, 38, 184: compute SCAN (moving outward) and C-SCAN head movement.
2. For the same queue, tabulate each request's wait in cylinders travelled under SCAN and C-SCAN, and compute the variance of each.
3. Interview-style: "C-SCAN moves the head further than SCAN yet is often described as fairer. Reconcile those two facts." Hint: identify the metric each one optimises, and think about how often a given cylinder is visited per cycle under each.

LOOK and C-LOOK

Theory

SCAN and C-SCAN contain an obvious inefficiency once you look closely at the diagram: the arm travels all the way to cylinder 0 and cylinder 199 even when no request is waiting there. In our example that wasted 14 cylinders on the way in and 16 on the way out — pure mechanical movement in service of nothing.

LOOK removes it. The arm behaves exactly like SCAN, but before continuing it looks ahead: if no request remains in the current direction, it reverses immediately. C-LOOK does the same for C-SCAN — it services outward to the highest pending request, then jumps directly back to the lowest pending request rather than to cylinder 0.

The improvement is free. LOOK preserves SCAN's bounded-wait guarantee (the arm still visits every pending request in a systematic sweep) and C-LOOK preserves C-SCAN's uniform service, while both avoid travel to empty regions. On our example, LOOK costs 208 cylinders against SCAN's 236, and C-LOOK costs 322 against C-SCAN's 382. There is no compensating disadvantage, which is why every real implementation is a LOOK variant, even though textbooks and interviewers usually say "SCAN". Linux's mq-deadline is a C-LOOK sweep with deadline overrides layered on top.

The saving grows with skew. If a workload's requests all live in the outer third of a disk — which is exactly what happens when a file system allocates from the front, or when only a fraction of a large drive is in use — SCAN wastes two-thirds of every round trip and LOOK wastes none.

That deadline overlay is worth understanding, because it is how the pure algorithm becomes usable in practice. Sorting alone can still delay a request for a long time under continuous load, so mq-deadline keeps two structures: a sorted queue (the C-LOOK sweep, good for throughput) and FIFO queues with expiry times (500 ms for reads, 5 s for writes by default). It normally serves from the sorted queue, but when the head of a FIFO queue expires it jumps there and serves it out of order. The asymmetry is deliberate: reads are almost always synchronous — some process is blocked right now waiting — whereas writes are usually buffered and can be deferred. This pairing of a throughput-oriented policy with a latency backstop is the standard structure of real I/O schedulers.

Here is the full comparison on the shared example:

Algorithm	Head movement	Starvation possible	Wait-time uniformity	Real-world use
FCFS	640	No	Uniform by arrival	none on flash
SSTF	236	Yes	Poor	Rarely used alone
SCAN	236	No	Middle favoured	Conceptual baseline
C-SCAN	382	No	Uniform	Conceptual baseline
LOOK	208	No	Middle favoured	Common in practice
C-LOOK	322	No	Uniform	mq-deadline's sweep

Example

   LOOK vs SCAN: stop at the LAST REQUEST, not the edge of the disk

   0        14      37    53   65 67      98        122 124        183   199
   |--------|-------|-----|----|--|-------|---------|---|----------|-----|
   SCAN  <==|=======|=====|                                              to 0
   LOOK     <=======|=====|                        reverse AT 14, saving 14
            |=======|=====|====|==|=======|=========|===|=========>|
                                                          stop at 183, not 199

   53->37 =16, 37->14 =23, 14->183 =169                    TOTAL = 208
   (SCAN spent 236: the extra 28 was travel to cylinders 0 and back.)

   C-LOOK: jump back to the LOWEST PENDING request, not to cylinder 0

                          |====|==|=======|=========|===|=========>|
                            65 67   98      122     124     183
            <==============================================|
              jump straight to 14 (not to 0), servicing nothing
            |=======>|
              14, 37

   53->183 =130, 183->14 =169 (return), 14->37 =23         TOTAL = 322

   mq-deadline = C-LOOK SWEEP + DEADLINE OVERRIDE

   sorted queue (C-LOOK order)    FIFO read queue     FIFO write queue
   [65 67 98 122 124 183]         [r@183 exp 500ms]   [w@14 exp 5000ms]
        normal service                   |                    |
        from here             ----> if the head EXPIRES, jump to it now
   reads get a 500 ms deadline, writes 5 s: a blocked reader is waiting,
   a buffered writer usually is not.

def look(queue, head, direction="down"):
    below = sorted(c for c in queue if c < head)
    above = sorted(c for c in queue if c >= head)
    # Identical to SCAN, minus the trip to the physical edge.
    return (list(reversed(below)) + above) if direction == "down" \
           else (above + list(reversed(below)))

def c_look(queue, head):
    below = sorted(c for c in queue if c < head)
    above = sorted(c for c in queue if c >= head)
    return above + below          # jump to the LOWEST pending, not to 0

l = look(QUEUE, HEAD)
print(l, head_movement(l))        # [37, 14, 65, 67, 98, 122, 124, 183] 208
cl = c_look(QUEUE, HEAD)
print(cl, head_movement(cl))      # [65, 67, 98, 122, 124, 183, 14, 37] 322

# The saving grows when requests are skewed away from the disk edges.
skewed = [150, 155, 160, 158, 170, 165]
print(head_movement(scan(skewed, 152)))   # 322 -- travels to cylinder 0
print(head_movement(look(skewed, 152)))   #  22 -- never leaves the cluster

# Full comparison on the shared example.
for name, o in [("FCFS", fcfs(QUEUE, HEAD)), ("SSTF", sstf(QUEUE, HEAD)),
                ("SCAN", scan(QUEUE, HEAD)), ("C-SCAN", c_scan(QUEUE, HEAD)),
                ("LOOK", look(QUEUE, HEAD)), ("C-LOOK", c_look(QUEUE, HEAD))]:
    print(f"{name:7} {head_movement(o):4}")
# FCFS 640 | SSTF 236 | SCAN 236 | C-SCAN 382 | LOOK 208 | C-LOOK 322

# Choosing and tuning a scheduler on Linux.
cat /sys/block/sda/queue/scheduler
echo mq-deadline | sudo tee /sys/block/sda/queue/scheduler

# The deadline knobs, in milliseconds.
cat /sys/block/sda/queue/iosched/read_expire     # 500
cat /sys/block/sda/queue/iosched/write_expire    # 5000
cat /sys/block/sda/queue/iosched/writes_starved  # 2 -- reads served per write batch

# Make it stick across reboots with a udev rule keyed on rotational media.
cat <<'RULE' | sudo tee /etc/udev/rules.d/60-ioscheduler.rules
ACTION=="add|change", KERNEL=="sd[a-z]", ATTR{queue/rotational}=="1", \
  ATTR{queue/scheduler}="mq-deadline"
ACTION=="add|change", KERNEL=="nvme[0-9]n[0-9]", ATTR{queue/scheduler}="none"
RULE

Key takeaways

• LOOK and C-LOOK are SCAN and C-SCAN that reverse or wrap at the last pending request instead of the physical edge of the disk.
• The improvement is free: bounded wait and uniform service are preserved while wasted travel is eliminated (208 vs 236, and 322 vs 382).
• All practical implementations are LOOK variants, even when the literature says SCAN.
• Linux's mq-deadline is a C-LOOK sweep with FIFO deadline overrides — 500 ms for reads, 5 s for writes.
• The read/write deadline asymmetry exists because reads are usually synchronous while writes are usually buffered.
• Pairing a throughput policy with a latency backstop is the general structure of real schedulers, not a disk-specific trick.

🧪 Practice

1. Head at 100, queue 55, 58, 39, 18, 90, 160, 150, 38, 184: compute LOOK and C-LOOK head movement and compare against your SCAN and C-SCAN answers from the previous topic.
2. Construct a queue where LOOK saves more than 150 cylinders over SCAN, and explain the property of the queue that makes the gap large.
3. Interview-style: "Under mq-deadline, a write can sit for five seconds while reads are served ahead of it. Why is that acceptable, and when is it not?" Hint: think about who is blocked on each kind of request — then consider what fsync from a database changes about that answer.

NVM Scheduling Considerations

Theory

Every algorithm so far optimises one quantity: distance travelled by a mechanical arm. Remove the arm and the entire basis of the analysis disappears. On an SSD, the "distance" between LBA 10 and LBA 10,000,000 is zero, so sorting requests by address optimises nothing at all — it merely costs CPU time, adds latency, and destroys the concurrency the device needs.

The correct default for NVMe is therefore none: submit requests as they arrive, in parallel, and let the device's own controller do the ordering. It knows things the kernel cannot — which die is idle, which channel is free, where the FTL actually placed each page. Measurements on modern NVMe drives routinely show none beating mq-deadline on both throughput and latency, which inverts the entire textbook ranking.

But scheduling does not become irrelevant; the objectives change. Four concerns replace seek minimisation:

Feeding the parallelism. An SSD's throughput comes from many dies working at once, so the job is to keep enough requests in flight. This is why the kernel moved from a single request queue with a global lock to blk-mq: per-CPU software queues mapped onto multiple hardware queues, so submission scales with cores instead of serialising on one lock. Getting out of the way is the optimisation.

Merging still pays. Sorting is useless but merging is not. Combining four adjacent 4 KB requests into one 16 KB request costs one command instead of four — fewer doorbell writes, fewer completion interrupts, less per-request overhead throughout the stack. This is why even none performs adjacent-request merging.

Read/write interference. Programs are roughly ten times slower than reads and erases a hundred times slower, so a burst of writes can stall reads behind garbage collection. Fairness between readers and writers, and shaping write bursts so they do not trigger GC storms, matter far more than address order. The kyber scheduler exists precisely for this: it targets latency directly, throttling background throughput to protect read latency.

Write amplification and endurance. The scheduler is a place to align and batch writes so they match the erase-block structure the FTL prefers, and to pass discards down promptly. Large aligned sequential writes keep write amplification near 1; scattered small writes push it up, wearing the device and slowing it.

The remaining schedulers therefore serve narrower purposes. bfq provides strong per-process fairness and interactive responsiveness (worth it on a desktop with a slow drive, too costly on a fast one). kyber is a light latency-targeting scheduler for fast devices. And the wider trend continues past scheduling entirely: io_uring lets applications submit and complete thousands of operations through shared ring buffers with no system call per operation, and zoned namespaces (ZNS) hand the host responsibility for sequential-only zones so that the FTL's garbage collection can be eliminated rather than merely tolerated. In both cases the direction is the same one this whole topic describes — the software layer stops second-guessing the device and starts cooperating with it.

Example

   THE MODEL CHANGES COMPLETELY

   HDD                                   SSD (NVMe)
   cost = f(distance)                    cost = f(concurrency, GC state)
   one arm -> serialise and sort         many dies -> parallelise and merge
   deep sorting pays                     sorting is pure overhead
   scheduler adds value                  scheduler mostly adds latency

   SINGLE QUEUE vs blk-mq

   legacy                                blk-mq
   core0 --\                             core0 -> [sw q0] -\
   core1 ---> [ ONE queue + LOCK ] -> dev core1 -> [sw q1] --> [hw q0..qN] -> dev
   core2 --/    contention, cache          core2 -> [sw q2] -/
                line bouncing              per-CPU submission, no global lock

   WHAT STILL PAYS ON FLASH: MERGING, NOT SORTING

   requests:  LBA 100 (4K), 108 (4K), 116 (4K), 124 (4K)
     sorted   -> 4 commands, 4 completions   (order changed nothing)
     MERGED   -> 1 command for 16 KB         (1/4 of the per-request overhead)

   THE LATENCY TAIL COMES FROM GC, NOT FROM SEEKS

   read latency: |..|..|..|..|.....................|..|..|
                                    ^
                        stuck behind a 5 ms block erase
   p50 = 80 us, p99.9 = 5 ms. Sorting by LBA cannot help; shaping
   write bursts and reserving over-provisioning can.

# The recommended configuration, and how to verify it.
cat /sys/block/nvme0n1/queue/scheduler        # [none] mq-deadline kyber bfq
cat /sys/block/nvme0n1/queue/nr_requests      # per-queue depth
ls /sys/block/nvme0n1/mq/                     # one directory per hardware queue

# Measure rather than assume: same workload, three schedulers.
for s in none mq-deadline kyber; do
  echo $s | sudo tee /sys/block/nvme0n1/queue/scheduler >/dev/null
  sudo fio --name=$s --filename=/dev/nvme0n1 --rw=randread --bs=4k \
           --iodepth=32 --numjobs=4 --direct=1 --runtime=30 --time_based \
           --readonly --output-format=json | jq -r \
    '"\(.jobs[0].jobname): \(.jobs[0].read.iops|floor) IOPS, p99 \(.jobs[0].read.clat_ns.percentile."99.000000"/1000)us"'
done
# none:        612000 IOPS, p99 180us
# mq-deadline: 410000 IOPS, p99 260us   <- sorting costs, buys nothing
# kyber:       585000 IOPS, p99 140us   <- lower tail under mixed load

# Why merging survives and sorting does not: a per-request overhead model.

PER_REQUEST_US = 6.0      # driver, doorbell, completion, interrupt handling
PER_KB_US      = 0.35     # actual data movement

def cost_us(n_requests, kb_each):
    return n_requests * (PER_REQUEST_US + kb_each * PER_KB_US)

print(cost_us(4, 4))      # 29.6 us -- four separate 4 KB commands
print(cost_us(1, 16))     # 11.6 us -- one merged 16 KB command
# 61% saved, and NOT ONE BYTE of it came from reordering by address.

# Sorting on flash: pure loss.
SORT_OVERHEAD_US = 1.2
print(cost_us(4, 4) + SORT_OVERHEAD_US)   # 30.8 us: strictly worse than 29.6

Key takeaways

• Flash has no seek cost, so address-sorting optimises nothing and adds latency; none is the correct default for NVMe.
• Performance now comes from concurrency, so the kernel's job is to feed many dies — hence blk-mq's per-CPU software queues and multiple hardware queues.
• Merging adjacent requests still pays, because per-request overhead is real even when positioning is not.
• The dominant latency risk is a read stuck behind garbage collection or a slow program/erase, which motivates latency-targeting schedulers like kyber.
• Write shaping, alignment, and prompt discards matter for write amplification and endurance — objectives the classic algorithms never had.
• The trend continues beyond scheduling: io_uring removes per-operation system calls, and zoned namespaces move GC responsibility to the host.

🧪 Practice

1. Explain why C-LOOK can reduce throughput on an NVMe SSD, naming two distinct costs it introduces.
2. Run the three-scheduler fio comparison above (or reason it through) and state which metric would justify choosing kyber over none.
3. Interview-style: "Our database has stable p50 latency but a p99.9 forty times higher, on NVMe. Where do you look first?" Hint: seeks are not a candidate — think about what internal operation on flash takes milliseconds and what triggers it.

<a id="93-reliability-and-performance"></a>

9.3 Reliability and Performance

Individual drives fail, corrupt data silently, and run out of speed. This section covers the standard answer — combining many devices so the array is faster and more reliable than any member — plus the two storage roles the OS manages directly: the swap area behind virtual memory, and the tiering that decides which device holds what.

RAID Levels

Theory

A single disk has a mean time to failure (MTTF) of perhaps 100,000 hours — about eleven years, which sounds comfortable until you own a hundred of them, at which point you should expect a failure roughly every six weeks. Meanwhile a single disk also has a fixed ceiling on throughput. RAID — Redundant Arrays of Independent Disks — attacks both problems with the same idea: use several drives together, so that capacity, speed, and redundancy become things you can choose rather than things the hardware hands you.

The critical insight is that adding disks reduces reliability unless you add redundancy. If an array of N disks fails when any member fails, its MTTF is roughly MTTF/N — a hundred-disk array has a failure every six weeks. Redundancy inverts this: with a spare copy of the data, the array survives a member failure and only loses data if a second failure lands before the first is repaired. That is a far less likely event, and its probability is what the standard formulas estimate:

mirrored pair : MTTDL ~= MTTF^2 / (2 x MTTR)
RAID 5 (N)    : MTTDL ~= MTTF^2 / (N x (N-1) x MTTR)

With MTTF = 100,000 h and a mean repair time of 10 h, a mirrored pair has a mean time to data loss of about 57,000 years, and a five-disk RAID 5 about 5,700 years. Those numbers are optimistic — they assume independent failures, which drives from the same batch in the same rack at the same temperature are not — but they show the shape of the effect.

The levels differ in how redundancy is arranged:

Level	Technique	Min disks	Usable capacity	Survives	Read	Write	Where it fits
0	Striping only	2	N (100%)	nothing	Excellent	Excellent	Scratch data, caches
1	Mirroring	2	N/2 (50%)	1 disk (per pair)	Excellent	Good	Boot volumes, small critical sets
2	Bit-level + Hamming	3	varies	1 disk	—	—	Obsolete; drives have own ECC
3	Byte-level + dedicated parity	3	N-1	1 disk	Good	Poor	Obsolete
4	Block-level + dedicated parity	3	N-1	1 disk	Good	Poor	Rare; parity disk is a bottleneck
5	Block-level + distributed parity	3	N-1	1 disk	Excellent	Moderate	The general-purpose workhorse
6	Dual distributed parity	4	N-2	2 disks	Excellent	Poor	Large drives, long rebuilds
10	Stripe of mirrors	4	N/2	1 per mirror	Excellent	Excellent	Databases, write-heavy work

RAID 0 deserves its warning label: it is the only level with no redundancy, and it makes reliability strictly worse than a single disk while making the name ("redundant array") a misnomer. RAID 2 and 3 are historical — modern drives already carry per-sector ECC, so bit-level striping buys nothing. RAID 4's dedicated parity disk must be written on every single write in the array, making it the bottleneck; RAID 5 fixes this by rotating parity across all members.

The most important modern shift is the drift from RAID 5 to RAID 6, and the reason is drive capacity rather than drive quality. Rebuilding a failed member requires reading every remaining disk in full. A consumer drive's unrecoverable read error (URE) rate of one sector per 10^14 bits means an expected error every 12.5 TB read. Rebuilding a five-disk array of 4 TB drives reads 16 TB — so the chance of hitting a URE mid-rebuild is around 72%, and in RAID 5 a URE during rebuild means data loss, because there is no second parity to fall back on. RAID 6 tolerates exactly this: a whole disk gone and a bad sector elsewhere.

Two operational points complete the picture. A hot spare shrinks MTTR from "however long until a human notices" to minutes, and since MTTDL scales with 1/MTTR that is often the cheapest reliability improvement available. And RAID is emphatically not a backup: it protects against drive failure only, and replicates deletions, corruption, ransomware, and rm -rf instantly and faithfully to every member.

Example

   THE LEVELS, ONE STRIPE EACH (D=data block, P=parity, Q=second parity)

   RAID 0   disk0  disk1  disk2  disk3     capacity 100%, redundancy NONE
            D0     D1     D2     D3        any failure = total loss

   RAID 1   disk0  disk1                   capacity 50%
            D0     D0                      survives either disk
            D1     D1

   RAID 4   disk0  disk1  disk2  disk3     parity all on ONE disk
            D0     D1     D2     P(0-2)    -> disk3 written on EVERY write
            D3     D4     D5     P(3-5)       = bottleneck

   RAID 5   disk0  disk1  disk2  disk3     parity ROTATES
            D0     D1     D2     P(0-2)
            D3     D4     P(3-5) D5        -> write load spread evenly
            D6     P(6-8) D7     D8

   RAID 6   disk0  disk1  disk2  disk3  disk4
            D0     D1     D2     P      Q  -> survives ANY TWO failures
            D3     D4     P      Q      D5

   RAID 10  [ disk0 = disk1 ] [ disk2 = disk3 ]   mirror pairs...
              D0      D0        D1      D1        ...then striped across

   WHY BIG DRIVES KILLED RAID 5

   rebuild of 5 x 4 TB RAID 5: must read 16 TB from the survivors
   consumer URE rate 1 per 10^14 bits = one bad sector per 12.5 TB
   P(at least one URE during rebuild) ~= 1 - e^(-1.28) = 72%
   in RAID 5 that URE during rebuild = DATA LOSS (no second parity)
   in RAID 6 it is merely survivable  -> hence the migration

# Reliability arithmetic: why redundancy inverts the effect of adding disks.
MTTF_HOURS, MTTR_HOURS, HOURS_PER_YEAR = 100_000, 10, 8760

def years(hours): return hours / HOURS_PER_YEAR

# No redundancy: more disks means MORE failures.
for n in (1, 5, 100):
    print(f"RAID 0, {n:3} disks: MTTF {years(MTTF_HOURS/n):8.2f} years")
# RAID 0,   1 disks: MTTF   11.42 years
# RAID 0,   5 disks: MTTF    2.28 years
# RAID 0, 100 disks: MTTF    0.11 years   <- a failure every ~6 weeks

# With redundancy: loss needs a SECOND failure inside the repair window.
mirror = MTTF_HOURS**2 / (2 * MTTR_HOURS)
print(f"RAID 1 pair       : MTTDL {years(mirror):10.0f} years")   # 57,078
for n in (5, 8):
    r5 = MTTF_HOURS**2 / (n * (n - 1) * MTTR_HOURS)
    r6 = MTTF_HOURS**3 / (n * (n-1) * (n-2) * MTTR_HOURS**2)
    print(f"RAID 5, {n} disks  : MTTDL {years(r5):10.0f} years")
    print(f"RAID 6, {n} disks  : MTTDL {years(r6):10.3g} years")
# RAID 5, 5 disks  : MTTDL      5,708 years | RAID 6: 1.9e+07 years
# RAID 5, 8 disks  : MTTDL      2,038 years | RAID 6: 3.4e+06 years
# Note how RAID 5 degrades with array size and RAID 6 barely does.

import math
def rebuild_ure_risk(n_disks, tb_each, ure_rate=1e-14):
    bits_read = (n_disks - 1) * tb_each * 1e12 * 8      # read ALL survivors
    return 1 - math.exp(-bits_read * ure_rate)

print(f"{rebuild_ure_risk(5, 4):.1%}")    # 72.2% -- fatal in RAID 5
print(f"{rebuild_ure_risk(8, 2):.1%}")    # 67.4%

# Create and inspect a software RAID 6 array on Linux.
sudo mdadm --create /dev/md0 --level=6 --raid-devices=5 \
           --spare-devices=1 /dev/sd[b-g]     # the spare shrinks MTTR
cat /proc/mdstat                              # live status and rebuild progress
sudo mdadm --detail /dev/md0

# Simulate a failure and watch the spare take over automatically.
sudo mdadm --manage /dev/md0 --fail /dev/sdb
cat /proc/mdstat        # [====>................]  recovery = 21.3% ...

# Scrub the array: read everything and fix mismatches BEFORE a rebuild needs it.
echo check | sudo tee /sys/block/md0/md/sync_action
cat /sys/block/md0/md/mismatch_cnt      # non-zero means silent divergence

Key takeaways

• Adding disks without redundancy divides array MTTF by N; redundancy inverts this so that loss requires a second failure inside the repair window.
• RAID 0 is striping only — faster, larger, and less reliable than one disk.
• RAID 5 distributes parity to avoid RAID 4's dedicated-parity bottleneck and is the general-purpose default; RAID 6 adds a second parity and survives two failures.
• Large drives pushed practice from RAID 5 to RAID 6, because a URE during a multi-terabyte rebuild is fatal with single parity.
• RAID 10 gives the best write performance and rebuild behaviour at 50% capacity cost.
• MTTDL scales with 1/MTTR, so hot spares and prompt replacement often buy more reliability than a higher RAID level.
• RAID is not a backup: it replicates deletion and corruption perfectly.

🧪 Practice

1. For six 8 TB drives, give usable capacity and the number of tolerated failures under RAID 0, 5, 6, and 10.
2. Using MTTF = 150,000 h and MTTR = 4 h, compute MTTDL for a mirrored pair and a six-disk RAID 5, then recompute RAID 5 with MTTR = 48 h and comment.
3. Interview-style: "We run RAID 6 with nightly snapshots. Do we still need offsite backups?" Hint: enumerate the failure modes RAID addresses, then list ones it cannot — starting with anything that arrives as a valid write.

Mirroring and Striping

Theory

RAID levels are combinations of exactly two primitive techniques. Understanding the primitives separately makes every level self-explanatory, and explains a few behaviours that surprise people.

Striping splits data across disks to gain parallelism. The array is divided into fixed-size chunks (or strip size, typically 64 KB to 512 KB), and consecutive chunks live on consecutive disks. A request larger than one chunk therefore engages several disks at once, and its transfer time falls proportionally. Two distinct benefits follow, and they are worth distinguishing because different workloads need different ones:

• Throughput parallelism — one large request is split across N disks, so a single stream goes N times faster.
• Request parallelism — many small requests land on different disks and proceed concurrently, so IOPS scale with N.

Chunk size chooses between them. A small chunk spreads even tiny requests across many disks, maximising single-stream bandwidth but engaging every disk for every request. A large chunk keeps a small request on one disk, letting other disks serve other requests independently, which maximises aggregate IOPS. The rule of thumb: small chunks for a few large sequential streams (video, backups), large chunks for many small random requests (databases, mail servers).

Mirroring writes identical copies to two or more disks. Reads may be served by whichever copy is free — which makes read throughput scale with the number of copies, and lets the array pick the disk with the shorter queue or, on a rotating disk, the closer head. Writes must go to every copy, so write throughput does not improve; it is bounded by the slowest member, since the write is not complete until all copies are durable.

Combining them yields the two nested levels, and the order matters more than the names suggest:

• RAID 10 (1+0) — a stripe of mirrors: mirror disks in pairs first, then stripe across the pairs.
• RAID 01 (0+1) — a mirror of stripes: stripe first, then mirror the whole stripe set.

They have identical capacity and near-identical performance, but different fault tolerance. With four disks, a second failure is fatal in RAID 10 only if it hits the partner of the first failed disk — 2 of 6 possible pairs, so it survives 4 of 6. In RAID 01, the first failure breaks an entire stripe set, so any failure in the other set is fatal — 4 of 6 pairs, surviving only 2 of 6. Rebuild differs too: RAID 10 copies from one surviving partner (a simple disk-to-disk copy), while RAID 01 must rebuild an entire stripe set from the other set. RAID 10 is strictly better, and RAID 01 should not be used.

The analogy: striping is dealing one deck of cards into several piles so several people can search simultaneously; mirroring is photocopying the deck so a lost card is never a problem. Nesting them is doing both — and the lesson of 10-versus-01 is that you should photocopy each card and then deal, rather than deal and then photocopy each pile.

Example

   STRIPING: DATA SPREAD ACROSS DISKS (chunk = 64 KB)

   a 256 KB file    ->  disk0    disk1    disk2    disk3
                        chunk0   chunk1   chunk2   chunk3
                        (0-64K) (64-128K)(128-192)(192-256)
                        all four disks transfer AT THE SAME TIME
                        -> ~4x the single-disk transfer rate

   CHUNK SIZE IS THE THROUGHPUT / IOPS DIAL

   small chunk (16 KB)          large chunk (256 KB)
   one 64 KB read -> 4 disks    one 64 KB read -> 1 disk
   great single-stream MB/s     other disks stay free for OTHER requests
   poor concurrency             great aggregate IOPS
   USE: video, backups          USE: databases, mail, VMs

   MIRRORING: READS SCALE, WRITES DO NOT

   read  D0 -> serve from disk0 OR disk1 (whichever is free)  2x read IOPS
   write D0 -> MUST reach disk0 AND disk1                     1x write speed
                                (done only when the slowest one is durable)

   RAID 10 vs RAID 01: SAME CAPACITY, DIFFERENT SURVIVAL

   RAID 10 (mirror, then stripe)        RAID 01 (stripe, then mirror)
    stripe                               mirror
     +-- mirror A: [d0][d1]               +-- stripe X: [d0][d1]
     +-- mirror B: [d2][d3]               +-- stripe Y: [d2][d3]

    d0 fails: mirror A degraded          d0 fails: STRIPE X IS DEAD ENTIRELY
    fatal 2nd failure: d1 ONLY           fatal 2nd failure: d2 OR d3
    survives 4 of 6 disk pairs           survives 2 of 6 disk pairs
    rebuild: copy d1 -> d0 (one disk)    rebuild: reconstruct all of X from Y

# Which disk holds a given block, and what chunk size does to concurrency.
CHUNK_KB, N_DISKS = 64, 4

def stripe_location(block_offset_kb):
    chunk_index = block_offset_kb // CHUNK_KB
    return chunk_index % N_DISKS, chunk_index // N_DISKS   # (disk, chunk on it)

for off in (0, 64, 128, 192, 256, 320):
    d, c = stripe_location(off)
    print(f"offset {off:4} KB -> disk {d}, chunk {c}")
# offset  256 KB -> disk 0, chunk 1   <- wraps back to disk 0

def disks_touched(request_kb, chunk_kb, n_disks):
    return min(n_disks, max(1, -(-request_kb // chunk_kb)))   # ceiling division

for chunk in (16, 64, 256):
    for req in (4, 64, 1024):
        print(f"chunk {chunk:3} KB, request {req:4} KB -> "
              f"{disks_touched(req, chunk, N_DISKS)} disk(s)")
# chunk  16 KB, request   64 KB -> 4 disks  (fast single stream, no concurrency)
# chunk 256 KB, request   64 KB -> 1 disk   (slower single stream, 4x concurrency)

# RAID 10 vs RAID 01 survival, enumerated exhaustively.
from itertools import combinations
disks = [0, 1, 2, 3]
r10_pairs   = [{0, 1}, {2, 3}]           # mirror pairs
r01_stripes = [{0, 1}, {2, 3}]           # stripe sets, then mirrored

def survives_raid10(failed):
    return not any(set(failed) >= pair for pair in r10_pairs)   # both of a pair

def survives_raid01(failed):
    # Fatal when BOTH stripe sets are broken -- i.e. one failure in each.
    return not all(any(d in s for d in failed) for s in r01_stripes)

pairs = list(combinations(disks, 2))
print("RAID 10 survives", sum(survives_raid10(p) for p in pairs), "of", len(pairs))
print("RAID 01 survives", sum(survives_raid01(p) for p in pairs), "of", len(pairs))
# RAID 10 survives 4 of 6 | RAID 01 survives 2 of 6

# Build a RAID 10 with an explicit chunk size chosen for the workload.
sudo mdadm --create /dev/md0 --level=10 --raid-devices=4 \
           --chunk=256 /dev/sd[b-e]        # 256 KB: random-IOPS oriented

# Read back the geometry the array is actually using.
sudo mdadm --detail /dev/md0 | grep -Ei 'chunk|layout|level'
cat /sys/block/md0/md/chunk_size

# Align the file system to the array so writes do not straddle chunks.
# stride = chunk / fs-block ; stripe-width = stride x data disks (2 for 4-disk R10)
sudo mkfs.ext4 -b 4096 -E stride=64,stripe-width=128 /dev/md0
# Misalignment here silently turns full-stripe writes into read-modify-writes.

Key takeaways

• Striping distributes chunks across disks, giving both single-stream throughput (a large request split N ways) and aggregate IOPS (small requests on different disks).
• Chunk size trades these against each other: small chunks favour sequential bandwidth, large chunks favour concurrent small requests.
• Mirroring scales reads (any copy will do) but not writes (every copy must be written, and completion waits for the slowest).
• RAID 10 mirrors then stripes; RAID 01 stripes then mirrors. Capacity is equal, but RAID 10 survives more double-failure combinations and rebuilds from a single partner disk.
• File system stride and stripe-width must be aligned to the array's chunk geometry, or full-stripe writes degrade into read-modify-writes.

🧪 Practice

1. An 8-disk RAID 0 uses 128 KB chunks. Which disk holds the byte at offset 1,200,000, and how many disks does a 512 KB read engage?
2. A mirrored pair of drives each does 200 IOPS. Give the array's read and write IOPS, and explain the asymmetry.
3. Interview-style: "Two arrays, same four disks, same capacity — one RAID 10, one RAID 01. Which do you deploy and why?" Hint: enumerate every two-disk failure combination for each layout and count the survivable ones.

Parity and Error Correction

Theory

Mirroring is conceptually simple but costs 50% of capacity. Parity achieves single-failure tolerance for the cost of one disk regardless of array size — and the mechanism is one XOR.

XOR has the property that makes this work: it is its own inverse. If P = D0 XOR D1 XOR D2, then any missing operand can be recovered by XORing everything that remains, including P. Lose D1 and compute D0 XOR D2 XOR P, and D1 comes back exactly. Nothing is stored twice; the parity block holds just enough information to reconstruct whichever single block is missing.

The crucial precondition is that you must know which block is missing. Parity is erasure coding, not error detection: it can reconstruct a block whose absence is announced (a dead drive, a sector the drive reports as unreadable), but given three data blocks and a parity block that disagree, it cannot tell you which one is wrong. This is exactly why parity alone is insufficient against silent corruption, and why the checksum discussion below is not an optional extra.

Parity's cost appears on writes, in the form of the small-write penalty. Changing one block requires updating parity, and parity depends on every block in the stripe. Rather than read the whole stripe, implementations use the incremental identity:

P_new = P_old XOR D_old XOR D_new

which needs two reads (old data, old parity) and two writes (new data, new parity): four I/O operations for one logical write. RAID 6 needs six, because there are two parity blocks. A full-stripe write escapes the penalty entirely — if every block in the stripe is being written, parity is computed directly with no reads at all, which is why write-back caching, log-structured layouts, and stripe-aligned file systems matter so much on parity arrays.

RAID 6's second parity, Q, cannot be another XOR — two identical equations cannot solve for two unknowns. Q is computed with Reed-Solomon coding over the Galois field GF(2^8), multiplying each block by a distinct constant before combining. That gives two independent equations in two unknowns, so any two missing blocks can be recovered by solving the pair.

Parity arrays also suffer the write hole: if power is lost between writing the data block and writing the parity block, the stripe is inconsistent, and a later rebuild will "reconstruct" wrong data from bad parity — silently. Battery-backed write caches, journals, and copy-on-write layouts (ZFS's RAID-Z writes variable-width full stripes and so has no hole at all) are the standard defences.

Below RAID sits a second, older layer of protection. Every sector carries an ECC computed by the drive: Reed-Solomon on hard disks, LDPC on modern SSDs, correcting small numbers of bit errors invisibly and reporting an unrecoverable read error only when the damage exceeds the code's capacity. That handles bit rot within a sector, but not a drive that returns the wrong sector, a controller that writes to the wrong address, or a cable that flips a bit in flight — "silent" corruption that arrives with every appearance of validity.

Defending against that requires end-to-end checksums: the file system stores a hash of each block's contents in the block's parent metadata, and verifies it on every read. ZFS and Btrfs do this, and the payoff is exactly the case parity cannot handle — when a mirror's two copies disagree, the checksum identifies which one is right, so the array can repair itself instead of guessing. Combined with periodic scrubbing (reading and verifying everything on a schedule), this converts latent corruption from a time bomb discovered during a rebuild into a routine, automatically repaired event.

Example

   XOR PARITY: ONE EQUATION, ANY ONE UNKNOWN

   D0 = 1101
   D1 = 0110
   D2 = 1001
   ---------  XOR
   P  = 0010          (1101 ^ 0110 = 1011, ^ 1001 = 0010)

   disk 1 dies. Recover D1 from everything that remains:
   D0 ^ D2 ^ P = 1101 ^ 1001 ^ 0010
               = 0100 ^ 0010
               = 0110   <- exactly D1, bit for bit

   BUT: given D0, D1, D2, P that DISAGREE, parity cannot say which is wrong.
   Parity corrects ERASURES (known-missing), not ERRORS (unknown-wrong).

   THE SMALL-WRITE PENALTY (RAID 5): 1 logical write = 4 physical I/Os

   write 4 KB to D1:
     1. READ  D1_old       (needed for the incremental identity)
     2. READ  P_old
     3. WRITE D1_new
     4. WRITE P_new = P_old ^ D1_old ^ D1_new
   RAID 6: 6 I/Os (read D, P, Q; write D, P, Q)

   FULL-STRIPE WRITE: no reads at all
     write D0,D1,D2 together -> P = D0^D1^D2 computed directly -> 4 writes
     => 3 blocks of data for 4 I/Os, instead of 3 blocks for 12.

   THE WRITE HOLE

   t0  write D1_new  -> SUCCEEDS
   t1  POWER LOSS
   t2  write P_new   -> NEVER HAPPENS
   stripe is now inconsistent. Nothing reports an error. A later rebuild
   uses the stale parity and reconstructs GARBAGE, confidently.

   THE TWO LAYERS OF PROTECTION, AND THE GAP BETWEEN THEM

   per-sector ECC (in the drive)   catches bit rot inside a sector
   RAID parity                     catches a WHOLE DRIVE being gone
   ---------------------------------------------------------------
   GAP: misdirected write, phantom write, bit flip on the cable
        -> data is wrong but looks perfectly valid to both layers
   end-to-end checksums (ZFS/Btrfs) close the gap AND tell a mirror
        which of two disagreeing copies is the correct one

# Parity, reconstruction, and the write penalty -- all of it is XOR.

def parity(blocks):
    p = 0
    for b in blocks:
        p ^= b                      # XOR is associative and commutative:
    return p                        # order does not matter

D = [0b1101, 0b0110, 0b1001]
P = parity(D)
print(format(P, '04b'))             # 0010

def reconstruct(surviving, parity_block):
    return parity(surviving + [parity_block])     # XOR everything that is left

print(format(reconstruct([D[0], D[2]], P), '04b'))   # 0110 == D[1]

# The incremental identity that avoids reading the whole stripe.
d1_new = 0b1111
p_new_incremental = P ^ D[1] ^ d1_new             # 2 reads + 2 writes
p_new_full        = parity([D[0], d1_new, D[2]])  # recompute from scratch
assert p_new_incremental == p_new_full            # identical result, less I/O

# Counting physical I/Os per logical 4 KB write.
def write_ios(level, full_stripe, data_disks):
    if level == 5:
        return (data_disks + 1) if full_stripe else 4
    if level == 6:
        return (data_disks + 2) if full_stripe else 6
    if level == 1:
        return 2                                  # mirroring: write both copies
    return 1

print(write_ios(5, False, 4))   # 4 <- the small-write penalty
print(write_ios(6, False, 4))   # 6
print(write_ios(5, True,  4))   # 5 I/Os for FOUR blocks of data, not one

# Why parity alone cannot identify a corrupted block.
corrupted = [0b1101, 0b0111, 0b1001]              # D1 silently flipped one bit
print(parity(corrupted) != P)   # True: we know SOMETHING is wrong...
                                # ...but not WHICH block. A checksum per block
                                # answers that; parity never can.

# Scrub regularly: find latent corruption before a rebuild depends on it.
sudo zpool scrub tank
zpool status tank
#   scan: scrub repaired 128K in 02:14:31 with 0 errors
#   NAME   STATE  READ WRITE CKSUM
#   tank   ONLINE    0     0     0
#   raidz2 ONLINE    0     0     0
#     sdb  ONLINE    0     0     2   <- checksum errors: silent corruption,
#                                       detected AND repaired from redundancy

sudo btrfs scrub start -B /mnt/data
sudo btrfs scrub status /mnt/data

# md RAID has no checksums, so 'check' can only report mismatches, not fix them.
echo check | sudo tee /sys/block/md0/md/sync_action
cat /sys/block/md0/md/mismatch_cnt     # non-zero: which disk is wrong? unknown.

# Battery/flash-backed write cache is the standard write-hole defence on HW RAID.
sudo storcli /c0 show | grep -i 'bbu\|cache'

Key takeaways

• Parity is XOR: P = D0 XOR D1 XOR ... , and any single missing block is recovered by XORing all survivors with P.
• It corrects erasures, not errors — parity cannot identify which block is wrong when blocks disagree.
• The small-write penalty is four I/Os per logical write in RAID 5 and six in RAID 6; full-stripe writes avoid it entirely.
• RAID 6's second parity uses Reed-Solomon over GF(2^8), giving two independent equations so two unknowns can be solved.
• The write hole leaves a stripe inconsistent after a power loss mid-write; battery-backed caches, journals, or copy-on-write layouts close it.
• Per-sector ECC handles bit rot, but misdirected and phantom writes need end-to-end checksums, which also let a mirror decide which copy is correct.
• Scrubbing turns latent corruption into a routine repair instead of a surprise during a rebuild.

🧪 Practice

1. Given D0 = 1011, D1 = 0101, D2 = 1110, compute P. Then assume D2 is lost and reconstruct it, showing each XOR.
2. A RAID 5 array of five disks sustains 400 random 4 KB writes per second at the application level. How many physical I/Os per second must the disks perform? Redo the calculation for RAID 6 and RAID 10.
3. Interview-style: "A RAID 5 array rebuilt successfully after a disk failure, but a database on it now returns corrupt rows. Give a plausible mechanism." Hint: think about what could have been wrong in the stripe before the rebuild started, and what the rebuild does with parity it has no way to validate.

Swap Space Management

Theory

Chapter 8 treated the backing store as an abstraction — "pages go to disk." This topic is that abstraction made concrete: how the OS lays out swap space, decides what goes there, and keeps a slow device from destroying interactive performance.

Swap space holds anonymous pages: memory with no file behind it — the heap, the stack, malloced regions, anonymous mappings. It is worth being precise, because a common misconception hides here. File-backed pages (program text, memory-mapped files, the page cache) do not need swap; if they are clean they can simply be dropped and re-read from the file. Swap exists specifically for pages that have nowhere else to go.

Two layouts are possible. A swap partition is a raw device region: no file system in the path, contiguous blocks, and the OS manages its own slot allocation — historically the faster option. A swap file lives inside a file system, so it can be created, resized, and removed without repartitioning, at the cost of going through the file system's block mapping. On modern kernels and hardware the performance difference is small enough that flexibility usually wins, which is why swap files are now the common default.

The OS tracks swap as an array of page-sized slots and maintains a map from slot to owner. Because the page table entry for a swapped-out page is invalid anyway, the kernel reuses its bits to record the slot number — a neat trick that avoids a separate data structure entirely. A swap cache tracks pages present in both memory and swap; if such a page has not been modified since it was read back, it can be evicted again without being rewritten, which turns a repeated swap-in/swap-out cycle from two I/Os into one.

The policy question is how eagerly to swap. Linux exposes this as vm.swappiness (0–200, default 60), which biases reclaim between evicting file-backed pages and swapping anonymous ones. The tempting move — set it to 0 and "avoid swapping" — is usually a mistake. A small amount of swapping is beneficial: it evicts genuinely idle anonymous pages (initialisation code, an idle daemon's heap) and hands that memory to the page cache, where it does measurable good. What is harmful is sustained swapping of an active working set, which is the thrashing of Chapter 8. Swap does not cause thrashing; insufficient memory does. Disabling swap does not fix the shortage, it merely changes the symptom from slowness to the OOM killer.

The modern refinement is compressed swap. zram creates a compressed block device in RAM and swaps to it; zswap puts a compressed cache in front of a real swap device. Compressing a page costs microseconds while writing one to disk costs hundreds, and typical anonymous pages compress by a factor of two to four — so a large fraction of swap traffic never touches storage at all. This is the default configuration on Android, on Chrome OS, and increasingly on Linux desktops.

Sizing has largely escaped its folklore. The old "twice RAM" rule dates from machines with 64 MB and is meaningless at 64 GB. The real drivers are: enough space for hibernation (which must hold all of RAM), enough headroom to absorb idle anonymous pages, and whatever a specific workload actually demands. Windows manages pagefile.sys automatically with the same considerations, and macOS creates swap files dynamically with no configuration at all.

Example

   WHAT GOES TO SWAP, AND WHAT DOES NOT

   page type              backed by       on eviction
   ---------------------------------------------------------------
   program text (code)    the exe file    DROP it, re-read from disk
   mmap'd file, clean     that file       DROP it
   mmap'd file, dirty     that file       WRITE BACK to the file
   heap / stack / malloc  NOTHING         must go to SWAP  <-- this is why
   tmpfs / shared memory  NOTHING         must go to SWAP      swap exists

   THE PTE DOES DOUBLE DUTY AGAIN (compare Chapter 8)

   resident:     [ frame number ][ valid=1 ][ flags ]
   swapped out:  [  swap slot #  ][ valid=0 ][ flags ]
                    ^ the same bits, reinterpreted -- no extra table needed
   On fault: kernel reads valid=0, pulls the slot number from the PTE,
   reads that slot, installs the frame, sets valid=1, restarts the instruction.

   COMPRESSED SWAP: MOST TRAFFIC NEVER REACHES THE DEVICE

   without zswap:  page -> [ disk write ~200 us ] -> swap device
   with zswap:     page -> [ compress ~3 us ] -> RAM pool (1/3 the size)
                             overflow only -> disk

   4 GB of anonymous pages at 3:1 compression occupy ~1.3 GB of RAM
   and cost microseconds instead of milliseconds to reclaim.

   HEALTHY vs PATHOLOGICAL SWAPPING -- the RATE is the signal, not the SIZE

   healthy:      2 GB swapped, si/so ~ 0 KB/s   (idle pages parked, fine)
   thrashing:  0.5 GB swapped, si/so ~ 50 MB/s  (active working set, ALARM)

# What swap exists, and how heavily it is used.
swapon --show
# NAME       TYPE      SIZE USED PRIO
# /swapfile  file      8G   1.2G   -2
free -h
cat /proc/swaps

# THE metric: swap-in/swap-out RATE, not the amount in use.
vmstat 2 5
# procs -----------memory---------- ---swap-- -----io----
#  r  b   swpd   free  buff  cache   si   so    bi    bo
#  1  0 1258291 204800 ...            0    0     6    12   <- fine
#  4  3 1310720  51200 ...        51200 48128 ...          <- THRASHING

# Per-process swap usage, when you need to know who is responsible.
for p in /proc/[0-9]*; do
  s=$(grep -s VmSwap "$p/status" | awk '{print $2}')
  [ -n "$s" ] && [ "$s" -gt 0 ] && echo "$s KB $(cat $p/comm)"
done | sort -rn | head

# Create a swap file (no repartitioning needed).
sudo fallocate -l 8G /swapfile && sudo chmod 600 /swapfile
sudo mkswap /swapfile && sudo swapon /swapfile
echo '/swapfile none swap sw 0 0' | sudo tee -a /etc/fstab

# Policy. Lower = prefer dropping page cache; higher = prefer swapping anon.
sysctl vm.swappiness                 # 60 default
sudo sysctl -w vm.swappiness=10      # common on DB servers with ample RAM
# Setting 0 does NOT disable swap -- it makes the OOM killer more likely.

# Compressed swap in RAM: usually better than a swap partition on any device.
sudo modprobe zram
echo lz4 | sudo tee /sys/block/zram0/comp_algorithm
echo 4G  | sudo tee /sys/block/zram0/disksize
sudo mkswap /dev/zram0 && sudo swapon -p 100 /dev/zram0   # higher prio than disk
cat /sys/block/zram0/mm_stat        # orig_data_size compr_data_size ...

Key takeaways

• Swap holds anonymous pages (heap, stack, anonymous mappings); clean file-backed pages are dropped and re-read instead.
• Swap partitions avoid file system indirection; swap files trade a little performance for flexibility and are now the common default.
• The kernel reuses the invalid PTE's bits to store the swap slot number, so no extra per-page structure is needed.
• Moderate swapping is beneficial — it converts idle anonymous memory into page cache; sustained swapping of an active working set is thrashing.
• Disabling swap does not create memory; it replaces slow degradation with the OOM killer.
• Compressed swap (zram, zswap) trades microseconds of CPU for hundreds of microseconds of I/O and keeps most swap traffic in RAM.
• The diagnostic is the swap-in/swap-out rate (si/so), not the amount of swap in use.

🧪 Practice

1. Classify each as swap-backed or file-backed: a process's stack, its executable's text, a dirty mmap of a data file, a tmpfs file, a clean page-cache page.
2. free shows 6 GB of 8 GB swap in use, but vmstat shows si and so at 0. Is the system in trouble? Justify your answer.
3. Interview-style: "A team disabled swap entirely to 'avoid slow paging'. What did they actually change?" Hint: ask what the kernel now has to do when it cannot reclaim enough file-backed pages, and what happens to genuinely idle anonymous memory.

Storage Tiering

Theory

Nothing in the storage hierarchy is simultaneously fast, large, and cheap; every device picks two. Tiering is the systematic exploitation of that fact: keep hot data on expensive fast media, cold data on cheap slow media, and move it automatically as temperature changes. It is the same principle as CPU caching and virtual memory, applied one level down and at a much larger granularity.

The hierarchy spans roughly nine orders of magnitude in latency:

Tier	Typical latency	Cost per GB	Capacity	Volatile
CPU registers	~0.3 ns	—	bytes	Yes
L1/L2/L3 cache	1–40 ns	—	KB–MB	Yes
DRAM	~80 ns	$3–5	GB–TB	Yes
Persistent memory	~300 ns	$1–2	100s GB	No
NVMe SSD	20–100 us	$0.08–0.20	TB	No
SATA SSD	~100 us	$0.05–0.10	TB	No
Hard disk	5–10 ms	$0.015–0.03	10s TB	No
Cloud archive	minutes–hours	$0.001–0.004	unbounded	No
Tape	minutes	$0.005	PB	No

Notice the gaps. DRAM to NVMe is roughly 1,000x in latency; NVMe to HDD another 100x. Those cliffs are what tiering exists to hide, and they are also why getting placement wrong is so expensive.

Tiering comes in two architectural flavours, and confusing them causes real design errors:

• Caching keeps a copy on the fast tier while the authoritative data stays on the slow tier. A cache miss is a performance event; losing the cache entirely loses nothing (for a write-through cache). Examples: the page cache, ZFS's ARC and L2ARC, bcache, dm-cache.
• Tiering moves data, so exactly one tier holds it. Capacity is the sum of tiers rather than the largest, but a wrongly placed block is slow rather than merely uncached, and the fast tier is not disposable. Examples: enterprise array auto-tiering, HSM to tape, S3 lifecycle transitions.

Placement is driven by access statistics. The standard machinery is a promotion threshold (blocks accessed more than N times in a window move up), a demotion policy (typically LRU, and often lazy), and hysteresis to prevent thrashing between tiers — a block that oscillates around the threshold must not be copied back and forth continuously, since migration is itself expensive I/O.

Write handling is where designs diverge most. Write-through sends writes to both tiers, so the fast tier is disposable and consistency is simple, but write latency is the slow tier's. Write-back acknowledges at the fast tier and flushes later, giving excellent write latency at the cost of making the cache device authoritative for dirty data — which means it needs its own redundancy, or a failure loses acknowledged writes. This is the same trade-off as the write hole earlier in this section, and the same answer applies: if a fast layer holds the only copy of acknowledged data, that layer must be as reliable as the slow one.

Cloud storage classes are tiering with an explicit price list, and they add a dimension the local hierarchy does not have: retrieval cost and time. Archive tiers are cheap to store and expensive to read, sometimes with hours of restore latency, so the economics reward accurate cold classification and punish mistakes asymmetrically. The classic guide to whether data belongs on a faster tier is the five-minute rule (Gray and Putzolu, 1987): compare the cost of keeping a page in the fast tier against the cost of the I/Os saved by doing so. The break-even interval has shifted with every hardware generation, but the method — compare the price of memory against the price of the accesses it avoids — is exactly how tiering decisions should still be made.

Example

   THE HIERARCHY, WITH THE CLIFFS MARKED

   registers   0.3 ns   |
   L1/L2/L3    1-40 ns  |  bytes .. MB      volatile
   DRAM        80 ns    |  GB .. TB
   ------------------------ ~1,000x cliff ------------------------
   PMEM        300 ns   |  100s GB          persistent
   NVMe SSD    50 us    |  TB
   ------------------------ ~100x cliff --------------------------
   HDD         8 ms     |  10s TB
   ------------------------ ~10,000x cliff -----------------------
   cloud archive/tape   |  unbounded        minutes to hours

   CACHING vs TIERING -- the difference is WHERE THE ONLY COPY LIVES

   CACHING                          TIERING
   +-------------+ copy             +-------------+  the ONLY copy
   |  SSD cache  |                  |  SSD tier   |
   +------|------+                  +------|------+
          | miss -> fetch                  | migrate up/down
   +------v------+ AUTHORITATIVE    +------v------+  the ONLY copy
   |  HDD        |                  |  HDD tier   |
   +-------------+                  +-------------+
   capacity = HDD                   capacity = SSD + HDD
   lose the cache: lose nothing     lose the tier: LOSE DATA

   PROMOTION, DEMOTION, AND WHY HYSTERESIS IS REQUIRED

   block accessed 5x in window -> promote to SSD
   block idle for 24h          -> demote to HDD

   without hysteresis:  4,5,4,5,4,5 accesses -> promote,demote,promote,...
                        migration I/O swamps the benefit ("tier thrashing")
   with hysteresis:     promote at 5, demote only below 2 -> stable

   WRITE POLICY DECIDES WHO MUST BE RELIABLE

   write-through: ack after BOTH  -> cache disposable, slow-tier write latency
   write-back   : ack after FAST  -> fast writes, but the cache device now
                                     holds the only copy of acknowledged data
                                     => it needs redundancy of its own

# A tiering engine: access counting, promotion, demotion, and hysteresis.

class TieredStore:
    def __init__(self, fast_capacity, promote_at=5):
        self.fast       = set()              # blocks currently on the fast tier
        self.capacity   = fast_capacity
        self.promote_at = promote_at         # accesses needed to earn promotion
        self.counts     = {}
        self.fast_hits = self.slow_hits = self.migrations = 0

    def access(self, block):
        self.counts[block] = self.counts.get(block, 0) + 1
        if block in self.fast:
            self.fast_hits += 1
            return 50e-6                     # NVMe: 50 microseconds
        self.slow_hits += 1
        if self.counts[block] >= self.promote_at:
            self._promote(block)
        return 8e-3                          # HDD: 8 milliseconds

    def _promote(self, block):
        if len(self.fast) >= self.capacity:
            coldest = min(self.fast, key=lambda b: self.counts[b])
            # HYSTERESIS: only evict a resident block for a STRICTLY hotter one.
            # Without this test, two blocks of equal temperature trade places
            # forever and the migration I/O swamps the benefit.
            if self.counts[coldest] >= self.counts[block]:
                return
            self.fast.discard(coldest)
            self.migrations += 1             # demotion costs I/O too
        self.fast.add(block)
        self.migrations += 1

import random
random.seed(1)                               # reproducible run
store, blocks, total = TieredStore(fast_capacity=200), list(range(1000)), 0.0
for _ in range(20_000):
    # 80/20: 80% of accesses hit 20% of blocks -- the pattern tiering exploits.
    b = random.choice(blocks[:200]) if random.random() < 0.8 else random.choice(blocks)
    total += store.access(b)

print(f"fast hits  : {store.fast_hits}")            # fast hits  : 15835  (79%)
print(f"slow hits  : {store.slow_hits}")            # slow hits  : 4165
print(f"migrations : {store.migrations}")           # migrations : 200
print(f"avg latency: {total/20_000*1e6:.0f} us")    # avg latency: 1706 us
print(f"all-HDD    : {8e-3*1e6:.0f} us")            # all-HDD    : 8000 us
print(f"all-NVMe   : {50e-6*1e6:.0f} us")           # all-NVMe   : 50 us
# Fast media sized at 20% of the data absorbed 79% of accesses and cut average
# latency 4.7x. Migrations stayed at 200 -- one per hot block, not a churn:
# that stability is the hysteresis test doing its job.

# ZFS: RAM cache (ARC), SSD read cache (L2ARC), SSD write log (SLOG).
sudo zpool add tank cache /dev/nvme0n1p1     # L2ARC: disposable read cache
sudo zpool add tank log mirror /dev/nvme1n1 /dev/nvme2n1
# The SLOG is MIRRORED on purpose: it holds acknowledged sync writes.
arc_summary | head -30
zpool iostat -v tank 2

# lvmcache: an SSD cache in front of an HDD logical volume.
sudo lvcreate --type cache --cachemode writethrough \
     --cachevol fastvol -l 100%FREE vg0/slowvol
sudo lvs -o name,cache_total_blocks,cache_used_blocks,cache_read_hits

# Cloud lifecycle tiering -- the same policy, with a price list attached.
aws s3api put-bucket-lifecycle-configuration --bucket archive --lifecycle-configuration '{
  "Rules": [{
    "ID": "cool-down", "Status": "Enabled", "Filter": {"Prefix": "logs/"},
    "Transitions": [
      {"Days": 30,  "StorageClass": "STANDARD_IA"},
      {"Days": 90,  "StorageClass": "GLACIER"},
      {"Days": 365, "StorageClass": "DEEP_ARCHIVE"}
    ]}]}'
# Watch the retrieval side: DEEP_ARCHIVE costs little to hold and a great
# deal -- in money and in hours of latency -- to read back.

Key takeaways

• The storage hierarchy spans about nine orders of magnitude in latency, with sharp cliffs at DRAM-to-NVMe and NVMe-to-HDD.
• Caching keeps a copy with the slow tier authoritative; tiering moves data so one tier holds it — capacity adds up, but placement mistakes cost more.
• Placement uses access counting with promotion and demotion thresholds, and hysteresis is required to prevent migration thrashing.
• Write-through keeps the fast tier disposable at the cost of slow write latency; write-back is fast but makes the cache device authoritative, so it needs its own redundancy.
• Cloud storage classes add retrieval cost and restore latency as first-class dimensions, punishing misclassification of hot data asymmetrically.
• The five-minute rule's method still applies: compare the cost of fast-tier residency against the cost of the I/Os it avoids.

🧪 Practice

1. A workload does 10,000 IOPS with 90% hitting 10% of the data. Estimate average latency with all data on HDD (8 ms), all on NVMe (50 us), and with the hot 10% cached on NVMe.
2. Explain why a write-back SSD cache in front of an HDD array should itself be mirrored, and what exactly is lost if it is not.
3. Interview-style: "Our S3 bill dropped after moving objects to Glacier, then tripled the next month. What happened?" Hint: storage price is not the only line item — think about what an access to an archived object costs and how an application that is unaware of the tier behaves.

---

<a id="10-file-systems"></a>