Failure Classification

Failure Classification:

 Transaction Failure: There are two types of errors that may cause a transaction to fail:
• Logical error: The transaction can no longer continue with its normal execution because of some internal condition, such as bad input, data not found, overflow, or resource limit exceeded.
• System error: The system has entered an undesirable state like deadlock, as a result of which a transaction cannot continue with its normal execution. The transaction however, can be reexecuted at a later time.

 System Crash: There is a hardware malfunction, or a bug in the database software or the operating system, that causes the loss of the content of volatile storage, and brings transaction processing to a halt. The content of nonvolatile storage remains intact, and is not corrupted.

 Disk Failure: A disk block loses its content as a result of either a head crash or failure during a data transfer operation. Copies of the data on other disks, or archival backups on tertiary media are used to recover from failure.




To recover from failures, recovery algorithms are used which usually have two parts:
Actions taken during normal transaction processing to ensure that enough information exists to allow recovery from failures.
Actions taken after a failure to recover the database contents to a state that ensures database consistency, transaction atomicity, and durability.


Log-Based Recovery
The log is a sequence of log records, recording all the update activities in the database. There are several types of log records. An update log record describes a single data base write. It has these fields:

• Transaction identifier is the unique identifier of the transaction that performed the write operation.
• Data-item identifier is the unique identifier of the data item written. Typically, it is location on disk of the data item.
• Old value is the value of the data item prior to the write.
• New value is the value that the data item will have after the write.

Other special log records exist to record significant events during transaction processing, such as the start of a transaction and the commit and abort of a transaction.


Various types of log record are denoted as:
• Transaction Ti has started.
• Transaction Ti has performed a write on data item Xj. Xj had value V1 before the write, and will have value V2 after the write.
• Transaction Ti has committed.
• Transaction Ti has aborted.

Whenever a transaction performs a write, it is essential that the log record for that write be created before the database is modified.
Once a log record exists, we can output the modification to the database if that is desirable.
We have the ability to undo a modification that has already been output to the database. We can do that by using the old-value field in log records.

For log records to be useful for recovery from system and disk failures, the log must reside in stable storage.



Backup Recovery

The backup of the whole database is created and stored in stable storage from time to time.
When failure occurs, then the most current backup is retrieved to get the most current database.





Shadow Paging
• The database is partitioned into some number of fixed-length blocks, which are referred to as pages.
• To find the ith page of the database we use a page table.
• The page table contains n entries, one for each database page. Each entry contains a pointer to a page on disk.

The key idea behind the shadow-paging technique is to maintain two page tables during the life of a transaction: the current page table and the shadow page table.
When the transaction starts, both page tables are identical.
The shadow page is never changed over the duration of the transaction.
The current page table may be changed when a transaction performs a write operation.













Suppose that the transaction Tj performs a write(X) operation, and that X resides on the ith page. The system executes the write operation as follows:

1. If the ith page (i.e. the page in which X resides) is not already in main memory, then the system issues input(X).

2. If this is the write first performed on the ith page by this transaction, then the system modifies the current page table as follows:
a) It finds an unused page on disk. Usually, the database system has access to a list of unused (free) pages.
b) It deletes the page found in 2a from the list of free the list of free pages frames; it copies the contents of the ith to the page found in step 2a.
c) It modifies the current page table so that the ith entry points to the page found in step 2a.

3. It assigns the value of xj to X in the buffer page.

Thus, the shadow-page approach to recovery is to store the shadow page table in nonvolatile storage, so that the state of the database prior to the execution of the transaction can be recovered in the event of a crash, or transaction abort.

When the transaction commits, the system writes the current page table to nonvolatile storage. The current page table then becomes the new shadow page table and the next transaction is allowed to begin execution.

Using shadow page based technique, to commit a transaction we must do the following:

Ensure that all buffer pages in main memory that have been changed by the transaction are output to disk. These output operation do not change the database pages pointed to by some entry in the shadow page table.

Output the current page table to disk. Note that we must not overwrite the shadow page table, since we may need it for recovery from a crash.

Output the disk address of the current page table to the fixed location in stable storage containing the address of the shadow page table. This action overwrites the address of the old shadow page table. Therefore, the current page table has become the shadow page table, and the transaction is committed.



Advantages of the shadow-page technique:

• The overhead of log-record output is eliminated.
• Recovery from crashes is significantly faster since no undo or redo operations are needed.




Drawbacks:

• Commit overhead: The commit of a single transaction using shadow paging requires multiple blocks to be the output- the actual data blocks, the current page table, and the disk address of the current page table.

• Data fragmentation: Shadow paging causes database pages to change location when they are updated. As a result, either we lose the locality property of the pages or we must resort to more complex, higher-overhead schemes for physical storage management.

• Garbage collection: Each time that a transaction commits, the database pages containing the old version of data changed by the transaction become inaccessible. Such pages are considered garbage, since they are not part of free space and do not contain useful information.