· software-engineers Editorial · Career · 6 min read
Write Ahead Log Crash Recovery Databases
How write-ahead logging guarantees crash recovery in databases: ARIES phases, fsync semantics, and interview-ready explanations.
Write Ahead Log Crash Recovery Databases
Write-ahead logging (WAL) underlies crash recovery in essentially every production relational database — PostgreSQL, MySQL/InnoDB, SQLite — and increasingly in distributed systems built from scratch, making it a recurring topic in both database-internals interviews and generalist system-design rounds. The core rule is simple to state and surprisingly easy to get wrong when asked to explain why it works: no data page may be flushed to disk before the log record describing the change that produced it has itself been flushed to disk.
This article walks through the mechanism precisely enough to answer follow-up “but why” questions.
The Core WAL Invariant
The invariant, often called the write-ahead rule: before a modified data page is written to disk, the corresponding log record must already be durably on disk (fsynced). This is why it’s called “write-ahead” — the log is always ahead of the data.
Why this matters: if the database crashes after the data page is flushed but before the log record is flushed, recovery has no way to know what changed (or to undo it if the transaction wasn’t committed). By forcing the log first, recovery always has a durable, ordered record of every change, regardless of when the underlying data pages actually made it to disk.
The second half of the guarantee: a transaction is not considered committed until its commit log record is durably flushed. This is what gives WAL its durability guarantee (the D in ACID) — the data pages themselves can lag behind on disk indefinitely, as long as the log is durable and complete.
The Three-Phase ARIES Recovery Algorithm
ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the canonical recovery algorithm referenced in database interviews, and its three phases are worth memorizing precisely:
- Analysis: scan the log forward from the last checkpoint to reconstruct the transaction table (which transactions were active at crash time) and the dirty page table (which pages had uncommitted changes in memory not yet flushed).
- Redo: replay every logged change since the earliest relevant log record — including changes from transactions that eventually committed and those that didn’t — bringing the database to the exact state it was in at the moment of the crash. This is the step candidates most often get wrong: redo is not selective; it reapplies everything, because it’s cheaper to redo-then-undo than to figure out precisely what needs redoing.
- Undo: roll back any transactions that were still active (uncommitted) at crash time, using the log’s undo information, restoring the database to a state where only committed transactions’ effects remain.
The subtlety interviewers probe for: why redo everything instead of just uncommitted transactions? Because after a crash, you don’t yet know which pages made it to disk before the crash. Blindly redoing from the log (which is idempotent by design, using page LSNs to skip already-applied changes) is simpler and provably correct, whereas selectively determining “what actually needs redoing” would require information you don’t reliably have.
Comparison: WAL vs Shadow Paging vs No Durability Guarantee
| Approach | Write Amplification | Recovery Complexity | Concurrent Write Throughput | Used By |
|---|---|---|---|---|
| Write-ahead log (WAL) | Low (sequential log append + async page flush) | Medium (ARIES-style redo/undo) | High (log is append-only, sequential I/O) | PostgreSQL, MySQL InnoDB, SQLite (WAL mode), most modern RDBMS |
| Shadow paging | Higher (whole pages copy-on-write) | Low (atomic pointer swap) | Lower (page copying overhead) | Older systems, some LMDB-style engines |
| No durability guarantee (write-back only) | Lowest | N/A — undefined state on crash | Highest | In-memory caches, non-durable stores (explicitly accepted tradeoff) |
| fsync-per-write, no log | High (random page writes) | Trivial but slow | Low | Rarely used in practice due to throughput cost |
The key tradeoff to articulate: WAL wins because log writes are sequential (fast on both spinning disk and SSD) even though the eventual data-page writes are random, decoupling durability latency from data-layout complexity.
fsync Semantics: The Detail That Trips Up Senior Candidates
“Flushed to disk” is doing a lot of work in the invariant above, and interviewers at the staff level will push on what it actually means:
- A
write()syscall only copies data into the OS page cache — it does not guarantee durability against a power loss or kernel panic. fsync()(orfdatasync()) forces the OS to flush the page cache to the physical storage device, and critically, the storage device itself must honor the flush (disabling write caching, or having battery-backed/capacitor-backed cache that survives power loss).- Databases group multiple transactions’ commit records into a single fsync call (group commit) to amortize fsync’s latency cost across many transactions, which is why commit latency under load is often better per-transaction than under low concurrency — a counterintuitive fact worth citing if this comes up.
A cheap SSD or cloud volume with fsync effectively a no-op (write caching enabled, no power-loss protection) silently breaks the entire WAL durability guarantee — this is the classic “why did we lose data during a crash even though we use Postgres” postmortem finding, and naming it is a strong interview signal.
Checkpointing: Why Recovery Doesn’t Replay the Entire Log History
Without checkpoints, recovery would need to scan the log back to the beginning of time. A checkpoint periodically records the current transaction table and dirty page table, giving recovery a bounded starting point — Analysis only needs to scan forward from the last checkpoint, not from log record zero. The cost/benefit tradeoff: more frequent checkpoints mean faster recovery but more write overhead during normal operation (since checkpointing typically forces outstanding dirty pages to disk).
FAQ
Q: Why is the log written sequentially instead of updating the data page directly? A: Sequential appends to a log file are dramatically faster than random writes to scattered data pages (even on SSDs, due to write amplification and journaling overhead), and deferring the actual data page write lets the database batch and reorder those writes for efficiency without sacrificing durability, since the log already guarantees recoverability.
Q: What happens if the crash occurs mid-write to the log itself? A: WAL records include checksums; a partially-written or corrupted trailing log record is detected and treated as if it never happened — recovery simply stops replaying at that point, since an incomplete write means the corresponding fsync never completed and the record was never considered durable.
Q: Does WAL alone guarantee consistency in a distributed database? A: No — WAL guarantees single-node crash recovery and durability. Distributed consistency additionally requires a replication/consensus protocol (like Raft or Paxos) to ensure the log itself is durable across node failures, not just page failures on a single node.
For interview-style walkthroughs of database internals questions including WAL, indexing, and transaction isolation, see The 0-to-1 SWE Interview Playbook (https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20).