Journaling and Crash Consistency

A file-system update — creating a file, appending data, truncating — typically requires modifying several on-disk structures that must remain mutually consistent: an inode's size and block pointers, a free-space bitmap or extent tree, a directory entry, and the data blocks themselves. These writes physically land on disk one at a time (or a few at a time, subject to hardware write ordering), never all atomically. If the machine loses power, or the OS crashes, between writes, the disk is left in a state that corresponds to no single point in the intended sequence of operations — some updates happened, others did not. This is the crash-consistency problem: after an arbitrary crash, restore the on-disk image to a state that is consistent, meaning it satisfies the file system's own invariants (every allocated block is referenced by exactly one live inode, every bitmap bit matches actual allocation, every directory entry points to a valid inode, and so on). Two broad strategies solve this. Write-ahead logging (journaling) preserves in-place updates but adds a redundant, sequential log recording the intent of a transaction before it is applied; after a crash, the log is consulted to either finish or fully discard incomplete transactions, restoring a state equivalent to "transaction happened" or "transaction never happened" — this atomicity property is what database theory calls the A in ACID, applied to file-system metadata. Copy-on-write (CoW) instead never overwrites live, referenced data: every update writes new blocks and a new metadata tree pointing to them, culminating in a single atomic write of a root pointer (a superblock update) that switches the entire file system from the old, still-fully-intact tree to the new one. Both approaches guarantee that a crash can only ever be observed at a transaction boundary — never mid-transaction — which is precisely the consistency guarantee `fsck` had to reconstruct at great cost by inspecting every structure on disk.

Baseline: `fsck` (file system check). Before journaling, systems like the classic Unix File System (FFS) relied on `fsck` to run at boot after an unclean shutdown. It performs a global consistency pass: ``` FSCK(): scan all inodes; build a table of which blocks each live inode claims scan the free-space bitmap for each block: if claimed by >1 inode: flag cross-link, allocate a copy to one, or truncate if claimed by an inode but marked free in bitmap: fix bitmap if marked allocated in bitmap but claimed by no inode: mark free (leaked block) for each directory: verify every entry references a valid, allocated inode verify link counts on inodes match number of directory entries referencing them for each inode with link count 0 but still referenced: fix reference, or free it write corrected bitmaps / inodes / directories back to disk ``` This works — it can detect and repair every class of pointer, count, and allocation inconsistency — but it must touch metadata proportional to the size of the entire volume, not the size of the interrupted update. On a multi-terabyte disk this is minutes to hours, an unacceptable outage, and it cannot recover data that was mid-write, only restore metadata consistency.

Write-ahead journaling. The fix is to record, before touching the real (in-place) structures, a compact description of the transaction in a dedicated log region (the journal), and only mark the transaction as "committed" once that description is durably on disk. Journals are typically implemented as a circular buffer of fixed size at a known disk location. A generic journaling protocol proceeds in phases: ``` BEGIN_TRANSACTION(TID): allocate a transaction record in the journal

# Journal write phase WRITE_JOURNAL(TID, blocks): write a transaction-begin record (TID, list of target block numbers) write the contents of each modified block into the journal (or, in ordered mode, only metadata blocks — see below) write a transaction-commit record (TID), tagged with a checksum force all of the above to disk with a barrier / flush (commit record must be the LAST thing to become durable)

# Checkpoint phase — only after commit record is durably on disk CHECKPOINT(TID): write each journaled block to its real, in-place location on disk once all writes succeed, mark the transaction as "free" in the journal (its journal space may now be reused) RECOVER(): # run at reboot, replaces fsck's full scan scan the journal from its oldest live position for each transaction record found: if a valid commit record exists for it (checksum matches): replay: re-write its logged blocks to their in-place locations else: discard: skip it entirely, as if it never began resume normal operation ``` The crucial correctness property is the ordering constraint: the commit record must reach stable storage strictly after all the transaction's logged data, and in-place ("checkpoint") writes must happen strictly after the commit record is durable. This ordering, not the journal's mere existence, is what makes recovery well-defined; file systems enforce it with write barriers or explicit cache-flush commands (since disks and SSDs may reorder or buffer writes internally).

Metadata (ordered) journaling vs. full data journaling. Journaling every byte of every write (full data journaling, `journal` mode in ext3/ext4) gives the strongest guarantee — both data and metadata are transactionally consistent — but every block is written twice: once to the journal, once at checkpoint, roughly doubling write traffic and halving effective bandwidth for write-heavy workloads.

Ordered journaling (`ordered` mode, ext3/ext4's default) journals only metadata (inode updates, bitmap changes, directory entries), but adds one ordering rule: all data blocks belonging to a transaction must be written to their final location before the corresponding metadata's commit record is written. This avoids double-writing data while still preventing the classic "garbage data" bug: without this rule, a crash after the metadata commits but before data is written could expose an inode pointing at a block full of previously-deleted, unrelated data (a security and correctness hazard) or, in the case of appends, a block full of uninitialized disk content. Ordered mode guarantees that if metadata says "this block belongs to this file," the block's content is at least the new content, or, if the transaction never committed, the old content — never leftover garbage from something else.

Writeback journaling (the third, weakest mode) journals only metadata without ordering it after data. It is fastest but permits stale/garbage data to appear after crash recovery, since metadata can commit and be replayed before the corresponding data write ever reaches disk. It preserves metadata consistency (no more `fsck` needed for structure) but not data consistency.

Copy-on-write. CoW file systems (ZFS, Btrfs, WAFL) take a structurally different approach: they never modify a live block in place. An update to a file allocates new blocks for the changed data, then allocates new copies of every metadata block on the path from that data block up to the root (the classic technique is a copy-on-write Merkle-like tree, sometimes literally a B-tree of block checksums). The very last step is a single atomic write of the filesystem's root pointer (in a superblock or uberblock) to point at the new tree root instead of the old one. ``` CoW_UPDATE(file, new_data_block): new_data = allocate_block(); write(new_data, new_data_block) leaf = copy_of(inode_block_pointing_to(old_data_block)) leaf.pointer = new_data new_leaf = allocate_block(); write(new_leaf, leaf)

# propagate the copy upward to the root for each ancestor level up to the root: parent_copy = copy_of(parent) parent_copy.pointer_to_child =

`fsck` complexity. A full scan must read every inode, every bitmap block, and every directory to cross-validate structures, so its time is $\Theta(N)$ where $N$ is the number of blocks/inodes on the volume, independent of how much was actually being modified at crash time. Space is $O(N)$ in the worst case (in-memory tables mapping blocks to owning inodes for cross-link detection), though streaming implementations reduce this with multiple passes. This is correct — it is a full re-derivation of every invariant from scratch — but asymptotically wasteful relative to the size of the actual interrupted operation, which is typically $O(1)$ to $O(k)$ blocks for a small transaction.

Journaling recovery complexity. Recovery scans only the journal region, of fixed, administrator-configured size $J$ (typically tens to hundreds of MB), replaying at most the transactions still resident in it: time is $O(J)$, and in practice $O(\text{number of uncommitted/uncheckpointed transactions})$, since old, checkpointed transactions are pruned from the journal continuously during normal operation. Because $J \ll N$ for any real volume, recovery time becomes independent of total disk size — this is the entire point, and it is what makes journaling recovery a constant-ish, sub-second-to-seconds operation rather than an hours-long scan.

Correctness argument for journaling. Define a transaction $T$ as committed if and only if its commit record, with a valid checksum covering all its logged blocks, is present in the journal on disk. The protocol enforces two ordering invariants via write barriers: 1. (Log-before-commit) All of $T$'s data/metadata blocks are durable in the journal before $T$'s commit record is written. 2. (Commit-before-checkpoint) $T$'s commit record is durable before any of $T$'s blocks are written to their in-place locations. Claim: after recovery, the on-disk state is exactly as if either all of $T$'s writes happened atomically, or none did — for every transaction $T$, regardless of when the crash occurred. Proof sketch. Suppose crash occurs before $T$'s commit record is durable. By invariant 1's contrapositive, no in-place checkpoint write for $T$ could have happened yet, because checkpoint writes only start after commit — so the disk still shows the pre-$T$ state for every block $T$ would have touched; recovery finds no valid commit record (checksum fails or record absent) and correctly discards $T$, matching the pre-state. Now suppose the commit record is durable at crash time. Then, by invariant 1, all of $T$'s logged block images are already safely in the journal. Recovery finds the valid commit record and replays every logged block to its in-place location; whether zero, some, or all of the "real" checkpoint writes had already succeeded before the crash is irrelevant, because replay is idempotent — rewriting a block that already holds the correct value is a no-op in effect. So after replay, every block $T$ touches holds exactly $T$'s intended final value, i.e., the post-$T$ state. Since this holds for every transaction independently, and transactions are applied to the journal (and hence recovered) in log order, the disk after recovery equals the state reachable by applying some prefix of committed transactions in order — precisely the "all-or-nothing, in order" guarantee required. $\blacksquare$ The checksum on the commit record is what makes this robust to torn writes — a crash mid-write to the commit record itself must not be mistaken for a valid commit; without a checksum, a partially written commit record could be misinterpreted as valid, breaking invariant 1's guarantee at the boundary.

Ordered-mode data-safety argument. Ordered mode adds: data blocks for $T$ are written in place before $T$'s commit record is durable. Combined with the commit-based atomicity above, this guarantees that whenever metadata claims a block belongs to file $f$ with certain content, that content is already correctly in place before the claim could ever become visible via recovery — ruling out the garbage-data exposure that writeback mode permits. It costs one additional ordering constraint (data-before-commit) but no extra journal writes for data, which is why it dominates in practice: near the safety of full data journaling, near the speed of writeback.

CoW correctness argument. The old tree, rooted at pointer $R_{\text{old}}$, is never mutated — every write in an update targets freshly allocated blocks. The new tree, rooted at a freshly written block, is fully built and durable before the superblock write that installs $R_{\text{new}}$. Because a single-sector (or single-block, protected by its own checksum) superblock write is atomic with respect to crashes on essentially all block devices, at any crash instant the visible root pointer is either $R_{\text{old}}$ (old tree, untouched, was already consistent) or $R_{\text{new}}$ (new tree, fully built before being pointed to). There is no third possibility and no replay step — the invariant "the current root always points to a fully-formed, self-consistent tree" is maintained by construction rather than repaired after the fact. This makes CoW recovery $O(1)$ in the size of the interrupted update (just re-read the current superblock), though real systems still perform a small bounded amount of work to reclaim space from an aborted, never-linked-in tree.

Tradeoffs, stated plainly.

Consider appending 4 KB of new data to an existing file `report.txt`, which requires three writes: (1) a new data block D, (2) an updated inode I (new size, new block pointer), and (3) an updated free-space bitmap B (mark D's block as allocated). Assume ext4-style ordered journaling with a 4-block journal region and this update assigned transaction id `T7`.

Notice the key ordered-mode discipline at Step 1: data block D is written to its real location before the metadata transaction even begins in the journal — never the other way around. If the crash had happened between a metadata-first write and a later data write (which ordered mode forbids by construction), the inode could claim block D belongs to the file while D still held stale content from whatever previously occupied that block — the garbage-data hazard that ordered mode is specifically designed to prevent. Also notice that at Steps 1–2, a crash leaves unreferenced allocated-looking data (D was written, but no metadata points to it yet) — this is not a violation of consistency, merely a small, harmless leak that a future write can silently reclaim once the bitmap is regenerated or a background scrubber runs; it is never visible as corrupted file content, because no directory entry or inode ever pointed at it.

Every mainstream production file system relies on one of these two families. ext3/ext4 (Linux's long-standing defaults) use ordered-mode write-ahead journaling via the JBD2 journaling layer, directly implementing the transaction lifecycle described above. NTFS uses a write-ahead log (`$LogFile`) modeled closely on database transaction logging, journaling metadata operations for Windows. XFS, built for large-scale servers, uses write-ahead logging with fine-grained, per-structure transactions to keep recovery fast even on very large volumes. ZFS and Btrfs use copy-on-write trees with checksummed blocks, enabling not just crash consistency but nearly free, consistent snapshots — because an old tree root, by construction, is a perfectly valid, frozen, consistent snapshot of the file system at that instant. F2FS, designed for flash storage, is explicitly log-structured to match flash's own append-friendly, erase-before-write characteristics. Database systems (PostgreSQL's WAL, MySQL's InnoDB redo log, SQLite's WAL mode) apply the identical write-ahead-logging principle one layer up the stack, to transactions over rows and pages rather than blocks and inodes — the same proof structure (log-before-commit, commit-before-checkpoint, idempotent replay) underlies both. Cloud block-storage and distributed file systems layer additional replication atop these single-machine techniques, which is exactly where the concerns of RAID and Redundant Storage pick up: journaling and CoW answer "how do we survive a crash on one device," while RAID and replication answer "how do we survive losing the device entirely."

Ask the tutor: How would ordered-mode journaling behave differently if the underlying disk silently ignores write-barrier (flush) commands?