Write-Ahead Logging (WAL)

Imagine a database processing thousands of financial transactions per second. Power fails mid-transaction. When the system restarts, how does it know which transactions completed, which partially executed, and which never started? How does it restore consistency without losing committed data or keeping uncommitted changes?

The answer lies in a deceptively simple principle that underpins every production database system: Write-Ahead Logging (WAL). This protocol—sometimes called journaling in file systems—is the fundamental mechanism that transforms databases from fragile data stores into resilient, recoverable systems.

The WAL rule is not merely an optimization or a convenience. It is an absolute requirement for crash recovery. Without it, durability guarantees collapse, and databases cannot reliably recover from failures.

Before we can appreciate the WAL rule, we must understand the fundamental problem it solves. Consider what happens during normal database operation:

Two storage locations exist:

1. Main Memory (Volatile) — Fast access, but contents are lost on power failure
2. Disk Storage (Non-Volatile) — Slow access, but contents survive power failures

Databases cache frequently accessed data pages in main memory (the buffer pool) for performance. When transactions modify data, they first modify the in-memory copies. Eventually, these modified pages must be written back to disk—but exactly when this happens creates a critical problem.

This creates an apparently impossible situation. We want:

1. High performance — Minimize disk I/O by batching and deferring writes
2. Durability — Committed transactions must survive crashes
3. Atomicity — Uncommitted transactions must be completely undone after crashes

These requirements seem contradictory. If we don't immediately write committed changes to disk, how do we guarantee they survive crashes? If we do write them immediately, how do we maintain performance?

The WAL protocol resolves this tension through an elegant insight: What if we don't need to write the data immediately—only a record of what changed?

The Write-Ahead Logging rule is stated with precision:

The WAL Rule: Before any in-place update to a data page is written to stable storage (disk), the corresponding log record must first be written to stable storage.

In simpler terms: Log first, then data.

This rule is sometimes expressed as two separate guarantees:

The combination of these rules provides a complete recovery guarantee:

• If a transaction commits: All its changes are logged to stable storage. Even if the data pages were never written to disk, recovery can reconstruct them.

• If a transaction fails to commit: The undo information is on stable storage. Recovery can roll back any changes that may have reached disk prematurely.

Notice the elegance: We never need to force data pages to disk at any particular time. We only need to ensure the log maintains a complete history of all changes. Data pages can be written lazily, in whatever order is convenient for performance—because the log can always reconstruct them.

The term "write-ahead" is not arbitrary—it describes a strict ordering requirement. Let's understand why this order is critical by examining what happens if we violate it.

Scenario: Violating the WAL Rule

Consider a transaction T1 that updates a bank account balance from $1000 to $500:

T1: UPDATE accounts SET balance = 500 WHERE id = 'A001';

Without WAL, the sequence might be:

1. T1 modifies the data page in memory (balance → $500)
2. The buffer manager writes the modified page to disk
3. System crashes
4. T1's log record is never written

After restart, the database sees balance = $500 on disk. But there's no record of T1—no way to know if T1 committed or not. If T1 actually never committed before the crash, we now have:

• $500 deducted without a corresponding credit anywhere
• No way to recover the original $1000 balance
• Database is permanently corrupted

Now consider the correct WAL-compliant sequence:

1. T1 modifies the data page in memory (balance → $500)
2. Before the data page is written to disk, the log record is written:
   • <T1, accounts.A001.balance, 1000, 500> (transaction, item, old value, new value)
3. Log record reaches stable storage ✓
4. Data page can now be written to disk (whenever convenient)
5. System crashes (at any point after step 3)

After restart:

• If T1 committed before crash: The commit record is in the log. Recovery can redo the update if the data page didn't make it to disk.
• If T1 did not commit: The log shows an incomplete transaction. Recovery can undo the update if the data page did make it to disk.

In both cases, the database returns to a consistent state. The key is that the log record—containing both old and new values—reached stable storage before any data modification could reach disk.

For the WAL rule to support complete recovery, log records must contain sufficient information for both undo and redo operations. A typical log record structure includes:

Essential Fields:

Understanding the Before and After Images:

The before-image (also called undo information) and after-image (also called redo information) are the key to recovery:

• Before-Image: The value that existed before this modification. If we need to undo this change (because the transaction didn't commit), we restore this value.

• After-Image: The value after this modification. If we need to redo this change (because the transaction committed but the data didn't reach disk), we apply this value.

Some systems use physical logging (recording actual byte changes), while others use logical logging (recording the operation itself, like 'increment counter by 5'). Modern systems often use physiological logging—physical to the page, logical within the page—balancing recovery complexity with logging efficiency.

The WAL rule tells us that log records must be written before data pages. But it doesn't tell us when data pages should be written. This leads to two policy decisions that significantly impact performance:

Question 1: Force Policy (at commit time)

When a transaction commits, do we force all its modified pages to disk?

• FORCE: All dirty pages modified by committing transaction are written to disk immediately
• NO-FORCE: Dirty pages can remain in memory after commit; they'll be written later

Question 2: Steal Policy (before commit)

Can a transaction's modified pages be written to disk before the transaction commits?

• STEAL: Buffer manager can write uncommitted pages to disk (to free buffer space)
• NO-STEAL: Uncommitted pages must remain in memory until commit

Why STEAL/NO-FORCE Dominates:

The STEAL/NO-FORCE combination provides the best runtime performance:

1. NO-FORCE means commits are fast — A transaction commits by writing only its log records (sequential I/O), not its data pages (random I/O). This can be 100x faster.

2. STEAL means buffer management is flexible — The buffer manager can evict any page when it needs space. It doesn't have to keep uncommitted pages pinned in memory, avoiding out-of-memory situations.

The cost is more complex recovery—we need both undo and redo capabilities. But since crashes are rare and performance matters constantly, this trade-off is universally preferred in production systems.

Implementing the WAL rule correctly requires careful engineering. Several subtle issues can undermine the guarantee:

1. Page Tearing

Most file systems write in units smaller than database pages (often 4KB file system blocks vs 8KB or 16KB database pages). If power fails mid-write, you might have half an old page and half a new page—a torn page.

Solutions:

• Checksums on every page to detect torn pages
• Double-write buffer (InnoDB) — write pages to a safe buffer first
• Full-page images in log (PostgreSQL) — log entire page on first modification after checkpoint

2. Ensuring Log Durability

Writing to the OS file system doesn't guarantee data reaches disk. The OS may buffer writes in its own cache. To truly satisfy WAL:

• Use fsync() or equivalent to force log to disk
• Or use battery-backed write caches that guarantee durability
• Or use direct I/O to bypass OS buffering

3. Log Buffer Management

For performance, databases buffer log records in memory before flushing to disk:

• Log records accumulate in a log buffer
• Flush the buffer when: transaction commits, buffer fills, periodic timer fires
• Commit request blocks until the flush including its commit record completes
• Multiple transactions can share a single log flush (group commit)

Every major database implements WAL, though with variations in naming and implementation details:

PostgreSQL — Write-Ahead Log (WAL)

PostgreSQL coined the term 'WAL' and implements a sophisticated version:

• Logs stored in the pg_wal directory (formerly pg_xlog)
• 16MB segment files by default
• Full-page writes after checkpoint to handle torn pages
• WAL used for both crash recovery and streaming replication

MySQL/InnoDB — Redo Log

InnoDB uses a circular redo log:

• Fixed-size redo log files (configurable)
• Checkpointing moves 'oldest LSN' forward to allow log reuse
• Double-write buffer to handle torn pages

Oracle — Redo Log

Oracle uses groups of redo log files:

• Multiple redo log groups for availability
• Log switches cycle between groups
• Archived logs enable point-in-time recovery

Beyond Databases:

The WAL principle extends far beyond traditional databases:

• File systems (ext4, NTFS) use journaling—WAL for metadata changes
• Key-value stores (RocksDB, LevelDB) write to a WAL before memtables
• Message queues (Kafka) are essentially a distributed commit log
• Versioned storage (Git) maintains a transaction log of all changes

Once you understand WAL, you see it everywhere—it's the universal pattern for reliable persistent state.

We've covered the foundational protocol that makes database recovery possible. Let's consolidate the key concepts:

What's Next:

Now that we understand the WAL rule as a protocol, the next page explores why logging must happen before data writes—examining the causality and timing constraints that make 'write-ahead' the only viable ordering for crash recovery.