Disks, SSDs, RAID and the I/O cost model

A database lives on drives that are far slower than memory, and the way those drives work explains much of how databases are built. A hard disk spends milliseconds moving its arm and waiting for the platter to turn before it can read one block, then streams the blocks that follow at little extra cost: random reads are expensive, sequential reads are cheap. An SSD has no moving parts, but it writes in pages and erases only whole blocks of pages, so random overwrites make it copy data you never asked it to write. A write is not safe until it has passed the operating system’s cache and the drive’s own cache. RAID combines several drives so that data survives a failed drive, and each level pays for that in capacity or in extra disk operations per write. Because moving blocks between storage and memory used to cost far more than anything else a query does, the classic cost model of query processing counts block transfers, and this track counts them too.

Hard disks: seek, rotation and transfer

A hard disk keeps data on spinning platters, in concentric tracks divided into sectors, and reads it with heads on an arm that moves across the platters. Reading one block takes three steps:

1. Seek: the arm moves the head to the right track. The example below assumes 9 ms on average.
2. Rotational latency: the head waits for the block to turn under it. A disk at 7,200 revolutions a minute turns once every 60,000 ÷ 7,200 = 8.33 ms, and on average the block is half a turn away, so the average wait is 4.17 ms.
3. Transfer: the head reads the block as it passes, at the drive’s transfer rate. 4,096 bytes at 200 MB/s take about 0.02 ms.

The program works this out for a drive with round numbers, then compares 1,000 blocks scattered over the disk with 1,000 blocks that lie one after another:

"""Seek, rotation and transfer: what one block read costs on a hard disk.

The drive is a round-number example, not a measured product: 7,200 revolutions
a minute, a 9 ms average seek and a sustained transfer rate of 200 MB/s.
"""
RPM = 7200
AVG_SEEK_MS = 9.0
TRANSFER_BYTES_PER_S = 200 * 10**6
BLOCK = 4096

revolution_ms = 60_000 / RPM
latency_ms = revolution_ms / 2                 # on average the block is half a turn away
transfer_ms = BLOCK / TRANSFER_BYTES_PER_S * 1000
one_random_ms = AVG_SEEK_MS + latency_ms + transfer_ms

print(f"one revolution               {revolution_ms:8.3f} ms")
print(f"average rotational latency   {latency_ms:8.3f} ms")
print(f"transfer of one 4 KB block   {transfer_ms:8.3f} ms")
print(f"one random block read        {one_random_ms:8.3f} ms  ({1000 / one_random_ms:.0f} a second)")

N = 1000
scattered_ms = N * one_random_ms               # every block needs its own seek and rotation
in_a_row_ms = AVG_SEEK_MS + latency_ms + N * transfer_ms   # one seek, then the blocks stream past
print(f"{N:,} scattered blocks         {scattered_ms:8.0f} ms")
print(f"{N:,} consecutive blocks       {in_a_row_ms:8.0f} ms  ({scattered_ms / in_a_row_ms:.0f} times faster)")

# A commit that waits for its writes to reach the platter: about two revolutions.
print(f"commits a second at two revolutions each: {1000 / (2 * revolution_ms):.0f}")

one revolution                  8.333 ms
average rotational latency      4.167 ms
transfer of one 4 KB block      0.020 ms
one random block read          13.187 ms  (76 a second)
1,000 scattered blocks            13187 ms
1,000 consecutive blocks             34 ms  (392 times faster)
commits a second at two revolutions each: 60

One random read costs about 13 ms, so the drive manages only about 76 of them a second, and the transfer is a tiny part of each. A thousand scattered blocks take 13 seconds; a thousand consecutive blocks take one seek, one wait and 34 ms in all, about 390 times faster. That ratio is why databases work so hard to read runs of consecutive blocks: a full scan reads the file in order, files grow in large chunks, and sorting writes long sorted runs.

The last line is a limit on writes. The SQLite FAQ explains that a commit normally needs two complete rotations of the platter, which on a 7,200 rpm disk limits you to about 60 transactions a second: the program’s 60. A thousand inserts in one transaction pay that price once; a thousand inserts that each commit pay it a thousand times.

SSDs: pages, erase blocks and the translation layer

An SSD stores data in NAND flash. Nothing moves, so a read waits for no seek and no rotation. Writing is where flash is unusual: it is read and written in pages but erased only in whole blocks of many pages, and a page cannot be written again until its whole block has been erased. In the flash part that Agrawal and colleagues used as their example in a 2008 study of SSD design, a page held 4 KB and a block 64 pages (256 KB); reading a page took 25 µs, writing one 200 µs and erasing a block 1.5 ms, and a block could be erased only about 100,000 times before it wore out. Other parts have other sizes and timings; the gap between reading, writing and erasing is what matters.

So an SSD never overwrites a page in place. Its flash translation layer (FTL) keeps a map from each logical block address that the computer uses to the physical page that holds it now. An overwrite goes to a fresh page, the map is updated, and the old page is marked invalid. When fresh pages run low, a cleaner (the garbage collector) picks a block with few valid pages, copies those pages elsewhere and erases the block. The copies are writes the computer never asked for: write amplification is the number of pages written to flash divided by the number the computer wrote. The simulation below runs a small FTL with a greedy cleaner and overwrites its data in two ways, in order and at random, with the drive half, three quarters and nine tenths full:

"""Why random overwrites cost an SSD more than the bytes you write.

A toy flash translation layer: 64 erase blocks of 32 pages. Every write goes to
a fresh page (flash cannot overwrite in place), the old copy becomes invalid,
and when free blocks run out the cleaner erases the block with the fewest
valid pages after copying those pages elsewhere. Write amplification is the
pages written to flash divided by the pages the host asked to write.
"""
import random

BLOCKS, PAGES = 64, 32


def simulate(used_share, pattern, host_writes=40_000, seed=7):
    rng = random.Random(seed)
    logical = int(BLOCKS * PAGES * used_share)   # pages the host can address
    where = {}                                   # logical page -> (block, page)
    valid = [set() for _ in range(BLOCKS)]       # logical pages stored in each block
    free = list(range(1, BLOCKS))
    open_block, next_page = 0, 0
    flash_writes = 0

    def place(lpage):
        nonlocal open_block, next_page, flash_writes
        if next_page == PAGES:                   # the open block is full
            open_block, next_page = free.pop(0), 0
        old = where.get(lpage)
        if old:
            valid[old[0]].discard(lpage)
        where[lpage] = (open_block, next_page)
        valid[open_block].add(lpage)
        next_page += 1
        flash_writes += 1

    def clean():
        while len(free) < 2:                     # keep two erased blocks in reserve
            victims = [b for b in range(BLOCKS) if b != open_block and b not in free]
            victim = min(victims, key=lambda b: len(valid[b]))
            for lpage in sorted(valid[victim]):  # copy the pages that are still valid
                place(lpage)
            valid[victim].clear()
            free.append(victim)                  # erased: ready for new writes

    for lpage in range(logical):                 # fill the drive once
        place(lpage)
        clean()
    flash_writes = 0
    for i in range(host_writes):
        lpage = rng.randrange(logical) if pattern == "random" else i % logical
        place(lpage)
        clean()
    return flash_writes / host_writes


print("share of flash in use   pattern      write amplification")
for share in (0.50, 0.75, 0.90):
    for pattern in ("sequential", "random"):
        print(f"{share:>11.0%}            {pattern:<12} {simulate(share, pattern):6.2f}")

share of flash in use   pattern      write amplification
        50%            sequential     1.00
        50%            random         1.25
        75%            sequential     1.00
        75%            random         2.29
        90%            sequential     1.00
        90%            random         6.06

Overwriting in order invalidates whole blocks together, so the cleaner always finds empty blocks and copies nothing: amplification 1.00 at every fill level. Random overwrites leave every block partly valid, and the fuller the drive, the more each cleaning has to copy: here 1.25 flash writes per page at half full, 2.29 at three quarters and 6.06 at nine tenths. Every extra write costs time and wears the flash. That is why drives keep spare capacity the computer cannot address, and why writing in order, as a database’s log does, costs a drive the least.

Durable writes: the caches between you and the media

A write is not durable just because write() returned. PostgreSQL’s chapter on reliability lists the layers between a program and the disk: the operating system’s buffer cache, a cache in the disk controller (common on RAID cards), and the drive’s own cache. It warns that consumer-grade drives are particularly likely to have write-back caches that do not survive a power failure, and that many SSDs do not honour cache flush commands by default. Apple’s manual page for fsync is just as direct: fsync() moves the data to the drive, but the drive may write it to the platters much later and in a different order, and the F_FULLFSYNC request asks the drive to flush everything it holds to permanent storage.

The program below times each step on the computer that recorded this lesson’s runs, a Mac with Apple silicon and its internal SSD: a plain write, a write followed by os.fsync(), and a write followed by F_FULLFSYNC.

"""How long a 4 KB write takes, and how long until it is really safe.

write() hands the bytes to the operating system's cache; os.fsync() asks the
system to pass them to the drive; on macOS, fcntl's F_FULLFSYNC also asks the
drive to move them from its own cache to permanent storage. The timings depend
on the computer, the drive and what else is running, so they differ every run.
"""
import os
import statistics
import time

try:
    import fcntl
except ImportError:          # Windows has no fcntl module
    fcntl = None

PAGE = bytes(4096)
ROUNDS = 200


def median_us(make_durable):
    fd = os.open("probe.bin", os.O_WRONLY | os.O_CREAT | os.O_TRUNC, 0o600)
    times = []
    try:
        for i in range(ROUNDS):
            start = time.perf_counter_ns()
            os.pwrite(fd, PAGE, (i % 64) * len(PAGE))
            if make_durable:
                make_durable(fd)
            times.append((time.perf_counter_ns() - start) / 1000)
    finally:
        os.close(fd)
        os.remove("probe.bin")
    return statistics.median(times)


steps = [("write() only", None), ("write() + os.fsync()", os.fsync)]
if fcntl is not None and hasattr(fcntl, "F_FULLFSYNC"):
    steps.append(("write() + F_FULLFSYNC", lambda fd: fcntl.fcntl(fd, fcntl.F_FULLFSYNC)))

print(f"{ROUNDS} writes of {len(PAGE):,} bytes, median time of each step")
slowest = 0.0
for label, make_durable in steps:
    us = median_us(make_durable)
    slowest = max(slowest, us)
    print(f"{label:<24} {us:10.1f} µs")
print(f"one durable commit at a time: at most {1_000_000 / slowest:,.0f} commits a second")

200 writes of 4,096 bytes, median time of each step
write() only                    2.2 µs
write() + os.fsync()           61.3 µs
write() + F_FULLFSYNC        3998.5 µs
one durable commit at a time: at most 250 commits a second

The plain write took a few microseconds, because it only copied the bytes into the operating system’s cache. os.fsync() took tens of microseconds, and on macOS it still leaves the data in the drive’s cache. F_FULLFSYNC, which asks the drive to flush everything it holds to permanent storage, took about 4 ms. A system that flushes once per commit, one commit at a time, therefore manages about 250 commits a second here: better than the 60 of a 7,200 rpm disk, but far from the hundreds of thousands of plain writes a second. Run it on your own computer and the numbers will differ.

Databases choose which of these steps a commit waits for. SQLite’s PRAGMA fullfsync turns F_FULLFSYNC on; it is off by default, and SQLite’s documentation notes that only macOS supports it. PostgreSQL’s manual says that on macOS write caching can be prevented by setting wal_sync_method to fsync_writethrough. And both try to make one flush cover many changes: SQLite’s FAQ advises putting many statements in one transaction, and PostgreSQL’s commit_delay setting exists to let more transactions from different sessions commit through a single flush of the log, which is called group commit.

RAID: striping, mirroring and parity

RAID (redundant arrays of inexpensive disks) makes several drives look like one. Patterson, Gibson and Katz’s 1988 paper that introduced the name described five levels, numbered 1 to 5; RAID 0, 6 and 10 are names that came into use later, and Linux’s md driver, for one, offers levels 0, 1, 4, 5, 6 and 10. The levels combine three ideas:

• RAID 0 stripes: consecutive chunks of data go to different drives, so large reads and writes use every drive at once. Nothing is stored twice, so one failed drive loses the array.
• RAID 1 mirrors: every block is written to two drives, and either copy can serve a read. It survives the loss of one drive and stores one drive’s worth of data.
• RAID 5 stripes with parity: in each stripe one block holds the XOR of the others, and the parity block moves to a different drive from stripe to stripe. Any one failed drive can be rebuilt from the rest.
• RAID 6 keeps two independent check blocks in every stripe instead of one. It survives any two failed drives and gives up two drives’ worth of space.
• RAID 10 stripes over mirrored pairs. It survives one failure for certain, and more when the failed drives sit in different pairs.

Parity has a price on small writes. To change one block in RAID 5, the array reads the old block and the old parity, computes the new parity as old parity XOR old data XOR new data, and writes the new block and the new parity: four disk operations for one logical write. RAID 6 needs six, a mirror two. The program sets six 4 TB drives against each level:

"""Capacity, failures survived and the cost of a small write for common RAID levels.

Six drives of 4 TB each. "Survives" is the guarantee: any that many drives may
fail at once. A small write changes one block in place, and the parity or the
copy of that block must change with it, so it costs several disk operations.
"""
from itertools import combinations

DRIVES, SIZE_TB = 6, 4

LEVELS = [
    # name, drives' worth of data, failures always survived, disk operations per small write
    ("RAID 0", DRIVES, 0, 1),        # striping, no redundancy
    ("RAID 5", DRIVES - 1, 1, 4),    # read data and parity, write data and parity
    ("RAID 6", DRIVES - 2, 2, 6),    # read data and two check blocks, write all three
    ("RAID 10", DRIVES // 2, 1, 2),  # three mirrored pairs, striped: write both copies
]

print(f"{DRIVES} drives of {SIZE_TB} TB = {DRIVES * SIZE_TB} TB raw")
print(f"{'level':<8}{'usable':>8}{'share':>7}{'survives':>10}{'operations':>12}{'small-write rate':>18}")
print(f"{'':<8}{'':>8}{'':>7}{'failures':>10}{'per write':>12}{'vs one drive':>18}")
for name, data_drives, survives, ops in LEVELS:
    print(f"{name:<8}{data_drives * SIZE_TB:>5} TB{data_drives / DRIVES:>7.0%}{survives:>10}{ops:>12}{DRIVES / ops:>17.1f}x")

# RAID 10 often survives a second failure: only two drives of the same mirror are fatal.
mirrors = {(0, 1), (2, 3), (4, 5)}
pairs = list(combinations(range(DRIVES), 2))
survived = [p for p in pairs if p not in mirrors]
print(f"RAID 10 with two failed drives: {len(survived)} of {len(pairs)} pairs survive "
      f"({len(survived) / len(pairs):.0%})")

6 drives of 4 TB = 24 TB raw
level     usable  share  survives  operations  small-write rate
                         failures   per write      vs one drive
RAID 0     24 TB   100%         0           1              6.0x
RAID 5     20 TB    83%         1           4              1.5x
RAID 6     16 TB    67%         2           6              1.0x
RAID 10    12 TB    50%         1           2              3.0x
RAID 10 with two failed drives: 12 of 15 pairs survive (80%)

The trade-off is plain in the table. RAID 6 stores the most of the safe levels and survives two failures, but six operations per small write leave it with the random-write speed of a single drive. RAID 10 stores the least and survives one failure for certain (four failed pairs in five are survivable), but it writes small blocks three times as fast as RAID 6. Write-heavy databases tend towards mirrors, data that is mostly read towards parity.

Two failure cases matter on top of the table. A parity array that has lost a drive has no redundancy left until the rebuild ends (RAID 5) or only one drive’s worth (RAID 6), and the rebuild reads every surviving drive in full. And a crash in the middle of a stripe update can leave data and parity that disagree: Linux’s md documentation warns that a RAID 5 or 6 array that is both dirty and degraded could have undetectable data corruption, and md refuses to start such an array by default.

The I/O cost model of this track

From here on, the lessons of this track count the cost of an operation in block transfers: how many blocks it reads from storage or writes to it. B stands for the size of a block in bytes and b for the number of blocks in a file. Where the order matters, a lesson counts random accesses (each with its seek and wait) apart from the blocks that follow them in sequence: scanning a file of b blocks in order costs one seek and b transfers, while visiting the same b blocks in random order costs b of each.

The model leaves CPU time out on purpose. On the disk of this lesson a random read costs 13 ms; unless an operation reads nothing from storage, the reads decide how long it takes. Query planners price their choices the same way. PostgreSQL’s planner charges seq_page_cost (1.0 by default) for a page read in sequence and random_page_cost (4.0 by default) for a page read out of order. Its manual is open about the choice: on storage that has to be read, a random page costs much more than four sequential ones, and the default is lower only because most random reads are expected to find their page already cached.

The model has a limit. When the data fits in memory, as it does for a main-memory engine or a hot table, block transfers stop dominating and CPU and memory traffic decide; the lesson on buffer pools picks that up. The next lesson opens the block itself: how a page of a table lays out its records.

Exercise

"""Storage arithmetic: the time of a disk read and the capacity of a RAID array.

Times are in milliseconds, transfer rates in megabytes (10**6 bytes) a second
and drive sizes in terabytes. RAID levels are the strings "0", "1", "5", "6"
and "10".
"""


def rotational_latency_ms(rpm):
    """The average wait for the block to turn under the head: half a revolution."""
    # Replace this line with your code.
    return 0.0


def random_read_ms(seek_ms, rpm, transfer_mb_s, block_bytes):
    """Seek, wait for the block to come round, then transfer it."""
    # Replace this line with your code.
    return 0.0


def raid_usable_tb(level, drives, size_tb):
    """Terabytes one array of equal drives can store; ValueError when the level needs more drives."""
    # Replace this line with your code.
    return 0


def small_write_ops(level):
    """Disk operations needed to change one block in place."""
    # Replace this line with your code.
    return 0

from math import isclose

from storage_math import raid_usable_tb, random_read_ms, rotational_latency_ms, small_write_ops


def test_rotational_latency_is_half_a_revolution():
    """60,000 / rpm milliseconds for one revolution, half of it on average"""
    assert isclose(rotational_latency_ms(7200), 4.16667, rel_tol=1e-4)
    assert isclose(rotational_latency_ms(15000), 2.0, rel_tol=1e-9)
    assert isclose(rotational_latency_ms(5400), 5.55556, rel_tol=1e-4)


def test_random_read_adds_three_parts():
    """seek + rotational latency + transfer of the block"""
    assert isclose(random_read_ms(9, 7200, 200, 4096), 13.18715, rel_tol=1e-4)
    assert isclose(random_read_ms(4, 15000, 250, 8192), 6.032768, rel_tol=1e-6)
    assert isclose(random_read_ms(8, 5400, 100, 4096), 13.59652, rel_tol=1e-4)


def test_raid_capacity():
    """striping keeps all the space, mirrors one copy's worth, parity costs one or two drives"""
    assert raid_usable_tb("0", 4, 2) == 8
    assert raid_usable_tb("1", 2, 4) == 4
    assert raid_usable_tb("1", 3, 4) == 4
    assert raid_usable_tb("5", 6, 4) == 20
    assert raid_usable_tb("6", 8, 2) == 12
    assert raid_usable_tb("10", 6, 4) == 12
    assert raid_usable_tb("10", 8, 4) == 16


def test_raid_needs_enough_drives():
    """RAID 0 and 1 need 2 drives, RAID 5 needs 3, RAID 6 needs 4, RAID 10 an even number of at least 4"""
    for level, drives in [("0", 1), ("1", 1), ("5", 2), ("6", 3), ("10", 2), ("10", 5)]:
        try:
            raid_usable_tb(level, drives, 4)
        except ValueError:
            continue
        raise AssertionError(f"RAID {level} with {drives} drives should raise ValueError")
    assert raid_usable_tb("5", 3, 4) == 8
    assert raid_usable_tb("6", 4, 4) == 8


def test_small_write_costs():
    """parity levels read the old data and parity before they write the new ones"""
    assert [small_write_ops(level) for level in ["0", "1", "5", "6", "10"]] == [1, 2, 4, 6, 2]

Interview questions

Why is reading 1,000 random blocks from a hard disk so much slower than reading 1,000 consecutive blocks? Each random block costs a seek, to move the head to its track, and a rotational wait, half a revolution on average, before its transfer starts; on a 7,200 rpm disk with a 9 ms seek that is about 13 ms per block, almost all of it mechanical. Consecutive blocks pay the seek and the wait once and then stream under the head at the transfer rate, so 1,000 of them take tens of milliseconds instead of 13 seconds. That gap is why databases prefer sequential scans for large fractions of a table, allocate files in large contiguous chunks and write sorted runs. An SSD has no seek or rotation to pay, so the gap for reads is far smaller there, but random overwrites still cost it extra writes.

Why can’t an SSD overwrite a page in place, and what does it do instead? Flash memory can write a page only after the block that holds it has been erased, and it erases whole blocks of many pages at once, so rewriting one page in place would mean erasing and rewriting its whole block. Instead, the flash translation layer writes the new version to a fresh page, points the logical address at it and marks the old page invalid. A cleaner later copies the still-valid pages out of mostly invalid blocks and erases them. Those copies are extra writes, called write amplification, and they grow with random overwrites and with how full the drive is.

Key takeaways

• A hard-disk read costs seek + rotational latency + transfer; the average rotational latency is half a revolution, 4.17 ms at 7,200 rpm. Random blocks pay the mechanical part every time, consecutive blocks once.
• Flash writes pages but erases blocks, so an SSD writes out of place through its translation layer, and its cleaner adds write amplification that grows with random overwrites and with how full the drive is.
• write() reaches the operating system’s cache, fsync() the drive, and only a cache flush (F_FULLFSYNC on macOS) the flash itself. Each flush costs milliseconds, so databases share one flush among many commits.
• RAID 0 stripes, RAID 1 mirrors, RAID 5 and 6 add one or two check blocks per stripe, RAID 10 stripes mirrors; a small write costs 1, 2, 4, 6 and 2 disk operations.
• This track counts cost in block transfers, separating random accesses from sequential ones, because I/O decides the time of most operations on data that is not in memory.