Crash Recovery
Open in the Padhaiko app8.1 Failure classification
To maintain the Atomicity and Durability of transactions despite hardware faults or software errors, a DBMS classifies failures according to what storage layers survive:
Three Classes of Database Failures
- Transaction Failure: Affects only a single transaction while the rest of the DBMS continues running.
- Logical error: Transaction cannot continue due to internal conditions such as invalid input, data not found, division by zero, or constraint violation.
- System error: DBMS aborts an active transaction due to an undesirable system state (e.g., deadlock victim rollback or resource timeout).
- System Crash: A power outage, OS panic, or hardware malfunction stops the database engine. Under the fail-stop assumption, volatile storage (RAM buffer pool, CPU registers) is lost, while non-volatile disk storage remains intact and uncorrupted.
- Disk Failure: A physical disk block loses its contents due to a head crash or media corruption during transfer. Recovered using archival database dumps plus archived transaction logs, or via RAID redundancy.
Storage Media Classification for Recovery
- Volatile Storage: Main memory and CPU cache; destroyed on system crash.
- Non-Volatile Storage: Magnetic disks and flash SSDs; survives system crashes, vulnerable to disk failure.
- Stable Storage: Theoretical storage that never loses data—approximated in practice by replicating data blocks across multiple independent non-volatile disks (RAID 1 mirroring or remote replication) with atomic write protocols.
8.2 Recovery and atomicity
When a transaction modifies an item , it updates the buffer block in RAM first, not directly on disk. How the buffer manager schedules disk writes determines what work recovery must perform after a crash:
| Policy Pair | Meaning | Recovery Implication |
|---|---|---|
STEAL vs. NO-STEAL | STEAL allows the buffer manager to flush dirty pages of an uncommitted transaction to disk to free RAM. NO-STEAL forbids flushing dirty pages until commit. | STEAL requires UNDO capability on crash/abort; NO-STEAL avoids UNDO on disk pages. |
FORCE vs. NO-FORCE | FORCE immediately writes all modified pages to disk before allowing COMMIT to finish. NO-FORCE lets modified pages stay cached in RAM after commit. | NO-FORCE requires REDO capability to replay committed updates lost from RAM; FORCE avoids REDO but hurts write speed. |
Most high-performance RDBMSs use STEAL / NO-FORCE (fast RAM caching, fast sequential log flushes), which requires both UNDO and REDO during recovery. All recovery operations must be idempotent—meaning running recovery again after a second crash mid-recovery produces the exact same consistent database state.
8.3 Log-based recovery
The most widely used recovery structure is the system log—an append-only sequence of log records stored on stable storage recording every database modification before it hits data pages.
Standard Log Records and Write-Ahead Logging (WAL)
- Log Record Formats:
- : Transaction has begun.
- : Update record— modified item from old value (before-image) to new value (after-image).
- : Transaction has committed.
- : Transaction has aborted.
- Write-Ahead Logging (WAL) Protocol (Two Mandatory Rules):
- Before any modified data block is written to disk, its corresponding undo log record () must already be flushed to stable storage.
- Before a transaction can enter the Committed state, all of its log records—including —must be flushed to stable storage.
Deferred vs. Immediate Database Modification
| Aspect | Deferred Database Modification | Immediate Database Modification |
|---|---|---|
| When Disk Data Updates Occur | All write(X) outputs are deferred in log/private workspace until after is on stable storage. | Updates may be written to disk data blocks before commits (while is still active). |
| Log Record Content | Needs only the new value : . | Needs both old value and new value : . |
| Crash Recovery Operations | REDO-only: redo committed transactions in forward order; ignore uncommitted transactions (they never touched disk). | UNDO + REDO: undo uncommitted/aborted transactions in reverse log order, then redo committed transactions in forward order. |
Checkpointing
Without checkpoints, crash recovery would have to scan the entire log from the beginning of database history and redo every committed transaction ever run. Checkpointing bounds recovery time:
- Output all log records currently in main memory to stable storage.
- Flush all dirty (modified) buffer blocks to disk.
- Write a checkpoint log record to stable storage, where is the list of transactions currently active at the checkpoint.
During crash recovery, the DBMS scans backward only until it finds the most recent record and stops once it has processed every transaction in (no transaction that committed before that checkpoint ever needs REDO!). Advanced engines such as ARIES refine this with Analysis, Redo (repeating history), and Undo passes using Compensation Log Records (CLRs).
8.4 Shadow paging
Shadow paging is a copy-on-write recovery alternative to logging that eliminates log files for single-user or low-concurrency databases.
Shadow Paging Mechanism
The database is partitioned into fixed-size pages addressed through a page table. Shadow paging maintains two page tables during a transaction:
- Shadow Page Table: Points to the consistent pre-transaction pages on disk. It is never modified during the transaction and is saved on disk.
- Current Page Table: Initialized as a copy of the Shadow Page Table when the transaction starts. Whenever the transaction modifies page , it allocates a brand-new disk block, writes the modified page there, and updates only entry in the Current Page Table—leaving the original page untouched.
- To Abort: Simply discard the Current Page Table and free newly allocated pages; the Shadow Page Table still points to the untouched original data!
- To Commit: Flush all newly modified pages to disk, flush the Current Page Table, and atomically switch a single fixed disk pointer to point to the Current Page Table (making it the new Shadow Page Table).
| Aspect | Log-Based Recovery (WAL) | Shadow Paging |
|---|---|---|
| Disk Updates | In-place updates protected by sequential append-only log writes. | Out-of-place (copy-on-write); never overwrites original pages during active execution. |
| Data Clustering | Preserves contiguous sequential page placement on disk. | Fragments data blocks across disk as modified pages scatter to new locations. |
| Concurrency Support | Supports high concurrency (row/page locking across many active transactions). | Poor concurrency: hard to share one shadow/current page-table pair across multiple concurrent writers. |
| Commit & Cleanup Overhead | Fast sequential log flush; asynchronous dirty-page writes. | High overhead copying large page tables and garbage-collecting orphaned old pages. |
8.5 High availability using remote backup systems
Local disk logs and RAID cannot protect a database from site-wide disasters (fires, floods, earthquakes, prolonged power outages). Remote backup systems achieve high availability by replicating data continuously to a geographically distant backup (secondary) site connected via a network.
Failure Detection and Failover
- The backup site monitors the primary site using periodic heartbeat messages. If the primary fails to respond across multiple timeouts, the backup takes over (failover).
- Hot Spare (Active-Standby): The backup DBMS runs continuously, applying incoming log records in real time so failover completes in seconds.
- Warm / Cold Spare: Backup receives logs or periodic snapshots and must replay backlog or boot up during failover (longer downtime).
| Mode | When Primary Commits a Transaction | Latency & Availability | Data-Loss Risk on Disaster |
|---|---|---|---|
| One-Safe | Primary commits immediately after flushing its local log; sends log records asynchronously to backup. | Fastest commit latency; primary never stalls if backup/WAN goes down. | May lose recent committed transactions whose logs were still in transit when disaster struck. |
| Two-Very-Safe | Primary waits until both local log and remote backup confirm receipt on stable storage before committing. | Highest latency (WAN round-trip per commit); blocks if backup or network fails! | Zero data loss (guaranteed durable at two sites). |
| Two-Safe | Waits for remote confirmation while backup is reachable; if backup disconnects, drops down to one-safe mode. | Balances durability with availability (primary stays online during network splits). | Zero loss during normal operation; minor risk only if both fail simultaneously during a disconnect. |
Worked Out Examples
8.1
Initially, accounts have balances , , and . Using Immediate Database Modification (with WAL), a system crashes right after the last log entry below:
(Wait—suppose updated and before crashing and never committed, while and committed; note in practice strict 2PL prevents from overwriting before commits, or suppose updated —let us trace on literally as logged and observe why reverse-order UNDO then forward-order REDO matters!) Wait: actually assume line 6 is and line 8 is (distinct items and , as enforced by Strict 2PL):
- Line 1:
- Line 2:
- Line 3:
- Line 4:
- Line 5:
- Line 6:
- Line 7:
- Line 8:
- CRASH!
Determine the UNDO list, REDO list, and the final recovered values of .
Classifying Transactions into REDO and UNDO Lists: Scan the log to inspect each transaction's final status at crash time:
- : has both and
REDOlist. - : has but no commit or abort record
UNDOlist. - : has both and
REDOlist.
Executing the UNDO Phase (Backward Scan) Followed by REDO Phase (Forward Scan):
UNDOphase (scan backward for ):- At line 5 : restore (and append ).
REDOphase (scan forward for ):- At line 2 : set .
- At line 7 : set .
UNDOlist: ;REDOlist: .- Recovered values: , , .
8.2
Trace crash recovery on the following log that includes a checkpoint (initial values: ):
- CRASH!
Which log records can be skipped during recovery, and what are the final values of ?
Scanning Backward to the Most Recent Checkpoint:
- Find at line 6.
- Because committed before the checkpoint (line 3), all of 's dirty pages were flushed to disk during the checkpoint! Therefore, lines 1–3 () are completely skipped ( is already safely on disk).
- Active at checkpoint: . Scan backward only as far as needed to find (line 4).
Determining UNDO/REDO Lists and Final Values:
- started before the checkpoint and never committed
UNDO: restore . - started after the checkpoint and committed (line 9)
REDO: set .
- Skipped: (lines 1–3, already durable before the checkpoint).
UNDO: ;REDO: .- Final state: (from disk), (undone), (redone).
8.3
Suppose a database uses Shadow Paging with logical pages () initially mapped by the Shadow Page Table to physical disk blocks [B10, B20, B30, B40]. Transaction modifies logical pages and (allocated free blocks B51 and B52).
- Show the Shadow Page Table and Current Page Table right before commits.
- Explain what happens to the page tables and disk blocks if (a) aborts vs. (b) commits.
Page Tables During Active Execution of :
- Shadow Page Table (unchanged on disk): , , , .
- Current Page Table (updated for modified pages): , , , .
(Original blocks B20 and B40 remain completely untouched on disk!)
Handling Abort vs. Commit:
- (a) If aborts (or crashes before pointer swap): Discard the Current Page Table and return
B51,B52to the free-block list. The Shadow Page Table still points cleanly to[B10, B20, B30, B40]—zero undo I/O needed. - (b) If commits: Flush modified blocks
B51,B52and the Current Page Table to disk, then atomically update the database root pointer to the Current Page Table[B10, B51, B30, B52]. Old blocksB20andB40are freed for reuse.
- Shadow:
[B10, B20, B30, B40]; Current:[B10, B51, B30, B52]. - Abort: discard Current table and free
B51, B52. Commit: flushB51, B52and Current table, atomically swing the root pointer to Current, and freeB20, B40.
Exercises
Practice Exercises — Crash Recovery
Classify the three types of database failures and distinguish between volatile, non-volatile, and stable storage. How is stable storage approximated in real database servers?
Failure Classification:
- Transaction Failure: Single-transaction abort due to logical errors (constraint/input error) or system errors (deadlock abort).
- System Crash: Power/OS/hardware failure wiping volatile RAM while non-volatile disk contents survive (fail-stop assumption).
- Disk Failure: Physical destruction/corruption of disk blocks, requiring media replacement and restoration from archival backups + logs or RAID mirrors.
Storage Hierarchy for Recovery:
- Volatile storage (RAM/cache) loses contents on power loss; non-volatile storage (HDD/SSD) survives crashes; stable storage is an idealized medium that never loses data.
- In practice, stable storage is approximated by mirroring data across multiple independent disks (RAID 1) with separate controllers, or replicating logs to a remote backup site using atomic write protocols.
Failures are classified into transaction failures, system crashes, and disk failures. Volatile memory is lost on crash, non-volatile disk survives crashes, and stable storage (approximated via RAID mirroring and remote log replication) protects against disk loss.
State the two rules of Write-Ahead Logging (WAL), and explain how the buffer manager's STEAL / NO-STEAL and FORCE / NO-FORCE policies dictate whether UNDO and REDO are required during recovery.
Write-Ahead Logging (WAL) Rules:
- Undo Rule: An update log record must be written to stable storage before the modified data block is flushed to disk.
- Redo Rule: All log records of , including , must be flushed to stable storage before is declared committed.
STEAL/NO-STEAL and FORCE/NO-FORCE:
STEALlets uncommitted dirty buffers hit disk requiresUNDOon crash (NO-STEALdoes not).NO-FORCElets committed transactions keep dirty pages in RAM without immediate data-block disk writes requiresREDOon crash (FORCEdoes not).
Most modern DBMSs adopt STEAL / NO-FORCE, requiring both UNDO and REDO.
WAL requires flushing undo log records before dirty data pages hit disk and flushing all log records + commit record before commit completes. STEAL necessitates UNDO and NO-FORCE necessitates REDO.
Compare Deferred Database Modification and Immediate Database Modification in log-based recovery. Why is checkpointing essential in large production databases?
Deferred vs. Immediate Modification:
- Deferred Modification: Holds all writes in buffers/log until is safely logged; never modifies disk before commit, so recovery needs only
REDO(noUNDO). - Immediate Modification: Permits uncommitted updates to be written to disk during execution (
STEAL); logs both old and new values, so recovery performsUNDO(reverse order) thenREDO(forward order).
Role of Checkpointing: Without checkpoints, a server running for months would accumulate gigabytes of log records, forcing crash recovery to scan and redo millions of ancient committed transactions. Checkpointing periodically flushes dirty buffer pages and records , bounding recovery log scans to transactions active at or started after the last checkpoint.
Deferred modification defers disk writes until commit (REDO-only), whereas immediate modification permits uncommitted disk writes (UNDO + REDO). Checkpointing bounds crash-recovery time by flushing dirty buffers and recording active transactions so earlier committed history can be skipped.
Describe Shadow Paging and list three major drawbacks that make log-based recovery preferable to shadow paging in modern multi-user RDBMSs.
Shadow Paging Mechanism: Shadow paging maintains a read-only Shadow Page Table (pointing to pre-transaction disk blocks) and a Current Page Table (pointing modified pages to newly allocated disk blocks). Commit atomically swaps the root pointer to the Current Page Table; abort simply discards it.
Three Drawbacks of Shadow Paging:
- Data Fragmentation: Copying modified pages to new disk blocks destroys physical contiguity/clustering, slowing sequential scans.
- High Commit & Page-Table Overhead: Large databases require copying huge page tables and flushing them on every commit, plus running garbage collection to reclaim orphaned old blocks.
- Poor Concurrency: Coordinating multiple concurrent transactions sharing a single global page table without overwriting each other's uncommitted changes is extremely complex compared to WAL + row locking.
Shadow paging uses copy-on-write pages and swaps a root pointer between Shadow and Current page tables on commit. It is rarely used in multi-user RDBMSs because it causes disk fragmentation, incurs page-table copy and garbage-collection overhead, and handles concurrent transactions poorly.
- Given initial values , , and log entries before a crash: Determine the recovered values of and under Immediate Database Modification.
- Compare one-safe, two-safe, and two-very-safe synchronization in remote backup systems.
Recovering and :
- has REDO : .
- lacks a commit record UNDO : restore .
Remote Backup Synchronization Modes:
- One-safe: Primary commits locally without waiting for remote backup acknowledgement (fast, high availability, risks losing latest commits on sudden primary destruction).
- Two-very-safe: Primary waits for remote backup confirmation before committing (zero data loss, stalls if WAN or backup fails).
- Two-safe: Waits for remote confirmation while backup is online, and automatically falls back to one-safe if the backup becomes unreachable.
- Recovered state: (redone), (undone).
- One-safe commits locally first (fast, slight loss risk); two-very-safe always waits for remote ack (zero loss, blocks on link failure); two-safe waits when connected and degrades to one-safe if disconnected.