§42.3–42.5Solution #2: Journaling (Write-Ahead Logging)

Rather than repair inconsistencies after the fact, what if we prevented them? Journaling journaling A crash-consistency technique (write-ahead logging, borrowed from databases): before overwriting structures in place, first write a note describing the update to an on-disk log. After a crash, recovery replays only the log — turning recovery from O(disk size) into O(log size). Used by ext3/ext4, XFS, JFS, NTFS. defined in ch. 42 — open in glossary — write-ahead logging, borrowed from databases — does exactly that: before overwriting structures in place, first write a note describing the update to an on-disk log. If a crash strikes mid-update, recovery reads the note and finishes (or discards) the update — scanning only the log, not the whole disk.

42.3 Journaling: The Basic Idea

ext3 is just ext2 plus a journal — a reserved region (or separate device) that holds these notes:

Data journaling

Take our append (write I[v2], B[v2], Db). With data journaling data journaling The journaling mode (ext3) that logs everything — metadata AND user data — to the journal before checkpointing. Safest, but writes every data block to disk twice, roughly halving write bandwidth. defined in ch. 42 — open in glossary , we first write the whole update to the log as a transaction transaction The unit of a journaled update: a transaction-begin block (TxB, with the target addresses and a transaction id/TID), the blocks being updated (metadata and, in data journaling, data), and a transaction-end/commit block (TxE, with the same TID). A transaction is atomic — recovery applies it fully or not at all. defined in ch. 42 — open in glossary : a transaction-begin block TxB (with the target addresses and a transaction id, TID), the blocks themselves, and a transaction-end block TxE. Once the transaction is safely logged, we checkpoint — checkpointing checkpointing The step that writes a committed transaction's updates to their FINAL on-disk locations (overwriting the old structures in place), after the transaction is safely in the log. Only once checkpointing succeeds is the update truly done; its journal space can then be freed. defined in ch. 42 — open in glossary writes the blocks to their real homes, overwriting the old structures in place.

But how we write the transaction matters enormously:

The lesson: the disk can reorder an all-at-once write, so a valid-looking transaction could contain garbage. The fix is a two-step write — content first, then the atomic TxE. Getting the disk to honor this ordering needs a write barrier write barrier A mechanism that forces write ordering: when a barrier completes, all writes issued before it are guaranteed on disk before any issued after. Needed because disk write caches (immediate reporting) otherwise let writes reach the platter out of order — which would break journaling. (Some disks cheat and ignore barriers for speed.) defined in ch. 42 — open in glossary (some disks, alas, cheat and ignore barriers for speed). That gives the three-phase protocol: journal write → journal commit (TxE) → checkpoint.

Recovery

After a crash, recovery scans the log. A transaction that never committed (missing/mismatched TxE) is simply skipped. A committed transaction is replayed — its blocks re-written to their final locations. This is redo logging redo logging The recovery style journaling uses: on reboot, scan the log and re-apply (replay, in order) every transaction that committed (has a matching TxB/TxE), writing its blocks to their final locations. Transactions not fully committed are skipped. Redundantly re-doing already-checkpointed writes is harmless. defined in ch. 42 — open in glossary ; because a crash during checkpointing just re-does a few already-done writes, redundant redo is harmless. Recovery is now O(log size), not O(disk size).

Batching and the circular log

Committing every update separately would re-write the same blocks (e.g. an inode bitmap touched by two file creates) over and over. So file systems batch: buffer many updates into one global transaction, committed together after a few seconds. And since the log is finite, it’s a circular log circular log The journal treated as a fixed-size ring reused over and over. Once a transaction is checkpointed, its log space is freed for reuse; a journal superblock records which transactions are not yet checkpointed. This bounds the log size (and thus recovery time) and prevents the log from filling up and stalling the FS. defined in ch. 42 — open in glossary — reused round and round. Once a transaction is checkpointed, its space is freed; a journal superblock records which transactions still need checkpointing:

This adds a fourth phase: journal write → commit → checkpoint → free.

42.3 (cont.) Metadata Journaling

Data journaling writes every data block twice (once to the log, once to its home) — roughly halving write bandwidth. Metadata journaling metadata journaling Ordered journaling: journal only metadata (inodes, bitmaps, directories), not user data. To avoid an inode pointing at garbage, the rule is 'write the pointed-to data block to its final location BEFORE committing the metadata that points to it.' Far less journal traffic than data journaling; the common choice (ext3 ordered mode, XFS, NTFS). defined in ch. 42 — open in glossary (ordered mode, the common choice) fixes this: it logs only metadata (inode, bitmaps, directories), never user data. The data block goes straight to its final location — but when? It must be written before the metadata is committed; otherwise the inode could be committed pointing at a block that never received its data (garbage). This is the core rule of crash consistency: write the pointed-to object before the object that points to it. So the protocols differ:

Tricky case: block reuse

Metadata journaling has a subtle hazard when a freed block is reused, which a revoke record revoke record A journal entry (ext3) that marks a block as NOT to be replayed during recovery. It solves the block-reuse hazard: if a directory block is logged, then that block is freed and reused as user data for a new file, replaying the old logged contents would clobber the new data. Recovery scans for revoke records first and skips revoked blocks. defined in ch. 42 — open in glossary solves:

42.4 Other Approaches

Journaling isn’t the only answer. Soft updates soft updates An alternative to journaling (Ganger & Patt): carefully ORDER all writes so the on-disk structures are never inconsistent — e.g. always write a data block before the inode that points to it. Avoids a journal, but needs intricate, file-system-specific knowledge of every structure, making it complex to implement. defined in ch. 42 — open in glossary carefully orders writes so the disk is never inconsistent; copy-on-write ( COW copy-on-write COW (from TENEX): to 'copy' a page, map it read-only into both address spaces; only when someone writes does a trap allocate a real private copy. Makes fork()+exec() affordable and shared libraries cheap. defined in ch. 23 — open in glossary , as in ZFS and the next chapter’s LFS) never overwrites in place, flipping a root pointer to swap in new structures atomically; and research approaches (backpointer-based, optimistic) push further still:

42.5 Summary

The crash-consistency problem — updating persistent structures atomically despite crashes — has no free solution. fsck repairs after the fact but is O(disk size) and far too slow. Journaling writes a note ahead of time and replays it, cutting recovery to O(log size); its ordered metadata-journaling flavor is the popular sweet spot, keeping metadata consistent at modest cost. Next, LFS takes the log idea to its logical extreme — making the entire file system one big log.