Recovery And Reliability
Failures and the Write-Ahead Log
One transaction cannot complete — a constraint
JrCodex·7 min read
Jr Codex DBMS Notes
Level: Advanced Prerequisites: Module 7, Chapter 5; Module 5, Chapter 5 Time to complete: ~20 minutes
Table of Contents
- Kinds of Failure
- The Problem, Stated Precisely
- The Write-Ahead Log
- The Two WAL Rules
- What a Log Record Contains
- Why the Log Is Fast
- Summary & Next Steps
1. Kinds of Failure
Three Categories
─────────────────────────────────────────
TRANSACTION FAILURE
One transaction cannot complete — a constraint
violation, a deadlock victim (Module 7,
Chapter 5), an explicit ROLLBACK.
Fix: UNDO that transaction's changes.
SYSTEM CRASH
The process or machine stops. Memory is lost;
disk survives.
Fix: on restart, REDO committed transactions
and UNDO uncommitted ones. ── this module
MEDIA FAILURE
The disk itself is lost or corrupted.
Fix: restore from a backup and replay the log
(Chapter 3).
─────────────────────────────────────────
2. The Problem, Stated Precisely
The Contradiction to Resolve
─────────────────────────────────────────
Module 5, Chapter 5: writes modify pages in the
BUFFER POOL. Table files are updated lazily,
possibly minutes later.
Module 1, Chapter 4: once COMMIT returns, the
change survives any crash.
So: a crash one millisecond after COMMIT loses
the buffer pool, and the table file does not
contain the change.
Where did the durability come from?
─────────────────────────────────────────
Two Bad Answers, and Why
─────────────────────────────────────────
"WRITE THE PAGE ON COMMIT"
A page is 8KB and lives at a random location.
Each commit becomes a random write plus an
fsync. Throughput collapses, and a transaction
touching ten pages needs ten random writes —
which are not atomic together anyway.
"NEVER CACHE; WRITE EVERYTHING IMMEDIATELY"
Every update is a random disk write. This is
the file-based approach from Module 1,
Chapter 1, and it is orders of magnitude
slower.
─────────────────────────────────────────
3. The Write-Ahead Log
The Idea
─────────────────────────────────────────
Do not write the DATA. Write a DESCRIPTION of the
change to a SEQUENTIAL log file, and flush THAT.
The data pages follow later, lazily, in the
background.
If the machine crashes, the log contains
everything needed to reconstruct the pages.
─────────────────────────────────────────
The Flow
─────────────────────────────────────────
UPDATE accounts SET balance=200 WHERE id='A'
1. Read page into the buffer pool
2. APPEND a log record describing the change
LSN 1042: T7 changed page 88, offset 120,
from 300 to 200
3. Modify the page IN MEMORY (now dirty)
4. On COMMIT: append a COMMIT record and FSYNC
THE LOG ── this is the durability point
5. Return success to the client
6. ...minutes later, a background writer flushes
page 88 to disk
─────────────────────────────────────────
Why This Is Fast
─────────────────────────────────────────
Step 4 is a SEQUENTIAL append to one file.
Sequential writes are one to two orders of
magnitude faster than random ones, and many
concurrent commits can be batched into a single
fsync (GROUP COMMIT).
So durability costs one sequential flush rather
than N random writes — which is the whole trick.
─────────────────────────────────────────
4. The Two WAL Rules
RULE 1 — THE UNDO RULE
─────────────────────────────────────────
A log record describing a change must reach
durable storage BEFORE the modified data page
does.
WHY: if the page reached disk first and the
machine crashed, the table would contain an
uncommitted change with no record of how to undo
it. The database would be permanently corrupt.
This is what "write-AHEAD" names.
RULE 2 — THE REDO RULE
─────────────────────────────────────────
All log records for a transaction, including its
COMMIT record, must be durable BEFORE the commit
is acknowledged.
WHY: otherwise a crash could lose a change the
client was told had succeeded — a broken
durability promise.
─────────────────────────────────────────
def commit(txn, log, buffer_pool):
"""The ordering here IS the durability guarantee. Nothing may be reordered."""
for change in txn.changes:
log.append(change) # RULE 1: log record first...
buffer_pool.apply(change) # ...then the in-memory page
log.append(CommitRecord(txn.id))
log.fsync() # RULE 2: durable BEFORE acknowledging
return "COMMITTED" # only now is the client told
# The data pages are still dirty in memory. That is fine — the log has them.Together They Give You Everything
─────────────────────────────────────────
Rule 1 makes UNDO possible: any change that
reached disk has a log record preceding it.
Rule 2 makes REDO possible: any acknowledged
commit has durable log records.
Chapter 2's recovery algorithm is just these two
guarantees, used.
─────────────────────────────────────────
5. What a Log Record Contains
The Fields
─────────────────────────────────────────
LSN Log Sequence Number — a
monotonically increasing id. Every
page also stores the LSN of the
last change applied to it.
txn_id which transaction
type UPDATE | COMMIT | ABORT | BEGIN |
CHECKPOINT | CLR
page_id which page was changed
before_image the old value ── used for UNDO
after_image the new value ── used for REDO
prev_lsn the previous record for THIS
transaction, forming a backward
chain for efficient rollback
─────────────────────────────────────────
Why the Page Stores Its Own LSN
─────────────────────────────────────────
During recovery, the database compares the LSN
written on a page with the LSN of a log record.
page_lsn >= record_lsn ──► this change is
ALREADY on the
page. Skip it.
page_lsn < record_lsn ──► apply it.
This is what makes recovery IDEMPOTENT — safe to
run repeatedly, which matters because a machine
can crash again DURING recovery.
─────────────────────────────────────────
UNDO/REDO vs Simpler Schemes
─────────────────────────────────────────
Storing BOTH images gives the buffer manager
complete freedom:
STEAL a dirty page from an UNCOMMITTED
transaction may be written to disk
(needs UNDO to clean up)
NO-FORCE a COMMITTED transaction's pages need
NOT be written at commit (needs REDO
to reapply)
STEAL/NO-FORCE is the fastest combination and
what every serious database uses. It is also the
only one requiring both undo and redo — which is
why the log carries both images.
─────────────────────────────────────────
6. Why the Log Is Fast
Sequential vs Random, Again
─────────────────────────────────────────
Module 5, Chapter 1's cost model applies here
directly.
Random 8KB write ~100 µs (SSD)
Sequential append ~10 µs, and the device
pipelines them
A transaction touching 10 pages:
force the pages ──► 10 random writes + fsync
log it ──► 1 sequential append + fsync
─────────────────────────────────────────
GROUP COMMIT
─────────────────────────────────────────
fsync is the expensive part, and it costs the
same for 1 record as for 100.
So the database WAITS a moment, collects commit
records from concurrent transactions, and flushes
them together.
Each transaction sees slightly higher latency;
total throughput rises enormously. This is why
batching inserts helps so much (Module 3,
Chapter 6).
─────────────────────────────────────────
-- The durability dial. Know what you are trading.
SHOW synchronous_commit; -- PostgreSQL, default 'on'
SET synchronous_commit = off;
-- COMMIT returns BEFORE the log is flushed.
-- Much faster. A crash can lose the last ~0.2s of COMMITTED transactions.
-- The database stays CONSISTENT — it loses whole transactions, never half of one.
-- Defensible for: analytics loads, rebuildable data, bulk imports.
-- Not for: money, orders, anything a user was told succeeded.7. Summary & Next Steps
Key Takeaways
- Writes go to memory, so durability comes from appending a description of each change to a sequential log and flushing that instead of the data pages.
- The write-ahead rule requires a change's log record to reach disk before the page it describes; the commit rule requires all of a transaction's records to be durable before acknowledging.
- Log records carry both before and after images, which is what permits the fast STEAL/NO-FORCE buffer policy every serious database uses.
- Each page stores the LSN of its last applied change, making recovery idempotent — essential because a machine can crash again during recovery.
Concept Check
- Resolve the apparent contradiction between lazy page writes and the durability guarantee, in two sentences.
- What specifically goes wrong if a data page reaches disk before its log record?
- Why is
synchronous_commit = offa loss of durability but not of consistency?
Next Chapter
→ Chapter 2: Checkpoints and Crash Recovery
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index