Write-Ahead Log (WAL)

The WAL is the primary mechanism for implementing the Atomicity and Durability guarantees in ACID-compliant database transactions. Atomicity is achieved by ensuring all operations of a transaction are logged; if the transaction aborts, the log contains the information needed to roll back. Durability is guaranteed because a transaction is only considered committed once its log records are flushed to persistent storage, surviving any subsequent system crash. This makes the WAL non-negotiable for financial systems and any application requiring strict data integrity.

A WAL is an append-only, sequentially-written file. All data modifications (inserts, updates, deletes) are written as log records to the end of the file in the order they occur. This pattern is critical for performance because:

• Sequential I/O is orders of magnitude faster than random I/O on mechanical and solid-state drives.
• Append-only simplifies crash recovery, as the system only needs to read the log forward from a known checkpoint.
• It provides a single, authoritative timeline of all changes, which is also foundational for replication (as used in Raft consensus) and change data capture.

The WAL enables deterministic crash recovery via redo and undo processing. After a crash, the database replays the log:

• Redo (Forward Recovery): Re-applies all committed transactions found in the log to the main data files, ensuring durability. This recovers work that was logged but not yet written to the primary data structures.
• Undo (Rollback Recovery): Rolls back any uncommitted transactions by applying compensating log records, ensuring atomicity. This process restores the database to a consistent state, as if the incomplete transaction never happened. The log must contain enough before-images and after-images of data to perform both operations.

Checkpointing is a periodic operation that synchronizes the in-memory state with the persistent data files and truncates the WAL. A checkpoint records a known-good, consistent point in the log stream. This is essential because:

• It limits recovery time. On restart, the system only needs to process log records from the last checkpoint forward, not the entire history.
• It allows old log segments to be safely archived or deleted, controlling disk space usage.
• It often involves flushing dirty pages from the buffer pool to disk. Checkpoints can be fuzzy (allow concurrent transactions) or sharp (require a quiescent state), trading off between performance and implementation complexity.

The fundamental Write-Ahead Rule states: The log record for a data modification must be flushed to persistent storage before the corresponding dirty data page is written to the main database file. This rule is the linchpin of the protocol. Violating it would allow a scenario where a data page is written to disk but its originating transaction log is lost in a crash, making the change permanent but un-recoverable and potentially breaking atomicity. The rule ensures the log always contains a complete record to reconstruct or roll back any change that may have reached the durable storage.

The WAL principle is central to modern storage engines like the Log-Structured Merge-Tree (LSM-Tree). In an LSM-Tree:

• The in-memory component (memtable) acts as the primary write buffer.
• A separate WAL file (often called a commit log) is written to disk for every write before it is acknowledged to the client, providing durability for the memtable's contents.
• If the system crashes, the memtable is rebuilt on startup by replaying the WAL. This decouples fast, sequential logging from the eventual compaction and sorting processes of the LSM-Tree. The same pattern is used in streaming systems like Apache Kafka, where the partition log is itself a form of WAL.

A high-performance storage engine data structure that optimizes write-heavy workloads, commonly used with a WAL for durability. It batches writes in a memory-resident component (memtable) before flushing them to sorted, immutable files on disk (SSTables).

• Key Mechanism: All writes are first appended to the WAL for crash recovery, then inserted into the memtable.
• Read/Write Trade-off: Provides extremely fast writes by sequential logging, while reads may require checking multiple SSTable levels.
• Use Case: The foundational storage engine for databases like Apache Cassandra, RocksDB, and Google's LevelDB, where the WAL guarantees durability of the memtable's contents.

A database isolation technique that allows multiple transactions to read and write concurrently without blocking, often implemented using a WAL to record version changes.

• How it Works with WAL: When a row is updated, the WAL records the new version. The database maintains multiple timestamped versions of data items, allowing readers to see a consistent snapshot without locking.
• Benefit: Enables high-throughput, non-blocking reads in systems like PostgreSQL and MySQL (InnoDB). The WAL provides the durable record of each version's creation.
• Garbage Collection: Old versions referenced in the WAL must be periodically cleaned up (VACUUM in PostgreSQL) to reclaim space.

A protocol for managing a replicated log to ensure fault tolerance in distributed systems. It is a direct implementation of a distributed, consensus-backed WAL.

• Core Concept: A leader node appends commands to its log, which are then replicated to follower nodes. Once a majority acknowledges, the entry is committed and applied to the state machine.
• Role of WAL: Each node's log is its local WAL. The Raft protocol ensures all nodes' logs are consistent, making the cluster's shared WAL fault-tolerant.
• Primary Use: The foundational consensus mechanism for distributed systems like etcd, Consul, and TiKV, providing a reliable replicated state machine.

A storage optimization technique that contrasts with the WAL's write-through philosophy. Modifications are written only to the cache initially, with updates to the backing store deferred until eviction.

• Performance vs. Durability: Offers superior write performance but risks data loss if the cache fails before the deferred write occurs. A WAL prioritizes durability over raw write speed.
• Hybrid Approach: High-performance databases often use a write-back cache in front of a WAL-backed persistent store. The cache absorbs writes, which are asynchronously flushed to the durable log.
• Example: CPU caches and many file system page caches operate in write-back mode, requiring explicit flush commands (e.g., fsync) for durability.

The process of periodically creating a stable, condensed snapshot of the current system state, which truncates the WAL and accelerates recovery.

• Purpose: Without checkpoints, system recovery would require replaying the entire WAL from the beginning, which could be prohibitively long. A checkpoint provides a recent starting point.
• Mechanism: The system flushes all dirty pages from memory to the main data files and records this moment in the WAL. Log entries prior to the checkpoint can be safely archived or deleted.
• Application: Critical for long-running agentic systems to bound recovery time. Used in databases (PostgreSQL CHECKPOINT), stream processors (Apache Flink savepoints), and machine learning training frameworks.

The set of properties that guarantee reliable processing of database transactions. The WAL is the primary engineering mechanism for ensuring the Durability and Atomicity guarantees.

• Durability (D): Once a transaction is committed, it persists even after a system crash. The WAL ensures this by forcing log records to stable storage before signaling commit success.
• Atomicity (A): A transaction is all-or-nothing. The WAL records all of a transaction's modifications; if the transaction aborts or crashes mid-way, the log contains the information needed to roll back the partial changes during recovery.
• Foundation: The WAL enables the A and D in ACID, which are prerequisites for building systems with strong consistency (C) and isolation (I) models.