Recovery System ShortNotes

16.1 Failure Classification

Goal: Database systems must maintain atomicity (all-or-nothing transactions) and durability (committed changes persist) despite failures. Recovery schemes restore the database to a consistent, correct state after a failure.
High Availability: Minimizing the duration during which the database is unavailable after a failure.
Failure Types:
- Transaction Failure:
  - Logical Error: The transaction cannot proceed due to internal conditions. Examples:
    - Bad input.
    - Data not found.
    - Overflow (numeric value too large).
    - Resource limit exceeded.
  - System Error: The entire system enters an undesirable state, preventing the transaction from continuing. Example:
    - Deadlock (transactions waiting for each other).
    - The transaction can often be retried later.
- System Crash:
  - Hardware malfunction or software bug (in database software or operating system).
  - Causes loss of volatile storage (e.g., RAM, cache) content.
  - Nonvolatile storage (e.g., disk) content remains intact. This is called the fail-stop assumption.
- Disk Failure:
  - A disk block loses its contents. Causes:
    - Head crash.
    - Failure during data transfer.
  - Recovery relies on:
    - Copies of data on other disks.
    - Archival backups (e.g., DVDs, tapes).

16.2 Storage

Classification of Storage Media: $B a se d o n s p ee d, c a p a c i t y, an d f ai l u re res i l i e n ce$ .

Storage Types:
- Volatile Storage:
  - Information is lost when the system crashes.
  - Examples: Main memory (RAM), CPU caches.
- Nonvolatile Storage:
  - Information survives system crashes.
  - Examples: Disk drives, solid-state drives (SSDs), magnetic tape.
- Stable Storage:
  - A theoretical ideal: Information is never lost.
  - Approximated in practice, but never perfectly achieved.
16.2.1 Stable-Storage Implementation
- Goal: Approximate stable storage to ensure data survival.
- Method:
  - Replicate information across multiple nonvolatile storage devices (typically disks).
  - These devices should have independent failure modes (i.e., they are unlikely to fail simultaneously).
  - Controlled updates to ensure data consistency even during transfer failures.
- RAID Systems: Use redundancy to protect against disk failures. Mirrored disks (RAID 1) provide the simplest and fastest form, keeping two copies of each block.
- Remote Backup Systems: Maintain a copy of each stable storage block at a remote site (via a network). Protects against disasters (fire, flood) affecting the primary site.
- Data-Transfer Failure Outcomes:
  - Successful Completion: Data transferred correctly to the destination.
  - Partial Failure: A failure occurs during transfer; the destination block contains incorrect information.
  - Total Failure: Failure occurs early enough that the destination block remains unchanged (and thus still valid).
- Stable-Storage Write Protocol (using two physical blocks):
  1. Write the information to the first physical block.
  2. Only after the first write completes successfully, write the same information to the second physical block.
  3. The output operation is considered complete only after the second write completes successfully.
- Recovery Procedure:
  - Case 1: Both blocks identical and no errors: No action is needed.
  - Case 2: One block has a detectable error: Replace the erroneous block with the content of the other (good) block.
  - Case 3: Blocks differ, but no errors: Replace the content of the first block with the content of the second block.
  - $N o n v o l a t i l e R A M i s u se d t o t r a c k b l oc k t ha t a re b e in g w r i tt e n .$
- Key Point: This protocol ensures that a write to stable storage either completely succeeds (all copies updated) or results in no change (original data preserved).
16.2.2 Data Access
- Database Location: Primarily resides on nonvolatile storage (usually disks). Only parts of the database are in main memory at any given time.
- Blocks:
  - Database is partitioned into fixed-length storage units called blocks.
  - Blocks are the units of data transfer between disk and main memory.
  - Assumption: A single data item does not span multiple blocks.
  - Physical Blocks: Blocks residing on the disk.
  - Buffer Blocks: Blocks residing temporarily in main memory (in the disk buffer).
  - Disk Buffer: The area of memory holding buffer blocks.
- Block Movement Operations:
  - $input (B)$ : Transfers physical block $B$ from disk to a buffer block in main memory.
  - $output (B)$ : Transfers buffer block $B$ from main memory to disk, replacing the corresponding physical block on disk.
- Transaction Work Area: Each transaction $T_{i}$ has a private work area in memory. Copies of data items accessed and updated by $T_{i}$ are kept here.
- First Access: $Wh e n a t r an s a c t i o n T_{i} n ee d s t o a ccess d a t a X f or t h e f i rs t t im e, i t m u s t c a ll re a d (X) .$
- Data Access Operations (for transaction $T_{i}$ ):
  - $read (X)$ :
    1. If block $B_{X}$ (containing data item $X$ ) is not already in main memory, issue $input (B_{X})$ .
    2. Assign the value of $X$ (from the buffer block $B_{X}$ ) to the transaction’s local variable $x_{i}$ .
  - $write (X)$ :
    1. If block $B_{X}$ (containing data item $X$ ) is not already in main memory, issue $input (B_{X})$ .
    2. Assign the value of the transaction’s local variable $x_{i}$ to $X$ within the buffer block $B_{X}$ .
- Important Note: $read (X)$ and $write (X)$ may require transferring blocks from disk to memory, but they do not directly cause blocks to be written back to disk.
- Force-Output: $output (B)$ is performed when the buffer manager needs the memory space or the database system wants to make changes persistent on disk.

16.3 Recovery and Atomicity

Central Problem: System crashes can occur during transaction execution, potentially leaving the database in an inconsistent state, violating atomicity.

Example: Transaction \ T_i \ transfer \ \50 \ from \ account \ A \ to \ B.$
- $Initial \ values: \ A = \$ 1000, \ B= $2000$
- $S ys t e m cr a s h occ u rs a f t er o u tp u t (B_{A}) b u t b e f ore o u tp u t (B_{B}) .$
- $Final \ state \ after \ system \ restart: \ A = \$ 950 \ and \ B=$2000.$

Solution: Output information describing the modifications to stable storage before actually modifying the database. This is achieved using a log.
16.3.1 Log Records
- Log: A sequence of log records. Records all update activities performed on the database. The log must reside in stable storage.
- Update Log Record Structure: $⟨ T_{i}, X_{j}, V_{1}, V_{2} ⟩$
  - $T_{i}$ : Transaction identifier (unique ID of the transaction).
  - $X_{j}$ : Data-item identifier (location on disk: block ID and offset within the block).
  - $V_{1}$ : Old value of $X_{j}$ (before the write).
  - $V_{2}$ : New value of $X_{j}$ (after the write).
- Other Log Record Types:
  - $⟨ T_{i} start ⟩$ : Transaction $T_{i}$ has begun execution.
  - $⟨ T_{i} commit ⟩$ : Transaction $T_{i}$ has successfully completed (committed).
  - $⟨ T_{i} abort ⟩$ : Transaction $T_{i}$ has been aborted (rolled back).
- Crucial Rule: The log record for a write operation must be written to stable storage before the corresponding database modification is applied.
16.3.2 Database Modification
- Log-First Principle: A log record is always created before the corresponding database modification.
- Undo Operation: Using a log record, restore a data item to its old value ( $V_{1}$ in the log record).
- Redo Operation: Using a log record, set a data item to its new value ( $V_{2}$ in the log record).
- Modification Steps:
  1. Transaction performs computation in memory.
  2. Transaction modifies data in the disk buffer.
  3. Database executes $o u tp u t$ operation.
- Deferred Modification:
  - Database modifications are performed only after the transaction commits.
  - Transactions work on local copies of data items.
- Immediate Modification:
  - Database modifications can occur while the transaction is still active.
  - This is the approach primarily covered in the chapter.
- Recovery Algorithm Requirements:
  - Handle committed transactions whose changes might only exist in the buffer (not yet written to disk).
  - Handle active transactions that modified the database and need to be aborted due to a failure.
16.3.3 Concurrency Control and Recovery
- Critical Restriction: If transaction $T_{1}$ modifies data item $X$ , no other transaction $T_{2}$ can modify $X$ until $T_{1}$ either commits or aborts.
- Enforcement:
  - Strict Two-Phase Locking: Acquire exclusive locks on updated items and hold them until commit/abort.
  - Snapshot Isolation and Validation: Also acquire exclusive locks (at validation time) and hold them until commit.
16.3.4 Transaction Commit
- $A t r an s a c t i o n T_{i} co mmi t s w h e n t h e l o g recor d < T_{i} co mmi t > ha s b ee n w r i tt e n t o s t ab l e s t or a g e$ .
16.3.5 Using the Log to Redo and Undo Transactions
- $redo (T_{i})$ :
  - Sets all data items updated by $T_{i}$ to their new values, using information from the log records.
  - Order matters: Redo operations must be performed in the same order as the original updates.
- $undo (T_{i})$ :
  - Restores all data items updated by $T_{i}$ to their old values, using information from the log records.
  - Writes redo-only log records during the undo process (see Section 16.4.1).
  - Ends by writing a $⟨ T_{i} abort ⟩$ log record.
- Recovery After a System Crash:
  - Undo: If the log contains $⟨ T_{i} start ⟩$ but no corresponding $⟨ T_{i} commit ⟩$ or $⟨ T_{i} abort ⟩$ record, transaction $T_{i}$ must be undone.
  - Redo: If the log contains $⟨ T_{i} start ⟩$ and either $⟨ T_{i} commit ⟩$ or $⟨ T_{i} abort ⟩$ , transaction $T_{i}$ must be redone. (Even if aborted, redo-only records exist).
16.3.6 Checkpoints
- Motivation: Searching the entire log during recovery is time-consuming, and many redone transactions might have already written their updates to disk. Checkpoints reduce this overhead.
- Simple Checkpoint Procedure:
  1. Output all log records currently in main memory to stable storage.
  2. Output all modified buffer blocks to disk.
  3. Output a log record of the form $⟨ checkpoint L ⟩$ to stable storage, where $L$ is a list of all transactions that are active at the time of the checkpoint.
  - $N o u p d a t e i s a ll o w e d t o p er f or m w hi l e c h ec k p o in t i s in p ro g ress .$
- Recovery Using Checkpoints:
  1. Find the most recent $⟨ checkpoint L ⟩$ record in the log (search backward).
  2. Identify the set of transactions, $T$ , consisting of:
    - Transactions in the list $L$ .
    - Transactions that started after the $⟨ checkpoint L ⟩$ record was written.
  3. Undo: For each transaction $T_{k}$ in $T$ that has no $⟨ T_{k} commit ⟩$ or $⟨ T_{k} abort ⟩$ record in the log, execute $undo (T_{k})$ .
  4. Redo: For each transaction $T_{k}$ in $T$ that has a $⟨ T_{k} commit ⟩$ or $⟨ T_{k} abort ⟩$ record in the log, execute $redo (T_{k})$ .
- Fuzzy Checkpoint: A more advanced technique that allows transactions to perform updates during the checkpointing process (discussed later).

16.4 Recovery Algorithm

16.4.1 Transaction Rollback (during normal operation, not after a crash)
1. Scan Log Backward: Scan the log backward from the end. For each log record of transaction $T_{i}$ of the form $⟨ T_{i}, X_{j}, V_{1}, V_{2} ⟩$ that is found:
  - Write the old value $V_{1}$ to data item $X_{j}$ .
  - Write a special redo-only log record: $⟨ T_{i}, X_{j}, V_{1} ⟩$ . This records the undo operation itself. These are called compensation log records.
    - Note: Redo-only records do not need an “old value” field because undo operations are never undone.
2. Stop: Stop the backward scan when the $⟨ T_{i} start ⟩$ record is found. Write a $⟨ T_{i} abort ⟩$ record to the log.
16.4.2 Recovery After a System Crash
1. Redo Phase: Scan the log forward from the last checkpoint.
  - Initialize a list called undo-list to the list $L$ from the most recent $⟨ checkpoint L ⟩$ record.
  - For each log record encountered:
    - If it’s a normal update record $⟨ T_{i}, X_{j}, V_{1}, V_{2} ⟩$ or a redo-only record $⟨ T_{i}, X_{j}, V_{2} ⟩$ :
      - Perform the redo operation: Write the value $V_{2}$ to data item $X_{j}$ .
    - If it’s a $⟨ T_{i} start ⟩$ record:
      - Add transaction $T_{i}$ to the undo-list.
    - If it’s a $⟨ T_{i} commit ⟩$ or $⟨ T_{i} abort ⟩$ record:
      - Remove transaction $T_{i}$ from the undo-list.
  - At the end of the redo phase, undo-list contains all transactions that were incomplete (neither committed nor fully rolled back) at the time of the crash.
2. Undo Phase: Scan the log backward from the end.
  - For each log record encountered that belongs to a transaction currently in the undo-list:
    - Perform the undo operation (as described in Section 16.4.1), including writing redo-only log records.
  - When a $⟨ T_{i} start ⟩$ record is found for a transaction $T_{i}$ that is in undo-list:
    - Write a $⟨ T_{i} abort ⟩$ record to the log.
    - Remove $T_{i}$ from undo-list.
  - The undo phase terminates when undo-list becomes empty (all incomplete transactions have been rolled back).
- Repeating History: The redo phase replays all updates since the last checkpoint, including updates made by transactions that were later aborted (or are being aborted during recovery). This is called “repeating history.” It simplifies the recovery algorithm, even though it might seem redundant.

Quartz 4

Explorer

Recovery System ShortNotes

Graph View

Backlinks