Transaction processing - Recovery and Advanced Techniques

Methodology and Recovery Techniques Introduction Database systems must handle unexpected failures gracefully. When transactions fail, users expect their data to remain consistent—either all changes from a transaction are applied, or none of them are. When entire systems crash, organizations need to recover their databases to a known state without losing committed work. This section covers the key techniques transaction-processing systems use to achieve these goals: rollback (undoing incomplete work), rollforward (reapplying committed work), and deadlock resolution (preventing transactions from getting stuck). Rollback Procedure When a transaction fails before completing, the system must undo any changes it made. This is where before images become essential. A before image is a snapshot of database values before a transaction modifies them. Transaction-processing systems maintain these snapshots during transaction execution. If a problem occurs—such as a violation of data integrity constraints, system error, or explicit user cancellation—the system uses the before images to restore the database to exactly the state it was in before the transaction began. Why this matters: Without before images, a failed transaction could leave the database in a partially-updated state, corrupting data that other transactions depend on. By restoring all before images, the system guarantees that either the entire transaction's effects are visible, or none of them are—this is the atomicity property of transactions. Example: Imagine a transaction transfers $100 between two bank accounts. It updates Account A (subtracts $100) but crashes before updating Account B (adding $100). The before images allow the system to reverse the Account A change, restoring the original balance so no money disappears. Rollforward (After-Image Journal) While rollback handles incomplete transactions, rollforward handles complete system failures—like power outages or hardware crashes. This is where after images become critical. An after image is a record of values after a transaction modifies them. Transaction-processing systems maintain a separate journal of all after images (often called an audit trail or transaction log). This journal is typically written to stable storage that survives crashes, like a dedicated hard drive or tape. When a complete database failure occurs, recovery happens in two stages: Restore from backup: The system restores the most recent complete database backup. However, this backup only reflects the state of the database at the time it was created. Any transactions committed after the backup was taken are not yet in the restored database. Roll forward using the after-image journal: The system then replays all after images from transactions that committed between the backup point and the failure. This brings the database forward to include all committed work. Why after images are separate from backups: Storing after images in a journal (rather than in the backup itself) is more efficient. The journal grows incrementally as transactions commit, while backups are large files created periodically. By keeping them separate, the system can create backups without constant updates, yet still recover recent transactions through the journal. Example: A backup is taken Monday at 9 AM. On Monday at 5 PM, the system crashes. The backup contains all data up to 9 AM. The after-image journal records every committed transaction between 9 AM and 5 PM. Recovery restores the backup, then replays the journal to recover transactions from 9 AM to 5 PM. Backup and Recovery Process The backup and recovery process coordinates rollback and rollforward into a complete recovery strategy. The fundamental gap: When a system fails, the most recent backup is restored. However, this backup is necessarily older than the failure point—it represents the database state at the time the backup was created. This means any transactions committed after the backup but before the failure are not yet restored. How recovery bridges this gap: The system identifies which transactions committed between the backup point and the failure (by checking timestamps in the transaction log) It retrieves the after images for these transactions from the journal It applies these after images in commit order, effectively rolling the database forward This process guarantees that all committed transactions are recovered, even if the database system crashed seconds after they committed. The tradeoff: More frequent backups reduce the amount of journal data that must be replayed during recovery (faster recovery), but cost more in storage and processing time. Less frequent backups save resources but require replaying longer periods of the journal during recovery. Deadlock Detection and Resolution A deadlock is a situation where two or more transactions cannot proceed because each holds a resource that another needs. How deadlocks occur: Consider two transactions running concurrently: Transaction A locks Record 1, then tries to lock Record 2 Transaction B locks Record 2, then tries to lock Record 1 If Transaction A acquires Record 1 while Transaction B acquires Record 2, then both transactions are blocked waiting for each other's records. Neither can proceed—both are stuck indefinitely. Deadlock detection: Transaction-processing systems detect these circular wait conditions by monitoring which transactions hold which locks. When the system detects a deadlock, it must break the cycle. Deadlock resolution strategies: Cancel all involved transactions: The system rolls back all deadlocked transactions using their before images, then automatically restarts them in a different order. This is a safe but costly approach, as all work done by these transactions is undone. Cancel one transaction (victim selection): The system selects one deadlocked transaction as the "victim," rolls it back, and restarts it after a brief delay. Other transactions can then proceed. This minimizes lost work but increases the delay for the restarted transaction. The choice of strategy depends on the workload. Systems with many small transactions often use victim selection, while systems with long-running transactions may prefer rolling back all involved transactions. Prevention vs. detection: Some systems try to prevent deadlocks by enforcing strict ordering rules (all transactions must lock resources in the same order). Others accept that deadlocks may occur and rely on detection and resolution. Compensating Transaction In some environments, the rollback mechanisms described above are not available or are undesirable. Compensating transactions provide an alternative recovery strategy. A compensating transaction is an additional transaction that undoes the effects of a failed transaction by performing the opposite operations. Rather than reverting to before images, the system creates new transactions that counteract the changes. When compensating transactions are used: Distributed systems where before images cannot be maintained across multiple databases Long-running transactions where holding locks for rollback is impractical External systems where you've already sent data outside the database and cannot retrieve it Audit requirements where you need to preserve the record of the original failed transaction rather than erasing it Example: A manufacturing system records a sale and decrements inventory. If payment fails, instead of using before images to restore the sale record and inventory count, the system might create a compensating transaction that records a "reversal of sale" and increments inventory back. The original failed transaction remains in the audit trail, but the system's state is restored. Important limitation: Compensating transactions restore the state of the system but not the history. The failed transaction's record persists. In contrast, rollback using before images completely removes evidence that the failed transaction ever occurred. This makes compensating transactions more suitable for regulated environments with audit requirements.