Database recovery techniques

Database recovery techniques
• There are many different approaches to recover a database: Manual reprocessing, a variety of automated recovery techniques.
1. Manual Reprocessing
• The database is periodically backed up (a database save) and all transactions applied since the last save are recorded
• If the system crashes, the latest database save is restored and all of the transactions are re-applied (by users) to bring the database back up to the point just before the crash.
• Limitations:
1. Time required to reapply transactions
2. Transactions might have other (physical) potential failures
3. Reapplying concurrent transactions is not straight forward.
2. Automated Recovery
• There are several types of automated recovery techniques including: deferred update and immediate update, shadow paging, etc.
• A transaction can be in one of the following states:
o Active - when the transaction just begins
o Partially Committed - after the last operation has completed (but before the commit point is reached)
o Failed - Normal operation is prevented (e.g., in the event of a system crash)
o Aborted - Transaction is rolled back. That is, all of its effects are undone
o Committed - Transaction completes all operations and moved the database to the next consistent state
• Each transaction writes the following information to the log:
1. Start(T) - the fact that transaction T has started
2. Write(T, X, old_value, new_value) - the fact that transaction T has written to item X with the new_value. old_value is also maintained.
3. Read(T, X) - the fact that transaction T has read data item X
4. Either:
Commit(T) - transaction T committed, or
Abort(T) - transaction T was aborted
• Checkpoint: A recovery point in the logs where all current transactions have terminated and all updates have been written to disk. Consists of 4 steps:
1. Cease accepting new transactions
2. Allow all unfinished transactions to complete (commit or abort)
3. Write all pending changes to disk and to logs
4. Resume accepting new transactions
• In many environments, it is possible to take checkpoints each 15 minutes or half hour, etc.
• Recovery must then only be done from the time of the last checkpoint (assuming no damage to stable storage).
2-1 Deferred Update Recovery
• Also called NO-UNDO/REDO
• During a transaction, only record the changes to data items in the log.
• When the transaction commits, actually update the data items on disk.
• Two main rules:
1. A transaction cannot change any items in the database until it commits.
2. A transaction may not commit until all of the write operations are successfully recorded in the log. This means that we must check to see that the log is actually written to disk.
• Example:
T1: Ra Rd Wd C
T2: Rb Wb Rd Wd C
T3: Ra Wa Rc Wc C
T4: Rb Wb Ra Wa C

Log file:
Start(T1)
Write(T1, d, old, new)
Commit(T1)
checkpoint
Start(T4)
Write(T4, b, old, new)
Write(T4, a, old. new)
Commit(T4)
Start(T2)
Write(T2, b, old, new)
Start(T3)
Write(T3, a, old, new)
s y s t e m c r a s h
• Since T1 and T4 committed, their changes were written to disk.
• However, T2 and T3 did not commit, hence their changes were not written to disk.
• To recover, we simply ignore those transactions that did not commit.
• Advantages:
1. Recovery is made easier:
Any transaction that reached the commit point (from the log) has its writes applied to the database.
All other transactions are ignored.
2. Cascading rollback does not occur because no other transaction sees the work of another until it is committed.
• Disadvantages:
1. Concurrency is limited: Must employ Strict 2PL which limits concurrency.
2-2 Immediate Update Recovery
• Immediate Update applies the write operations to the database as the transaction is executing (as opposed to at the end as with deferred update).
• Writes are still saved in the log before being applied to the database - a Write-Ahead Log (WAL)
• Maintain two logs:
1. REDO log: A record of each new data item in the database.
2. UNDO log: A record of each updated data item (old values).
• Two rules:
1. Transaction T may not update the database until all UNDO entries have been written to the UNDO log.
2. Transaction T is not allowed to commit until all REDO and UNDO log entries are written (forced-written to disk).
• To Recover:
1. Begin at the end of the log and read backwards to the last checkpoint Create two lists:
C - transactions that have committed
NC - transactions that did not commit
2. For each transaction T in C, make a third list of transactions, RB, that have read items that were updated by NC transactions during T.
3. UNDO: Undo the effects of the transactions in NC and RB.
4. REDO: Apply the effects of all of the transactions that did commit (all T in list C)
• Advantages:
o Immediate update allows higher concurrency because transactions write continuously to the database rather than waiting until the commit point.
• Disadvantages:
o Step 2 above can lead to cascading rollbacks - time consuming and may be problematic.
2-3 Shadow paging
• The AFIM (After Image) does not overwrite its BFIM (Before Image) but recorded at another place on the disk. Thus, at any time a data item has AFIM and BFIM (Shadow copy of the data item) at two different places on the disk.









X, Y: shadow copies; X’, Y’ : the current copies of data items




• To recover, it is sufficient to free the modified pages and discard the current directory. The state of the database before transaction execution is available through the shadow directory. Database can be returned to its previous state.
• Committing a transaction corresponds to discarding the previous shadow directory.
• Can be categorized as a NO-UNDO/NO-REDO technique for recovery
• Logs and checkpoints must be incorporated into the shadow paging technique.
• Disadvantages: complex storage management strategies, the overhead of writing shadow directories to disk, garbage collection overhead (old pages referenced by the shadow directory)