ACID Properties and Write-Ahead Logging (WAL)

Why We Need Recovery: The "A" and "D" of ACID

Let's start with a quick refresher on ACID, this time focusing on the properties relevant to crash recovery.

• Atomicity: Transactions are "all or nothing." If a transaction completes successfully (commits), all of its changes are saved. If it fails for any reason (aborts or the system crashes), none of its changes should be visible.
• Consistency: A transaction brings the database from one valid state to another. We largely covered this through isolation.
• Isolation: Concurrent transactions do not interfere with each other. From each transaction's perspective, it appears to be the only one running.
• Durability: Once a transaction has been committed, its changes are permanent and will survive any subsequent system failure (e.g., power loss, OS crash).

The challenge is that databases perform most of their work in volatile main memory (the buffer pool) for performance. Writing every change directly to non-volatile storage (like an SSD or HDD) would be incredibly slow. This reliance on memory creates a risk: what happens if the system crashes before the in-memory changes are persisted to disk?

To handle this, recovery algorithms rely on two key operations:

• UNDO: The process of removing the effects of an incomplete or aborted transaction. This is essential for Atomicity. If a transaction was halfway through its work when a crash occurred, we must undo what it did.
• REDO: The process of re-applying the effects of a committed transaction. This is essential for Durability. If a transaction committed but its changes were still only in memory at the time of a crash, we must redo them to ensure they are not lost.

The Buffer Pool's Role: A Critical Design Choice

How and when the DBMS writes dirty pages from the buffer pool to disk has a massive impact on recovery. This behavior is governed by two policies:

1. STEAL vs. NO-STEAL:

   • STEAL: The buffer manager is allowed to write a dirty page to disk even if the transaction that modified it has not yet committed.
   • NO-STEAL: The buffer manager must keep dirty pages from uncommitted transactions in memory.

2. FORCE vs. NO-FORCE:

   • FORCE: All pages modified by a transaction must be written to disk before the transaction is allowed to commit.
   • NO-FORCE: A transaction can commit even if its modified pages are still only in the buffer pool.

A simple, but slow, approach is NO-STEAL + FORCE. This simplifies recovery (no need for UNDO because uncommitted changes never hit disk; no need for REDO because committed changes are already on disk), but the performance is terrible due to frequent, forced disk writes.

For high performance, modern databases use a STEAL + NO-FORCE policy. This allows the buffer manager maximum flexibility but makes recovery much harder.

• A STEAL policy requires UNDO capability.
• A NO-FORCE policy requires REDO capability.

The question is: how can we implement STEAL + NO-FORCE safely and efficiently?

To understand the challenge, let's first look at why simply forcing writes to disk is so inefficient.

The Solution: Write-Ahead Logging (WAL)

As the video hints, the industry-standard solution is Write-Ahead Logging (WAL). The core idea is brilliantly simple: before modifying the actual database files (which involves slow, random I/O), the DBMS first writes a description of the change to a separate, append-only log file. This log write is a fast, sequential operation.

This approach decouples the logical completion of a transaction (commit) from the physical writing of data pages, enabling the high-performance STEAL + NO-FORCE policy.

The Two Golden Rules of WAL

The entire safety of the WAL protocol rests on two fundamental rules. Understanding these is the main goal of our lesson today.

Let's formalize these rules:

1. The UNDO Rule: The log record describing a change to a page must be written to stable storage (the log file on disk) before the page itself is written to stable storage (the database files on disk).

   • Ensures Atomicity: This rule makes the STEAL policy safe. If the system crashes, and we find a page on disk that was modified by an uncommitted transaction, this rule guarantees that the log record containing the UNDO information (the "before" value) is also safely on disk. The recovery process can then use this log record to roll back the change.

2. The REDO Rule: All log records for a transaction, including its final <COMMIT> record, must be written to stable storage before the transaction is acknowledged as committed to the client.

   • Ensures Durability: This rule makes the NO-FORCE policy safe. When an application receives a "commit successful" message, it's a promise that the change is durable. This rule fulfills that promise by ensuring that all information needed to REDO the transaction's changes exists in the log on disk, even if the data pages themselves haven't been written yet. If a crash occurs, the recovery process can replay the log to restore the changes of all committed transactions.

To reinforce these concepts, the following lecture slides from CMU provide a great summary of the WAL protocol and its relationship with the STEAL/NO-FORCE policy.

Conclusion

Today we've laid the groundwork for understanding how modern databases achieve resilience. You've learned that ensuring Atomicity and Durability in the face of system crashes is a non-trivial problem, deeply intertwined with the performance trade-offs of buffer pool management.

Key Takeaways:

• Atomicity (all-or-nothing) and Durability (committed changes survive crashes) are the cornerstones of database reliability. They are guaranteed by UNDO and REDO operations during recovery.
• For performance, databases use a STEAL/NO-FORCE buffer management policy, which requires a robust mechanism to handle both UNDO and REDO.
• Write-Ahead Logging (WAL) is that mechanism. It transforms slow, random disk writes to data files into fast, sequential writes to a log file.
• The two rules of WAL are paramount:
  1. Log records must be on disk before their corresponding dirty data pages (ensuring UNDO for atomicity).
  2. All of a transaction's log records must be on disk before the transaction is considered committed (ensuring REDO for durability).

Preview of the Next Lesson

We now understand the what and the why of Write-Ahead Logging. In our next lesson, we will begin our journey into the how by studying the famous ARIES recovery algorithm. We'll start by designing the specific data structures for various log record types, which are the fundamental building blocks of the entire recovery process.