Database Internals and Storage Engine Mechanics

The four jobs of a storage engine

A storage engine does four things. It stores records and finds them again. It makes a change durable before it reports success. It keeps concurrent transactions from seeing each other's partial work. It keeps the physical layout efficient as data arrives and leaves.

Every design trades those four against each other. The RUM conjecture states the trade formally: a data structure can optimize at most two of read overhead, update overhead, and memory overhead. A B-tree takes read and memory. An LSM-tree takes update and memory. An index on every column takes read and update and pays in memory.

Three amplification factors measure the result, and they are the vocabulary for the rest of the chapter.

• Read amplification is the bytes read from the device per byte returned.
• Write amplification is the bytes written to the device per byte the user wrote.
• Space amplification is the bytes stored per byte of live data.

The write amplification column for a B+tree surprises people. An update of one 100 byte row rewrites an 8 kilobyte page, and it writes that page to the write-ahead log as well under full-page logging. That is 160 times the logical write for one small update. LSM engines pay their amplification in background compaction instead, and the total often comes out similar.

The gap has also narrowed from the hardware side. Storage devices with built-in transparent compression let a B-tree write sparse pages that the device compresses away. That cuts B-tree write amplification by more than ten times and brings it close to RocksDB on the same workload. The FAST 2022 paper by Qiao and others measured exactly that.

Pages, the buffer pool, and the unit of I/O

A storage engine reads and writes pages, not rows. PostgreSQL uses 8 kilobyte pages. InnoDB uses 16 kilobyte pages. The page is the unit of caching, of locking in some designs, and of checksum verification.

The buffer pool caches pages in memory. Every read looks in the pool first. A hit costs a hash lookup and a pin, about 100 nanoseconds. A miss costs a device read, about 80 microseconds on NVMe. The hit ratio therefore decides almost everything about throughput, and a pool that holds the working set turns a disk-bound system into a memory-bound one.

Replacement policy decides which page leaves. Plain least recently used fails on a sequential scan, because one large scan evicts the whole working set for data it will never read again. Real engines use variants that resist this. PostgreSQL uses a clock sweep with a usage counter. InnoDB splits the list into young and old sublists and inserts new pages in the middle, so a scan touches only the old sublist. These are the same problems that Chapter 2 described for the kernel page cache, solved again inside the database because the database knows more.

Direct I/O against the page cache is a real decision with real consequences. A database that uses buffered I/O caches every page twice, once in its own pool and once in the kernel. A database that uses direct I/O owns the caching and must implement readahead, write scheduling, and asynchronous submission itself. PostgreSQL used buffered I/O for its whole history and added an asynchronous I/O subsystem in version 18, with an io_method that selects sync, worker threads, or io_uring. Benchmarks report two to three times better read throughput with io_uring on sequential scans and vacuum.

The B+tree family

A B+tree stores keys in internal nodes and key-value pairs in leaves, and it links the leaves so that a range scan walks them in order. Every leaf sits at the same depth. Fan-out is the number of children per node, and Chapter 3 showed why a high fan-out flattens the tree: 512-way fan-out reaches a leaf in four levels for a billion keys.

An insert into a full node splits it. The split allocates a new node, moves half the entries, and inserts a separator key into the parent. A split can cascade to the root, which is the only way that the tree gets taller. Deletes merge underfull nodes, though many engines skip merging and tolerate underfilled nodes because merges are expensive and rarely necessary.

Concurrency in a B+tree needs care, because a split changes the parent while another thread descends through it. Latch crabbing is the classical protocol. A thread holds a latch on a node, takes a latch on the child, and releases the parent latch as soon as it knows that the child cannot split. The rule for knowing is simple: a child with free space is safe for an insert, so the parent latch can go.

  step 1              step 2              step 3
  [root] LATCHED      [root] LATCHED      [root] released
    |                   |                   |
  [A]                 [A] LATCHED         [A] released (A has space)
    |                   |                   |
  [leaf]              [leaf]              [leaf] LATCHED, insert here

  Release the parent as soon as the child is "safe":
    insert  -> child has at least one free slot
    delete  -> child is more than half full
  If the child is unsafe, hold the parent: the operation may propagate.

The B-link tree removes most of the latching. It adds a right-link pointer to each node and a high key. A reader that arrives at a node during a split follows the right link to find the entry. Readers then need no latch coupling at all, which is why PostgreSQL uses a B-link tree for its default index.

Copy-on-write B-trees never modify a page in place. An update copies the leaf, then copies its parent to point at the new leaf, and so on to the root. A single atomic pointer swap at the root makes the whole change visible. LMDB works this way. The design gives crash safety with no write-ahead log, multi-version reads with no version chains, and readers that never block. It pays in write amplification, because one row change rewrites a path to the root, and in space, because old pages stay until no reader needs them.

The Bw-tree is a latch-free design for many-core machines. Instead of modifying a page, a thread prepends a delta record and installs it with one compare and swap on a mapping table. Pages consolidate in the background. The design removes latch contention and adds pointer chasing through delta chains. Microsoft's Hekaton and several research systems use it.

LSM-trees

A log-structured merge tree turns random writes into sequential ones. Writes go to an in-memory table, which is usually a skip list or a B-tree. When it fills, it flushes to an immutable sorted file on the device. Background compaction merges those files to keep the count bounded.

  write -> [ WAL ] (durability) and [ memtable ] (skip list, in memory)
                                         | full
                                         v flush, sequential write
  L0  [sst][sst][sst][sst]      overlapping key ranges, up to 4 files
       |  compact when L0 has 4 files
       v
  L1  [sst][sst][sst] ......    non-overlapping, 256 MB total
       |  10x
       v
  L2  [sst][sst][sst] ......    non-overlapping, 2.5 GB total
       |  10x
       v
  L3  ......                    25 GB, and so on

  Point read: memtable, then L0 files, then one file per level below.
  A Bloom filter per file skips the files that cannot hold the key,
  so the read usually touches one file and costs one device read.

Two compaction strategies cover the field. Leveled compaction keeps each level sorted and non-overlapping, and it merges a file from level N into the overlapping files of level N plus 1. Space amplification stays near 1.1 because each key exists roughly once per level, and write amplification runs 10 to 30 because each key gets rewritten once per level it passes through.

Tiered compaction, which Cassandra calls size-tiered, collects several files of similar size and merges them into one larger file. Write amplification falls to 4 to 10 because a key moves fewer times. Space amplification rises to 2 or 3 because several versions of a key coexist, and read amplification rises because a read consults more files.

Bloom filters are what make LSM point reads viable. Each sorted file carries a filter over its keys, and a read tests the filter before it reads the index. At 10 bits per key and a 1 percent false positive rate, a point read that misses skips almost every file and costs one device read. Chapter 3 gave the sizing table.

Key-value separation, which the WiscKey design introduced and which RocksDB ships as BlobDB, stores large values in a separate log and keeps only pointers in the tree. Compaction then moves pointers instead of values, and write amplification falls sharply. The cost is an extra read to fetch the value and a separate garbage collection process for the value log. The technique wins when values exceed about one kilobyte.

The write-ahead log and the meaning of durable

A write-ahead log makes a change durable before the change reaches its final place. The rule is in the name: the log record goes to stable storage before the modified page does. Recovery then replays the log and reaches a consistent state.

ARIES is the design that almost every relational engine follows. Three ideas carry it. Write-ahead logging gives durability. Repeating history during redo means that recovery first restores the exact state at the crash, including uncommitted changes, and then undoes the uncommitted ones. Logging the undo actions themselves means that a crash during recovery is survivable, because recovery is idempotent.

A log record is physical, logical, or both. A physical record says "page 412, offset 88, these 100 bytes". It is idempotent and large. A logical record says "insert this row into this index". It is small and it is not idempotent, because applying it twice inserts twice. ARIES uses physiological logging, which is logical within a page and physical between pages, and it carries a log sequence number on every page so that redo applies a record exactly once.

Checkpoints bound recovery time. A checkpoint records which transactions are active and which pages are dirty, so recovery starts from there rather than from the beginning of the log. A fuzzy checkpoint does this without stopping the system, which is why a modern database can checkpoint under full load.

The cost of durability is one fsync per commit, and the number is worth memorizing.

Group commit is why the last column differs from the one before it. The engine collects commit records from many transactions, writes them in one device operation, and completes all of those transactions together. Each transaction still waits one fsync, and the fsync covers sixty-four of them. Throughput rises by the batch factor and per-transaction latency stays the same.

The consumer SSD row is a trap that costs data. Without power loss protection, a drive acknowledges a write when it lands in a volatile cache. A power cut loses it. The database did everything correctly and the data is gone. Any machine that holds a primary copy needs either a drive with power loss protection or a replication factor that tolerates the loss.

ACID and the isolation levels

Atomicity means that a transaction applies fully or not at all. Consistency means that a transaction moves the database from one valid state to another, where valid is defined by the constraints the schema declares. Isolation means that concurrent transactions do not see each other's partial work. Durability means that a committed transaction survives a crash.

Isolation is the one with levels, and the levels are defined by which anomalies they permit.

Two rows in that table need explaining, because they cause real production bugs.

PostgreSQL calls its snapshot isolation level "repeatable read", and MySQL InnoDB calls its own variant the same thing. They are not the lock-based repeatable read of the SQL standard, and they behave differently from each other. Read the engine documentation, not the standard, and write a test that demonstrates the behavior that your code depends on.

Write skew is the anomaly that snapshot isolation allows and that surprises everyone. Two transactions read an overlapping set, each makes a decision based on what it read, and each writes a disjoint set. Neither write conflicts, both commit, and the combined result violates an invariant that each transaction alone preserved.

-- Invariant: at least one doctor stays on call.
-- Alice and Bob both run this at the same time, under snapshot isolation.

BEGIN;
SELECT count(*) FROM doctors
 WHERE on_call = true AND shift_id = 42;      -- both read 2

-- each transaction concludes that removing itself is safe
UPDATE doctors SET on_call = false
 WHERE name = 'alice' AND shift_id = 42;      -- Bob updates 'bob'
COMMIT;

-- Both commit. Zero doctors on call. No row conflicted.
-- Fixes, in order of preference:
--   SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;   (SSI detects it)
--   SELECT ... FOR UPDATE on the rows the decision depends on
--   a materialized conflict row that both transactions update

Serializable snapshot isolation, or SSI, fixes write skew without locks. It runs snapshot isolation and tracks read-write dependencies between concurrent transactions. When it finds the dangerous structure that can produce a non-serializable outcome, it aborts one of them. PostgreSQL implements SSI for its SERIALIZABLE level. The cost is aborts under contention, so the application must retry, and the retry loop is not optional.

Multi-version concurrency control

MVCC keeps several versions of each row so that a reader sees a consistent snapshot without blocking a writer. It is the single most important idea in modern database concurrency, because it removes the read lock.

A transaction gets a snapshot at its start, which is a rule for deciding which versions it can see. Each row version carries the transaction identifier that created it and the one that deleted it. Visibility is then a function of those identifiers and the snapshot.

The engines differ in where the old versions live, and the difference drives their operational behavior.

PostgreSQL stores every version in the table itself. An update writes a new row version and marks the old one dead. Readers walk forward through versions. The consequence is table bloat: dead rows occupy space until vacuum reclaims it. Autovacuum runs continuously, and a table with a high update rate and an under-configured autovacuum grows without bound. PostgreSQL also has transaction identifier wraparound, because the identifier is 32 bits, and a database that does not vacuum within about two billion transactions must stop to protect itself.

InnoDB stores the current version in the clustered index and old versions in a separate undo log. A reader that needs an old version walks the undo chain backward. The table stays compact, and a long-running read transaction makes the undo log grow, and a long chain makes that reader slow.

Oracle uses undo segments with similar behavior, and its "snapshot too old" error appears once a writer overwrote the undo record that a reader needs.

Query execution

An execution engine turns a plan into results. Three models dominate, and their difference is the amount of work done per function call.

The Volcano, or iterator, model gives every operator a next method that returns one row. It is simple and composable and it costs a virtual call per row per operator. A query over ten million rows with five operators makes fifty million virtual calls, and Chapter 5 priced a megamorphic virtual call at 5 to 12 nanoseconds.

Vectorized execution passes batches of a thousand or so values instead of single rows. The virtual call cost amortizes over the batch, the inner loops vectorize with SIMD, and the data stays in cache. Vectorized engines run 10 to 100 times faster than row-at-a-time engines on analytical queries. DuckDB, ClickHouse, Velox, and Arrow DataFusion all work this way.

Compiled execution generates machine code for the specific query, which removes the interpretation entirely and fuses operators into one tight loop. HyPer and the systems derived from it use this. Compilation costs milliseconds per query, so the technique pays for long queries and loses for short ones. Several systems compile adaptively, starting interpreted and switching when a query runs long.

Storage layout is the other half. A row store keeps a whole record together, which suits transactional access to one record. A column store keeps each column together, which suits analytical scans of a few columns over many rows. The column store reads only the columns the query names, compresses far better because a column holds similar values, and vectorizes naturally.

Column encodings do most of the work. Dictionary encoding replaces repeated strings with small integers. Run-length encoding stores a value and a count. Frame of reference stores a base and small offsets. Bit packing uses the minimum bits per value. Together these routinely give five to twenty times compression on real data, and many operations run directly on the encoded form without decoding.

Where the industry moved

Two structural changes reshaped database architecture over the past decade.

Compute and storage separated. Amazon Aurora pushed redo log application into the storage layer, so the database writes log records and never writes pages. Neon did the same for PostgreSQL with an open design. The result is that storage scales and replicates on its own, a replica starts without copying data, and a restore becomes a metadata operation.

Transactions and storage separated again for global systems. Amazon Aurora DSQL uses optimistic concurrency control with the transaction log outside the storage layer entirely, and it replicates rows, index entries, and transaction intents with Raft. Google Spanner uses Paxos groups plus TrueTime, and it runs two-phase commit between groups for cross-group transactions. Chapter 8 covers the consensus machinery that both depend on.

Choosing an engine

Sources and further reading

Alex Petrov, "Database Internals", for the engine mechanics. Andy Pavlo's CMU 15-445 and 15-721 lecture series, which are free and current. C. Mohan and others, "ARIES", ACM TODS 1992. Michael Cahill, Uwe Rohm, and Alan Fekete, "Serializable Isolation for Snapshot Databases", SIGMOD 2008, which is the SSI paper. Lu and others, "WiscKey", FAST 2016, for key-value separation. Qiao and others, "Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression", FAST 2022. Peter Boncz and others on vectorized execution, and Thomas Neumann on compiled execution.