Advanced Recovery Techniques

Advanced Recovery Technique

The advanced recovery techniques support for high-concurrency locking techniques such as those used for B⁺-tree concurrency control which releases lock early. It supports the “logical undo”. This recovery technique is based on the “repeating history” through which the recovery executes exactly the same actions as normal processing does including the redo of the log records of incomplete transactions followed by the subsequent undo. The key benefits of advanced recovery algorithms are:

• These algorithms support the logical undo.
• It is easier to understand or show the correctness.

Logical Undo Logging: The operations like those of B⁺-tree insertions and deletions release locks early. They cannot be undone by restoring old values (physical undo) since once a lock is released other transactions may have updated the B⁺-tree. Instead, the insertions are undone by executing a deletion operation (known as logical undo).

For such operations, the undo log records should contain the undo operation to be executed. This process of logging is called logical undo logging which is in contrast to physical undo logging. The operations are called logical operations.

Some of the other examples are:

• Deletion of tuples that is to undo insertion of the tuple. This allows early lock release on space allocation information.
• Subtract amount deposited to undo the deposit. It allows early lock release on the bank balance.

Physical Redo

The redo information is logged physically that is a new value is assigned to each write even for operations with the logical undo. Logical redo is very complicated since the database state on disk may not be “operation consistent” when the recovery starts. The physical redo logging does not conflict with early lock release.

Operation Logging:The Operation logging is performed as follows:

1. When the operation starts log <T_i, O_j, operation-begin> occurs. Here O_j is a unique identifier of the operation instance.
2. While the operation is executing the normal log records with physical redo and physical undo information are logged.
3. When the operation completes, <T_i, O_j, operation-end, U> is logged where U contains information that is needed to perform a logical undo information.

Example: Insertion of (key, record-id) pair (K5, RID7) into index I9

If crash or rollback occurs before operation completes:

• The log record operation-and is not found and
• the physical undo information is used to undo operation.

If crash or rollback occurs after the operation completes:

• The operation-end log record is found and in this case, the logical undo is performed using U which is the physical undo information for the operation is ignored.

The redo of operation after crash still uses physical redo information.

Txn Rollback: Rollback of transaction T_i is done as follows:

Scan the log backwards:

1. If a log record <T_i, X, Y, V₁, V₂> is found perform the undo and log a special redo-only log record <T_i, X, Y, V₁>.
2. If a <T_i, O_j, operation-end, U> record is found roll back the operation which is logically using the undo information U. The updates are performed while the roll backs are logged just like during the normal operation execution. At the end of the operation rollback instead of logging and operation-end record generates a record <T_i, O_j, operation-abort>. Skip all the preceding log records for T_i until the record <T_i, O_j, operation-begin> is found.
3. If a redo-only record is found then ignore it.
4. If a <T_i, O_j, operation-abort> record is found stop all preceding log records for T_i until the record <T_i, O_j, operation-begin> is found.
5. We should stop the scan when the record <T_i, start> is found.
6. Add a <T_i, abort> record to the log.

Here are some points to remember:

• Class 3 and 4 given above can occur only if the database crashes while a transaction is being rolled back.
• Skipping of log records as done in the case 4 is important in order to prevent the multiple rollbacks of the same operation.

Crash Recovery

The following actions are taken while we recover from system crash:

1. (Redo phase): Scan log forward from last <checkpoint L> record till the end of the log. Repeat the history by physically redoing all updates of all transactions. Create an undo-list during the scan as follows:
   First of all, the undo-list is set to L initially.
   Whenever <T_i start> is found T_i is added to undo-list.
   Whenever <T_i commit> or <T_i abort> is found T_i is deleted from the undo-list.
   This brings the database to the state of a crash with committed as well as uncommitted transactions having been redone. Now undo-list contains transactions that are incomplete which mean they have neither been committed nor been fully rolled back.
2. (Undo phase): Scan the log backwards performing undo on log records of transactions found in undo-list. The log records of transactions being rolled back are processed as described earlier as they are found. Single shared scan for all transactions is being undone. When <T_i start> is found for a transaction T_i in the undo-list write a <T_i abort> log record. Then stop the scan when <T_i start> records have been found for all T_i in the undo-list.

This undoes the effect of incomplete transactions which means those with neither commit nor abort log records. The Recovery is now completed.

Checkpointing:

Checkpointing is done as follows:

1. Output all log records in memory to stable storage.
2. Output all the modified buffer blocks to disk.
3. Output a <checkpoint L> record to log on stable storage.

The transactions are not allowed to perform any actions while checkpointing is in progress. Fuzzy checkpointing allows transactions to progress while the most time-consuming parts of checkpointing are in progress. Fuzzy checkpointing is done as follows:

1. Stop all the updates temporarily by transactions.
2. Write a < checkpoint L> log record and force log to stable storage.
3. Now list M of modified buffer blocks.
4. Now permit transactions to proceed with their actions.
5. Output all the modified buffer blocks in list M to the disk. The blocks should not be updated while being output. Follow WAL which means all the log records pertaining to a block must be output before the block is output.
6. Store a pointer to the checkpoint record in a fixed position last_checkpoint on disk.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.