Write-Ahead Log (WAL)

The WAL is an append-only file, meaning new log records are written sequentially to the end. This operation is designed to be atomic: the system ensures the entire log record is durably written to stable storage (e.g., disk) or not at all. This prevents torn writes where only part of a log record is persisted.

• Sequential I/O: Appending is much faster than random writes, optimizing for disk performance.
• Crash Safety: The atomicity guarantee is the foundation for recovery. If a crash occurs during a write, the system can detect the incomplete record on restart.

This mechanism controls when log writes are flushed from the OS buffer cache to the physical storage medium. The WAL protocol mandates that a transaction's commit record must be forced to disk before the commit operation returns as successful to the client.

• Synchronous Commit: Guarantees durability (the 'D' in ACID) but adds latency due to disk I/O.
• Group Commit: Batches multiple commit records into a single fsync operation to amortize this cost.
• Asynchronous/WAL-off Modes: Trade durability for performance by delaying or skipping forced writes, used when crash recovery to the latest committed transaction is not required.

A monotonically increasing identifier assigned to every record written to the WAL. The LSN provides a total order for all changes in the system and is the cornerstone of recovery and replication.

• Checkpointing: Periodically, the system records a checkpoint LSN, indicating that all data changes up to that point have been flushed from memory to the main data files. This limits recovery time.
• Page LSN: Each page in the main data store (e.g., a B-tree page) stores the LSN of the latest log record that modified it. During recovery, this is compared to the WAL to determine if a page needs to be redone.
• Replication: In systems like PostgreSQL, the LSN is used to track replication progress to standby servers.

The process of reapplying changes recorded in the WAL to the main data files after a crash. During recovery, the system starts from the last checkpoint and reads the WAL forward, replaying every action.

• Idempotent Operations: Redo operations must be safe to apply multiple times. If a page was partially updated before the crash, re-applying the full log record will bring it to the correct state.
• Physical & Logical Logging:
  • Physical Logging: Records the exact byte changes to a specific page (e.g., 'set bytes 100-120 to X'). Fast and deterministic for redo.
  • Logical Logging: Records high-level operations (e.g., 'INSERT INTO t VALUES (1)'). More compact but may require more complex redo logic.

The mechanism for rolling back uncommitted transactions, either due to an explicit ROLLBACK or during recovery from a crash. The WAL contains compensation log records (CLRs) that describe how to reverse the effects of a previous operation.

• Write-Ahead Logging Rule: The undo information (CLR) for any data modification must be written to the log before the modified data page itself is allowed to be written to disk. This ensures rollback is always possible.
• Crash During Rollback: If the system crashes during undo, the CLRs in the log allow the rollback process to continue upon restart.

A periodic operation that limits recovery time by creating a synchronization point between the WAL and the main data files. A checkpoint records a consistent snapshot of the system state to disk.

• Fuzzy Checkpoint: Does not require all dirty pages to be flushed immediately. Instead, it records the checkpoint LSN and a list of active transactions. Recovery starts from this LSN and reapplies all changes from transactions that were active at the time of the checkpoint.
• Benefits: Dramatically reduces the amount of WAL that must be replayed during recovery, minimizing restart time.
• Trade-off: More frequent checkpoints increase runtime I/O but improve worst-case recovery time.

An architectural pattern where the state of an application is derived from an immutable, append-only sequence of events, which serves as the system's primary source of truth. This is a higher-level application of the WAL principle.

• Core Idea: Instead of storing the current state, store the history of state-changing events (e.g., UserCreated, OrderPlaced).
• State Reconstruction: The current state is rebuilt by replaying the event log from the beginning or from a snapshot.
• Relationship to WAL: Event Sourcing uses a WAL-like structure (the event store) as its foundational persistence mechanism, guaranteeing durability and providing a complete audit trail.

A fundamental fault-tolerance technique where a deterministic service is replicated across multiple nodes. Consistency is achieved by ensuring all replicas start from the same state and process the same sequence of commands in the same order.

• Role of the Log: A replicated log (often implemented via a consensus algorithm like Raft) is used to agree on the total order of commands. This log is the WAL for the entire distributed system.
• Determinism Required: For this to work, the service's state machine must be deterministic; given the same initial state and command sequence, all replicas will produce identical states.
• Primary Use: The backbone of highly available distributed systems like etcd, Consul, and distributed databases.

A communication primitive that guarantees all correct processes in a distributed system deliver the same set of messages in the same total order. It is the communication layer that enables a replicated WAL.

• Total Order Broadcast: Another name for the same concept. It ensures message order is consistent across all receivers.
• Foundation for Consensus: Algorithms like Paxos and Raft implement Atomic Broadcast to maintain a consistent, replicated log.
• Critical Property: This guarantee is stronger than reliable broadcast; it solves the problem of agreeing on the sequence of entries in a distributed WAL.

The process of periodically persisting a snapshot of the current in-memory state to stable storage. It works in tandem with a WAL to optimize recovery time and manage log size.

• Recovery Optimization: After a crash, the system loads the latest checkpoint and then only replays WAL entries created after that checkpoint was taken.
• Log Truncation: Once a checkpoint is safely persisted, the WAL entries preceding it can be safely deleted or archived.
• Fuzzy vs. Consistent Checkpoints: A consistent checkpoint (or snapshot) captures a state that corresponds to a precise point in the WAL, often requiring a brief pause. A fuzzy checkpoint can be taken asynchronously but requires the WAL to replay or undo operations to reach a consistent state.

A distributed atomic commitment protocol that coordinates multiple participants (e.g., databases, services) to ensure a transaction either commits on all nodes or aborts on all nodes. It uses a write-ahead log for its own durability.

• Phases: 1) Prepare: The coordinator asks all participants if they can commit. Each participant writes a prepare record to its local WAL and locks resources. 2) Commit/Abort: If all vote yes, the coordinator instructs a commit; otherwise, it instructs an abort.
• WAL's Role: Each participant logs its prepare, commit, or abort decision. This ensures the participant can recover and finalize the transaction after a crash, preserving the protocol's guarantees.
• Blocking Nature: A key drawback is that it is a blocking protocol; if the coordinator fails, participants may remain in an uncertain state holding locks.

Two specific logging techniques used within database transaction systems, often implemented using a WAL, to guarantee Atomicity and Durability (the 'A' and 'D' in ACID).

• Redo Logging: Records the new value of a data item after a change. During recovery, all committed transactions are redone from the log to ensure durability, even if the data pages were not flushed to disk.
• Undo Logging: Records the old value of a data item before a change. During recovery or a rollback, uncommitted transactions are undone using the log to ensure atomicity.
• Modern Systems: Most systems use a combination called ARIES (Algorithm for Recovery and Isolation Exploiting Semantics), which employs a WAL with both redo and undo capabilities for highly efficient crash recovery.