BOOK DEEP READ · Database Internals · Chapter 5
Database Internals · Ch 5 · Alex Petrov · 2019
You tap "send money" on your phone. The spinner turns for half a second, then says success. Somewhere in that half second, the machine room loses power.
The first four chapters were about arranging data so it can be found fast. This one is about something else entirely: what happens when a change is only half made and the lights go out, and what happens when two people edit the same record at the same time. Without this chapter, that elegant index tree is a toy that only works for one user on a machine that never fails.
You probably assume the data files on disk are the database's master copy, and the log file sitting next to them is a backup. It is the other way round. The log is the master copy, the source of truth; the data files are just a fair copy of it — lose them and you can write them out again from the log. The whole reliability story rests on that inversion.
One: changing one thing means touching several places. A transfer subtracts here and adds there, and those two must both count or neither count — do half and money vanishes.
Two: changes happen in memory, and memory dies with the power. A database cannot make a trip to disk for every byte, so it pulls the pages it needs onto a "desk" in memory, edits them there and writes a batch back later. Cut the power mid-way and everything still on the desk is gone.
Three: writing to scattered spots on disk is agonizingly slow. The records you touched live on page 3, page 700 and page 90,000. Disks hate that kind of hunting around; what they love is writing straight on from where they stopped.
Write the ledger first, then touch the master copy. Before changing anything, add a line to a ledger that is only ever appended to, never gone back over: "I am about to change that number on page 700 from 100 to 80." Only once that line is safely on disk may you touch the master copy. The ledger is written straight on from where it stopped, exactly what a disk likes. So committing a transfer means waiting for one ledger line to land — the fair copy can be written out at leisure.
After a crash: replay first, undo second. This is the counterintuitive part. On restart the database does not begin by cleaning up the mess. It picks up the ledger and replays the whole stretch of history exactly as it happened — including the moves it already knows will have to be undone. Only once the world has been restored to the instant before the crash does it go back and undo the transactions that got half a sentence out and never said "I'm done." Laying the floor flat and then moving the furniture is far simpler than doing both at once.
Two completely different kinds of lock. One governs people: it stops you seeing work someone else has only half done, and it stays held for the whole transaction. The other governs hands: a page in memory is being rewritten right now, so another thread would read something half-finished — that one guards a few microseconds and is dropped the moment the edit is over. English calls both of them locks; they are not the same thing at all, and confusing them is the beginner's classic stumble.
With these in place a database can finally say success and mean it. Not "your money is already in the fair copy," but "this is written into the ledger, and the ledger really is on disk; leave the rest to me, a power cut cannot take it away." The cost hides in that same sentence: if any link in the chain — drive, firmware, filesystem — claims "written" when it has not, every clever design above it collapses together.
A database's truth is not in its data files, it is in that append-only ledger: write the entry before changing anything, and a commit waits only for that entry to land. After a crash, replay the whole history from the ledger first, then undo the sentences that were never finished. As for concurrency, remember there are two kinds of lock — one guarding the rules between transactions, one guarding a few microseconds on a single page in memory.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
This chapter promotes the storage engine from "a data structure that can store and find things" into an actual database: ACID is not supplied by any one module, it is squeezed out of three parts working together — the page cache, the write-ahead log, and concurrency control. Their shared trump card is a single rule: write down what you are about to do before you do it. From which follows the chapter's most counterintuitive judgement: the data files on disk are not the database's master copy. The log is. The data files are merely a materialized result of the log — discardable, recomputable.
8 KB, InnoDB to 16 KB).fsync — telling the OS to push bytes onto durable media and waiting for confirmation. The only operation that lets you say "this cannot be lost," and the slowest step in the whole chain.This is Chapter 5 of Part I, "Storage Engines," and the part's closing argument. The first four chapters — the overview, B-Tree basics, file formats, implementing B-Trees — all described how to lay out data in a world that is static, single-threaded and never loses power. This chapter throws that tree into the real one, where hundreds of connections read and write it at once and the power can go at any moment. Downstream, the copy-on-write of Ch6 (B-Tree Variants) is one branch of "another way to get atomicity," and Ch7 (LSM-Trees) promotes this chapter's log into the primary storage structure outright; in Part II, the local half of distributed transactions (Ch13) is exactly what is built here.
Put the first four chapters side by side and an awkward gap appears: one logically "atomic" change usually touches several pages. Inserting a record into a B-Tree may split a leaf, add a pointer to the parent, even push up a new root — three or four separate page modifications, and a power cut at any instant between them leaves a structurally broken tree on disk: a pointer into a page that was never finished, and the whole index is void.
Worse, none of those pages was modified on disk directly; they were modified in the page cache. Which means at any given moment the data files on disk are stale and internally inconsistent. Layer hundreds of concurrent transactions on top and the problem braids into three: how to move pages between memory and disk quickly but under control (page cache, eviction, checkpoints), how to reconstruct a self-consistent database out of a heap of half-finished work after a crash (logging and recovery), and how to keep concurrent transactions from seeing each other's half-finished work (concurrency control). Without all three, the strongest promise a database can offer is "good luck."
When an interview asks "how is ACID implemented," the right answer is not a sentence but a division of labour. A transaction passes through four components: the transaction manager coordinates it and decides commit or abort; the lock manager guards the logical objects it touches, making other transactions queue; the page cache pulls pages from disk into memory, where every modification actually happens; the log manager writes down what is about to change, before it changes.
The operating system already caches files, so why build another layer? Because the database needs three things the OS cannot give it: knowing which pages are in use (and must not be evicted), which have been modified (and must be flushed before eviction), and the authority to decide what gets written first. All three bear directly on correctness, so none can be delegated.
Four mechanisms matter. Pinning: a page in use carries a reference count, and a non-zero count forbids eviction — every page on a B-Tree's root-to-leaf path is pinned. Marking dirty: modified in memory, flagged. Eviction: when the cache fills, pick an unpinned page and drop it; if it is dirty it must be written back first, and before that, the log covering it must already be on disk. Checkpointing: rather than flushing reactively in dribs when the cache fills, flush in batches on a schedule and mark the log, pulling the recovery starting point forward.
Eviction policy is far messier than the textbook LRU, for a very practical reason: a single full table scan will wipe out a naive LRU. One SELECT * FROM big_table reads several million pages, uses each exactly once, and evicts hot pages accumulated over hours — when the scan ends the hit rate is zero and every query hits disk for minutes. So MySQL InnoDB splits its LRU list into a "young" and an "old" sublist: a newly read page is inserted at the midpoint (the head of the old sublist), not at the front, and is only promoted into the young sublist if it is accessed again. One-shot scan pages therefore make a lap of the old sublist and are evicted without ever touching the hot set. The old sublist defaults to 3/8 of the pool (innodb_old_blocks_pct defaults to 37).
The WAL rule is a single sentence that holds up the whole chapter: for any modification to a data page, its log record must reach disk before that page does. Read it backwards and it gets more interesting — as long as the log is there, a data page can be flushed whenever, because it can always be recomputed from the log. The data files are thereby demoted to "one materialized snapshot of the log."
Why the trade pays off, with real magnitudes. A transaction modifies five records scattered across different pages. Flushing honestly is five random writes; the WAL route packs five log records into one contiguous stretch of bytes — one sequential write plus one fsync. On spinning disks a random write pays a seek (roughly 5–10 ms) that a sequential write does not. On NVMe the seek is gone, but the intrinsic cost of an fsync (on the order of 0.1–1 ms) still dwarfs appending a few records into an existing log buffer. Group commit widens the gap further: dozens of concurrent transactions share one fsync — under 50,000 small transactions per second, that takes the fsync count from 50,000 down to a few thousand.
What goes into the log? Three flavours. Physical logging records "bytes 32 onward of page 700 changed from 0x0A to 0x14" — exact to replay, but one B-Tree split produces a flood of byte-level records. Logical logging records "insert (k=42, v=…) into table t" — compact, but replaying it requires the database to already be in a semantically complete state. ARIES takes the middle road, physiological logging: logical between pages, physical within a page — "insert this record into page 700," and how bytes shuffle inside the page is the page's own business.
Then two policy choices, forming the chapter's most famous quadrant. Steal: may a page dirtied by an uncommitted transaction be written back to disk? Force: must all pages a transaction modified be written back at commit?
Table 1 · The steal / force quadrant, and why industry converged on one corner
| force: flush all dirty pages at commit | no-force: flush nothing at commit | |
|---|---|---|
| no-steal uncommitted dirty pages stay | Needs neither redo nor undo — the simplest; but slow commits (random writes) and the cache is held hostage by uncommitted work | No undo needed, redo is; still suffers from large transactions filling the cache |
| steal uncommitted dirty pages may be written | Needs undo, not redo; commits are still slow | Needs both redo and undo — the most complex to implement, but a commit waits on one sequential write and the cache turns over freely. ARIES, InnoDB and PostgreSQL all live here |
Read it this way: the top-left corner is the easiest to write, the bottom-right the best to use. Moving complexity out of the runtime and into the recovery code is this chapter's central bargain — the runtime executes billions of times a day, recovery runs a handful of times a year.
ARIES (Mohan et al., IBM, 1992 — DB2's recovery algorithm) is the canonical answer for the steal / no-force corner. Recovery runs in three phases, in this order: analysis → redo → undo.
① Analysis scans forward from the last checkpoint and rebuilds two tables: the dirty page table (which pages were dirty at the crash, and which log record first dirtied each) and the transaction table (which transactions were still uncommitted — the "losers"). This phase only redraws the scene at the moment of the crash.
② Redo replays forward from the earliest log position in the dirty page table. Here is the counterintuitive part — ARIES calls it repeating history: every change by every transaction is redone, including transactions known to be losers that are about to be undone. Why not be clever and skip them? Because skipping means the redo logic must judge which changes belong, and that judgement depends on a state that has not been restored yet. Restoring the world blindly to the instant before the crash and then undoing in one pass is far simpler and far harder to get wrong. Avoiding pointless replay comes not from cleverness but from a blunt trick: each page header stores which log record last modified it (pageLSN), and a record whose number is not greater has already made it to disk — skip.
③ Undo walks backward through the log for the loser transactions, cancelling their changes one by one. The second piece of craft lives here — the compensation log record (CLR): every undo step writes another log record saying what was undone and which record is next. So even if the database crashes again during recovery, the CLRs tell the restart where the undo had got to, and nothing is undone twice. Recovery is therefore idempotent — which matters enormously in practice, because "crashing during recovery" is the single most common cascading failure (the bad memory stick that caused the first crash is, after all, still in the machine).
Concurrency control exists to block a family of anomalies: dirty reads (seeing uncommitted data), non-repeatable reads (the same row read twice in one transaction differs), phantoms (a range query returns a different set of rows the second time). The theoretical gold standard is serializability — the concurrent outcome is equivalent to running the transactions one at a time in some order. Isolation levels are, at bottom, a purchase of concurrency paid for by admitting particular anomalies.
There are three implementation routes. Pessimistic (locking): acquire before you act, wait on conflict, and get serializability from two-phase locking (only acquire, then only release). Optimistic (OCC): just do the work, then check at commit time whether anyone conflicted, and redo the whole transaction if so. Multiversion (MVCC): a write produces a new version rather than overwriting, and a read takes the version its timestamp entitles it to — so reads never block writes and writes never block reads, which is exactly why it dominates OLTP (PostgreSQL, InnoDB and Oracle are all MVCC).
And now the pair worth singling out, the highest-frequency database interview distinction there is: lock versus latch. Both are called locks in casual speech, yet they do not even guard the same kind of thing.
Table 2 · Lock vs latch: same word, two different worlds
| Lock | Latch | |
|---|---|---|
| Guards what | Logical objects: a row, a key range, a table | Physical structures: that page in memory, that list node |
| Held how long | The whole transaction — seconds or more | One structural operation — nanoseconds to microseconds |
| Exists for | Isolation: keep transactions from seeing half-done work | Correctness: keep threads from reading half-written memory |
| Managed by | The lock manager — wait queues, inspectable, can be taken explicitly | Just an OS mutex or reader-writer lock; no central registry |
| Deadlocks | Detected: keep a waits-for graph, find a cycle, roll back a victim | Not detected — avoided by design, via a fixed acquisition order |
| After a crash | Must be recovered (the lock table is rebuilt during recovery) | Vanishes with memory; nothing to recover |
The prettiest use of latches is latch crabbing on a B-Tree. Hold a latch at every level on the way down and the root becomes a global bottleneck; hold none and you may read an internal node mid-split. The crabbing rule is to move hand over hand like a crab: take hold of the child, confirm the child is "safe," then release the parent — where "safe" means this write cannot split or merge that node (there is room), so its ancestors cannot possibly be affected and can be let go. At most two levels are ever held at once.
Blink-trees go one step further: each node carries a pointer to its right sibling plus a high key, so even if you land on a node that has just split and whose parent pointer is not updated yet, you can follow the right pointer to where you should be — trading a little structural redundancy for fewer latches.
Table 3 · Three concurrency-control routes: what to pick when
| Pessimistic · 2PL | Multiversion · MVCC | Optimistic · OCC | |
|---|---|---|---|
| How it works | Acquire before acting, wait on conflict | Writes create versions; reads take the one their timestamp allows | Act first, validate for conflicts at commit |
| Reads block writes? | Yes — long transactions strangle concurrency | No — reads never block writes, writes never block reads | No (but work may be thrown away) |
| Main cost | Lock overhead plus deadlock detection; throughput falls fast as conflict rises | Old versions occupy space and must be cleaned (PostgreSQL vacuum, InnoDB undo-segment bloat) | Retry avalanche once conflict rates climb, burning CPU on discarded work |
| Suits | Conflict-heavy workloads with short transactions | Read-mostly general OLTP — most business systems | Rare conflicts, short transactions |
| Real systems | Early DB2, SQL Server defaults (locking plus intent locks) | PostgreSQL, MySQL InnoDB, Oracle | In-memory databases, the write path of some distributed engines |
Table 4 · Page eviction policies: why nobody ships the textbook LRU
| Policy | How it works | Cost / where it breaks |
|---|---|---|
| Naive LRU | Evict the least recently used page | One full table scan empties the whole pool; and maintaining the list needs locking, making it a contention point itself |
| CLOCK | Pages in a ring with a reference bit approximating LRU; the hand evicts entries whose bit is 0 | Less precise than LRU but almost lock-free — precision traded for concurrency |
| LFU / frequency | Evict the least frequently accessed page | Slow to react to pages that were hot and no longer are; needs an ageing scheme |
| LRU-K / 2Q / midpoint insertion | Look at the time of the K-th access, or park new pages in an "old" sublist until a second access promotes them | Needs tuning, more complex. InnoDB uses midpoint insertion, old sublist at 3/8 |
Three more trade-offs that never fit in a table but always have to be weighed:
checkpoint_timeout defaults to 5 minutes, a conservative midpoint between everyday overhead and worst-case recovery.fsync means higher commit latency and genuinely nothing lost. Relaxing to "flush once a second" (InnoDB's innodb_flush_log_at_trx_commit=2) can multiply throughput, at the price that a crash may lose the last second of committed transactions — trading durability straight for speed, acceptable only when the business has explicitly said so.This chapter is the common foundation under every single-node database, and its abstractions have barely dated: the recovery paths of PostgreSQL, InnoDB, SQLite and SQL Server are all variants or simplifications of ARIES, and even LSM engines like RocksDB put a functionally identical WAL in front of the memtable. One level up, it is the local half of distributed transactions — a participant's "I promise I can commit" in two-phase commit is redeemed precisely by its local log already being durable. In interviews, "why is WAL fast," "what do redo and undo each solve" and "what is the difference between a lock and a latch" are standard questions, and the dividing line is whether you can state the causal chain in this chapter.
3/8 of the pool (innodb_old_blocks_pct = 37), precisely so that scans cannot push out the hot set. Confirmation from the other direction that textbook LRU is not enough under real load. MySQL 8.4 Reference Manual · Buffer Pool ↗fsync as an I/O barrier and lists among the leading causes of corruption a filesystem or hardware that lies about fsync — one false "written" and every logging design above it fails at once. SQLite documentation · How To Corrupt An SQLite Database File ↗fsync might return success while that page was already lost — an assumption that had sat in the code for nearly twenty years. The fix was to PANIC on fsync failure (introduced in PostgreSQL 12, backpatched to 9.4 and later). The chapter's one counter-example: no logging algorithm, however rigorous, survives a lower-level interface whose semantics do not hold. PostgreSQL Wiki · Fsync Errors ↗fsync settles the matter. Fsyncgate showed that assumption quietly failing on the most mainstream OS for twenty years. Real durability requires hardware, firmware, filesystem and database all to be honest.① ACID is not any one module's doing: it is squeezed out of page cache + write-ahead log + concurrency control, whose shared trump card is "log it before you change it."
② The judgement to keep: the log is the database's master copy; the data files are only a discardable, recomputable materialization of it.
③ The database manages its own page cache to own three facts: what is in use (pinned), what has been modified (dirty), and what gets flushed first. A naive LRU is wiped out by one full table scan, so real engines use CLOCK or midpoint-insertion variants.
④ The write-ahead rule: the log covering a dirty page must reach disk before the page does. The cost of a commit therefore shrinks to one sequential write plus one fsync, amortized further by group commit.
⑤ The quadrant: industry converged unanimously on steal / no-force — fastest at runtime, at the price of needing both redo and undo in recovery. Complexity is moved off a path executed billions of times a day onto one run a handful of times a year.
⑥ ARIES in three phases: analysis → redo → undo. Redo repeats history, losers included; undo writes compensation records so that recovery itself can crash again without harm.
⑦ Three concurrency routes: pessimistic locking (conflict-heavy), MVCC (the general read-mostly choice, paying for it in version cleanup), optimistic OCC (rare conflicts, otherwise a retry avalanche).
⑧ Lock ≠ latch: a lock guards a logical object for a whole transaction and has deadlock detection; a latch guards a physical structure in memory for microseconds and avoids deadlock by a fixed acquisition order. B-Trees use latch crabbing — take the child, confirm it is safe, release the parent.
⑨ Three judgement calls that are yours to make: checkpoint frequency (everyday overhead vs recovery time), log flush strictness (latency vs possibly losing committed transactions), isolation level (concurrency vs which anomalies the application must defend against). And the foundation is thinner than it looks — one lie from fsync and everything above it falls.