How a database survives a crash

A database keeps its data in fixed-size pages — 8 KB in PostgreSQL, 16 KB in InnoDB, 4 KB by default in SQLite. To change a row it reads the page into memory, changes it there, and at some point writes the page back.

Reading pages is slow, so databases keep a cache of them: the buffer pool. A page that has been changed in memory but not yet written back is dirty. The buffer pool would love to keep dirty pages around for as long as possible — if the same page is updated a hundred times, it only needs writing once — but every dirty page is a change the disk does not know about yet.

So we have a tension. For speed, we want to delay writing pages. For safety, we want every committed change on disk before we say "committed". Writing every touched page at every commit would be correct and ruinously slow: random writes all over the disk, and a torn mess if the power fails halfway through a page.

The way out is the write-ahead log (WAL). Before a page is allowed to change on disk, a record describing the change is appended to a log — a single file that only ever grows at the end. At commit, the database makes sure the log is on disk up to and including that transaction’s commit record (an fsync), and then it says yes. The pages themselves can be written whenever it is convenient.

Why is that better? Because appending to one file is sequential I/O, which even spinning disks do quickly, and because a log record is small: "on page 4117, slot 3, set column 2 to 150" is tens of bytes, not 8 KB. And if the machine dies, the log is the truth: replay it from the last known-good point and every committed change is redone; a transaction with no commit record is undone or simply ignored.

You can watch PostgreSQL’s log grow. The console below is real PostgreSQL 18, running in your browser through PGlite. pg_current_wal_lsn() returns the log sequence number — the byte position at the end of the WAL — so the difference between two of them is how many bytes of log a piece of work produced.

The script measures three things. First, inserting 10,000 rows produces about 1.6 MB of log — more than the table and its primary-key index occupy. That is the price of writing everything twice: once to the log now, and once more to the table’s pages later.

The second and third numbers are the interesting ones. After a CHECKPOINT, the first change to a page writes far more log than the second: when I ran it, about 19,000 bytes against about 300. Both updates change one short text value. Why the difference?

Try this:

What you are seeing is full-page writes, and it is about torn pages.

A PostgreSQL page is 8 KB; the disk underneath may only guarantee that 512-byte or 4 KB sectors are written atomically. If the power fails while a page is being written back, the page on disk can be half old and half new — torn. A log record that says "set slot 3 to 150" is no use against a torn page: it describes a change to a page that no longer exists in any consistent form.

PostgreSQL’s answer is to put a complete copy of the page into the WAL the first time the page changes after each checkpoint. Recovery starts from that checkpoint, so for every page it touches it first finds a whole, known-good image in the log, restores it, and then replays the small records on top. The image costs about one page of log (your ~19,000 bytes were two or three page images: the table page, the index page and the mark table’s page); every later change to the same page, until the next checkpoint, is just the small record.

A checkpoint, then, is the database saying: "every dirty page that existed when I started has now been written to disk, so recovery never needs to look further back than here." It bounds how much log has to be kept and how long recovery takes, and it resets the full-page-write clock. Checkpoints too often and you write page images constantly; too rarely and recovery after a crash takes a long time. That is a real tuning knob (checkpoint_timeout, max_wal_size).

The storage-engines simulator draws all of this: the WAL, the buffer pool with its dirty pages, and the disk, with a counter of every byte written. This view runs its update-heavy scenario on the B+tree alone with full-page writes switched on.

Try this:

This is the whole bargain of a classical database engine: the buffer pool makes writes cheap by delaying them, the WAL makes the delay safe, and checkpoints stop the WAL growing for ever.

So far the pages have been the leaves and branches of a B+tree: one big sorted tree, updated in place. PostgreSQL’s indexes, InnoDB’s tables and SQLite’s files all work this way. Updating in place is what makes the WAL and the torn-page dance necessary.

There is another family that takes the log idea to its logical conclusion. A log-structured merge-tree (LSM-tree) — RocksDB, LevelDB, Cassandra, ScyllaDB, the storage under many modern systems — never updates a file on disk at all. A write goes to the WAL (for durability, exactly as before) and into a sorted structure in memory, the memtable. When the memtable is full it is frozen and written out in one sequential pass as an immutable sorted file, an SSTable. Its part of the WAL can then be thrown away.

Try this:

Crash recovery in an LSM-tree is pleasingly simple. The SSTables are immutable and were fsynced before they were recorded in the manifest, so they are either fully there or not there at all. The only thing lost in a crash is the memtable — and the WAL holds exactly the writes that were in it. Replay the WAL into a new memtable and you are back.

An LSM-tree buys fast writes by deferring work. Every flush adds another file, files overlap, and an updated or deleted key may now have several versions scattered across them. Reads get slower the more files there are, and old versions waste space. So, in the background, the engine compacts: it merge-sorts files together, keeps the newest version of each key, and writes fewer, bigger, non-overlapping files further down.

Try this:

Compaction also matters for crashes, in a quiet way: it, too, writes new files and only then records them in the manifest and deletes the old ones. A crash mid-compaction leaves some orphaned half-written output, which is simply ignored and deleted on restart. Immutable files make "atomic" cheap.

If you want to see the two families side by side, the simulator’s Range scans favour the B+tree and Bloom filters scenarios are good next stops; the trade-off is usually summarised as read, write, space — pick two.

SQLite is a useful contrast, because it has two complete answers to the crash problem and lets you switch between them with one PRAGMA.

In the default rollback journal mode, SQLite does the opposite of a WAL: before changing a page in the database file, it copies the page’s original content into a separate -journal file and fsyncs that. Then it writes the new pages into the database. If the process dies, the next program to open the database finds a "hot" journal and copies the old pages back. The database is rolled back to the last commit. The commit itself is the moment the journal is deleted.

In WAL mode, the database file is left alone during a transaction; new versions of pages are appended to a -wal file, readers look there first, and a checkpoint later copies them home. That is the same shape as PostgreSQL’s WAL, with whole pages as the records.

Try this:

The lab is honest about a limit: one browser page cannot pull the plug on itself, so what you see is the on-disk format the recovery logic relies on rather than a crash. But the mechanism is all here — a page either has a known-good copy somewhere or it was never touched.

Surviving a crash is the D in ACID — durability — and its sibling A, atomicity. But a database that is merely durable can still hand your application nonsense, if two transactions run at the same time and see each other’s half-finished work. That is the I: isolation.

The machinery is related. Modern databases keep several versions of a row (MVCC — multi-version concurrency control), and each transaction reads from a snapshot: the set of versions committed when it started (or, at READ COMMITTED, when each statement started). Old versions are what the undo log or the heap’s dead tuples are for. The isolation level decides which snapshot you get and what happens when two transactions want the same row.

The isolation lab steps two sessions through an interleaving, statement by statement, against models of PostgreSQL and InnoDB that have been checked against the real servers.

Try this:

The lost update has well-known fixes — SELECT … FOR UPDATE, an atomic SET balance = balance + 25, a version column — and they are all in the scenario list. The nastier anomaly is the one no row lock can see.

Try this:

Finally, the whole map at once. Every scenario, both engines, all four levels:

Try this:

Follow one UPDATE accounts SET balance = 175 WHERE id = 1; COMMIT; from start to finish:

An LSM-tree swaps steps 2 and 5 for a memtable and a flush, then spends its spare time compacting; SQLite in rollback mode inverts the log and saves the old pages instead of the new ones. But every one of them rests on the same rule: before you change the only copy of something, write down enough to get back.