Transaction recovery techniques

Recovery brings the data back to a consistent state after a failure or abort, using redundant information kept on stable storage.

Log-based recovery

A log (journal) records every update before it is applied to the database (write-ahead logging). Each record holds the transaction id, the object, the old value (before-image) and the new value (after-image); there are also start, commit and abort records.

• Undo: for an aborted or uncommitted transaction, the old values are restored from the log, scanning backwards.
• Redo: for a committed transaction whose updates may not have reached disk, the new values are re-applied, scanning forwards.
• Checkpoints in the log limit how far back recovery has to scan.

Example: the log holds <T1 start>, <T1, A, 100, 150>, <T1 commit>, <T2 start>, <T2, B, 20, 40>, and then the system crashes. On recovery, T1 is redone (A = 150), and T2, which has no commit record, is undone (B = 20).

Shadow paging

The database is a set of pages reached through a page table. When a transaction starts, a copy of the page table, the shadow page table, is kept unchanged. Updates are written to new pages, and only the current page table points to them. On commit, the current table atomically replaces the shadow table (a single pointer switch); on abort, the current table is discarded and the shadow table is still valid.

• No undo or redo is needed, and recovery is quick.
• Disadvantages: pages become scattered on disk, garbage collection is needed, and supporting many concurrent transactions is harder.

Comparison

Logging allows fine-grained, concurrent updates and is the standard method; shadow paging is simpler but suits systems where only one transaction updates at a time.