A storage engine that only read and wrote pages would lose data on every crash and corrupt it under every concurrent update. This chapter covers the machinery between the B-tree and the disk that prevents both: a page cache that keeps hot pages in memory and decides when to write them back, a write-ahead log that makes committed changes survive a crash and lets uncommitted ones be rolled back, and concurrency control that decides which interleavings of concurrent transactions are allowed and enforces that with locks, versions or validation.

These mechanisms sit behind the phrases in every production incident: "the buffer pool was cold", "checkpoint storm", "the WAL filled the disk", "we hit a deadlock", "REPEATABLE READ still let us double-book". Knowing what the engine does with a dirty page, an LSN or a lock request lets you reason about such failures.

In one minute

• A transaction is an all-or-nothing unit of work with ACID guarantees, provided by the transaction manager, lock manager, page cache and log manager together.
• The page cache tracks dirty and pinned pages and evicts by a replacement policy. Plain LRU is scan-hostile; engines use CLOCK or segmented lists.
• The write-ahead log records every change before the page is flushed. Records carry increasing LSNs; a commit is durable once the log is forced through its commit record.
• Steal (flush uncommitted dirty pages) requires undo; no-force (commit without flushing pages) requires redo. ARIES is steal/no-force.
• ARIES recovers in three passes: analysis, redo (repeat history) and undo (roll back losers, writing compensation log records).
• Isolation levels are defined by forbidden anomalies: dirty read, non-repeatable read, phantom; lost update, dirty write, write skew. Snapshot isolation stops lost updates but not write skew.
• Concurrency control is optimistic (validate at commit), multiversion (readers see a snapshot) or pessimistic (locks or timestamp ordering). Two-phase locking yields serializability; wait-for graphs find deadlocks.
• Latches protect the physical tree for microseconds; locks protect logical data for a transaction. Latch crabbing and Blink-trees let many threads traverse a B-tree at once.

Transactions and buffer management

ACID and the four components

A transaction is an indivisible unit of work. Atomicity: partial results of an aborted or crashed transaction are never visible. Consistency: the database moves between states satisfying the application's invariants, mostly the application's job, which makes this the loosest property. Isolation: concurrent transactions do not observe each other's intermediate state, to a degree set by the isolation level. Durability: once the client hears "committed", the change survives crashes.

Component	Responsibility
Transaction manager	Assigns IDs and timestamps, tracks state, coordinates commit and rollback
Lock manager	Grants shared and exclusive locks on logical objects, queues waiters, detects deadlocks
Page cache (buffer pool)	Holds pages in memory, tracks dirty pages, decides when to flush and evict
Log manager	Appends change records to the WAL, forces it, drives checkpoints and recovery

Caching semantics and pinning

Disk access is orders of magnitude slower than memory, so the page cache (buffer pool) sits between engine and file. A hit returns the cached copy; a miss pages in from disk, evicting another page if needed. Writes modify the cached copy and mark it dirty; the change reaches disk only when the page is flushed, and a dirty page must be flushed before it is evicted.

While the engine uses a page it pins it; pinned pages are not eviction candidates. Pinning can be long-lived: a B-tree's top levels are few and touched on every lookup, so keeping them resident is cheap and lets repeated root updates flush once. Prefetching loads pages the engine knows it will need, such as the next leaves of a range scan; immediate eviction marks pages a maintenance job just read as unlikely to be reused.

Flushing and durability

Flushing on eviction stalls the thread that needed the frame, so engines flush in the background and the checkpointer flushes on a schedule so the WAL can be truncated. Dirty pages are lost on a crash, so durability comes from the log, under one rule: a record describing a change must be on disk before the page containing it is flushed, and a record can be discarded only once every page it describes has been.

Page replacement policies

When the cache is full the replacement policy picks the victim. The ideal victim is the page not needed for the longest time, which cannot be known, so policies approximate from history. Belady's anomaly warns that under FIFO a larger cache can produce more misses; LRU and its relatives are immune.

Policy	Rule	Weakness
FIFO	Evict the page loaded longest ago	Ignores reuse; Belady's anomaly
LRU	Evict the page accessed longest ago	Every hit touches a list; one large scan evicts the working set
CLOCK	Circular buffer with a reference bit; the hand clears set bits and evicts the first clear, unpinned page	Coarse approximation of LRU
LFU / TinyLFU	Evict the least frequently used, with a compact frequency sketch	Pure LFU never forgets; needs ageing
2Q / segmented LRU	Newcomers enter a probationary list; promotion needs a second hit	Tuning the split

Why plain LRU is bad for scans. A sequential scan of a table larger than the cache touches each page once, and under LRU each is "most recently used" on arrival, so the scan evicts the hot working set for pages that will never be read again. InnoDB splits its list into young and old sublists (5/8 and 3/8 by default), inserts new pages at the midpoint and promotes only on re-access after a delay, so scans churn the old sublist only. PostgreSQL uses a clock sweep with a usage counter capped at 5 and routes large scans through a small ring buffer that recycles its own frames.

Recovery

Write-ahead log and log semantics

The write-ahead log (WAL, also redo log or journal) is an append-only sequence of records describing every change. It lets the cache keep modified pages in memory because the changes exist on disk in log form, and lets recovery rebuild changes that never reached the data pages. Appending is sequential I/O; flushing scattered pages is random I/O, so engines write the log at commit and defer the pages.

Each record has a log sequence number (LSN), monotonically increasing and usually equal to its byte offset. Records are buffered and written by a force operation in LSN order. Besides updates there are begin, commit and abort records, checkpoint records and compensation log records. A transaction is committed exactly when the log is forced through its commit record; group commit batches several commits into one fsync. Each update record carries its transaction's prevLSN so a transaction's history can be walked backwards, and each page stores the pageLSN of the last record applied to it, which tells recovery whether a change is already present.

Checkpoints

Replaying the whole log would take as long as the system had run. A sharp checkpoint flushes every dirty page and stalls, so engines use fuzzy checkpoints: write begin_checkpoint, record the dirty page table (page ID plus recLSN, the LSN of the first record that dirtied it) and the transaction table (active transactions and their last LSNs) in an end_checkpoint record, and let pages drain asynchronously. Once they have, a master record is pointed at the begin_checkpoint LSN, where recovery starts.

Operation versus data logging

• Physical logging records bytes: page ID plus before and after images. Redo is a copy and idempotent, but records are large and tied to the exact page.
• Logical logging records operations ("insert key K into index I"). Records are small and undo works even if the key moved, but redo needs the page in a known state.
• Physiological logging, which ARIES uses, is physical to a page and logical within it ("insert this tuple into slot 3"): compact, page-local for redo, tolerant of in-page reorganisation.

Redo uses physical or physiological records (fast, independent of higher-level state); undo uses logical ones (data may have moved). Shadow paging avoids logging altogether: write modified pages to new locations and switch a root pointer atomically on commit, as copy-on-write trees do (Chapter 6), at the price of copying a path to the root per commit.

Steal and force policies

Policy	Meaning	Consequence
Steal	A dirty page of an uncommitted transaction may be flushed (its frame "stolen")	Uncommitted data can be on disk after a crash, so the log needs undo information
No-steal	Dirty pages stay in memory until commit	No undo, but the cache must hold every active transaction's pages
Force	All of a transaction's dirty pages are flushed before it commits	No redo, but every commit pays random page writes
No-force	A transaction may commit with pages still dirty	Committed data can be missing after a crash, so the log needs redo information

No-steal/force needs almost no recovery logic but makes commit slow and large transactions impossible. Steal/no-force performs best (the cache evicts freely, commit costs one sequential force) and needs both undo and redo, which ARIES provides.

ARIES

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics, Mohan et al., 1992) is the steal/no-force algorithm most relational engines follow. Its defining ideas: LSNs on every page, repeating history during redo (the database is first restored to its exact state at the crash, uncommitted changes included), and logging undo actions as compensation log records so that recovery is itself recoverable.

1. Analysis scans forward from the last begin_checkpoint, starting from the checkpoint's tables: it adds pages dirtied and transactions begun since, removes transactions whose commit or abort it sees, and ends with the losers (active at the crash) and the dirty page table with its smallest recLSN.
2. Redo scans forward from that smallest recLSN. For each update or CLR whose page is in the dirty page table, it reads the page and applies the record if the pageLSN is less than the record's LSN. Committed and uncommitted changes alike are reapplied.
3. Undo rolls back losers: repeatedly take the largest LSN among their outstanding records, undo it, write a CLR, follow prevLSN; when a loser reaches its begin record, write an abort record.

The CLR carries an undoNextLSN, the prevLSN of the record it compensated: the next record still to undo. If the system crashes during undo, the next recovery redoes the CLRs (they are redo-only, never undone) and resumes undo from the undoNextLSN, skipping compensated work. Undo never loops and log growth across repeated crashes is bounded. A client ROLLBACK uses the same path.

Concurrency control and isolation

Three families

• Optimistic concurrency control (OCC) assumes conflicts are rare: run without blocking, validate at commit, abort on conflict.
• Multiversion concurrency control (MVCC) keeps several versions of each item so readers see a snapshot without blocking writers.
• Pessimistic concurrency control (PCC) assumes conflicts are common and prevents them up front, by locking or timestamp ordering.

Serializability

A schedule is the interleaved sequence of operations actually executed. It is serial if transactions do not interleave and serializable if its effect equals that of some serial schedule. The practical test is conflict serializability: two operations conflict if they belong to different transactions, touch the same object and at least one writes; a schedule is conflict serializable if its precedence graph (edge Ti to Tj when an operation of Ti conflicts with and precedes one of Tj) is acyclic.

Read anomalies

• Dirty read: T1 reads a value T2 wrote before T2 commits; if T2 aborts, T1 used data that never existed.
• Non-repeatable read: T1 reads a row, T2 updates and commits it, T1 rereads and sees a different value.
• Phantom read: T1 runs a range query, T2 inserts or deletes a matching row and commits, T1 reruns the query and gets a different set. Locking existing rows cannot prevent it.

Write anomalies

• Lost update: T1 and T2 both read a counter at 10 and both write 11; one increment vanishes.
• Dirty write: T2 overwrites a row T1 wrote before T1 commits; if T1 aborts, there is no correct value to revert to. Every serious level forbids this.
• Write skew: two transactions each read a set of rows, verify an invariant and write different rows, and the combined result violates the invariant: two on-call doctors each check "at least one remains" and both sign off.

Isolation levels

Level	Dirty read	Non-repeatable read	Phantom	Typical implementation
Read uncommitted	allowed	allowed	allowed	No read locks; PostgreSQL treats it as read committed
Read committed	prevented	allowed	allowed	Short read locks, or a fresh snapshot per statement (PostgreSQL default)
Repeatable read	prevented	prevented	allowed by the standard	Long row read locks, or a per-transaction snapshot
Serializable	prevented	prevented	prevented	Strict 2PL with range locks, or serializable snapshot isolation

Snapshot isolation (SI) is not in the SQL standard but is what MVCC engines provide under "repeatable read" (PostgreSQL, InnoDB) or even "serializable" (Oracle). Each transaction reads a snapshot as of its start, so no read anomalies occur. Writes follow first-committer-wins: a transaction committing a write to a row another transaction modified and committed since the snapshot aborts (PostgreSQL) or, in InnoDB, waits and updates the latest version. That eliminates lost updates but not write skew, because the skewed transactions write different rows. Serializable snapshot isolation (SSI, Cahill et al., 2008; PostgreSQL since 9.1) closes the gap by tracking read-write dependencies between concurrent transactions and aborting one when two consecutive rw-dependencies form a dangerous pattern.

Optimistic and multiversion concurrency control

OCC phases and validation

Under OCC a transaction has a read phase (execute without locks, record the read set, buffer the write set), a validation phase (check that committing preserves serializability) and a write phase (install the write set atomically, or discard and retry). Backward-oriented validation checks the read set against the write sets of transactions that committed during its lifetime; forward-oriented validation checks its write set against the read sets of still-active transactions. Validation itself must be serialised, which is OCC's one synchronisation point.

OCC wins when conflicts are rare and transactions short: no lock manager, no waiting, no deadlocks. It loses under high contention because conflicts are discovered after the work is done. Main-memory engines such as Silo and Hekaton are optimistic because lock overhead dominates when data is in memory.

MVCC

Under MVCC an update creates a new version tagged with the writer's transaction ID or commit timestamp, and the old version stays until no transaction can need it. A reader is given a snapshot and picks, per item, the newest version committed before it. Readers never block writers and writers never block readers; writers still conflict with writers on the same item. PostgreSQL keeps every version in the heap as a tuple with xmin and xmax, removed by VACUUM (Chapter 4); InnoDB keeps the latest version in the clustered index and rebuilds old ones from undo records. The running cost is version garbage: a long-running reader pins its snapshot and blocks cleanup of every version created since, the usual explanation for bloat and oversized undo.

Pessimistic concurrency control

Timestamp ordering

The simplest lock-free pessimistic scheme is basic timestamp ordering. Each transaction gets a timestamp at start; each item records the largest timestamp of any reader (max_read_timestamp) and writer (max_write_timestamp). A read by T is rejected if T's timestamp is below the item's max_write_timestamp (a younger transaction already wrote a value T should have seen first); a write is rejected if below max_read_timestamp (a younger transaction already read, so the write is too late in the serial order). Rejected transactions abort and restart; the schedule is serializable in timestamp order, but long transactions tend to be the victims.

Two-phase locking

The dominant pessimistic scheme locks logical objects: a shared lock permits concurrent readers, an exclusive lock permits one writer. Two-phase locking (2PL) requires a growing phase (acquire locks, release none) and then a shrinking phase (release locks, acquire none); every 2PL schedule is conflict serializable, with the serialization point at the last lock acquisition. Plain 2PL permits cascading aborts, so engines use strict 2PL, holding exclusive locks until commit or abort. Phantoms require locking what does not exist yet: predicate locks in theory, range (gap or next-key) locks on index intervals in practice, which is how InnoDB's REPEATABLE READ prevents phantoms.

Deadlocks

Locks introduce deadlocks: T1 holds A and waits for B, T2 holds B and waits for A.

• Timeouts abort any transaction that waits too long: simple, but slow transactions die too.
• Detection builds a wait-for graph (nodes are transactions, edge Ti to Tj means Ti waits for a lock Tj holds); a cycle is a deadlock and the lock manager aborts a victim, typically the youngest. InnoDB checks on every wait; PostgreSQL after deadlock_timeout (1 s by default).
• Prevention restricts waiting by age, older meaning higher priority. In wait-die a transaction may wait only for a younger one; if the holder is older, the requester aborts and restarts with its original timestamp. In wound-wait an older requester aborts the younger holder; a younger requester waits. Both rule out cycles because waits go one way in age.

Locks and latches

Locks versus latches

Transaction locks protect logical content (rows, keys, ranges), live in the lock manager outside the tree, last for the transaction and need deadlock detection because the application chooses access order. Latches protect the physical structure, a page frame while it is read or modified: lightweight mutexes held for microseconds, never across I/O, acquired in a fixed order so they cannot deadlock. Even "lock-free" transaction protocols need latches, or compare-and-swap (Chapter 6), to stop threads seeing half-written pages. Latches are usually readers-writer latches: many shared holders or one exclusive holder.

Latch crabbing

Latching the whole root-to-leaf path exclusively serialises everything through the root. Latch crabbing (latch coupling) releases latches as soon as it is safe: latch the child, inspect it, release the parent.

• Read path: latch parent (shared), find child, latch child (shared), release parent; at most two latches held.
• Insert path: latch parent, latch child; if the child is safe (has room for one more key, so cannot split and modify the parent), release all ancestors; otherwise keep them for the coming split.
• Delete path: the same, with "safe" meaning above minimum occupancy.

If a child is not in the cache, the engine releases the parent latch and restarts after the load, so no latch is held across disk I/O.

Latch upgrading and optimistic descent

Most inserts touch only a leaf, so exclusive latches on the whole path are pessimistic. Latch upgrading descends with shared latches, latches the leaf exclusively and, only if the leaf must split, upgrades the parent's latch to exclusive. If two threads race to upgrade only one succeeds; the loser restarts from the root. The root is the last node to split, since all nodes beneath must fill first, so optimistic shared latching of the root almost never has to be retried.

Blink-trees

Lehman and Yao's Blink-tree removes the need to hold any parent latch during descent by tolerating an intermediate state. A split first creates the new right sibling and links it through the old node's right pointer (the node is half-split: reachable via the sibling link but not yet via the parent), and only then inserts the separator into the parent. A reader descending through the stale parent lands on the old node, finds its key above the node's high key, and follows the right link. Every key is always reachable, readers never block on structural changes, and the parent is updated lazily. PostgreSQL implements this design, which is why its pages carry high keys and right links (Chapter 4).

Design trade-offs

Decision	Options	Trade-off
Buffer policy	Steal/no-force vs no-steal/force	Steal/no-force maximises throughput and needs undo and redo; the opposite needs little recovery logic but slow commits and bounded transactions
Concurrency control	OCC, MVCC, locking, timestamp ordering	OCC for low contention and in-memory data; MVCC for read-heavy mixed loads; locking where wasted work is costly
Isolation level	Read committed, SI, serializable	Weaker levels raise concurrency and admit anomalies; SSI or 2PL when invariants span rows

Interview angle

• Explain steal and force, and why ARIES chose steal/no-force. Steal lets the cache flush uncommitted dirty pages, so undo information is needed; no-force lets a transaction commit without flushing its pages, so redo information is needed. Steal/no-force frees the buffer manager and makes commit one sequential write, so it performs best at the price of needing both.

• Walk through recovery under ARIES. Analysis scans from the last checkpoint to rebuild the transaction and dirty page tables and identify losers. Redo scans from the minimum recLSN and reapplies every record whose LSN exceeds the page's pageLSN, repeating history including uncommitted work. Undo walks each loser's prevLSN chain backwards, applying logical undo and writing a CLR per step; CLRs record undoNextLSN so a crash during recovery does not redo the undo.

• Your service double-books under PostgreSQL REPEATABLE READ. Why, and what fixes it? That level is snapshot isolation. Two transactions each read "slot free", each insert a booking for different rows, and neither write conflicts: write skew. Fixes: SERIALIZABLE (SSI detects the cycle), SELECT ... FOR UPDATE on a row representing the resource, or a unique constraint that fails the second insert.

• Why is LRU a poor fit for a buffer pool, and what do real systems do? A scan larger than the cache makes every scanned page most-recently-used, evicting the working set for pages never reused. InnoDB inserts at the midpoint of a young/old list and promotes on re-access; PostgreSQL uses a clock sweep with usage counts and a ring buffer for large scans.

• What is the difference between a lock and a latch, and why does a B-tree need both? Locks are logical, transaction-scoped, deadlock-detected and protect rows or ranges. Latches are physical, operation-scoped, embedded in page frames and protect the in-memory page. A row lock cannot stop two threads from rearranging a page's cell pointers; a latch cannot express "this row is mine until commit".

• How does a Blink-tree avoid holding the parent latch while a child splits? It allows a half-split state in which the new sibling is reachable via the old node's right link before the parent is updated. A reader that overshoots sees its key exceed the high key and moves right, so readers need no ancestor latches.

Pitfalls and misconceptions

• "A committed transaction's data is on disk." Under no-force only its log records are; its pages may still be dirty. Redo rebuilds them, but the data files alone are not a consistent backup without the log.
• "A checkpoint flushes everything and the log can be deleted." A fuzzy checkpoint records which pages were dirty and which transactions were active; log records are still needed from the smallest recLSN, which can precede the checkpoint by a long way.
• "Redo replays only committed transactions." ARIES redoes everything, losers included, to reproduce the pre-crash state, then undoes the losers.
• "Repeatable read means serializable." Repeatable read, and the snapshot isolation most engines ship under that name, still allows write skew. Only serializable, via strict 2PL with range locks or SSI, prevents all anomalies.
• "MVCC eliminates all blocking." Readers and writers do not block each other, but two writers to one row still conflict (InnoDB waits, PostgreSQL aborts the second committer), and long readers block version cleanup.

Key terms

Term	Meaning
Page cache / buffer pool	In-memory cache of disk pages with dirty tracking, pinning and a replacement policy
Write-ahead log	Append-only log of changes written before the corresponding data pages
LSN	Log sequence number: monotonically increasing identifier and position of a record
Steal / force	Whether uncommitted dirty pages may be flushed / whether all dirty pages must be flushed at commit
ARIES	Steal/no-force recovery with analysis, redo and undo passes and repeating history
Compensation log record	Redo-only record of an undo action, with undoNextLSN for crash-safe rollback
Snapshot isolation	Per-transaction snapshot plus first-committer-wins; allows write skew
Two-phase locking	Growing then shrinking phase; strict 2PL holds write locks until commit
Wait-for graph	Transactions waiting on each other; a cycle is a deadlock
Latch	Short-lived physical mutex on a page, distinct from a transaction lock
Blink-tree	B-tree with right links and high keys that tolerates half-split nodes

Further reading

• Database Internals, Chapter 5 ("Transaction Processing and Recovery"); Chapter 4 for page layout and Chapter 6 for latch-free alternatives.
• C. Mohan et al., "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging", ACM TODS, 1992.
• Hal Berenson et al., "A Critique of ANSI SQL Isolation Levels", SIGMOD 1995: https://arxiv.org/abs/cs/0701157
• Michael J. Cahill, Uwe Röhm and Alan D. Fekete, "Serializable Isolation for Snapshot Databases", SIGMOD 2008.
• Dan R. K. Ports and Kevin Grittner, "Serializable Snapshot Isolation in PostgreSQL", VLDB 2012: https://arxiv.org/abs/1208.4179
• Philip L. Lehman and S. Bing Yao, "Efficient Locking for Concurrent Operations on B-Trees", ACM TODS, 1981.
• PostgreSQL documentation, "Transaction Isolation": https://www.postgresql.org/docs/current/transaction-iso.html