Write-Ahead Logging (WAL)

WAL provides the Durability guarantee in the ACID transaction model. By forcing log records to stable storage (e.g., disk) before a transaction commits, it ensures that committed transactions survive permanent storage media failures. This is achieved through the Force Log at Commit rule, where the log records for a transaction's updates must be on non-volatile storage before the transaction's commit record is written. This makes recovery after a crash deterministic and complete.

WAL enables Atomicity (the 'A' in ACID) by allowing the database to recover to a consistent state after a system crash. During recovery, the database replays the log:

• Redo (Forward Recovery): Re-applies all updates from committed transactions that may not have been written to the main data files before the crash.
• Undo (Backward Recovery): Rolls back updates from transactions that were active but not committed at the time of the crash. This two-phase process ensures the database reflects only the results of committed transactions.

A checkpoint is a periodic operation that synchronizes the in-memory database state with the data files and marks a point in the log from which recovery can start. This prevents recovery from having to process the entire log history. Key aspects include:

• Fuzzy Checkpoints: Allow normal transaction processing to continue during the checkpoint, improving concurrency.
• Recovery Start Point: After a crash, recovery begins at the most recent checkpoint, significantly reducing restart time.
• Write Amplification Reduction: By batching writes from the log to the main data files, checkpoints reduce random I/O.

WAL enables high-performance transaction processing through specific buffer management policies:

• STEAL Policy: Allows the buffer manager to write dirty pages (modified by uncommitted transactions) to disk before commit. This is possible because the log contains the undo information needed for rollback.
• NO-FORCE Policy: Does not require dirty pages to be written to disk at commit time. The durability guarantee is satisfied by the log, not the data pages. Together, STEAL/NO-FORCE minimizes I/O latency for committing transactions and allows for more efficient buffer pool management.

A Log Sequence Number is a monotonically increasing identifier assigned to every log record. LSNs are crucial for:

• Ordering: Establishing a total order of all operations in the system.
• Page LSNs: Every database page stores the LSN of the latest log record that describes a modification to that page. During recovery, this prevents redundant redo operations.
• Recovery Tracking: The recovery process uses LSNs to identify the exact point (the Last Checkpoint LSN) to start processing and to determine which transactions require undo.

The Aries recovery algorithm, used by systems like IBM DB2 and influencing many others, employs physiological logging within the WAL framework. Its key features are:

• Logging Granularity: Records logical operations (e.g., 'insert into slot X of page Y') rather than physical byte changes or full logical statements. This balances log volume with redo/undo efficiency.
• Write-Ahead Logging Protocol: A page's PageLSN must be ≤ the LSN of the log records flushed to disk for that page's modifications before the page itself can be written to disk.
• Repeatable History: During recovery, Aries retraces history exactly to reconstruct the state at crash time before performing undo, simplifying logic and supporting nested top actions.

A recovery mechanism where a system's complete operational state is periodically saved to persistent storage (a checkpoint). This snapshot can be reloaded to resume execution from that exact point after a crash or failure, minimizing data loss. It is often used in conjunction with WAL to limit log replay time.

• Key Mechanism: Periodically flushes all dirty pages from memory to the main data files and records a special marker in the WAL.
• Use Case: Database recovery, long-running scientific computations, and container migration.

A design pattern for managing long-running, distributed transactions by breaking them into a sequence of local transactions. Each local transaction updates the database and publishes an event or message. If a step fails, compensating transactions are executed to semantically undo the preceding steps. This provides eventual consistency without the blocking nature of Two-Phase Commit.

• Contrast with WAL: While WAL ensures durability of individual operations, Sagas manage business-level rollback across services.
• Example: An e-commerce order involving payment, inventory, and shipping services.

A distributed consensus protocol that ensures atomicity across multiple database or service participants. It coordinates all nodes to ensure they all either commit or abort a transaction based on a collective vote.

• Phases: 1) Prepare: The coordinator asks all participants if they can commit. 2) Commit/Rollback: If all vote yes, the coordinator instructs a commit; otherwise, it instructs a rollback.
• Relation to WAL: Participants use their own WAL to durably record their prepare and commit decisions, ensuring they can recover the transaction outcome after a crash.

A business-logic-specific operation invoked to semantically undo the effects of a previously committed transaction. It is a key component of the Saga pattern and enables forward recovery in systems that cannot use locking or immediate rollback.

• Not a Technical Rollback: Unlike WAL-based rollback, which uses a physical log to reverse byte-level changes, a compensating transaction is a new, inverse business operation (e.g., "Cancel Order" to compensate for "Place Order").
• Use Case: Essential for achieving eventual consistency in microservices architectures.

A database isolation technique that maintains multiple versions of a data item. This allows read operations to access a consistent snapshot of the data (from a past timestamp) without blocking write operations, and vice-versa.

• Synergy with WAL: The WAL is often used to store the undo information required to reconstruct older versions of rows for long-running readers. The log sequence number (LSN) is a critical component for tracking version visibility.
• Benefit: Provides high concurrency for read-heavy workloads, a feature of systems like PostgreSQL and Oracle.

A transaction management method where operations proceed without acquiring locks, assuming conflicts are rare. Modifications are made in a private workspace. Before commit, a validation phase checks if the read data has been modified by another transaction. If validation fails, the transaction is aborted and retried.

• Contrast with WAL: OCC manages logical conflicts, while WAL ensures physical durability. They are complementary: an OCC-based system still needs WAL to persist committed transactions.
• Use Case: Highly concurrent applications with low conflict rates, such as collaborative editing or certain caching layers.