Recovery System: Log-Based & WAL

What happens if the power goes out while a transaction is 50% done? The Recovery System ensures that the database returns to a consistent state.

The foundation of modern database recovery is Write-Ahead Logging (WAL) — a simple rule that guarantees atomicity and durability.

---

Learning Objectives

After completing this chapter, you will be able to:

• Classify different types of database failures.
• Explain Write-Ahead Logging (WAL) and why it’s critical.
• Describe log record structure and Log Sequence Numbers (LSN).
• Explain Undo and Redo operations.
• Understand checkpoints and why they speed recovery.
• Differentiate between log-based recovery and Shadow Paging.
• Answer recovery interview questions.

---

Types of Failures

Failure Type	Description	Effect
Transaction Failure	Logical error, constraint violation, deadlock	Only the affected transaction needs rollback
System Crash	Power failure, OS crash, hardware fault	RAM lost, disk intact. All active transactions affected
Disk Failure	Physical disk corruption, head crash	Requires restoration from backup + replay

---

Write-Ahead Logging (WAL)

WAL is the most important rule in database recovery. Every modern database uses it.

The WAL Rule

A transaction cannot commit until all its log records are written to stable storage (disk).

In other words: Log first, then commit.

Why WAL Matters

1. If the system crashes, the DBMS reads the log on disk to see what happened
2. Transactions that committed before the crash → Redo (re-apply changes that may not have reached disk)
3. Transactions that were active at the crash → Undo (roll back partial changes)

---

Log Record Structure

Each log record (also called a Log Sequence Number — LSN) contains:

Field	Description
LSN	Unique, monotonically increasing ID
Trans ID	Which transaction made this change
Page ID	Which data page was modified
Old Value (Before Image)	Value before the change (for Undo)
New Value (After Image)	Value after the change (for Redo)
Prev LSN	Previous LSN of the same transaction

Types of Log Records

Record Type	Meaning
<T start>	Transaction T has begun
<T X, V1, V2>	T wrote V2 to data item X (old value V1)
<T commit>	T has committed
<T abort>	T has aborted

---

Undo and Redo

Undo

Used for transactions that were active at the time of the crash.

Process: Scan the log backwards. For each change by the active transaction, restore the old value.

Result: The database is returned to the state before the transaction started.

Example: If T1 had executed A = A - 100 but not committed before the crash, Undo sets A back to its previous value.

Redo

Used for transactions that committed but whose changes may not have reached the disk.

Process: Scan the log forward. For each committed transaction, re-apply the new value.

Result: All committed changes are guaranteed to be on disk.

Example: T1 committed, but the page containing A was still in memory when the crash occurred. Redo writes A - 100 to disk.

---

Recovery After a Crash

1. Identify the last checkpoint
2. Scan the log from the checkpoint forward
3. Build two lists:
   - Undo-list: transactions that never committed
   - Redo-list: transactions that committed
4. Undo all transactions on the Undo-list (backward scan)
5. Redo all transactions on the Redo-list (forward scan)
6. Database is consistent

---

Checkpoints

Without checkpoints, recovery would scan the ENTIRE log from the beginning of time — impractical for databases that have been running for years.

What is a Checkpoint?

A Checkpoint is a moment where the DBMS:

1. Flushes all memory buffers to disk
2. Writes a checkpoint record to the log (listing active transactions)

How Checkpoints Accelerate Recovery

Without Checkpoint	With Checkpoint
Scan the entire log (millions of records)	Scan only log AFTER the last checkpoint
All transactions since DB was created	Only transactions since last checkpoint (minutes/hours)
Slow recovery (hours/days)	Fast recovery (seconds/minutes)

Types of Checkpoints

Type	Behavior
Begin/End Checkpoint	Records start and end of checkpoint — ensures consistency
Fuzzy Checkpoint	Allows transactions to continue during checkpoint — used by modern databases
Online Checkpoint	No database downtime needed

---

Shadow Paging (Alternative to Logging)

An older alternative to log-based recovery.

Feature	Log-Based (WAL)	Shadow Paging
Mechanism	Log every change	Maintain two page tables (current + shadow)
Commit	Write log, then apply changes	Swap page table pointers
Rollback	Undo from log	Discard current table, revert to shadow
Performance	Good for all workloads	Fast for crashes, slow for updates
Disk usage	Log grows continuously	More disk fragmentation

Shadow Paging is simpler conceptually (no log to manage) but results in disk fragmentation and is slower for update-heavy workloads. Log-based recovery is the modern standard.

---

Interview Deep Dive

---

Key Takeaways

• Write-Ahead Logging (WAL): Log first, commit later — guarantees atomicity and durability.
• Undo: Roll back changes of uncommitted transactions (backward scan).
• Redo: Re-apply changes of committed transactions that didn’t reach disk (forward scan).
• LSN: Unique identifier for each log record — used to compare page vs log state.
• Checkpoints: Flush buffers to disk periodically to bound the log scan during recovery.
• Shadow Paging: Alternative to WAL — simpler but slower and causes fragmentation.
• Recovery after crash: Find last checkpoint → build Undo/Redo lists → Undo then Redo.
• WAL is used by every modern database (PostgreSQL, MySQL, Oracle, SQL Server).