What a Write-Ahead Log Actually Promises
The durability primitive underneath every database, and the one number that shapes every decision in it.
What It Takes to Build a Write-Ahead Log
10 parts, in reading order.
- Part 1
- Part 2
Twenty-Two Bytes in Front of Every Record
A length prefix tells you where a record ends. A checksum tells you whether to believe the length prefix.
- Part 3
The Sequence Number That Was Never Written Down
The LSN is the identity of every record in the log. It isn't stored on disk, and three problems follow from that.
- Part 4
Group Commit, or Refusing to Pay for fsync Alone
Getting from 255 writes a second to nearly ten thousand, without weakening a single durability guarantee.
- Part 5
Backpressure, and a Cancel That Doesn't Cancel
A bounded queue forces you to decide who waits. Cancellation forces you to decide what an error means.
- Part 6
Segments, and the fsync That Hit the Wrong File
Splitting the log into files makes almost everything easier. The seam between writing and rotating is where a durability bug was hiding.
- Part 7
Three Ways to Recover, and What a Torn Tail Costs
Recovery isn't about salvaging as much as possible. It's about knowing exactly where you stopped believing the file.
- Part 8
Checkpoints, and What the Benchmark Wasn't Measuring
A 2.55x speedup that was real, produced by a mechanism that doesn't exist, hiding a bug that resurrects deleted keys.
- Part 9
Testing a Thing Whose Whole Job Is Surviving a Crash
You can't unit test a power cut. What I built instead, and the gap I left in the middle of it.
- Part 10
The Invariants I Didn't Hold
An honest accounting of a write-ahead log: what it guarantees, where the documentation outran the code, and the pattern in every gap.