Recovery Concepts

Every second, databases around the world commit millions of transactions. Users expect their data to persist forever, yet systems crash, power fails, and disks corrupt. Something must stand between chaos and data loss—that something is the Recovery Manager.

The recovery manager is the unsung hero of database systems. It operates silently during normal execution, ensuring every committed transaction is safely recorded. When disaster strikes, it springs into action, meticulously reconstructing the database to a consistent state.

Understanding the recovery manager means understanding how databases deliver on their most fundamental promise: your committed data will survive.

The recovery manager is a specialized component of the database management system responsible for ensuring the atomicity and durability properties of transactions. Let's establish its definition and scope:

Definition: The Recovery Manager is the DBMS component that implements transaction atomicity and durability by managing logging, coordinating with the buffer manager, and executing recovery procedures after failures.

The recovery manager's mission can be summarized as two complementary goals:

The Recovery Manager's Position in the DBMS:

┌──────────────────────────────────────────────────────────────────┐
│                      Application / SQL Engine                     │
└───────────────────────────────┬──────────────────────────────────┘
                                │
                                ▼
┌──────────────────────────────────────────────────────────────────┐
│                      Transaction Manager                          │
│   Coordinates begin, commit, abort decisions                      │
└───────────────────────────────┬──────────────────────────────────┘
                                │
          ┌─────────────────────┼─────────────────────┐
          │                     │                     │
          ▼                     ▼                     ▼
┌─────────────────┐   ┌─────────────────┐   ┌─────────────────────┐
│   Lock Manager  │   │ Recovery Manager│   │  Concurrency Control│
│  (Isolation)    │   │ (A + D in ACID) │   │  (Serialization)    │
└─────────────────┘   └────────┬────────┘   └─────────────────────┘
                               │
          ┌────────────────────┼────────────────────┐
          │                    │                    │
          ▼                    ▼                    ▼
┌─────────────────┐   ┌─────────────────┐   ┌─────────────────────┐
│   Log Manager   │   │  Buffer Manager │   │   Storage Manager   │
│ (Write log file)│   │  (Page caching) │   │   (Disk I/O)        │
└─────────────────┘   └─────────────────┘   └─────────────────────┘

The recovery manager is central—it coordinates with the transaction manager (for commit/abort decisions), the buffer manager (for page writes), and the log manager (for log persistence).

The recovery manager orchestrates multiple critical operations. Each responsibility requires careful design to balance correctness and performance:

Log Record Anatomy:

A typical log record contains:

This structure enables both forward (redo) and backward (undo) traversal, supporting all recovery scenarios.

The recovery manager and buffer manager have an intimate, carefully choreographed relationship. The buffer manager caches database pages in memory for performance, but this caching creates recovery challenges:

The Tension:

• Buffer manager wants to keep modified (dirty) pages in memory to batch disk writes
• Recovery manager needs to ensure recoverability regardless of which pages are in memory

The WAL Solution:

Write-Ahead Logging resolves this tension elegantly. The buffer manager can write dirty pages whenever convenient for performance, as long as it follows the WAL protocol:

WAL Rule: Before writing any dirty page to disk, all log records describing modifications to that page must already be on stable storage.

This ensures that if a crash occurs during or after a page write, the log contains enough information to redo the modification if needed.

Modern Databases: STEAL/NO-FORCE

Most production databases use STEAL/NO-FORCE policies because:

1. STEAL allows flexible buffer management — The buffer manager can evict any page when memory is needed, even if it contains uncommitted modifications. This prevents uncommitted transactions from monopolizing memory.

2. NO-FORCE enables fast commits — Transactions commit when their log records are durable, without waiting for all modified pages to be written. This dramatically reduces commit latency.

The cost of STEAL/NO-FORCE is that recovery must handle both REDO (committed work not yet on data pages) and UNDO (uncommitted work that reached data pages). ARIES, the dominant recovery algorithm, was designed specifically for this policy combination.

The Recovery Manager's Contract with Buffer Manager:

1. Before evicting a dirty page, call recovery manager to ensure WAL compliance
2. Track pageLSN for each buffered page
3. Report dirty page information during checkpoint
4. On recovery, participate in redo by accepting page corrections

Checkpoints are the recovery manager's mechanism for bounding recovery time. Without checkpoints, recovery would need to replay the entire transaction log from database creation—potentially gigabytes or terabytes of log records.

Checkpoint Purpose:

A checkpoint records a snapshot of the database's state at a point in time:

• Which transactions are active (and their status)
• Which pages are dirty (and their LSNs)
• The point in the log where recovery can safely start

After a crash, recovery only needs to process log records from the last checkpoint forward—dramatically reducing recovery time.

Fuzzy Checkpoint Details:

Modern databases use fuzzy checkpoints because they impose minimal disruption:

Time ──────────────────────────────────────────────────────────────▶

        │                                        │
        ▼                                        ▼
   CHECKPOINT_START                        CHECKPOINT_END
        │                                        │
        │    Normal transaction processing       │
        │    continues throughout                │
        │                                        │
        │◀────────────────────────────────────────▶│
        │    Capture ATT (Active Transaction Table)
        │    Capture DPT (Dirty Page Table)

Active Transaction Table (ATT):

• Transaction ID
• Transaction status (active, committing, aborting)
• LastLSN (most recent log record for this transaction)
• UndoNxtLSN (next log record to undo if aborted)

Dirty Page Table (DPT):

• Page ID
• RecoveryLSN (LSN of first log record that dirtied this page since last flush)

The minimum of all RecoveryLSNs in the DPT determines the earliest point from which redo must start—the 'redo point.'

When the database restarts after a failure, the recovery manager executes a systematic recovery process. Most modern databases follow the ARIES algorithm's three-phase approach:

Phase 1: Analysis

• Scan the log forward from the last checkpoint
• Reconstruct the Active Transaction Table (find uncommitted transactions at crash time)
• Reconstruct the Dirty Page Table (find pages that may need redo)
• Determine the 'redo point' (where redo phase should start)

Phase 2: Redo

• Scan the log forward from the redo point
• For each modification record, check if the page needs the modification reapplied
• Compare pageLSN with log record LSN—if pageLSN < logLSN, redo the operation
• This 'repeats history' to restore the database to crash-point state

Phase 3: Undo

• Roll back all uncommitted transactions identified in analysis
• Process transactions in reverse LSN order
• Write Compensation Log Records (CLRs) for each undo action
• CLRs ensure idempotent recovery—crashes during recovery can be recovered

Why Redo Before Undo?

A subtle but critical question: why not undo first? The answer lies in logging:

1. During normal operation, uncommitted modifications might have been written to disk (STEAL policy)
2. The log records for those modifications are also on disk
3. During redo, we restore the database to exactly its crash-point state, including uncommitted modifications
4. Now we can safely undo uncommitted transactions, because all relevant pages are in a known state

If we tried to undo first, pages might not reflect the modifications we're trying to undo (if they hadn't been flushed before the crash).

Recovery Time:

Recovery time depends on:

• Time since last checkpoint (affects log length to process)
• Number of dirty pages (affects redo work)
• Number of uncommitted transactions (affects undo work)
• Disk I/O speed and parallelism

Production systems design checkpoint intervals and recovery parallelism to meet Recovery Time Objectives (RTOs)—often minutes to single-digit minutes for large databases.

Compensation Log Records are a critical innovation in recovery algorithms. They solve a subtle but dangerous problem: what happens if the system crashes during recovery?

The Problem:

Imagine a transaction T1 made modifications M1, M2, M3 and then crashed before commit. During recovery, the undo phase reverses M3, M2... and then another crash occurs. Without CLRs, the next recovery would need to undo M3 again—but M3 might have already been undone. How do we avoid redoing or re-undoing work on recovery restart?

The CLR Solution:

When we undo an operation, we log the undo as a Compensation Log Record. CLRs have special properties:

CLR Example:

Original log sequence for transaction T1:

 LSN 100: T1, Update page P1 (old=A, new=B)
 LSN 150: T1, Update page P2 (old=X, new=Y)
 LSN 200: T1, Update page P3 (old=M, new=N)
 [CRASH - T1 never committed]

During first recovery, undo phase generates CLRs:

 LSN 300: CLR for LSN 200 (undid P3: N→M), UndoNxtLSN=150
 LSN 350: CLR for LSN 150 (undid P2: Y→X), UndoNxtLSN=100
 [CRASH DURING RECOVERY]

During second recovery:
 - Analysis finds T1 is uncommitted, last CLR is LSN 350
 - Redo replays CLRs 300 and 350 (if not already on pages)
 - Undo follows UndoNxtLSN pointer from LSN 350 → LSN 100
 - Generates CLR for LSN 100, completes undo

The already-undone operations (LSN 200, 150) are skipped via UndoNxtLSN pointers.

This mechanism guarantees that recovery is idempotent—running recovery multiple times produces the same correct result, regardless of how many crashes occur during recovery.

Implementing a robust recovery manager involves numerous practical challenges beyond the algorithm itself:

Real-World Recovery Manager Examples:

Double-Write Buffer (InnoDB):

InnoDB addresses the torn page problem (crash during partial page write) with a double-write buffer. Before writing a page to its actual location, InnoDB first writes it to a contiguous double-write area. If a crash causes a torn page write, recovery can restore the page from the double-write buffer. This provides additional protection beyond standard WAL.

The recovery manager is the guarantor of atomicity and durability—two of the four pillars that make transactional databases trustworthy. Let's consolidate the key insights:

What's Next:

The recovery manager depends on a critical abstraction: stable storage—storage that survives failures. But what makes storage 'stable'? The next page explores stable storage concepts, including how databases use disk redundancy, replication, and carefully designed I/O patterns to create the reliable storage foundation that recovery depends upon.