Write-Ahead Logging (WAL) for Durability and Recovery

The Core Problem: Performance vs. Durability

Databases aim to be fast. A major performance bottleneck is disk I/O. Writing data to a spinning disk or even an SSD involves physical operations that are orders of magnitude slower than writing to main memory (RAM). Specifically, modifying data files often requires random I/O—jumping to different locations on the disk to update various pages—which is particularly slow.

To mitigate this, databases use a buffer pool in memory to cache data pages. When a transaction modifies data, it updates the page in the buffer pool. This is very fast. These modified, in-memory pages are called "dirty pages." Eventually, the database's buffer manager will flush these dirty pages to disk.

This creates a serious problem: What happens if the system crashes after a transaction has committed, but before its dirty pages have been written from the buffer pool to disk? The changes, though committed, would be lost, violating the durability guarantee.

Forcing every change to disk immediately upon commit (a FORCE policy) would solve this but would be disastrous for performance. Allowing uncommitted changes to be written to disk to free up buffer space (a STEAL policy) improves performance but complicates recovery.

High-performance databases aim for a STEAL/NO-FORCE policy, which provides the best performance but presents the greatest recovery challenge. This is where Write-Ahead Logging comes in.

To understand this trade-off in more detail, let's start with a foundational reading.

The Solution: The Write-Ahead Logging Protocol

The STEAL/NO-FORCE policy requires a mechanism to both redo the changes of committed transactions that weren't on disk and undo the changes of uncommitted transactions that were on disk. Write-Ahead Logging (WAL) is the protocol that makes this possible.

The core idea is simple but powerful: before modifying a data page on disk, the database first writes a description of the change to a separate, append-only file on disk called a log. This log write is a sequential I/O operation, which is much faster than the random I/O needed to update the main data files.

This practice is governed by two fundamental rules.

To summarize the two rules of WAL:

1. A log record describing a page update must be written to stable storage (the log file on disk) before the page itself is written to stable storage (the main database file). This rule ensures that we always have the information needed to UNDO a change. If the system crashes after a dirty page from an uncommitted transaction is written to disk, the log will contain the "before image" of the data, allowing us to roll it back.

2. A transaction is not considered committed until all of its log records, including its final COMMIT record, have been written to stable storage. This rule ensures that we have the information needed to REDO a change. If the system crashes after a commit is acknowledged but before the data pages are written, the log contains the "after image," allowing us to re-apply the change during recovery.

How WAL Works: Components and The Protocol in Action

To implement this protocol, the database uses several key components and concepts.

A Log Sequence Number (LSN) is a unique, monotonically increasing number assigned to every log record. You can think of the LSN as the database's internal clock. LSNs are the key to coordinating the state between the log, the in-memory buffer pool, and the data pages on disk.

Two LSNs are particularly important for the WAL protocol:

• pageLSN: Stored on each data page, this is the LSN of the log record that describes the most recent change to that page.
• flushedLSN: An in-memory value that tracks the LSN of the last log record that has been successfully flushed from the WAL buffer to the log file on disk.

The first rule of WAL can be expressed as an inequality: a dirty page P can only be flushed to disk if pageLSN(P) <= flushedLSN.

This next video segment visualizes this interaction perfectly.

Crash Recovery: Bringing the Database Back to Life with ARIES

Now we have all the pieces in place to answer the main question: how does a database recover after a crash? The most famous and widely implemented recovery algorithm using WAL is ARIES (Algorithms for Recovery and Isolation Exploiting Semantics).

Before diving into the recovery phases, we need to understand the information ARIES uses. This includes the structure of log records and the in-memory tables it maintains during normal operation (which it reconstructs from the log during recovery).

With an understanding of these data structures, we can now look at the three phases of ARIES recovery.

The ARIES recovery process consists of three phases:

1. Analysis Phase:

   • The recovery process starts at the last successful checkpoint. A checkpoint is a record in the log that contains the state of the Transaction Table and Dirty Page Table at that time.
   • The system scans the log forward from the checkpoint to the end.
   • It rebuilds the Active Transaction Table (ATT) and Dirty Page Table (DPT) as they were at the moment of the crash. The ATT will list all transactions that had not yet written a final TXN-END record, and the DPT will list all pages that might be dirty and not yet on disk.

2. Redo Phase (Repeating History):

   • The goal is to restore the database to its exact state at the moment of the crash, including the effects of uncommitted transactions.
   • The system finds the smallest recLSN (recovery LSN) from the DPT built during the Analysis phase. This is the oldest update that might not have made it to disk.
   • It scans the log forward from this recLSN.
   • For every logged update, it checks if the change needs to be reapplied. It reapplies the change if the affected page's pageLSN on disk is less than the LSN of the log record. This brings all committed changes back into the database.

3. Undo Phase:

   • Now that the database state is as it was at the crash, the system must roll back any transactions that were active but not committed.
   • Using the ATT, the system identifies all "loser" transactions (those that were running or aborted but not finished).
   • It scans the log backwards, following the prevLSN chain for each loser transaction.
   • For each update from a loser transaction, it performs the undo operation and writes a special Compensation Log Record (CLR) to the log. The CLR ensures that if another crash happens during recovery, the undo operation is not performed twice.
   • Once a transaction is fully undone, a TXN-END record is written to the log.

This three-phase process may seem complex, but it robustly guarantees both atomicity and durability.

Conclusion

In this lesson, we've uncovered the technology that underpins one of the most fundamental promises of a database: durability.

Key Takeaways:

• WAL Solves the Performance/Durability Dilemma: It allows databases to use a high-performance STEAL/NO-FORCE buffer management policy by ensuring all changes are first recorded in a fast, sequential log on disk.
• The Two Rules are Law: 1) Log before writing data pages, and 2) Log before acknowledging a commit. These rules enable both undo and redo capabilities.
• LSNs are the Database's Clock: Log Sequence Numbers are critical for tracking the state of pages and transactions and coordinating the recovery process.
• ARIES Recovery is a Three-Act Play:
  1. Analysis: Figure out what was happening at the time of the crash.
  2. Redo: Repeat history to get back to the state at the moment of the crash, ensuring committed data is present.
  3. Undo: Reverse the actions of incomplete transactions to ensure atomicity.

Preview of the Next Lesson

The Write-Ahead Log is not just for crash recovery. It is a complete, ordered record of every change made to the database. What else can we do with this powerful stream of data? In our next lesson, we will explore primary-replica replication, where we'll see how the WAL is shipped from a primary database to one or more replicas to create read-only copies, a fundamental technique for scaling read-heavy workloads.