Recovery Based on Deferred Update

 

NO-UNDO / REDO Recovery Based on Deferred Update

1. Introduction

The Deferred Update recovery technique postpones all updates to the database on disk until the transaction successfully commits.

During transaction execution:

• Changes are stored in log records and main memory buffers.

• The actual database on disk is not updated immediately.

If the transaction fails before commit, no changes exist in the database, so no undo operation is required.

Therefore this method is called:

NO-UNDO / REDO Recovery

---

2. Basic Idea of Deferred Update

In this approach:

1. Transaction operations are executed normally.

2. All updates are recorded in the log file and buffer memory.

3. The database on disk is updated only after commit.

4. If a system crash occurs after commit but before updates reach disk, the updates must be redone from the log.

Thus:

Situation	Action
Transaction fails before commit	Nothing to undo
System crashes after commit	Redo updates from log

---

3. Logging Requirements

Only REDO-type log entries are needed.

Each log record contains:

[write_item, Transaction_ID, Data_Item, New_Value]

The new value is called:

AFIM (After Image)

Unlike other recovery methods, before images (BFIM) are not needed because undo operations are never required.

---

4. Deferred Update Protocol

The protocol for deferred update consists of two main rules.

Rule 1: No Disk Update Before Commit

A transaction cannot update the database on disk until it commits.

Therefore:

• All updated buffers must remain pinned in memory

• These buffers cannot be replaced

This corresponds to the No-Steal policy.

---

Rule 2: Log Must Be Written Before Commit

A transaction can reach its commit point only after all log entries are written to disk.

This rule follows Write-Ahead Logging (WAL).

Steps:

1. Write all log records to log buffer.

2. Force-write log buffer to disk.

3. Mark transaction as committed.

---

5. Recovery in Deferred Update

If the system crashes, recovery is performed using log records.

Recovery procedure:

1. Identify transactions committed after the last checkpoint.

2. Redo all write operations of these transactions.

3. Ignore transactions that were active but not committed.

Because updates were never written to disk for uncommitted transactions:

• Undo operations are unnecessary.

---

6. Recovery Algorithm (RDU_M)

In multiuser systems, a recovery algorithm called RDU_M (Recovery using Deferred Update in Multiuser systems) is used.

The system maintains two lists:

1. Commit List

Contains transactions that committed after the last checkpoint.

2. Active List

Contains transactions that started but did not commit before the crash.

---

Steps of RDU_M Recovery

1. Start scanning the log from the last checkpoint.

2. Identify committed transactions.

3. Redo all write operations of committed transactions.

4. Ignore active transactions.

Active transactions must be resubmitted for execution.

---

7. REDO Operation

Redo means reapplying a write operation from the log.

If the log entry is:

[write_item, T, X, new_value]

Then REDO performs:

X = new_value

Where:

• new_value = AFIM (After Image)

---

8. Example Scenario

Consider a timeline of transactions.

Time	Event
t1	Checkpoint taken
After t1	Transactions T2 and T3 commit
Before crash	T4 and T5 still active

During recovery:

• T1 → committed before checkpoint → ignore

• T2 and T3 → committed after checkpoint → REDO

• T4 and T5 → active → ignore (resubmit)

Thus only committed transactions after checkpoint are redone.

---

9. Optimization of REDO

Sometimes the same data item may be updated multiple times.

Example:

T1: X = 10
T2: X = 20
T3: X = 30

During recovery:

• Only the last update needs to be redone.

Optimization technique:

1. Start scanning log from the end.

2. Maintain a list of items already redone.

3. Skip repeated updates.

This improves recovery efficiency.

---

10. Advantages of Deferred Update

1. No Undo Required

Because database updates occur only after commit.

2. No Cascading Rollback

Transactions cannot read uncommitted values because of locking.

3. Simpler Recovery

Recovery process only requires redo operations.

---

11. Disadvantages of Deferred Update

1. Large Buffer Requirement

Updated pages must stay in memory until commit.

2. Reduced Concurrency

Items remain write-locked until commit.

3. Not Suitable for Long Transactions

Long transactions may exhaust buffer space.

---

12. Relationship with Concurrency Control

Deferred update is commonly used with:

Strict Two-Phase Locking (Strict 2PL)

Because:

• Write locks remain until commit.

• Other transactions cannot read uncommitted data.

This guarantees:

• Strict schedules

• Serializable execution

• No cascading rollback

---

13. Summary

Deferred update recovery works by postponing database updates until transaction commit.

Key characteristics:

Feature	Description
Update time	After commit
Log type	REDO only
Undo needed	No
Redo needed	Yes
Buffer policy	No-Steal
Concurrency	Limited

Thus it is called:

NO-UNDO / REDO Recovery

Deferred update recovery postpones database updates until the transaction commits. Updates are recorded only in the log and buffers during execution. If a crash occurs, only the committed transactions are redone from the log, and uncommitted transactions are ignored. Hence it is called the NO-UNDO/REDO recovery technique.