Write-Ahead Logging (WAL) is not merely a technique—it is the foundational protocol that enables all crash-consistent storage systems. From file systems to databases to distributed consensus algorithms, WAL provides the theoretical and practical machinery for durability and atomicity.\n\nThe principle appears deceptively simple: write a description of what you intend to do before you do it. But beneath this simplicity lies a carefully engineered protocol with precise ordering requirements, performance optimizations, and subtle correctness conditions. Understanding WAL deeply means understanding how computers can make guarantees about the future despite the uncertainty of crashes, power failures, and hardware errors.

The write-ahead logging protocol defines a precise sequence of operations that must be followed to ensure crash consistency. Let's examine each step in detail, understanding not just what is done but why each step is necessary.

Phase 1: Transaction Accumulation\n\nBefore any disk I/O occurs, the file system accumulates modification requests in memory. For a file append operation, this includes:\n\n- The new data blocks (in the page cache)\n- Modified inode (in the inode cache)\n- Modified bitmap blocks (in the buffer cache)\n\nThese modifications exist only in volatile memory. A crash at this point simply loses the operation—perfectly safe from a consistency perspective.\n\nPhase 2: Log Record Construction\n\nOnce a transaction is ready to commit (either triggered by fsync, a timer, or memory pressure), the file system constructs log records describing all modifications:

Phase 3: Log Write with Ordering\n\nThe log records are written to the journal with strict ordering constraints:\n\n1. Descriptor block first — Written and persisted before data blocks (some systems write together but flush descriptor first)\n2. Data blocks — Written to the journal area, may be issued in parallel\n3. Barrier — A write barrier ensures all previous writes complete before the commit\n4. Commit record — Written only after all other log blocks are persisted\n\nThe critical insight: the commit record must hit disk after everything it commits. If the commit record were written first, a crash could find a valid commit but missing or partially-written data.

Phase 4: Acknowledgment\n\nOnce the commit record is persisted (barrier completed, commit block on media), the transaction is officially committed. For operations that requested durability (via fsync), the file system can now return success to the application. At this point:\n\n- The transaction will be recovered on crash—guaranteed\n- The actual modifications may or may not be on disk yet\n- The application can rely on the data being durable\n\nPhase 5: Writeback (Background)\n\nAfter commit, the file system writes the actual modifications to their final on-disk locations. This can happen immediately or be deferred:\n\n- Data blocks written to their final locations\n- Metadata blocks (inodes, bitmaps) written to their final locations\n- These writes can be reordered and optimized for efficiency\n\nImportantly, these writeback operations need not complete for the transaction to be safe. They're already in the journal.

The correctness of WAL depends on precise ordering of writes. Modern storage systems aggressively reorder writes for performance, so file systems must explicitly enforce ordering. Let's examine the required constraints and how they're enforced.

Enforcement Mechanisms:\n\n1. Write Barriers (FUA and Flush)\n\nWrite barriers force visibility ordering:

2. Transaction Dependencies\n\nSome file systems allow concurrent transactions but track dependencies:\n\n- Transaction B modifies data written by Transaction A\n- B cannot commit until A commits\n- Dependency graph limits parallelism but ensures ordering\n\n3. Epoch-Based Ordering\n\nSome systems group transactions into epochs:\n\n- All transactions in epoch N must complete before epoch N+1 begins\n- Simplifies ordering: only need barriers between epochs\n- Allows parallelism within epoch\n\n4. Single-Threaded Journal Access\n\nSimplest approach: serialize all journal access\n\n- One thread handles all commits\n- Natural ordering through serialization\n- Can be a bottleneck for write-heavy workloads

The journal is a finite resource—typically a few hundred megabytes to a few gigabytes. Without a mechanism to reclaim space, it would quickly fill up and halt all file system operations. Checkpointing is the process that reclaims journal space by tracking which transactions have been fully written to their final locations.

The Checkpoint Invariant:\n\n> A transaction can be removed from the journal only after all its modifications have been written to their final on-disk locations.\n\nOnce this condition is met, the journal entries are redundant—the actual file system structures contain the data. The journal space can be reused.\n\nCheckpoint Record:\n\nThe checkpoint is itself recorded durably, typically in the journal superblock:

Checkpoint Triggers:\n\nFile systems checkpoint under several conditions:

Checkpoint Algorithm:\n\n\nCHECKPOINT_PROCEDURE():\n oldest_active = journal.tail_transaction\n \n for each txn from oldest_active forward:\n if txn.writeback_complete:\n // All blocks written to final locations\n journal.advance_tail(txn)\n free_journal_blocks(txn.log_blocks)\n else:\n // Cannot checkpoint past this transaction\n // May need to force writeback if journal is full\n if journal.space_remaining < threshold:\n force_writeback(txn)\n break\n \n update_journal_superblock(new_tail)\n issue_barrier() // Ensure superblock update is durable\n\n\nJournal Full Handling:\n\nIf the journal fills before transactions can be checkpointed, the file system must stall:\n\n1. Block all new transactions from starting\n2. Force writeback of oldest transactions' data\n3. Checkpoint completed transactions\n4. Resume normal operation\n\nThis stall is disruptive but necessary—there's no safe way to proceed without journal space. Proper journal sizing avoids this scenario under normal workloads.

When the system boots after a crash, the file system must recover to a consistent state before it can be mounted. The recovery algorithm scans the journal, identifies committed transactions that may not have been fully written back, and replays them.\n\nThis process is deterministic—given the same journal contents, recovery will always produce the same result. This determinism is essential for reliability.

Recovery Phases:

Key Recovery Properties:\n\nIdempotency: Replaying a transaction multiple times produces the same result as replaying once. This is essential because we don't know if a transaction was partially written back before the crash. Replaying is always safe.\n\nForward-only scanning: Recovery only scans forward from the checkpoint. We never need to undo work or scan backward—committed transactions are replayed, uncommitted transactions are ignored.\n\nBounded time: Recovery time depends on the number of transactions since last checkpoint, not on file system size. For a 5-second commit interval manager and typical workloads, this means tens to hundreds of transactions—seconds of recovery time regardless of file system size.

Committing each file system operation as a separate transaction would be catastrophically slow—each commit requires a flush and FUA write. Instead, modern journaling file systems batch multiple operations into compound transactions that commit together.

The Batching Window:\n\nThe file system maintains an "open" transaction that accumulates modifications over a time window (typically 5 seconds in ext4). All operations during this window become part of the same transaction:

Performance Impact:\n\nBatching dramatically improves throughput:

Early Commit Triggers:\n\nWhile batching defers commits, certain conditions force early commit:

Handling Dependencies Within a Batch:\n\nOperations within a batch may have dependencies:\n\n1. Create file F\n2. Write to file F\n3. Rename file F to G\n\nAll three are in the same transaction. On recovery, either all three happen or none. This is correct—the batch is atomic. But the file system must ensure the ordering of operations within the batch is preserved in the log, so replay produces the intended result.

Database systems distinguish between REDO logging and UNDO logging, and many use a combination called REDO-UNDO or ARIES (Algorithm for Recovery and Isolation Exploiting Semantics). File systems typically use simpler approaches. Understanding the distinction illuminates design choices.

Why File Systems Choose REDO:\n\nFile systems predominantly use REDO-only logging for several reasons:\n\n1. No application rollback: Unlike databases, file systems don't support "I changed my mind, undo this transaction." Transactions always complete.\n\n2. Simpler implementation: REDO-only avoids the complexity of reconstructing old values and handling partial undo.\n\n3. Metadata focus: Most file systems journal only metadata, not data. The metadata modifications are already in memory; logging them is straightforward.\n\n4. Batch commit model: The 5-second batching window means transactions are relatively short-lived. The overhead of buffering is acceptable.\n\nREDO-Only Constraint:\n\nREDO logging requires a steal/no-force buffer policy:\n- No-steal: Uncommitted data must not be written to final location (would require undo on crash)\n- No-force: Committed data need not be immediately written to final location (journal provides durability)\n\nThis is the standard approach in journaling file systems. Uncommitted modifications stay in memory; committed modifications are safe in the journal and can be lazily written back.

A crash can corrupt not just data but the journal itself. If the system was writing to the journal at crash time, the written blocks may be partially complete (torn writes). Modern journals use checksums to detect such corruption and ensure only valid transactions are replayed.

The Torn Write Problem:\n\nConsider a 4KB journal block being written when power fails:\n\n- First 2KB reaches the disk\n- Last 2KB does not\n- Result: Block contains half new data, half old (or garbage)\n\nIf this is a commit block, we might incorrectly conclude a transaction is complete. If it's a data block, we might replay corrupted data. Checksums provide defense.

Checksum Coverage:\n\nModern journals compute checksums over the entire transaction:\n\n1. Descriptor block — Includes all block tags and target addresses\n2. All data blocks — Every logged block is included\n3. Commit block — The commit itself (with checksum field zeroed during computation)\n\nThis creates an end-to-end integrity check. Any corruption—in any block of the transaction—will cause validation to fail.\n\nChecksum Algorithm Selection:

We've explored the detailed mechanics of write-ahead logging. Let's consolidate the key insights:

What's Next:\n\nWith the WAL mechanism understood, we'll now explore metadata journaling—the most common journaling mode that protects file system structure while allowing data to be written directly. This mode offers the best balance of performance and consistency for most workloads.