Database Recovery Techniques - Overview

The main goal of recovery is to ensure the atomicity property of a transaction. If a transaction fails before completing its execution, the recovery mechanism has to make sure that the transaction has no lasting effects on the database. The different approaches to recovery :
- Deferred Update : These techniques postpone any actual updating of the database on disk until a transaction reaches its commit point. The transaction force writes the log to disk before recording the updates in the database. This approach, when used with certain concurrency control methods, is designed never to require transaction rollback, and recovery simply consists of redoing the operations of transactions committed after the last checkpoint from the log.
Disadvantage : Too much buffer space may be needed, since updates are kept in the buffers and are not applied to disk until a transaction commits.
Deferred update can lead to a recovery algorithm known as NO-UNDO/REDO. Immediate update techniques may apply changes to the database on disk before the transaction reaches a successful conclusion. Any changes applied to the database must be first recorded in the log and force-written to disk so that these operations can be undone if necessary.
- Another algorithm, known as UNDO/NO-REDO, can also be developed for immediate update if all transaction actions are recorded in the database before commit.
- There is another technique, called shadow paging technique, which keeps track of old database pages by using a shadow directory. This technique, which is classified as NO UNDO/NO-REDO, does not require a log in single-user systems but still needs the log for multiuser systems.
- ARIES, a specific recovery scheme is used in some of IBM's relational database products.
- Two-phase commit protocol is used for recovery from failures involving multi-database transactions.
- Recovery from catastrophic failures is typically done by backing up the database and the log to tape. The log can then be backed up more frequently than the database, and the backup log can be used to redo operations starting from the last database backup.

How is shadow paging performed ?

Shadow paging is an alternative to log-based recovery techniques, which has both advantages and disadvantages. It may require fewer disk accesses, but it is hard to extend paging to allow multiple concurrent transactions. The paging is very similar to paging schemes used by the operating system for memory management.

How Shadow Paging is performed ?
- To commit a transaction :
* Flush all modified pages in main memory to disk.
* Output current page table to disk.
* Make the current page table the new shadow page table, as follows:
1. Keep a pointer to the shadow page table at a fixed (known) location on disk.
2. To make the current page table the new shadow page table, simply update the pointer to point to current page table on disk.
- Once pointer to shadow page table has been written, transaction is committed.
- No recovery is needed after a crash: New transactions can start right away, using the shadow page table.
- Pages not pointed to from current/shadow page table should be freed (garbage collected).

Advantages of shadow-paging technique:
- No overhead of writing log records.
- Recovery is trivial.

Disadvantages of shadow-page technique:
- Commit overhead : The commit of a single transaction using shadow paging requires multiple blocks to be output -- the current page table, the actual data and the disk address of the current page table. Log-based schemes need to output only the log records.
- Data fragmentation : Shadow paging causes database pages to change locations (therefore, no longer contiguous.
- Garbage collection : Each time that a transaction commits, the database pages containing the old version of data changed by the transactions must become inaccessible. Such pages are considered to be garbage since they are not part of the free space and do not contain any usable information. Periodically it is necessary to find all of the garbage pages and add them to the list of free pages. This process is called garbage collection and imposes additional overhead and complexity on the system.

Overview of Shadow Paging

A computer system, like any other mechanical or electrical system is subject to failure. There are a variety of causes, including disk crash, power failure, software errors, a fire in the machine room, or even sabotage. Whatever the cause, information may be lost. The database must take actions in advance to ensure that the atomicity and durability properties of transactions are preserved. An integral part of a database system is a recovery scheme that is responsible for the restoration of the database to a consistent stage that existed prior to the occurrence of the failure.

Shadow paging is a technique used to achieve atomic and durable transactions, and provides the ability to manipulate pages in a database. During a transaction, the pages affected by the transaction are copied from the database file into a workspace such as volatile memory, and modified in that workspace. When a transaction is committed, all of the pages that were modified by the transaction are written from the workspace to unused pages in the database file. During execution of the transaction, the state of the database exposed to the user is that is which the database existed prior to the transaction, since the database file still contains the original versions of the modified pages, as they existed before being copied into the workspace if a user accesses the database before the transaction is complete, or upon recovery of failure, it will appear as though the transaction has not occurred.

- Shadow paging is an alternative to log-based recovery; this scheme is useful if transactions execute serially.
- Basic Idea: Maintain two page tables during the lifetime of a transaction – the current page table, and the shadow page table.
- Store the shadow page table in nonvolatile storage, such that state of the database prior to transaction execution may be recovered.
* Shadow page table is never modified during execution.
- Initially, both the page tables are identical. Only current page table is used for data item accesses during execution of the transaction.
- Whenever any page is about to be written for the first time
* A copy of this page is made onto an unused page.
* The current page table is then made to point to the copy.
* The update is performed on the copy.