Unit 11: Recovery System

Failure Classification

To ensure database reliability, we must first understand the different ways a system can fail. Database failures can be broadly classified into three major categories based on their source and impact.

1. Transaction Failure

A transaction failure occurs when an individual transaction cannot complete its execution. This can happen due to two main reasons:

• Logical Error: The transaction cannot complete because of an internal error condition, such as bad input, data not found, overflow, or resource limit violations.
• System Error: The database system terminates the transaction because of an active deadlock situation or resource limitations, requiring the transaction to abort and roll back.

2. System Crash

A system crash occurs when a hardware malfunction or a software bug causes the database management system (DBMS) to stop running. Key characteristics include:

• Loss of content in volatile storage (such as main memory and cache).
• Non-volatile storage (such as disk drives) remains intact and undamaged.
• The Fail-Stop Assumption is applied: we assume that the system stops immediately upon failure without corrupting the non-volatile disk storage.

3. Disk Failure

A disk failure is a physical catastrophe where a storage device is destroyed or damaged. Examples include head crashes or bad sector allocation. Key characteristics include:

• Loss of content in non-volatile storage.
• Recovery from disk failure requires different mechanisms, such as backups (archival dumps) on stable, external storage media.

Summary of Failure Types

Storage Structure

To understand recovery algorithms, we must classify storage media according to their resilience to crashes and physical damage.

Volatile Storage

Volatile storage is extremely fast but does not survive power outages or system crashes. Examples include Main Memory (RAM) and Cache Memory. Information stored here is lost when the system halts.

Non-Volatile Storage

Non-volatile storage survives system crashes and power failures. Examples include Solid State Drives (SSDs), Hard Disk Drives (HDDs), optical discs, and magnetic tapes. However, non-volatile storage is still vulnerable to physical disk failures (e.g., magnetic head crashes).

Stable Storage

Stable storage is a theoretical concept representing storage that is completely immune to any failure. It is approximated in practice by replicating information across multiple non-volatile storage devices with independent failure modes.

Stable Storage Implementation Rule: To write a block to stable storage, the system must write the block to disk 1, wait for successful completion, then write the same block to disk 2, and wait for completion. If any write fails, a recovery procedure restores the corrupted block using the copy from the surviving disk.

Recovery and Atomicity

The Recovery Manager is the DBMS subsystem responsible for ensuring two crucial ACID properties: Atomicity (either all actions of a transaction complete or none do) and Durability (once committed, changes survive any subsequent failures).

Transaction Rollback and Commit

To achieve atomicity, the recovery system must support two fundamental operations on active transactions:

• Commit: The transaction has completed successfully. All its modifications must be made permanent in non-volatile storage.
• Rollback (Abort): The transaction has failed or been aborted. All changes it made to the database must be undone, restoring the database to its pre-transaction state.

Undo and Redo Operations

The recovery system uses two main operations to handle modifications:

• Undo: Reverts a data item to its original, pre-transaction value. This is used to roll back incomplete transactions.
• Redo: Re-applies the modifications made by a transaction to ensure durability, even if those modifications were lost in volatile memory during a crash.

Log-Based Recovery

The most widely used structure for recording database modifications is the Transaction Log. The log is an append-only sequence of log records kept in stable storage.

Log Record Structure

Each update to the database generates a log record. Common log records include:

• Start Record: [Ti, start] - Indicates transaction Ti has started.
• Update Record: [Ti, X, V1, V2] - Indicates transaction Ti modified data item X, changing its value from old value V1 (for undo) to new value V2 (for redo).
• Commit Record: [Ti, commit] - Indicates transaction Ti has successfully committed.
• Abort Record: [Ti, abort] - Indicates transaction Ti was aborted.

Deferred Database Modification

Under the deferred modification scheme, a transaction postpones all physical database writes until it commits. During execution, all updates are written only to the log.

Recovery Rules:

• If transaction Ti has [Ti, start] and [Ti, commit] in the log, the system executes Redo(Ti) to apply its modifications.
• If transaction Ti has [Ti, start] but does NOT have [Ti, commit] in the log, the system does nothing because no actual changes were written to the database. No Undo operation is needed.

Immediate Database Modification

Under the immediate modification scheme, database modifications can be written directly to the physical disk while the transaction is still active (before it commits).

Recovery Rules:

• If the log contains both [Ti, start] and [Ti, commit], the system executes Redo(Ti).
• If the log contains [Ti, start] but does NOT contain [Ti, commit] or [Ti, abort], the system must execute Undo(Ti) to restore the old values.

Checkpoints

Scanning the entire log from the beginning of time after a system crash is highly inefficient. To avoid this, the system periodically performs Checkpoints.

The Checkpointing Process:

1. Output all log records currently residing in volatile memory (main memory) to stable storage.
2. Output all modified buffer blocks (dirty database pages) to the physical disk.
3. Write a checkpoint record [checkpoint L] to the log on stable storage, where L is a list of all active transactions at the time of the checkpoint.

Checkpoint Benefit: During recovery, the system only needs to scan the log back to the most recent checkpoint record to identify active transactions, saving significant processing time.

Recovery with Concurrent Transactions

When multiple transactions run concurrently, the recovery manager must handle overlapping transactions during system recovery after a crash.

Recovery Algorithm with Checkpoints

When the system recovers from a crash, it searches backward through the log to find the most recent [checkpoint L] record. It then classifies transactions into two lists:

• Redo-List: Transactions that were active during the checkpoint or started after it, and have a commit record in the log.
• Undo-List: Transactions that were active during the checkpoint or started after it, but do NOT have a commit (or abort) record in the log.

Execution Phase

The recovery system processes the log in two passes:

1. Undo Pass: The system scans the log backward from the end, executing Undo for all transactions on the Undo-List. This restores the database to a consistent state.
2. Redo Pass: The system scans the log forward from the checkpoint (or from the oldest active transaction's start record), executing Redo for all transactions on the Redo-List to ensure durability.

Buffer Management

The database buffer is a region of volatile main memory used to cache database blocks from disk. Managing how and when these blocks are written back to disk is critical for recovery correctness.

Buffer Management Policies

Write-Ahead Logging (WAL) Rule

To ensure database atomicity and durability under a Steal policy, the system must adhere strictly to the Write-Ahead Logging (WAL) protocol.

Write-Ahead Logging (WAL) Rule: A modified database block (data block) cannot be written to non-volatile disk storage until the corresponding log records describing the modification have first been written to stable log storage.

If this rule were violated, and the system crashed after writing the data block but before writing the log record, the recovery system would not be able to undo the uncommitted change, violating Atomicity.

Failure with Loss of Non-Volatile Storage

When a physical disk failure occurs, both the active database on disk and the active log are lost. Under these conditions, standard log-based recovery is insufficient.

Archival Dumps (Database Backups)

To survive physical non-volatile storage failures, the system must periodically back up its entire contents to a separate, highly stable archive media (such as magnetic tape or remote cloud storage). This process is called an Archival Dump.

• Physical Backup: An exact copy of the database files from disk to backup media.
• Logical Backup: Exporting the database schema and SQL statements necessary to recreate the database.

Recovery Process after Disk Loss

To recover from a complete disk failure, the database administrator executes the following steps:

1. Replace the physically damaged disk with a new disk.
2. Restore the database to its last known consistent state by loading the most recent Archival Dump.
3. Locate the backup logs created since the last archival dump.
4. Replay the log records forward from the time of the dump to redo all committed transactions, bringing the database up to the point of failure.