7.3.3 — The Write-Ahead Log, Durability and LSM Trees

The power fails while the database is halfway through writing an 8 KB page. 4 KB of the new version is on the platter and 4 KB of the old one is still there. The page is now neither — its checksum will not match, and the row inside it is a mixture of two states.

This is a torn page, and it is the failure the entire durability design exists to survive. It is worth taking seriously as the starting point, because everything below follows from one uncomfortable fact: writing a page is not atomic, and no amount of careful ordering inside the page makes it so.

1. The rule: log first, then anything else

The answer is not to make the page write atomic. It is to make it repeatable.

The write-ahead logging rule: before a change to a data page is written to disk, a record describing that change must already be safely on disk.

The log is a sequential file of records: "on page 517, at offset 6120, this row version was written". Each record has a log sequence number (LSN), and every page header stores the LSN of the last record that touched it — which is how recovery knows whether a page already contains a given change.

Commit means one thing: the log records for this transaction are flushed to durable storage. The data pages are still sitting dirty in the buffer pool from Chapter 7.3.1. They may not reach disk for minutes.

That single decision buys three enormous things at once.

Speed. A commit is an append to the end of one file — sequential, and often already in the same file the previous commit wrote. The alternative would be a random write to every modified page, which on rotating disks is a thousand times slower and on SSDs is still far worse.

Batching. One page updated fifty times before the next checkpoint is written to the data file once. Fifty log records, one page write.

Crash recovery. On restart, the engine replays log records from the last known-good point. Any change that was committed but had not reached its data page is reapplied. Any change from a transaction that never committed is rolled back. This is redo and undo, and the algorithm behind it is ARIES (Mohan et al., 1992), still the shape used by PostgreSQL, InnoDB, SQL Server and Oracle.

The durable write is the small sequential one. The expensive random writes are deferred, batched, and often collapsed away entirely.

2. fsync, and the layers that lie about it

Writing to a file does not put bytes on a disk. It puts them in the operating system's page cache (Chapter 2.6), and the OS writes them out whenever it likes. fsync() is the call that says actually put it on stable storage and do not return until it is there.

So a commit is: append log records, fsync, return.

That fsync is the slowest thing in a transaction, and its cost is the reason for two mechanisms.

Group commit. If twenty transactions commit within the same short window, the engine flushes all their log records with one fsync. Throughput rises with concurrency instead of being capped at one commit per disk flush. PostgreSQL's commit_delay tunes how long to wait to collect a group.

Relaxed durability, honestly described. synchronous_commit = off in PostgreSQL, or innodb_flush_log_at_trx_commit = 2 in MySQL, means the commit returns before the fsync. Transactions become dramatically faster, and a power failure loses the last fraction of a second of committed work. Note precisely what is and is not lost: the database is still consistent — it recovers to a valid earlier state — you just lose the tail. For analytics ingestion or a cache-like table that is a reasonable trade. For a payment it is not. The value of stating it this way is that it is a per-workload decision, not a global setting to be brave about.

And the layers below can lie. Consumer SSDs and some RAID controllers acknowledge a flush while the data is still in a volatile write cache, so a power cut loses it anyway. Enterprise drives have power-loss protection — capacitors that finish the write — and that is a real hardware difference worth knowing exists.

One more piece of hard-won knowledge. In 2018 the PostgreSQL project found that on Linux, if an fsync fails, the error may be reported once and the dirty pages then dropped — so a retry returns success while the data is gone. The fix, in PostgreSQL 12, was to treat an fsync failure as a reason to crash and recover from the log rather than to continue. The lesson generalises: a durability layer that continues after an unclear failure is more dangerous than one that stops.

3. Torn pages, and the two answers

Return to the opening problem. The log lets you replay a change onto a page — but replaying onto a page that is half old and half new produces garbage, because the redo record assumes a known starting state.

PostgreSQL's answer: full_page_writes. The first time a page is modified after each checkpoint, the entire page image is written into the WAL, not just the change. Recovery restores that whole image and then replays subsequent changes onto a known-good base.

This is why WAL volume spikes right after a checkpoint, and why very frequent checkpoints can increase total write volume: every checkpoint resets the "first touch" flag for every page. It is a real tuning trade — longer checkpoint intervals mean less WAL and longer recovery.

InnoDB's answer: the double-write buffer. Every page is written twice — first to a small contiguous scratch area, then to its real location. If a crash tears the real write, the intact copy in the scratch area is used. Same guarantee, different cost shape: constant doubled page writes rather than bursts of full-page log records.

Some filesystems make both unnecessary — ZFS's copy-on-write never overwrites a page in place — and you can then turn full_page_writes off. That is a genuine optimisation and a genuinely dangerous one to guess at.

4. Checkpoints and recovery time

A checkpoint flushes all dirty buffers to the data files and records "everything before this LSN is safely applied". Recovery only needs to replay from the last checkpoint.

The tuning trade is clean and you should be able to state it both ways:

• Frequent checkpoints — short recovery, but constant I/O and more full-page writes.
• Rare checkpoints — smooth steady-state I/O and less WAL, but recovery after a crash may take many minutes, and each checkpoint is a large burst of writes.

PostgreSQL spreads a checkpoint's writes over the interval (checkpoint_completion_target) so it is a gentle slope rather than a stall. A database that periodically freezes for a few seconds is very often a checkpoint storm, and it is diagnosable from pg_stat_bgwriter, where checkpoints_req (forced because WAL filled up) exceeding checkpoints_timed means the interval is too short for the write volume.

5. The log is also a change stream

Once every change is in an ordered durable log, several other features come almost free — and this is why the WAL is one of the most reused ideas in data systems.

Replication. Ship the log records to another machine and replay them. That is physical replication, and it gives an exact byte-level copy. It is how PostgreSQL streaming replicas and MySQL's InnoDB redo shipping work. Chapter 10.5 covers the distributed consequences — lag, read-your-writes, failover.

Point-in-time recovery. Keep a base backup plus every WAL segment since, and you can restore to any moment: "the state at 14:32:10, just before the bad migration". This is what makes a backup strategy an actual recovery strategy rather than a daily snapshot.

Change data capture. Logical decoding turns log records back into logical row changes — "row 42 in orders changed status from paid to shipped" — which can be streamed to a queue. That is how Debezium and similar tools mirror a database into Kafka without any application code and without polling, and it is the only mechanism a manual UPDATE cannot bypass, which Chapter 10.14.2 relies on for cache invalidation.

MySQL has two logs, and this confuses people. The InnoDB redo log is the crash-recovery WAL described above. The binlog is a separate server-level log of logical changes used for replication and PITR. A transaction commits to both, coordinated by an internal two-phase commit. PostgreSQL uses one log for both jobs.

WAL is not free. Every write is written twice — once to the log, once eventually to the data file. That is the baseline write amplification of a B-tree engine, and it is the number the next section attacks.

6. LSM trees: the opposite trade

A B-tree updates data in place. To change a row you find its page and modify it, which means a random write. On write-heavy workloads that is the bottleneck.

A log-structured merge tree never updates in place. It only ever appends.

This is the engine behind RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and the storage layer of many time-series and key-value systems.

How a write works:

1. Append the record to a commit log (durability, same idea as WAL).
2. Insert into the memtable, a sorted in-memory structure (usually a skip list, Chapter 4.13.2).
3. Return. The write never touched a disk page at a random location.

When the memtable is full, it is written out as an SSTable (sorted string table) — an immutable file of sorted key-value pairs, written sequentially in one pass. A new empty memtable takes over.

How a read works, and here is the cost. The key might be in the memtable, or in any SSTable, with the newest copy winning. Naively that is a search per file.

Three mechanisms rescue it:

• A Bloom filter per SSTable answers "this file definitely does not contain this key" in a few bits (Chapter 4.29 builds one). Most files are skipped without any I/O. This is what makes LSM reads viable at all.
• A sparse index in each file gives the block to read for a key range.
• Compaction merges SSTables in the background, discarding overwritten and deleted entries, keeping the file count bounded.

Deletes are the counter-intuitive part. You cannot remove a key from an immutable file, so a delete writes a tombstone — a marker meaning "deleted at this time". Reads see the tombstone and report nothing. The space is only reclaimed when compaction merges away every older copy. A workload that deletes heavily can therefore use more space after deleting, and in Cassandra, accumulated tombstones are a classic cause of queries getting slower over time.

Compaction is where the difficulty lives. It runs in the background, consuming disk bandwidth and CPU, and if it falls behind, read performance degrades as file counts grow. Two strategies with an honest trade:

• Levelled compaction — files organised into levels of increasing size, each level having non-overlapping key ranges. Reads touch few files; writes are amplified more, because data is rewritten as it moves down levels.
• Size-tiered compaction — merge files of similar size when enough accumulate. Cheaper writes; reads may touch more files; and it needs temporary space up to the size of the merged set.

	B-tree	LSM tree
Write path	Random, in place	Sequential append
Write amplification	~2× (WAL + page)	Higher, from compaction
Read path	One tree walk	Memtable + several files
Space	Some slack in pages	Compact, but tombstones linger
Range scan	Excellent	Good; merges files
Best at	Mixed read/write, transactions	Write-heavy, key-value, time series

The honest summary: B-trees make reads simple and pay on writes; LSM trees make writes cheap and pay on reads and on background work. Both are used at enormous scale, and modern systems blur the line — MySQL has a RocksDB engine, and PostgreSQL's heap plus WAL already borrows the append-only idea for durability.

What the interviewer will push on

"What is write-ahead logging and why is it faster?" The log record must reach disk before the data page does; commit means the log is flushed, not the page. It is faster because a commit is a small sequential append rather than random writes to every modified page, and because fifty updates to one page collapse into a single later flush.

"What actually happens on COMMIT?" Append the transaction's log records, fsync, return. Then volunteer group commit — many transactions share one flush, which is why throughput improves with concurrency — and name what synchronous_commit = off trades: the last fraction of a second of committed work, in exchange for a large speed gain, with the database still consistent.

"How does the database survive a torn page?" A redo record assumes a known starting state, and half-written pages have none. PostgreSQL writes the full page image into the WAL on first touch after a checkpoint; InnoDB writes every page twice through the double-write buffer. Explaining why the log alone is insufficient is the tell.

"What does a checkpoint do, and what is the trade?" Flushes dirty buffers and marks a recovery start point. Frequent means fast recovery and more I/O plus more full-page writes; rare means smoother I/O and slow recovery. Add the diagnosis: requested checkpoints exceeding timed ones means the interval is too short for the write volume.

"How is replication built?" By shipping the same log. Physical replication replays byte-level records; logical decoding turns them into row-level changes for change data capture, which mirrors a database without application code or polling. Mention that MySQL has two logs — redo for recovery, binlog for replication — coordinated by an internal two-phase commit.

"When would you choose an LSM tree over a B-tree?" Write-heavy key-value or time-series workloads, where sequential appends beat random in-place updates. Then price it: reads must check the memtable plus several SSTables, saved by Bloom filters; compaction consumes background I/O; and deletes write tombstones, so heavy deletion can temporarily increase space use.

One thing to volunteer: mention the 2018 fsync finding — a failed flush on Linux could report the error once and drop the dirty pages, so a retry succeeded while the data was gone, and the fix was to crash and recover from the log instead. It shows you understand that a durability layer that continues after an unclear failure is worse than one that stops.

Recall

• Write-ahead rule: the log record reaches disk before the data page does. Commit = flush the log, not the page. Buys speed (sequential append), batching (many updates, one page write) and crash recovery (redo committed, undo uncommitted — the ARIES shape).
• fsync is the expensive part. Group commit shares one flush across many transactions. synchronous_commit = off returns before the flush and loses the last fraction of a second — consistent, but truncated.
• A torn page cannot be repaired by redo alone. PostgreSQL writes full page images after each checkpoint; InnoDB writes every page twice via the double-write buffer.
• Checkpoints bound recovery time. Frequent = fast recovery, more I/O and more full-page writes. checkpoints_req exceeding checkpoints_timed means the interval is too short.
• The log is also a change stream: physical replication, point-in-time recovery, and logical decoding for change data capture that no manual UPDATE can bypass. MySQL splits the jobs into redo log and binlog.
• An LSM tree never updates in place: append to a commit log, insert into a sorted memtable, flush sequentially as an immutable SSTable. Writes are cheap; reads must check several files.
• Reads survive because of a Bloom filter per SSTable (definitely-not-here in a few bits), a sparse index, and background compaction. Levelled compaction favours reads; size-tiered favours writes.
• Deletes write a tombstone, so space is reclaimed only at compaction and heavy deletion can temporarily increase usage — the classic cause of a key-value store getting slower over time.

Self-test: Why is a commit fast when the data page has not been written? · Why is a redo record not enough to repair a torn page? · What exactly do you lose with synchronous_commit = off? · How does replication reuse the durability mechanism? · Why does an LSM read need a Bloom filter? · Why can deleting rows make an LSM store bigger?

Next: 7.4.1 moves from one writer to many — what ACID actually promises, the anomalies each isolation level permits, and why "read committed" is the default that surprises people.