Database Recovery & Shadow Paging: Crash Handling & Rollback

TAKEAWAYS:

• Databases use checkpoints and transaction logs to track changes before a crash, enabling rollback to a consistent state.
• Shadow paging creates a full copy of the database on disk (a "shadow") and swaps it in when needed, allowing instant recovery without complex rollback.
• Before-image logging (pre-write) and after-image logging (post-write) are two logging strategies, each with trade-offs in recovery speed and space.
• Concurrent transactions can corrupt data; recovery ensures no lost updates or dirty reads after a crash.
• Recovery algorithms like ARIES (Adaptive Recovery Using Log Information and Shadowing) combine logging and shadow paging for efficiency.
• Real-world use: eSewa’s transaction logs ensure no failed payments are lost; Ncell’s call records recover from server crashes.

1. Why Databases Need Recovery

Databases store critical data (bank transactions, user accounts, inventory). If a system crashes mid-transaction, the database may become inconsistent:

• Uncommitted transactions may have written partial data.
• Locks may be held indefinitely, blocking other users.
• Disk corruption can destroy pages.

Recovery restores the database to a consistent state after a failure. It relies on:

• Transaction logs (a journal of all changes).
• Checkpoints (periodic snapshots of the database state).
• Shadow paging (a full backup copy for instant rollback).

2. Transaction Logs: The Database’s Diary

A transaction log records every change before it’s written to disk. Log entries include:

• Before-image (old data, for rollback).
• After-image (new data, for redo).
• Operation type (insert, update, delete).

Logging Strategies

Example: Bank Transfer Crash Suppose a transfer from Account A to Account B fails mid-execution. The log might look like:

<START TRANSACTION>
<BEFORE-IMAGE: A.balance = 1000>
<UPDATE: A.balance = 900>
<AFTER-IMAGE: A.balance = 900>
<BEFORE-IMAGE: B.balance = 500>
<UPDATE: B.balance = 500>
<AFTER-IMAGE: B.balance = 600>
<COMMIT>

If the system crashes before commit, the log helps:

• Undo: Revert A’s balance to 1000 (using before-image).
• Redo: Apply B’s balance update (using after-image).

3. Checkpoints: Periodic Snapshots

A checkpoint is a snapshot of the database state at a given time. It:

• Reduces log size by marking all committed transactions up to that point.
• Speeds up recovery by avoiding scanning the entire log.

Checkpoint Process:

1. Flush buffers to disk (ensure all recent changes are saved).
2. Write a checkpoint record to the log (e.g., CHECKPOINT: TID=123).
3. Mark all active transactions as completed.

Example: eSewa’s Checkpoint eSewa (Nepal’s digital wallet) takes checkpoints every 5 minutes. If a crash occurs:

• It scans the log from the last checkpoint.
• Only transactions after the checkpoint need redo/undo.

4. Shadow Paging: The Instant Backup

Shadow paging is a copy-on-write technique where:

• The database has a primary page (active version) and a shadow page (backup).
• When a transaction modifies a page, it writes to the shadow page instead.
• On commit, the shadow page becomes the new primary page.

How Shadow Paging Works

sequenceDiagram
    participant DB as Database
    participant Shadow as Shadow Page
    participant Transaction as Active Transaction

    Transaction->>DB: Requests update to Page X
    DB->>Shadow: Writes to shadow page (copy of X)
    Transaction->>Shadow: Commits (shadow becomes primary)
    DB->>Shadow: Swaps shadow and primary

Advantages:

• Instant recovery: Swap the shadow back in if the primary crashes.
• No complex rollback: Unlike logging, shadow paging avoids scanning logs.

Disadvantages:

• Space overhead: Requires double the disk space.
• Slower writes: Copying pages to shadow slows performance.

Example: Daraz’s Order Processing Daraz (Nepal’s Amazon) uses shadow paging for order updates:

• When a customer updates an order, the change is written to a shadow page.
• If the server crashes, Daraz swaps the shadow page back in, ensuring no lost updates.

5. Recovery Algorithms: Putting It All Together

The ARIES (Adaptive Recovery Using Log Information and Shadowing) algorithm combines:

1. Analysis Phase: Scans the log to find the last checkpoint.
2. Redo Phase: Applies all committed transactions (using after-images).
3. Undo Phase: Rolls back uncommitted transactions (using before-images).
4. Shadow Swap: If shadow paging is used, swaps the shadow back in.

ARIES Workflow:

stateDiagram-v2
    [*] --> Analysis
    Analysis --> Redo: "Scan log from checkpoint"
    Redo --> Undo: "Apply committed changes (redo phase)"
    Undo --> UndoUncommitted: "Roll back uncommitted (undo phase)"
    UndoUncommitted --> ShadowSwap: "Swap shadow if used"
    ShadowSwap --> [*]: "Restore database"
    Note right of Redo: "After-images"
    Note right of UndoUncommitted: "Before-images"

6. Handling Concurrent Transactions

When multiple users access the database simultaneously, concurrency control ensures:

• No lost updates (e.g., two users edit the same record).
• No dirty reads (reading uncommitted data).
• Isolation levels (e.g., Read Committed, Repeatable Read) define how transactions see each other.

Example: Kathmandu Traffic Routes Imagine two Pathao drivers updating the same route:

• Driver A updates the route to Gyaneshwor.
• Driver B updates it to Budhanilkantha before A commits. If no concurrency control exists, Driver B’s update might overwrite A’s, causing confusion.

7. Real-World Applications

In the Real World

1. eSewa’s Transaction Logs

   • Idea: Uses write-ahead logging to ensure no failed payments are lost.
   • How: Every transaction (e.g., paying a bill) is logged before execution. If the server crashes, eSewa redoes successful transactions and undoes failed ones.

2. Ncell’s Call Records

   • Idea: Uses checkpoints to recover call logs after crashes.
   • How: Ncell takes checkpoints every hour. If a crash occurs, it restores the last good state and reapplies recent logs.

3. NEPSE’s Stock Trades

   • Idea: Uses shadow paging for instant recovery of trade data.
   • How: Every trade update is written to a shadow page. If NEPSE’s server crashes, the shadow page is swapped back in, ensuring no lost trades.

8. Worked Example: Recovery from a Crash

Scenario: A university database crashes after processing 3 transactions:

1. T1: Withdraws ₹500 from Account 101.
2. T2: Deposits ₹300 into Account 102 (uncommitted).
3. T3: Transfers ₹200 from Account 101 to Account 103 (committed).

Log Entries:

<START T1>
<BEFORE: A101 = 2000>
<UPDATE: A101 = 1500>
<AFTER: A101 = 1500>
<COMMIT T1>

<START T2>
<BEFORE: A102 = 1000>
<UPDATE: A102 = 1300>
<AFTER: A102 = 1300>
<CRASH>

Recovery Steps:

1. Find last checkpoint: Assume checkpoint was taken before T1.
2. Redo Phase: Apply T1’s commit (A101 = 1500).
3. Undo Phase: Roll back T2 (A102 = 1000).
4. Shadow Swap: If shadow paging was used, swap the shadow back in.

Final State:

• A101: ₹1500 (T1 committed).
• A102: ₹1000 (T2 rolled back).
• A103: Unchanged (T3 was committed before the crash).

9. Comparison: Logging vs. Shadow Paging

10. Exam Tip

• Focus on definitions: Know what checkpoints, shadow paging, and ARIES are.
• Diagrams are key: Draw the shadow paging process and ARIES workflow for full marks.
• Worked examples: Practice recovering from crashes using logs (like the bank transfer example).
• Real-world tie-ins: Link to eSewa, Ncell, or Daraz in your answers.
• Avoid vague answers: Examiners mark down generic statements like "recovery ensures data integrity." Instead, say:

  "Shadow paging creates a full backup copy (shadow) of the database. When a crash occurs, the shadow is swapped back in, ensuring zero data loss without complex rollback."

erDiagram
    Database ||--o{ Transaction : "contains"
    Transaction ||--o{ LogEntry : "logs"
    LogEntry ||--|| Checkpoint : "belongs to"
    Database ||--o{ ShadowPage : "has backup"
    Transaction ||--o{ ShadowPage : "shadows"
    Note for Transaction : "Active transactions"
    Note for ShadowPage : "Shadow copy of database pages"