Storage Engine Internals

1.1What we ask of an engine

Strip away SQL and an engine is asked for a short list of things. Ada's UPDATE turns into three of them: get(1) to fetch the row whose key is 1, put(1, …) to store the new version of it, and commit() to make everything safe. The key is what you look rows up by (here the id), and the value is the rest of the row. A transaction is a group of changes that must all take effect or none of them, and a database runs many of them at once.

Postgres calls its version of this list the table access method and index access method APIs. RocksDB, which we meet in section 6, offers almost exactly the five rows above, plus iterators for walking keys in order.

Read the right-hand column again. Most of it is about blocks, and the rest is about a crash landing between two writes. So the first decision an engine makes is how to lay rows out in blocks.

1.2Everything is a page

A disk or SSD moves data in blocks, 512 bytes or 4 KB at the device, and as chapter 08 showed, the kernel's page cache works in 4 KB pieces too. Reading one byte costs as much as reading the block it sits in, and changing one byte means writing its whole block back. An engine that fetched one row at a time would waste nearly all of every read. So engines group rows into fixed-size pages, and every read and write moves a whole page. A page is a chunk of the database file, usually a small multiple of the device's block size, and it's the unit the rest of this chapter works in.

?Why do engines pick 8 or 16 KB instead of 4?

Bigger pages mean fewer pages to read on the way to a row (section 3 shows how few that can be), at the price of rewriting more bytes for every small change. Postgres uses 8 KB, InnoDB 16 KB by default, SQLite 4 KB. None of them match the device exactly (an 8 KB Postgres page is two 4 KB blocks), and section 5 shows the problem that causes.

1.3Looking at a real database file

You can see pages in a real database without installing anything, because Python ships with SQLite, a small database that lives in a single file and runs inside your program. The script below creates a table of 100,000 users and inserts them in one go. Then it asks SQLite two questions with PRAGMA, the command SQLite uses to read and change its own settings: page_size is the size of each page, and page_count is how many pages the file holds. Last, it changes one row and checks whether the file size moved.

import os, sqlite3
 
path = "pages_demo.db"
if os.path.exists(path): os.remove(path)
db = sqlite3.connect(path)
db.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT, email TEXT)")
db.executemany("INSERT INTO users VALUES (?, ?, ?)",
               ((i, f"user{i}", f"user{i}@example.com") for i in range(100_000)))
db.commit()
 
size  = db.execute("PRAGMA page_size").fetchone()[0]
count = db.execute("PRAGMA page_count").fetchone()[0]
print(f"page size : {size:,} bytes")
print(f"pages     : {count:,}")
print(f"file size : {os.path.getsize(path):,} bytes  (= {size:,} x {count:,})")
print(f"rows      : 100,000  ->  about {100_000 / count:.0f} rows per page")
 
before = os.path.getsize(path)
db.execute("UPDATE users SET name = 'renamed' WHERE id = 5"); db.commit()
print(f"after changing one row, file size: {os.path.getsize(path):,} bytes (was {before:,})")

page size : 4,096 bytes
pages     : 977
file size : 4,001,792 bytes  (= 4,096 x 977)
rows      : 100,000  ->  about 102 rows per page
after changing one row, file size: 4,001,792 bytes (was 4,001,792)

Look at the first lines of the output. The file is 977 pages of 4,096 bytes, and its size in bytes is exactly those two numbers multiplied, so the file is nothing but pages laid end to end. With 100,000 rows in 977 pages, about a hundred rows share each page. The last line is the surprising one: after the update the file is exactly the same size. SQLite found the page that held the row, changed it, and wrote that page back, which means a change of a few bytes made it write 4,096.

1.4What one changed row costs

For ada the numbers are worse. Her age is a 4-byte integer and a Postgres page is 8,192 bytes, so changing one number means writing about two thousand times as many bytes as we meant to change. The ratio of bytes written to the device to bytes the user changed is called write amplification, and it's the first of three costs that every storage design pays.

The other two have the same shape. Read amplification is how many blocks the engine reads for each value it returns: if finding ada's row takes four page reads, that's four. Space amplification is how many bytes sit on disk for each byte of live data, which grows when pages are part empty or old versions of rows linger. Athanassoulis and colleagues named the trade the RUM conjecture (EDBT 2016): an access method that's optimal for two of read, update and memory overhead can't be optimal for the third.

Keep these three costs in mind. Every design choice in this chapter moves cost from one to another, and section 7 lines the two main designs up against all three. For now we know that ada's row lives in a page with its neighbours, and the next question is what a page looks like inside.

2.1Packing rows into a page

A page has to hold rows of different lengths: ada's row is 36 bytes and grace's is 40. Suppose we pack them one after another from the start of the page, and let anything that needs to find a row later remember its byte offset within the page. Two things go wrong. If ada's name ever becomes longer, every row after it has to shift to make room, and every remembered offset to those rows is now wrong. And if a row is deleted, it leaves a hole nobody can use until the rows after it slide down, which breaks the offsets again.

What we want is a page where rows can move around freely, but the address that other structures hold for a row never changes.

2.2The slotted page

The standard fix is one layer of indirection. The page starts with a small header. After the header comes an array of numbered slots, which Postgres calls line pointers, and each slot records where one row starts and how long it is. The rows themselves are packed from the end of the page backwards. The slot array grows forward, the rows grow backward, and the free space is the gap between them. This layout is the slotted page, and Postgres uses a textbook version. (Postgres calls a table's pages the heap, because rows sit in them in no particular order.)

Other structures now remember a row's address as (page number, slot number) and never its byte offset. The engine can slide rows around inside the page, and the only thing it has to fix afterwards is the slot array.

Here is the page header from Postgres's source. For now look at the three offsets: pd_lower is where the free space starts, pd_upper is where it ends, and pd_special marks an optional area at the very end of the page that heap pages don't use. The pd_lsn field ties the page to the log, and we'll meet it in section 5.

typedef struct PageHeaderData
{
	/* XXX LSN is member of *any* block, not only page-organized ones */
	PageXLogRecPtr pd_lsn;		/* LSN: next byte after last byte of xlog
								 * record for last change to this page */
	uint16		pd_checksum;	/* checksum */
	uint16		pd_flags;		/* flag bits, see below */
	LocationIndex pd_lower;		/* offset to start of free space */
	LocationIndex pd_upper;		/* offset to end of free space */
	LocationIndex pd_special;	/* offset to start of special space */
	uint16		pd_pagesize_version;
	TransactionId pd_prune_xid; /* oldest prunable XID, or zero if none */
	ItemIdData	pd_linp[FLEXIBLE_ARRAY_MEMBER]; /* line pointer array */
} PageHeaderData;

Each line pointer is 4 bytes: a 15-bit offset, a 15-bit length and 2 bits of state (itemid.h).

2.3Trying it: a page with three rows

Postgres ships an extension called pageinspect that shows the raw contents of a page from SQL (switch it on with create extension pageinspect;). In the script below, get_raw_page('users', 0) reads page 0 of the table users. page_header decodes that page's header, and heap_page_items lists its slots: lp is the slot number, lp_off and lp_len say where the row starts and how long it is, t_xmin is the id of the transaction that created the row (more on that in 2.4), and t_ctid is the row's own address as (page, slot). The three rows are ada, grace and linus.

create table users(id int primary key, name text, age int);
insert into users values (1,'ada',36),(2,'grace',45),(3,'linus',28);
 
select lower, upper, special, pagesize from page_header(get_raw_page('users',0));
select lp, lp_off, lp_len, t_xmin, t_ctid from heap_page_items(get_raw_page('users',0));

 lower | upper | special | pagesize
-------+-------+---------+----------
    36 |  8072 |    8192 |     8192
 
 lp | lp_off | lp_len | t_xmin | t_ctid
----+--------+--------+--------+--------
  1 |   8152 |     36 |    732 | (0,1)
  2 |   8112 |     40 |    732 | (0,2)
  3 |   8072 |     40 |    732 | (0,3)

lower is 36: a 24-byte header plus three 4-byte slots. upper is 8072, where the third row starts, and the 8,036 bytes between them are free. Row 1 sits at the very end of the page and each later row sits just in front of the one before it. The offsets step down by 40 each time because Postgres pads every row to a multiple of 8 bytes. Row 1 is only 36 bytes long, but it still takes the 40 bytes from 8152 to the end of the page.

?Why the extra layer of line pointers?

So that nothing outside the page needs to know a row's byte offset. An index (the lookup structure we build in section 3) entry points at (page 0, slot 2), called a TID (tuple id, ctid in SQL) in Postgres. The engine can compact the page, sliding rows around to merge free space, and only the slot array changes. Every index pointing into the page stays valid.

2.4What a row costs

Rows aren't free inside a page. In Postgres each one carries a 23-byte header (padded to 24) that holds, among other things, the ids of the transactions that created and deleted it, plus a 4-byte slot. That header is how Postgres lets many transactions see consistent data at once, a technique called MVCC (multi-version concurrency control) that keeps old versions of a row around so readers don't have to wait for writers. Chapter 19 takes it apart.

So a table with a single bigint column pays 24 + 8 + 4 = 36 bytes per 8-byte value. Take such a table, call it t, with one bigint column id and ten million rows. Its page 0 holds 226 rows, which is what 8168 / 36 predicts (8,168 bytes are left in an 8 KB page after its 24-byte header), and the whole table comes to 346 MB for 80 MB of integers. That's 44,248 pages, a number we'll meet again.

2.5An UPDATE writes a new row version

Now we can run ada's update. Her new age is the same size as the old one, so a slotted page could overwrite the 36 with 37 right where it sits. Postgres never does, because of MVCC: a transaction that started a moment earlier may still need to see ada at 36, so the old version has to stay. Instead an UPDATE writes a complete new version of the row into free space in the page, and marks the old version dead:

 lp | lp_off | t_xmin | t_xmax | t_ctid
----+--------+--------+--------+--------
  1 |   8152 |    732 |    733 | (0,4)     <- old version, deleted by xact 733
  4 |   8032 |    733 |      0 | (0,4)     <- new version, written by xact 733

That's the page after update users set age=37 where id=1. In slot 1, t_xmax is the id of the transaction that replaced this version (it is 0 while a row is alive), and its t_ctid now points forward to the new version at (0,4). Slot 4 holds the new version, created by that same transaction, 733.

InnoDB takes the other path: it updates the row where it sits and copies the old version into a separate undo log. Both approaches are MVCC. They keep old versions in different places, and that choice decides who has to clean up afterwards: vacuum in Postgres, a background job that reclaims dead row versions, and the purge thread in InnoDB.

Ada's new version is now in a page. That leaves the question we skipped: how did the engine get to that page? A table of ten million rows is 44,248 pages, and nothing so far tells us which one holds id 1.

3.1From a list of pages to a tree

Reading all 44,248 pages to find one row would be hopeless, so let's give the engine a way to jump. Keep the rows sorted by key, and keep a small list saying where each range of keys starts. Here is a toy table of nine users, three to a page. The list is a page of its own that says "keys from 1 are in page A, from 4 in page B, from 7 in page C". To find id 7, read the list, see that 7 belongs in page C, read page C, and search its three keys.

If the table grows until the list no longer fits in one page, we do the same thing again: put a list over the lists. The result is a tree of pages. The pages at the bottom, which hold the keys and their values (or pointers to the rows) in sorted order, are leaf pages. The pages above them hold only separator keys and pointers to child pages, and they're called internal pages. The single page at the top is the root. Each leaf also links to its right-hand neighbour, so scan(4, 8) can find the key 4 and then walk along the leaves without climbing back up.

This structure is the B+tree. Bayer and McCreight introduced the B-tree in 1972, and the B+tree variant, which keeps every value in the leaves, is surveyed in Comer's The Ubiquitous B-Tree (1979). Almost every relational engine uses it.

3.2Why the tree is shallow

Real pages aren't three entries wide. Each one holds hundreds of entries, so an internal page has hundreds of children (its fan-out) and the tree widens by hundreds at every level. That makes it surprisingly short. Here's the arithmetic for an index on id in the ten-million-row table t from 2.4, using the entry counts Postgres reports with its bt_page_stats function:

Postgres agreed: bt_metap reported the root at level 2 (levels 0, 1 and 2, with the leaves at level 0) with 97 entries, and the index had 27,422 pages. At a billion keys it's one level more. That's four page reads to find any of a billion rows, and the top two levels are used by every lookup, so they almost always sit in memory already (section 4 explains where).

3.3One lookup, page by page

Let's follow a lookup of id = 5000001 in that index, with the query SELECT id FROM t WHERE id = 5000001. Three terms first. Page 0 of every index is a metapage that records which page is the root. A leaf entry holds a TID pointing at the row in the heap. And because this query asks only for id, which the index already holds, Postgres can answer from the index alone (an index-only scan), as long as it can confirm that this transaction is allowed to see the row. The visibility map answers that: it's a compact map that records which heap pages contain only rows every transaction can see, so those pages can be skipped.

And here is Postgres reporting exactly that:

 Index Only Scan using t_id on t (actual rows=1 loops=1)
   Index Cond: (id = 5000001)
   Heap Fetches: 0
   Buffers: shared hit=4

shared hit=4 means four pages were found in Postgres's own cache of pages (section 4): three index pages and one visibility-map page. If the leaf had to go to the heap, it would be one more.

3.4Where the row lives: heap or clustered index

A leaf entry has to lead to the row, and there are two ways to arrange that. A table can have several indexes, one on its primary key and secondary indexes on other columns, and the choice decides what each of them holds.

Postgres softens its downside with HOT updates (heap-only tuples): if no indexed column changed and the new version fits on the same page, no index entry is added. Ada's update is one of these, since her age isn't indexed, and the dump of the log in section 5.6 shows two HOT_UPDATE records for exactly that reason.

3.5Inserts and the page split

Now insert a new user. The engine finds the right leaf the same way a lookup does and adds the key. But a page has a fixed size, and a full leaf has nowhere to put it. For drawing, let's say a leaf holds three rows, so the leaf with ada, grace and linus is full, and we insert id 4.

A split makes a full leaf into two half-empty ones, and a split of the root is the only way the tree gets taller. That keeps every leaf at the same depth. A split also changes three pages at once, which is dangerous if the machine crashes halfway, and section 5 is about exactly that danger. (Postgres records the split of the leaf in its log as one record and the new separator in the parent as a second one. If a crash lands between the two, the leaf carries a flag saying the split is unfinished, and the next insert that reaches it finishes the job.)

?How do readers survive a split happening under them?

Other connections are reading while the split runs, and between the third and fourth frames above the root points at A for the key 3, which has already moved. The answer is a trick from Lehman and Yao's 1981 paper. Every page has a right-link to its right-hand sibling and a high key, the largest key that belongs on it. A reader that lands on a page and finds its key above the high key knows a split moved it, and follows the right-link. Postgres's nbtree is built on it, and a descent holds a lock on only one page at a time:

Compared to a classic B-tree, L&Y adds a right-link pointer to each page,
to the page's right sibling.  It also adds a "high key" to each page, which
is an upper bound on the keys that are allowed on that page.  These two
additions make it possible to detect a concurrent page split, which allows
the tree to be searched without holding any read locks (except to keep a
single page from being modified while reading it).

3.6Random keys and half-empty pages

Where the page splits matters more than it looks. A split in the middle leaves two pages half full. If keys arrive in increasing order (a sequence, a timestamp), only the rightmost leaf ever splits, and Postgres special-cases it: it leaves the left page at the fillfactor, the fraction of a page it fills before moving on, which is 90% for leaves (nbtsplitloc.c). Random keys split pages all over the tree and leave them part empty.

Size isn't the only cost. A random key sends each insert to a different leaf, so the working set (the pages the workload keeps using) is the whole index. With sequential keys, inserts hit the same few rightmost pages, which stay in cache.

Everything in this section, from the lookup to the split, reads and changes pages, and each of those pages had to be fetched from the disk. That's the next cost to look at.

4.1A cache of pages, run by the engine

Reading a page from disk costs about 45 microseconds on a fast SSD (chapter 08) and milliseconds on network storage, against nanoseconds from RAM. An engine that went to disk for each of the four pages in a lookup would spend nearly all its time waiting. So it keeps copies of pages in memory, the way the kernel keeps file data in its page cache. Every B+tree engine has such a cache of its own, called the buffer pool (shared_buffers in Postgres, innodb_buffer_pool_size in InnoDB).

?Doesn't the operating system already cache files?

It does, and Postgres benefits from it (4.4 comes back to this). But the kernel only sees blocks of a file. The engine knows things the kernel can't: which pages are in use right now and mustn't be moved, which have been changed and in what order those changes must reach the disk (section 5), and which page accesses belong to a one-off scan that shouldn't push out the pages everyone needs (4.3). So the engine runs a cache where it can make those decisions.

The buffer pool is an array of page-sized frames, a hash table from (file, block number) to frame, and a small header per frame:

Every access in sections 2 and 3 went through this: look up the tag, pin the frame, lock it, read, unlock, unpin. A request that finds its page in the pool is a hit, as in chapter 08, and one that has to read the page from disk is a miss. The shared hit=4 in section 3.3 counts exactly those pins.

4.2Choosing a victim: the clock sweep

When a new page needs a frame and the pool is full, something has to go. Least-recently-used (LRU, which evicts the page that has gone untouched for longest) is the obvious choice, but true LRU moves a page to the head of a list on every hit, and that list is a lock every backend fights over.

Postgres uses a clock sweep instead. Each frame has a usage count, capped at 5 (BM_MAX_USAGE_COUNT). A hit just bumps the count. To find a victim, a hand sweeps the frames, decrementing counts, and takes the first unpinned frame at zero:

	/* Nothing on the freelist, so run the "clock sweep" algorithm */
	trycounter = NBuffers;
	for (;;)
	{
		buf = GetBufferDescriptor(ClockSweepTick());
 
		/*
		 * If the buffer is pinned or has a nonzero usage_count, we cannot use
		 * it; decrement the usage_count (unless pinned) and keep scanning.
		 */
		local_buf_state = LockBufHdr(buf);
 
		if (BUF_STATE_GET_REFCOUNT(local_buf_state) == 0)
		{
			if (BUF_STATE_GET_USAGECOUNT(local_buf_state) != 0)
			{
				local_buf_state -= BUF_USAGECOUNT_ONE;
 
				trycounter = NBuffers;
			}
			else
			{
				/* Found a usable buffer */
				if (strategy != NULL)
					AddBufferToRing(strategy, buf);
				*buf_state = local_buf_state;
				return buf;
			}
		}
		/* ... error if every buffer is pinned ... */
		UnlockBufHdr(buf, local_buf_state);
	}

A page used five times survives roughly five passes of the hand. A page used once survives one. That approximates LRU with a counter update per hit instead of a list operation.

4.3Why one big scan doesn't flush the cache

There's a way for this to go wrong. A full scan of a table bigger than the cache, say select count(*) from t over a 346 MB table with a 128 MB pool, reads every page exactly once. Under plain LRU or clock, those pages would evict every hot page in the pool to make room for pages that will never be read again, and the next lookup for ada would miss.

?What does Postgres do with a scan bigger than the cache?

It gives any sequential scan of a table larger than a quarter of shared_buffers a ring buffer of 256 KB, which is 32 frames, and the scan recycles those frames instead of taking new ones from the pool (heapam.c, freelist.c). The picture below shrinks everything: a pool of six frames, four of them holding pages the application uses all day, and a ring of three.

Here is the real thing. After restarting Postgres, so that the pool starts empty, the script below scans the table and then counts how many of its pages are in the pool. pg_buffercache is an extension that lists every frame, and the query joins it with pg_class to learn which table each frame belongs to.

select count(*) from t;          -- 10M rows, 44,248 pages, parallel seq scan
 
select c.relname, count(*) as buffers
from pg_buffercache b join pg_class c on c.relfilenode = b.relfilenode
where c.relname = 't' group by 1;

   Buffers: shared read=44248
 
 relname | buffers
---------+---------
 t       |      96

All 44,248 pages were read, and 96 stayed: three rings of 32, one for the leader and one for each of the two parallel workers (the helper processes a parallel scan splits its work between). Of 16,384 frames, 16,126 were still empty afterwards.

InnoDB defends against the same problem with midpoint insertion. Its LRU list is split: new pages enter at the head of the "old" sublist, 3/8 of the pool (innodb_old_blocks_pct = 37), and only move to the young end if touched again more than innodb_old_blocks_time (1,000 ms) later (MySQL 8.4 manual). A scan touches each page several times within a second, then never again, so its pages age out of the old sublist without disturbing the young one.

Index scans get no ring. After the scan above, a range query over three million keys pulled 64 MB of the index into the pool, as it should: index pages are the ones worth caching.

4.4Two caches: shared_buffers and the page cache

Postgres reads and writes through the kernel, so a page can sit in both shared_buffers and the operating system's page cache (chapter 08). The docs suggest starting at 25% of RAM and say more than 40% is unlikely to help, "because PostgreSQL also relies on the operating system cache". InnoDB skips the page cache. Its innodb_flush_method defaults to O_DIRECT on Linux as of MySQL 8.4 (manual), a flag that makes reads and writes bypass the kernel's cache, and the buffer pool is given most of the machine's memory instead.

Pages now stay in memory, which makes reads cheap. Changes happen in memory too, though. When ada's UPDATE changes a page in its frame and sets the dirty bit, nothing on the disk knows yet, and chapter 08 has already told us what that means for a crash.

5.1What a crash can leave behind

A write goes through the pool the same way a read does: the engine changes the page in its frame, sets the dirty bit and carries on, and the page reaches the disk later. That's the trade the kernel's page cache made in chapter 08, and it has the same danger. Until the dirty page is written, a power cut loses the change, and COMMIT promised that wouldn't happen.

The obvious fix is to write the dirty pages out before answering COMMIT. For ada's update that means one 8 KB page. But a commit can change several pages, as the split in section 3.5 did (leaf A, the new page B, and the root), and the disk writes them one at a time in whatever order its cache chooses. A power cut can land between any two. Let's walk the cases for that split:

• Only the new page B reached the disk. Nothing points at B, and A still holds the old rows, so the row with id 4 is lost.
• Only A reached the disk. A has dropped id 3 to make room, but B was never written, so id 3 has vanished from the tree.
• Only the root reached the disk. It sends lookups for 3 and 4 to page B, which on disk is blank or holds somebody else's leftover bytes.
• Half of a page reached the disk. An 8 KB Postgres page is two 4 KB filesystem blocks, and a crash can land between them. The page is then half old and half new, which is called a torn page.

Every case leaves a tree that contradicts itself, and nobody can tell afterwards which case it was. It's the problem the filesystem journal solved in chapter 08, and the databases' answer is the same: write down what you're about to do before you do it.

5.2The rule

Before touching any data page, the engine describes the change in a write-ahead log, or WAL, a file that is only ever appended to. It makes that description durable first, meaning safely on the disk. After a crash it replays the log from a recent starting point (5.5 explains where), redoing every change the log describes, and every page ends up as it should be. Postgres's own design notes state the rule:

A basic assumption of a write AHEAD log is that log entries must reach stable
storage before the data-page changes they describe.  This ensures that
replaying the log to its end will bring us to a consistent state where there
are no partially-performed transactions.  To guarantee this, each data page
(either heap or index) is marked with the LSN (log sequence number --- in
practice, a WAL file location) of the latest XLOG record affecting the page.
Before the bufmgr can write out a dirty page, it must ensure that xlog has
been flushed to disk at least up to the page's LSN.

That LSN is pd_lsn, the first field of the page header in section 2. A log sequence number is a position in the log, so each log record has one, and each page remembers the LSN of the last record that changed it. That's what ties a page to the log.

?Why is writing everything twice faster than writing it once?

Because the log write is sequential and small, and the page writes can wait. A commit only needs its log records on disk, a few hundred bytes appended to one file. Dirty 8 KB pages stay in memory and get written later, in bulk, possibly after many more changes to the same page. Without a log, every commit would have to force every page it touched.

5.3What a commit waits for

Here is ada's single-row UPDATE with autocommit (each statement commits by itself), from the client to the disk, followed by a power cut and the restart. The two buffers at the top are just memory, one holding pages and the other holding log records not yet on disk. fdatasync is the system call fsync from chapter 08 with a small shortcut: it skips flushing details such as the file's modification time, which a log doesn't need.

Notice what the commit waited for: a single flush of a few hundred bytes appended to the log, at the fifth frame. Everything else happened in memory. What happens when that flush fails is the story of fsyncgate in chapter 08.

5.4Group commit, and turning the wait off

If every commit waits for its own fdatasync, one connection can commit at most once per flush. Postgres ships a tool, pg_test_fsync, that times this, and for the setup behind the numbers below it reported a median of 185 µs per 8 KB fdatasync. That caps one connection at about 5,400 commits a second before the transaction does any work of its own. Treat the figure as optimistic. Virtual machines and container mounts can report a flush as done before the bytes reach flash, and real drives range from tens of microseconds to several milliseconds per flush.

?How do 16 clients commit faster than one flush allows?

Group commit, the trick from chapter 08. While one backend is inside fdatasync, the others append their commit records behind it. When the flush finishes, the next backend flushes all of them at once. pg_stat_wal shows it directly: WAL syncs per committed transaction fall as clients are added. In these pgbench runs (pgbench is Postgres's own benchmark tool), each client commits one small transaction after another for 10 seconds:

That's one run per row, a TPC-B-like pgbench workload at scale 10, so the absolute throughput is noisy. What's stable is the ratio: at 16 clients about three commits share each flush.

You can also stop waiting. synchronous_commit = off returns success before the flush. In three 15-second runs each at 16 clients, the median went from 2,258 tps with it on to 4,351 with it off (tps is transactions per second). The Postgres docs are precise about the price: the risk window is at most three times wal_writer_delay, which is 200 ms by default and so 600 ms, and "the risk that is taken by using asynchronous commit is of data loss, not data corruption."

5.5Checkpoints

The log can't grow forever, and the engine can't replay all of it after every crash. If nobody ever wrote the dirty pages, recovery would have to start from the first record ever logged. So from time to time the engine writes every dirty page in the pool to the data files, then records "everything before LSN X is on disk". That's a checkpoint. Recovery starts from X, and any log older than X can be recycled.

A checkpoint has a side effect that matters for the next problem, and it comes from the torn page we met in 5.1.

5.6Torn pages and full-page writes

Replaying a log record assumes the page it applies to is intact. A torn page breaks that: a small record like "age 36 → 37" can't repair a page that is half old and half new. Postgres's answer is that the first time a page is changed after a checkpoint, the log record carries a copy of the whole page. Replay restores that image and applies the later records on top. These are full-page writes, and they show up in the log as the FPW flag. Here are the log records from two updates to the same row straight after a checkpoint, as printed by pg_waldump, the tool that reads a WAL file:

rmgr: Heap        len (rec/tot): 65/ 309, tx: 545604, desc: HOT_UPDATE ... blkref #0: rel 1663/5/16437 blk 0 FPW
rmgr: Transaction len (rec/tot): 34/  34, tx: 545604, desc: COMMIT 2026-09-27 04:12:29.911940 UTC
rmgr: Heap        len (rec/tot): 71/  71, tx: 545605, desc: HOT_UPDATE ... blkref #0: rel 1663/5/16437 blk 0
rmgr: Transaction len (rec/tot): 34/  34, tx: 545605, desc: COMMIT 2026-09-27 04:12:29.975972 UTC

The same change cost 309 bytes the first time and 71 the second. The first record includes the page image, which is only about 240 bytes here because Postgres leaves out the unused gap in the middle of a page and this table's page was almost empty. A full page costs close to 8 KB.

?Why does WAL volume spike after every checkpoint?

Because every page touched for the first time since the checkpoint costs a full-page image. In pgbench runs (4 clients, 8,000 transactions per run, median of three runs) the log grew like this:

Full-page images made up over 90% of the WAL in these runs. That seems high, but the data set was a 1-million-row table, big enough that most updates still hit a page that hadn't been imaged yet.

full_page_writes = off is only safe on storage that can't tear an 8 KB write, such as a copy-on-write filesystem like ZFS. InnoDB solves the same problem differently, with a doublewrite buffer: each dirty page is first written to a separate area, flushed, and only then written to its real location, so an intact copy exists somewhere.

5.7Crash recovery, step by step

Now we can watch recovery happen on a real server. Stop Postgres with pg_ctl stop -m immediate, which skips the shutdown checkpoint and is as close to a power cut as a command gets, five seconds into a pgbench run, then start it again. The server first reads pg_control, a small file where Postgres records what state it was in when it stopped, and then the log tells the rest:

?What about transactions that were running at the crash?

The classic algorithm, ARIES (Mohan et al., 1992), replays everything (redo) and then rolls back the transactions that hadn't committed, using undo records. InnoDB follows that shape, with its undo log. Postgres skips the undo phase entirely: a crashed transaction's row versions stay on disk, but its transaction id never got a commit record, so every reader treats them as invisible and vacuum removes them later. MVCC doubles as undo.

5.8Postgres and InnoDB, side by side

Now that both engines' machinery is on the table, here's how they differ:

Look at the torn-page row. Full-page images and the doublewrite buffer exist because the engine overwrites pages in place, and the log exists because every commit still dirties pages scattered across the file. Is there a design that never overwrites anything?

6.1The write path

A B+tree engine does random writes. Each insert changes a leaf somewhere in the tree, and eventually that 8 KB page is written back, often for a change of a few bytes, with a full-page image on top. O'Neil, Cheng, Gawlick and O'Neil's log-structured merge-tree (1996), or LSM tree, starts from the opposite premise: buffer writes in memory, write them out as large, sorted files that are never modified again, and merge those files together in the background.

RocksDB, which grew out of Google's LevelDB, is the engine most LSM systems use or copy: MyRocks (MySQL with RocksDB inside), CockroachDB's Pebble, TiKV, Kafka Streams state stores. Cassandra and ScyllaDB have their own. Let's run ada's update through one as put(1, age 37). (RocksDB writes level 0 as L0, level 1 as L1, and so on.) First the log, as in section 5. Then the new value goes into the memtable, a sorted structure in memory (in RocksDB a skiplist, a layered linked list that keeps keys in order). Then put returns.

The memtable is flushed as a sorted string table, an SST: a sorted file that's never modified once written. Files on level 0 come straight from memtables, so their key ranges can overlap one another. Compaction merges level 0 into level 1, and each level into the next when it outgrows its target, which is 10 times the level above by default. A full memtable is frozen as an immutable memtable, a background thread writes it out, and a fresh memtable takes new writes in the meantime. In each merge, newer values win, and a deleted key is dropped once nothing older lies beneath it.

One difference from Postgres matters for ada's 37. By default RocksDB appends to its WAL without waiting for the flush, so a crashed process loses nothing but a power cut can lose the last few writes. A program that wants the promise COMMIT made in section 5 sets sync = true on its writes and pays for an fdatasync each time, or shares one across a group of writes as Postgres does.

?Why is this fast for writes?

Apart from the log append, every disk write is a large sequential write of a whole sorted file, and no write waits for a read. A B+tree insert into a cold part of the tree has to read the leaf first. An LSM insert never reads anything.

6.2The read path, and bloom filters

The price is paid on reads. The newest value of a key could be in the memtable, in any level-0 file, or in one file per level below. A lookup has to check them newest first and stop at the first hit. Checking every file would mean a disk read per file, so each file carries a bloom filter: a small bit array that answers "is this key in the file?" with either "definitely not" or "maybe". The "definitely not" answer is the common one, and it costs no I/O.

In a bloom filter each key switches on a few bits in the array, and a key can't be in the file if any of its bits is off. A textbook filter with 10 bits per key and 7 bits switched on per key (7 hash functions) has a false-positive rate of (1 − e^(−7/10))^7, about 0.8%. In RocksDB 8.9's db_bench benchmark tool, 2 million random puts followed by 200,000 reads of existing keys and 200,000 reads of missing ones gave these counters:

Building the same database with --bloom_bits=0 (no filters) and running the same reads shows what the filters save. Without them the 400,000 lookups needed 627,884 data-block reads instead of 147,099, 4.3 times as many. Lookups of missing keys, which have to check every level, averaged 5.8 µs without filters and 1.1 µs with them. Timings for existing keys depend on how warm the cache is, so they don't compare cleanly between the two runs and are left out.

6.3Compaction and write amplification

Compaction is where the LSM tree pays for its cheap writes. Each byte you put is written to the WAL, then to level 0, and then rewritten each time it's merged down a level.

In a 5-million-put db_bench run (100-byte values, 4 MB memtables, a 16 MB level 1), RocksDB's own compaction statistics reported:

0.61 GB of user data turned into 3.9 GB of compaction writes, plus the WAL. This tree only reached three levels, and L3 wasn't full yet. RocksDB's leveled compaction page says write amplification for leveled compaction "is often larger than 10" on bigger trees.

?What can you trade to write less?

The compaction style. Leveled compaction keeps one sorted run per level, which keeps reads and space tight but rewrites data up to the size ratio between levels (10) times per level. Tiered compaction (RocksDB's "universal", Cassandra's size-tiered) lets several runs pile up in a level before merging them all at once. That writes each byte fewer times, but reads check more files and space can temporarily double during a big merge.

There's a second price. If compaction can't keep up with the incoming writes, level 0 piles up files, and RocksDB deliberately slows or pauses new writes until compaction catches up. This is a write stall.

6.4Deletes are writes

An LSM tree can't remove a key from an immutable file. A delete writes a tombstone, a marker saying "this key is gone", which shadows older values until compaction drops both. Until then, every scan that crosses the deleted range reads the tombstones and skips them.

We now have two designs that answer the same question in opposite ways. The next question is which one to pick.

7.1The three costs, side by side

Neither structure wins everywhere. Section 1.4 named three costs, and the table below says where each design puts them. Read amplification is worst for LSM trees, because a key may live in any of several files. Write amplification is paid by B+trees as whole pages rewritten, and by LSM trees as data rewritten during compaction. Space amplification is a B+tree's part-empty pages against an LSM tree's stale versions waiting for compaction.

?When does the difference decide a migration?

When writes or disk space dominate the bill. Facebook moved its main MySQL user database (UDB) from InnoDB to MyRocks in 2017. The VLDB 2020 paper reports the instance size fell by 62.3% compared to compressed InnoDB, bytes written to flash went down 75%, and the server count fell to less than half. It comes down to the table above: InnoDB "wasted 25-30% space in fragmentation", and compressed 16 KB pages still had to align to 8 KB on disk, while RocksDB stores a block compressed to 5 KB in 5 KB.

For read-heavy workloads whose working set fits in memory, a B+tree is simpler to reason about, has no compaction to tune, and gives steadier latency. That covers most OLTP applications (the many small reads and writes of an ordinary application), and it's why Postgres and InnoDB remain the default.

8.1The numbers side by side

Here are the measurements from the chapter in one place. They come from different tools and setups, so compare them within a row, and expect different values on other machines. What carries over is the shape.

8.2What full-page images do to log volume

The WAL rows are the easiest to turn into something you'd feel. Say a server commits 10,000 transactions a second, each like the small pgbench transactions in section 5. The log has to be written, shipped to replicas (other servers that keep a copy of the data) and archived, so its volume matters:

9.1Where to look

Each question this chapter raised has a command that answers it on a running server.

-- What's in the buffer pool, by relation? (section 4)
create extension pg_buffercache;
select c.relname, count(*) from pg_buffercache b
  join pg_class c on c.relfilenode = b.relfilenode group by 1 order by 2 desc limit 10;
 
-- Cache hit ratio per table, heap and index (section 4)
select relname, heap_blks_hit, heap_blks_read, idx_blks_hit, idx_blks_read
from pg_statio_user_tables order by heap_blks_read desc limit 10;
 
-- WAL volume, full-page images and syncs since the last reset (section 5)
select wal_records, wal_fpi, wal_bytes, wal_sync from pg_stat_wal;
 
-- Checkpoints forced by WAL volume, not by time (section 5.6)
select checkpoints_timed, checkpoints_req from pg_stat_bgwriter;   -- Postgres 16
select num_timed, num_requested from pg_stat_checkpointer;         -- Postgres 17 and later
 
-- Index fill and tree height (section 3)
create extension pageinspect;
select * from bt_metap('my_index');

# The WAL records between two LSNs (section 5)
pg_waldump -p $PGDATA/pg_wal -s 0/8D19EFB0 -e 0/8D19F180
 
# RocksDB: per-level compaction stats and stall counters are in the LOG file (section 6)
grep -A 12 'Compaction Stats' /path/to/db/LOG | tail -14

9.2Rules that hold up

1. Give big, insert-heavy tables sequential or time-ordered keys. A bigint sequence or a UUIDv7 inserts at the right edge, and random keys cost space and cache (section 3.6).
2. Don't read a high hit ratio as "the database fits in memory". In Postgres a miss in shared_buffers may still be a hit in the page cache, so watch blks_read as a rate and look at device latency (section 4.4).
3. Size max_wal_size so checkpoints come from the timer. Frequent checkpoints multiply full-page images (section 5.6).
4. Relax synchronous_commit only for writes you can lose, and never turn fsync off. The first risks up to 600 ms of commits by default, the second can corrupt the cluster (section 5.4).
5. Keep an LSM tree's filters and index blocks in memory, or point reads turn into disk reads (section 6.2).
6. Don't use an LSM store as a queue. The tombstones of consumed items slow every scan (section 6.4).

9.3What you trade for what

9.4Symptom, cause, fix