Recovery Algorithms Overview

When a database crashes, how does it come back to life with all committed data intact and no trace of incomplete transactions? The answer lies in recovery algorithms—carefully designed procedures that analyze what happened before the crash and restore the database to a consistent state.

Recovery algorithms represent decades of computer science research. From the early, simple approaches that traded performance for simplicity, to ARIES—the sophisticated algorithm that enables high-performance databases to recover correctly from any failure scenario—this evolution tells the story of how database theory became practice.

Understanding recovery algorithms at a conceptual level prepares you to appreciate the detailed algorithms in subsequent chapters and to make informed decisions about database selection and configuration.

Recovery algorithms can be classified along several dimensions. Understanding these dimensions clarifies why different algorithms exist and which scenarios each addresses best:

Key Classification Dimensions:

The Fundamental Recovery Requirements:

All recovery algorithms must provide:

1. Atomicity: Uncommitted transactions must leave no trace after recovery
2. Durability: Committed transactions must be fully present after recovery
3. Correctness: The recovered database must be in a consistent state
4. Restartability: Recovery must succeed even if the system crashes during recovery

Undo and Redo Capabilities:

Most modern databases use STEAL/NO-FORCE because it provides maximum flexibility for the buffer manager, even though it requires the most sophisticated recovery.

Deferred update is conceptually the simplest recovery approach. Under this scheme, modifications are not written to the database until after the transaction commits. All modifications are kept in memory and written to a log, but the actual database pages remain unchanged until commit time.

Deferred Update Algorithm:

Where Deferred Update is Used:

Deferred update is rarely used in production OLTP databases due to its limitations. However, it appears in:

• In-memory databases: Where 'writing to disk' happens only at checkpoint time
• Transaction-isolated analytics: Where long-running analytical transactions build result sets in memory
• Simple embedded databases: Where implementation simplicity is valued over performance

The fundamental limitation is that NO-STEAL policy prevents the buffer manager from evicting dirty pages from uncommitted transactions, which can exhaust memory under concurrent load.

Immediate update allows modifications to be written to the database before the transaction commits. This is the STEAL policy—dirty pages can be 'stolen' from the buffer pool and written to disk even if their transaction is still active.

Immediate Update Algorithm:

The UNDO/REDO Challenge:

Immediate update recovery is more complex because:

1. Pages on disk may contain uncommitted modifications — These must be undone
2. Pages on disk may be missing committed modifications — These must be redone
3. Order matters — Redo must happen before undo to establish correct page state
4. Crash during recovery — Must handle crashes during undo (CLRs needed)

Log Record Requirements:

┌─────────────────────────────────────────────────────────┐
│  Immediate Update Log Record                            │
├─────────────────────────────────────────────────────────┤
│  LSN: Unique log sequence number                        │
│  Transaction ID: Which transaction                       │
│  Previous LSN: Previous record for this transaction     │
│  Page ID: Which page was modified                       │
│  Offset: Where on the page                              │
│  Before Image: Old value (for UNDO)                     │
│  After Image: New value (for REDO)                      │
│  Operation Type: INSERT/UPDATE/DELETE                   │
└─────────────────────────────────────────────────────────┘

Before images enable undo; after images enable redo. Both are required.

Shadow paging takes a completely different approach to recovery by never overwriting existing data. Instead, modifications create new pages, and commit atomically switches from old pages to new pages.

Shadow Paging Concept:

BEFORE TRANSACTION:

  Page Table (Current)        Data Pages
  ┌─────────────────┐        ┌──────────────┐
  │ Page 0 → Addr A │───────▶│  Original    │ (Address A)
  │ Page 1 → Addr B │───────▶│  Original    │ (Address B)
  │ Page 2 → Addr C │───────▶│  Original    │ (Address C)
  └─────────────────┘        └──────────────┘
        │
        └── Shadow (Copy)
            ┌─────────────────┐
            │ Page 0 → Addr A │
            │ Page 1 → Addr B │  (Identical at start)
            │ Page 2 → Addr C │
            └─────────────────┘

DURING TRANSACTION (modify Page 1):

  Current Page Table         Shadow Page Table      Data Pages
  ┌─────────────────┐       ┌─────────────────┐    ┌──────────────┐
  │ Page 0 → Addr A │       │ Page 0 → Addr A │───▶│  Original    │ (A)
  │ Page 1 → Addr B │       │ Page 1 → Addr D │───▶│  Modified!   │ (D) NEW
  │ Page 2 → Addr C │       │ Page 2 → Addr C │───▶│  Original    │ (C)
  └─────────────────┘       └─────────────────┘    └──────────────┘

COMMIT: Atomically replace Current Page Table pointer with Shadow Page Table
        Now Address D is the official Page 1; Address B can be reclaimed

Where Shadow Paging is Used:

• SQLite: Uses a simplified form of shadow paging (rollback journal) for single-writer transactions
• LMDB: Memory-mapped database using copy-on-write B-trees (shadow paging variant)
• File system journaling: Many journaling file systems use shadow-like techniques

Shadow paging's main weakness—difficulty with concurrent transactions—limits its use in high-concurrency OLTP systems. However, its simplicity makes it attractive for embedded databases and copy-on-write file systems.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the dominant recovery algorithm in modern database systems. Developed at IBM Research in the early 1990s, ARIES provides a comprehensive framework for recovery that handles all the complexities of STEAL/NO-FORCE buffer management.

ARIES Design Principles:

ARIES Three-Phase Recovery:

    ┌─────────────────────────────────────────────────────────────────┐
    │                       ARIES RECOVERY                            │
    └─────────────────────────────────────────────────────────────────┘
                                   │
    ┌──────────────────────────────┼──────────────────────────────────┐
    │                              │                                  │
    ▼                              ▼                                  ▼
┌──────────┐                 ┌──────────┐                      ┌──────────┐
│ ANALYSIS │                 │   REDO   │                      │   UNDO   │
│  PHASE   │                 │  PHASE   │                      │  PHASE   │
├──────────┤                 ├──────────┤                      ├──────────┤
│ Scan log │                 │ Repeat   │                      │ Rollback │
│ forward  │                 │ history: │                      │ loser    │
│ from     │                 │ redo all │                      │ trans-   │
│ last     │────────────────▶│ logged   │─────────────────────▶│ actions  │
│ check-   │                 │ actions  │                      │ using    │
│ point    │                 │ since    │                      │ log      │
│          │                 │ redo     │                      │          │
│ Build:   │                 │ point    │                      │ Write    │
│ • ATT    │                 │          │                      │ CLRs     │
│ • DPT    │                 │ Compare  │                      │          │
│          │                 │ LSNs     │                      │          │
└──────────┘                 └──────────┘                      └──────────┘
      │                            │                                 │
      │                            │                                 │
      └────────────────────────────┴─────────────────────────────────┘
                                   │
                                   ▼
                        Database Consistent!

Phase Purposes:

Recovery algorithms differ in what information they log. This choice affects log size, recovery complexity, and concurrency:

Logging Granularity Options:

Physical Logging:

Log Record: "At page 42, offset 128, replace bytes [A,B,C,D] with [W,X,Y,Z]"

• Exact byte location and content
• Simple redo/undo: just copy bytes
• Large logs: every byte change recorded
• Parallelism limited: concurrent changes to same page conflict

Logical Logging:

Log Record: "INSERT into Employee table: (id=42, name='Alice', dept=5)"

• High-level operation
• Compact logs: just operation and parameters
• Complex redo: must re-execute the insert (find free space, update indexes...)
• Concurrent logical operations can be serialized differently

Physiological Logging (ARIES Approach):

Log Record: "On page 42: INSERT row at slot 7, content = [...]"

• Physical location (page 42) + logical operation (insert at slot)
• Middle ground: more compact than physical, simpler than pure logical
• Redo is 'local' to a single page (doesn't need to find the page)
• ARIES uses this to enable efficient parallel redo

Let's bring together all the recovery algorithms into a comprehensive comparison:

Why ARIES Dominates:

ARIES became the industry standard because it achieves the best combination of:

1. Maximum buffer manager flexibility — STEAL/NO-FORCE allows optimal buffer utilization
2. Fast commits — NO-FORCE means commit only requires log force, not data page force
3. Large transaction support — STEAL allows arbitrary transaction size
4. High concurrency — Physiological logging and fine-grained locking
5. Recovery restartability — CLRs ensure recovery survives crashes during recovery
6. Theoretical correctness — Proven correct in academic literature
7. Battle-tested implementation — Decades of production experience

The Complexity Cost:

ARIES's sophistication comes with implementation complexity. The algorithm has many subtle details:

• Checkpoint and restart logic
• CLR generation and processing
• LSN management and comparison
• Fuzzy checkpoint coordination
• Parallel redo optimization

This complexity is why database recovery code is among the most carefully reviewed and tested in any software system.