Log-Based Recovery

A transaction log also called a redo log or write-ahead log is a sequential record of all database modifications. It is stored on stable non-volatile storage and is the p

What is a Transaction Log?

A transaction log (also called a redo log or write-ahead log) is a sequential record of all database modifications. It is stored on stable (non-volatile) storage and is the primary mechanism for database recovery.

Log Record Types

Record Type	Format	Description
Begin	`<Ti, start>`	Transaction Ti has started
Write	`<Ti, X, old_val, new_val>`	Ti wrote X; old and new values stored
Commit	`<Ti, commit>`	Ti has committed successfully
Abort	`<Ti, abort>`	Ti has been aborted
Checkpoint	`<checkpoint, {active_list}>`	Checkpoint taken with active transactions

Write-Ahead Logging (WAL)

The WAL Protocol is the fundamental rule of log-based recovery:

Rule 1 (Atomicity)

Before a data page is written to disk, ALL log records for

that page's transactions must be written to stable storage first.

Rule 2 (Durability)

Before a transaction commits, ALL its log records must be

written to stable storage.

┌──────────────────────────────────────────────────────┐

│ Write log record → THEN → Write data page to disk │

│ The log ALWAYS goes first. │

└──────────────────────────────────────────────────────┘

Recovery After System Crash

When the system restarts after a crash:

Step 1	ANALYSIS PASS
• Committed transactions (have <Ti, commit> in log)	REDO set
• Active/incomplete transactions (no commit)	UNDO set
Step 2	REDO PASS
Step 3	UNDO PASS

Example — Recovery Walkthrough

Log (time goes down)

<T1, start>

<T1, A, 100, 200> ← T1 writes A: 100 → 200

<T2, start>

<T2, B, 500, 400> ← T2 writes B: 500 → 400

<T1, commit> ← T1 committed ✓

<T3, start>

<T3, C, 300, 350> ← T3 writes C: 300 → 350

<T2, B, 400, 450> ← T2 writes B again: 400 → 450

*** SYSTEM CRASH ***

After crash

REDO set: {T1} ← has <commit> in log

UNDO set: {T2, T3} ← no <commit> in log

REDO PASS (forward)

T1: A = 200 ← ensure T1's changes are on disk

UNDO PASS (backward)

T2: B = 400 (undo second write)

T3: C = 300 (undo T3's write)

T2: B = 500 (undo first write)

Log: <T2, abort>, <T3, abort>

Final state: A=200, B=500, C=300 ← consistent ✓

Immediate vs. Deferred Modification

Deferred Modification

Database modifications are deferred until the transaction commits. All writes are held in memory (or temp storage) until COMMIT — then all are applied at once.

Advantage	Only need REDO (no UNDO needed for incomplete txns)
Disadvantage	Large memory requirement for long transactions
Log needs	Only new_value (no old_value needed for undo)

Immediate Modification

Database modifications are applied to disk as they occur, even before commit.

Advantage	Low memory requirement
Disadvantage	Need both UNDO and REDO
Log needs	Both old_value and new_value in each record

Undo-Only Logging

Used when NO-FORCE policy: all data is forced to disk at commit.

Log format: <Ti, X, old_val> Recovery: Only need to UNDO incomplete transactions No REDO needed (committed data already on disk)

Redo-Only Logging

Used when NO-STEAL policy: no dirty pages written to disk.

Log format: <Ti, X, new_val> Recovery: Only need to REDO committed transactions No UNDO needed (incomplete data never reached disk)

Undo-Redo Logging

Used with STEAL + NO-FORCE (most common).

Log format: <Ti, X, old_val, new_val> Recovery: Need both UNDO (for incomplete) and REDO (for committed) Most flexible and commonly used approach.

ARIES Recovery Algorithm

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the industry-standard recovery algorithm used by IBM DB2, SQL Server, and many others.

Key features of ARIES

1. Write-Ahead Logging (WAL)

2. Repeating History During REDO

→ Redo ALL changes (even from aborted transactions)

→ Then UNDO the aborted ones

3. Logging changes during UNDO

→ Compensation Log Records (CLR) prevent re-undoing

Three passes on restart

1. Analysis → Identify redo and undo sets

2. Redo → Repeat all logged operations

3. Undo → Roll back all incomplete transactions

What is a Transaction Log?

Log Record Types

Record Type	Format	Description
Begin	`<Ti, start>`	Transaction Ti has started
Write	`<Ti, X, old_val, new_val>`	Ti wrote X; old and new values stored
Commit	`<Ti, commit>`	Ti has committed successfully
Abort	`<Ti, abort>`	Ti has been aborted
Checkpoint	`<checkpoint, {active_list}>`	Checkpoint taken with active transactions

Write-Ahead Logging (WAL)

The WAL Protocol is the fundamental rule of log-based recovery:

Rule 1 (Atomicity)

Before a data page is written to disk, ALL log records for

that page's transactions must be written to stable storage first.

Rule 2 (Durability)

Before a transaction commits, ALL its log records must be

written to stable storage.

┌──────────────────────────────────────────────────────┐

│ Write log record → THEN → Write data page to disk │

│ The log ALWAYS goes first. │

└──────────────────────────────────────────────────────┘

Recovery After System Crash

When the system restarts after a crash:

Step 1	ANALYSIS PASS
• Committed transactions (have <Ti, commit> in log)	REDO set
• Active/incomplete transactions (no commit)	UNDO set
Step 2	REDO PASS
Step 3	UNDO PASS

Example — Recovery Walkthrough

Log (time goes down)

<T1, start>

<T1, A, 100, 200> ← T1 writes A: 100 → 200

<T2, start>

<T2, B, 500, 400> ← T2 writes B: 500 → 400

<T1, commit> ← T1 committed ✓

<T3, start>

<T3, C, 300, 350> ← T3 writes C: 300 → 350

<T2, B, 400, 450> ← T2 writes B again: 400 → 450

*** SYSTEM CRASH ***

After crash

REDO set: {T1} ← has <commit> in log

UNDO set: {T2, T3} ← no <commit> in log

REDO PASS (forward)

T1: A = 200 ← ensure T1's changes are on disk

UNDO PASS (backward)

T2: B = 400 (undo second write)

T3: C = 300 (undo T3's write)

T2: B = 500 (undo first write)

Log: <T2, abort>, <T3, abort>

Final state: A=200, B=500, C=300 ← consistent ✓

Immediate vs. Deferred Modification

Deferred Modification

Database modifications are deferred until the transaction commits. All writes are held in memory (or temp storage) until COMMIT — then all are applied at once.

Advantage	Only need REDO (no UNDO needed for incomplete txns)
Disadvantage	Large memory requirement for long transactions
Log needs	Only new_value (no old_value needed for undo)

Immediate Modification

Database modifications are applied to disk as they occur, even before commit.

Advantage	Low memory requirement
Disadvantage	Need both UNDO and REDO
Log needs	Both old_value and new_value in each record

Undo-Only Logging

Used when NO-FORCE policy: all data is forced to disk at commit.

Log format: <Ti, X, old_val> Recovery: Only need to UNDO incomplete transactions No REDO needed (committed data already on disk)

Redo-Only Logging

Used when NO-STEAL policy: no dirty pages written to disk.

Log format: <Ti, X, new_val> Recovery: Only need to REDO committed transactions No UNDO needed (incomplete data never reached disk)

Undo-Redo Logging

Used with STEAL + NO-FORCE (most common).

Log format: <Ti, X, old_val, new_val> Recovery: Need both UNDO (for incomplete) and REDO (for committed) Most flexible and commonly used approach.

ARIES Recovery Algorithm

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the industry-standard recovery algorithm used by IBM DB2, SQL Server, and many others.

Key features of ARIES

1. Write-Ahead Logging (WAL)

2. Repeating History During REDO

→ Redo ALL changes (even from aborted transactions)

→ Then UNDO the aborted ones

3. Logging changes during UNDO

→ Compensation Log Records (CLR) prevent re-undoing

Three passes on restart

1. Analysis → Identify redo and undo sets

2. Redo → Repeat all logged operations

3. Undo → Roll back all incomplete transactions

What is a Transaction Log?

Log Record Types

Write-Ahead Logging (WAL)

Rule 1 (Atomicity)

Rule 2 (Durability)

Recovery After System Crash

Example — Recovery Walkthrough

Log (time goes down)

After crash

REDO PASS (forward)

UNDO PASS (backward)

Immediate vs. Deferred Modification

Deferred Modification

Immediate Modification

Undo-Only Logging

Redo-Only Logging

Undo-Redo Logging

ARIES Recovery Algorithm

Key features of ARIES

Three passes on restart

Continue learning this concept

What is a Transaction Log?

Log Record Types

Write-Ahead Logging (WAL)

Rule 1 (Atomicity)

Rule 2 (Durability)

Recovery After System Crash

Example — Recovery Walkthrough

Log (time goes down)

After crash

REDO PASS (forward)

UNDO PASS (backward)

Immediate vs. Deferred Modification

Deferred Modification

Immediate Modification

Undo-Only Logging

Redo-Only Logging

Undo-Redo Logging

ARIES Recovery Algorithm

Key features of ARIES

Three passes on restart

Continue learning this concept