Database Recovery Techniques: Failures, Log-Based Recovery, and Checkpoints

Introduction to Database Recovery

Database recovery is the process of restoring the database to a correct and consistent state after a failure has occurred. In a multi-user environment, transactions are executed concurrently, and failures can lead to partial updates, which violate the ACID properties—specifically Atomicity (all or nothing) and Durability (once committed, changes are permanent).

Recovery techniques are designed to ensure that even if the system crashes, the database can recover to the last consistent state.

Failure Classification

To understand recovery, we must first classify the types of failures that can occur:

1. Transaction Failure:
   • Logical Error: The transaction cannot complete due to some internal condition (e.g., insufficient balance, division by zero).
   • System Error: The DBMS terminates an active transaction because of an error condition (e.g., deadlock) or because the user aborted it.
2. System Crash:
   • Hardware or software failure causes the system to stop.
   • The contents of the main memory (volatile storage) are lost, but the data on the disk (non-volatile storage) remains intact.
3. Disk Failure (Media Failure):
   • A physical failure of the disk (e.g., head crash) results in the loss of data stored on the disk. This is the most severe type of failure and requires backups for recovery.

Storage Structure

Recovery depends on how data is stored across different media:

• Volatile Storage: Fast, but data is lost during power failure or system crash (e.g., RAM, Cache).
• Non-volatile Storage: Slower, but survives system crashes (e.g., Hard Disks, SSDs).
• Stable Storage: A theoretical storage that survives all types of failures, including disk crashes. It is implemented using techniques like Disk Mirroring or RAID, where data is replicated across multiple non-volatile devices.

Recovery Concepts and the Log

The most widely used recovery mechanism is the Transaction Log (or Journal). The log is a sequence of records kept on stable storage that tracks all updates made to the database.

Log Record Structure

A typical log record contains:

• <T, Start>: Transaction $T$ has started.
• <T, X, V1, V2>: Transaction $T$ changed data item $X$ from old value $V1$ to new value $V2$.
• <T, Commit>: Transaction $T$ has successfully completed.
• <T, Abort>: Transaction $T$ has been rolled back.

Write-Ahead Logging (WAL)

The WAL protocol states that:

1. Before a data item in the database is modified on disk, the corresponding log record (containing the old value) must be written to stable storage.
2. A transaction is not considered "committed" until its commit log record is written to stable storage.

Log-Based Recovery Techniques

There are two primary approaches to log-based recovery: Deferred Update and Immediate Update.

1. Deferred Update (No-Undo/Redo)

In this technique, the database is not updated on the disk until the transaction reaches its commit point. All updates are recorded in the log and kept in local buffers.

• During Execution: Only the log is updated; the actual database remains unchanged.
• At Commit: The log records are written to stable storage, and then the database is updated.
• Recovery Procedure:
  • If a transaction $T$ has a <T, Start> and a <T, Commit> record, it is Redone.
  • If a transaction $T$ has a <T, Start> but no <T, Commit> record, nothing needs to be done (No-Undo) because the disk was never updated.

2. Immediate Update (Undo/Redo)

In this technique, the database can be updated on the disk even before the transaction commits. However, the WAL protocol must be followed.

• During Execution: Updates are written to the log and may be written to the disk.
• Recovery Procedure:
  • If a transaction $T$ has a <T, Start> and a <T, Commit> record, it is Redone (to ensure durability).
  • If a transaction $T$ has a <T, Start> but no <T, Commit> record, it must be Undone (to ensure atomicity). The old values from the log are used to restore the data.

Comparison Table: Deferred vs. Immediate Update

Checkpoints

In a real-world system, the log file grows indefinitely. During recovery, scanning the entire log is time-consuming. To optimize this, the DBMS uses Checkpoints.

A checkpoint is a point in time where the DBMS ensures that all log records and modified buffer blocks are physically written to the disk.

Recovery with Checkpoints:

1. Find the last [checkpoint] record in the log.
2. Only transactions that were active at the time of the checkpoint or started after the checkpoint need to be processed.
3. Transactions that committed before the checkpoint are already safely on the disk and do not need to be redone.

Shadow Paging

Shadow paging is an alternative to log-based recovery. It considers the database to be made up of fixed-size logical units called pages.

How it works:

1. The system maintains two page tables: the Current Page Table and the Shadow Page Table.
2. When a transaction starts, both tables are identical.
3. When a page is modified, a new page is created on the disk. The Current Page Table is updated to point to this new page, while the Shadow Page Table continues to point to the original (old) page.
4. Commit: The Current Page Table is saved to disk, becoming the new Shadow Page Table.
5. Recovery: If the system crashes, the Current Page Table in volatile memory is lost. The system simply reloads the Shadow Page Table from the disk. Since the shadow table points to the state before the transaction started, the database is automatically in a consistent state.

Shadow Paging Diagram:

    [Page Table]              [Disk Pages]
    +-------+-------+         +-----------+
    | Index | Addr  | ------> | Page 0    |
    +-------+-------+         +-----------+
    | Index | Addr  | ------> | Page 1    | (Original)
    +-------+-------+         +-----------+
                              | Page 1'   | (Modified Copy)
                              +-----------+

    * Current Table points to Page 1'
    * Shadow Table points to Page 1

Advantages:

• No overhead of maintaining log files.
• Recovery is very fast (no Undo/Redo).

Disadvantages:

• Data Fragmentation: Pages become scattered on the disk.
• Garbage Collection: Old pages need to be cleaned up.
• Commit Overhead: Writing the entire page table can be expensive for large databases.

Worked Example: Log-Based Recovery (Immediate Update)

Consider the following log at the time of a system crash:

1. <T1, Start>
2. <T1, A, 100, 200>
3. <T2, Start>
4. <T1, Commit>
5. <T2, B, 500, 600>
6. <T3, Start>
7. <T3, C, 10, 20> --- CRASH ---

Recovery Steps:

1. Identify Transactions:
   • $T1$: Started and Committed.
   • $T2$: Started but not Committed.
   • $T3$: Started but not Committed.
2. Undo Phase:
   • Undo $T3$: Restore $C$ to 10.
   • Undo $T2$: Restore $B$ to 500.
3. Redo Phase:
   • Redo $T1$: Set $A$ to 200.

Final State: $A=200,B=500,C=10$.

ARIES Recovery Algorithm

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is a sophisticated recovery algorithm used in many modern DBMSs (like IBM DB2 and SQL Server). It operates in three phases:

1. Analysis Phase: Identifies which transactions were active at the time of the crash and which pages in the buffer were "dirty" (modified but not written to disk).
2. Redo Phase: Repeats all history found in the log to bring the database to the state it was in at the moment of the crash.
3. Undo Phase: Rolls back all transactions that were active at the time of the crash in reverse chronological order.

Advantages and Disadvantages of Recovery Techniques

Exam Tip

In TU/PU exams, this unit is frequently tested through the following:

1. ACID Properties: Always mention how recovery ensures Atomicity and Durability.
2. Deferred vs. Immediate Update: This is a favorite "Differentiate between" question. Use a table and explain the Undo/Redo logic clearly.
3. Numerical/Trace Problems: You might be given a log sequence (like the example above) and asked to identify which transactions are Undone and which are Redone.
4. Checkpoints: Explain how checkpoints reduce the work of the recovery manager.
5. Shadow Paging: Often asked as a short note. Mention the "Current" and "Shadow" page tables.

When answering "Explain any one recovery technique," choose Log-based recovery with Immediate Update as it allows you to demonstrate your knowledge of both Undo and Redo operations, which usually earns higher marks.