Unit 4.8 · about 6 h
264 / 324Write-ahead logging, recovery, checksums and durability
Build on Systems' files-fsync-durability unit rather than repeat its rename experiment. The new mechanism is recovery of logical state and its index after interruption, with a precise acknowledgment and corruption contract.
- explain
- implement
You can now
- Trace WAL-before-page and commit-before-ack ordering using log sequence numbers.
- Implement bounded, checksummed append records and deterministic recovery of complete prefixes.
- Specify snapshot publication, directory durability and a safe log-retention boundary.
- Diagnose torn tails, corruption and lost acknowledged writes without treating process death as a power-loss test.
Covers
- Write-ahead logging, log sequence and recovery order
- Checksums, torn tails, snapshots and atomic metadata replacement
- Acknowledgement, page-cache flush and stable durability boundaries
Study, in this order
6 steps
- Lecture 21: Database LoggingCMU 15-445/645 - database and storage core
Sections 1-2, pp. 1-2, and sections 6-7, pp. 4-6: buffer policies, WAL and logging schemes
Depth · Skip section 5: SQLite did not replace rollback journals after 2010; WAL is optional. Skip section 8's blanket checkpoint-pruning claim; use the recovery metadata in Lecture 22 to determine needed log history.
- Lecture 22: Database Crash RecoveryCMU 15-445/645 - database and storage core
Sections 1-5, pp. 1-6: LSNs, execution, checkpoints and ARIES recovery
Depth · Trace analysis, redo and undo; do not implement ARIES. Redo can start before the checkpoint at the minimum
recLSN. In Figure 4, follow the text's largest-lastLSN reverse undo rule, not the caption's 'oldest' starting point. PostgreSQL's MVCC/WAL recovery is not a literal implementation of this generic undo protocol. - OSTEP: crash consistencyOperating Systems: Three Easy Pieces - persistence and integrity
Chapter 42, section 42.3, Journaling (or Write-Ahead Logging)
Depth · Use write ordering and corruption detection for your own append-only store. Skip filesystem simulation and performance exercises.
- OSTEP: data integrityOperating Systems: Three Easy Pieces - persistence and integrity
Chapter 45, sections 45.3-45.6, Detecting Corruption, Using Checksums, Misdirected Writes and Lost Writes
- PostgreSQL 18: Write-Ahead LoggingPostgreSQL - EXPLAIN and transaction isolation lab
Section 28.3, WAL-before-data, REDO and group commit
- SQLite: rollback journal versus WAL modeSQLite Write-Ahead Logging
Sections 1, Overview, and 3, Activating And Configuring WAL Mode
Depth · Inspect the default using one connection. Do not run a multi-connection WAL exercise on an old bundled SQLite build.
Focus on
- Before flushing a dirty page, durable WAL must cover its
pageLSN. Before acknowledging a durable commit, durable WAL must cover its commit record; data pages can follow later. - ARIES repeats history, including loser updates, then undoes losers. A single-writer append-only store can instead replay complete committed records into a rebuildable index; its recovery protocol is smaller.
- A checksum detects many corruptions, not intent, lost whole records or adversarial changes. Bound lengths before allocating; distinguish incomplete EOF from a complete frame with a bad checksum.
- For a snapshot at log offset \(K\), flush the new snapshot, durably publish its name, flush a new manifest, atomically replace the old manifest and fsync its directory. Retain the old generation and required log until publication is durable.
Reproduce closed-book
python3 -I), print sqlite3.sqlite_version and inspect PRAGMA journal_mode on a fresh on-disk database with one connection: the tested SQLite 3.46.1 returned delete, not wal. Then implement a single-writer log with struct.pack('>II',length,crc) followed by payload; length is the payload byte count, capped at 1024, and crc is zlib.crc32(struct.pack('>I',length)+payload). Use payloads b'a=1', b'b=2', b'a=3'. Each frame is 11 bytes. Append all bytes with short-write handling and fsync before acknowledging; for a newly created log, fsync its parent directory too. Rebuild the latest-key index by scanning validated frames. Test every byte-prefix truncation from 0 through 33: recover exactly the complete prefix and return its ending offset, giving 34 cases. Incomplete EOF is an uncommitted tail under this model; a complete frame with a bad CRC or an excessive length is an error, not silently discarded. Flip byte 9 in the complete log and require a corruption error. The full log gives a=3,b=2, and rebuilding twice gives the same state. Finally draw crashes before and after durable manifest publication: recovery must select a complete old or new generation and retain the log needed by that generation. These are deterministic fault-model tests, not evidence of surviving a real power cut.Traps
- Acknowledging after write returns, but before
fsyncsucceeds. Kernel page-cache acceptance is not stable-storage durability. - Deleting the old log as soon as a snapshot file exists. Its contents and the selecting manifest must both be durably published first.
- Silently truncating any bad checksum as a torn tail. That can hide corruption or destroy acknowledged state; fail closed unless the recovery contract independently proves the suffix was uncommitted.
Practice
The section mini-project covers this: checksummed append-only state, a rebuildable offset index, every short-write and publication boundary, fsync-error handling, torn-tail versus corruption policy, snapshot/manifest recovery and an acknowledged-prefix oracle.
Self-test
-
What is illegal about flushing a page at
pageLSN=80when durable WAL ends at 70?A crash could leave the changed page without the recovery record needed to explain it. Flush WAL through 80 first. -
Can a committed transaction survive while its data pages are still dirty in memory?
Yes, if durable log records are sufficient to redo its committed effects and the engine's durability settings guarantee that log boundary. -
Can a record checksum detect deletion of the entire final valid frame?
No. The remaining frames still validate. An independent expected boundary or acknowledgment record is needed to detect that loss. -
Why does SIGKILL not establish power-loss durability?
It kills a process but leaves the kernel and its dirty page cache alive. The data can persist after process death without having been durable before it.
Completion criterion
Stop when
All 34 prefix cases match the independent prefix oracle, the corruption case fails closed, replay is idempotent, and the publication trace never selects an incomplete generation or drops its required log.
Mark passed, then open 4.9 Only mark this when you can do it without notes.Leads to
- 4.9 Record evolution, amplification and LSM trees Preserve this recovery contract during format changes and compaction.
- 5.5 Durable logs, delivery guarantees and idempotent consumers Separate durable local acknowledgment from delivery and replay effects.
Comes after
- 4.7 Two-phase locking, timestamp ordering and MVCCSeparate version visibility and commit status from persistence.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.
Also in this section
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.