Crash Recovery: Undo, Redo, and ARIES

When a database crashes (power failure, OS crash, hardware fault), committed transactions must be durable, and uncommitted transactions must be completely undone.

The ARIES recovery algorithm is the industry standard — used by PostgreSQL, Oracle, SQL Server, and MySQL (InnoDB).

This chapter covers the complete recovery process.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain the three phases of ARIES recovery.
• Differentiate between REDO and UNDO operations.
• Understand the role of checkpoints in recovery.
• Explain buffering policies (Steal/No-Steal, Force/No-Force).
• Describe media recovery from backups.
• Answer crash recovery interview questions.

---

Failure Classification

Failure Type	Example	Impact
Transaction failure	Logical error, deadlock	Single transaction aborted
System crash	Power failure, OS crash	All in-memory data lost; disk is safe
Media failure	Disk corruption, head crash	Data on disk is lost
Natural disaster	Fire, flood	Entire site destroyed

This chapter focuses on system crash recovery. Media failure requires backup restoration.

---

Buffering Policies

Databases use different policies for when dirty pages and logs are written to disk.

Force vs No-Force

Policy	Data Pages at Commit	Recovery Implication
Force	All changes written to disk at commit	No REDO needed (data is durable)
No-Force	Changes may still be in buffer	REDO needed for committed transactions

Steal vs No-Steal

Policy	Dirty Pages Written Early	Recovery Implication
No-Steal	Dirty pages stay in buffer till commit	No UNDO needed (abort just discards pages)
Steal	Dirty pages can be flushed early	UNDO needed to revert uncommitted changes

Real Database Choice

Steal + No-Force + WAL

Why?

• Steal: Allows buffer reuse even with dirty pages (better memory utilization).
• No-Force: Committed pages stay in memory (better write performance).
• WAL: Log records guarantee recovery — REDO for No-Force, UNDO for Steal.

---

ARIES Overview

ARIES = Algorithm for Recovery and Isolation Exploiting Semantics.

Developed at IBM in the early 1990s. The standard recovery method used by virtually all relational databases.

Three Phases

1. Analysis   — Scan log from last checkpoint. Identify dirty pages and in-flight transactions.
2. REDO       — Reapply all changes (committed and uncommitted) to restore database state at crash.
3. UNDO       — Roll back all uncommitted transactions.

---

Phase 1: Analysis

Goal: Determine what state the database was in at the crash.

Steps

1. Start from the last checkpoint record.
2. Scan forward through the log.

What Analysis Builds

Dirty Page Table (DPT)

Page ID	LSN of first modification (recLSN)
5	101
7	102

Transaction Table (TT)

Transaction ID	Status	Last LSN
T1	COMMITTED	103
T2	IN-PROGRESS	105
T3	IN-PROGRESS	106

Result

• Know which transactions were active at crash time (need UNDO).
• Know which pages were dirty and the earliest log record that might need redo.

---

Phase 2: REDO

Goal: Restore the database to the exact state it was at the moment of the crash.

Steps

1. Start from the smallest recLSN in the Dirty Page Table (the first modification of the oldest dirty page).
2. Scan forward through the log.
3. For each update log record:
   • Read the page from disk.
   • If pageLSN < logLSN → redo the change (write Redo value to page).
   • If pageLSN >= logLSN → skip (page is already up to date).

Why REDO Everything

Even uncommitted transactions are redone. This is intentional — it simplifies the algorithm (no need to determine transaction state during REDO). The UNDO phase fixes the uncommitted ones.

---

Phase 3: UNDO

Goal: Roll back all transactions that were still active at the time of the crash.

Steps

1. Work backward through the log (from end to beginning) using the Prev LSN chain for each transaction.
2. For each update log record of a transaction to be undone:
   • Write a CLR (Compensation Log Record) to the log.
   • Restore the page to its Undo value (the value before the change).
3. Continue until all active transactions are rolled back.

Compensation Log Record (CLR)

• A CLR records that an undo action was performed.
• Contains the Undo value.
• A CLR is never undone — if the system crashes during UNDO, the restart simply redoes the CLR (which reapplies the undo).

This property is called idempotent recovery — recovery can be interrupted and restarted safely.

---

ARIES Recovery Example

Initial State

Log:
LSN 100: T1 BEGIN
LSN 101: T1 UPDATE P5, Undo: [A=100], Redo: [A=90]
LSN 102: T1 UPDATE P7, Undo: [B=200], Redo: [B=180]
LSN 103: CHECKPOINT
LSN 104: T1 COMMIT
LSN 105: T2 BEGIN
LSN 106: T2 UPDATE P5, Undo: [A=90], Redo: [A=80]

Crash occurs after LSN 106

Recovery

Analysis Phase

• Last checkpoint: LSN 103.
• Transaction Table: T1 (COMMITTED), T2 (IN-PROGRESS, Last LSN = 106).
• Dirty Page Table: P5 (recLSN = 101), P7 (recLSN = 102).

REDO Phase (LSN 101 → 106)

• LSN 101: REDO P5 (A=90) if pageLSN < 101.
• LSN 102: REDO P7 (B=180) if pageLSN < 102.
• LSN 104: No change (commit record).
• LSN 106: REDO P5 (A=80) if pageLSN < 106.

UNDO Phase

• T2 is active → undo from last T2 record.
• LSN 106: CLR written. Restore P5 to A=90.
• LSN 105: T2 BEGIN (no undo needed).
• End UNDO.

---

Media Recovery (From Backup)

Full Backup

A complete copy of the database taken at a point in time.

Incremental Backup

Only the changes since the last full backup.

Recovery Process

1. Restore the latest full backup.
2. Restore all incremental backups (in order).
3. Apply WAL logs from the backup time to the present (point-in-time recovery).

Point-in-Time Recovery (PITR)

Recover to a specific moment (e.g., just before an accidental DROP TABLE).

-- PostgreSQL PITR
RECOVERY_TARGET_TIME = '2024-03-15 14:30:00';

---

Checkpoint Integration with ARIES

Fuzzy Checkpoint

ARIES uses fuzzy checkpoints that don’t halt transactions.

Checkpoint Record Contains

• List of active transactions.
• Dirty Page Table.
• LSN of the oldest log record needed for redo.

Recovery Impact

• Analysis starts from the fuzzy checkpoint (not the beginning of time).
• REDO starts from the oldest recLSN in the checkpoint’s DPT.

---

Interview Deep Dive

---

Key Takeaways

• ARIES is the standard recovery algorithm with three phases: Analysis, REDO, UNDO.
• Steal/No-Force + WAL is the standard buffering strategy for performance with safety.
• REDO reapplies all changes from the log (both committed and uncommitted).
• UNDO rolls back uncommitted transactions by writing CLRs.
• CLRs are never undone (idempotent recovery).
• Analysis phase builds transaction and dirty page tables from the last checkpoint.
• Fuzzy checkpoints allow normal operation during checkpointing.
• Media recovery = full backup + incremental backups + WAL replay.
• Point-in-time recovery restores to a specific moment.
• ARIES guarantees atomicity and durability after any crash.