11. Transactions and data recovery

This chapter examines the possibilities of data recovery after system failures, i.e. Property (D) - durability of transactions.

The main requirement for the longevity of these transactions is that the data of committed transactions must be stored in the system, even if the next time the system fails. It would seem that the easiest way to provide such a guarantee is to record all changes on disk media at once during each operation. This method is not satisfactory, since There is a significant difference in the speed of work with operational and external memory. The only way to achieve acceptable performance is to buffer in-memory database pages. This means that the data fall into the external long-term memory not immediately after making changes, but after some (long enough) time. However, something in the external memory should remain, because otherwise there is no place to get information for recovery.

The requirement of transaction atomicity states that incomplete or rolled back transactions should not leave traces in the database. This means that the data must be stored in a redundant database, which allows you to have information on which the state of the database is restored at the time of the start of a failed transaction. This redundancy is usually provided by the transaction log. The transaction log contains details of all data modification operations in the database, in particular, the old and new values ​​of the modified object, the system transaction number, the modified object, and other information.

Types of data recovery

Database recovery can be performed in the following cases:

• Individual transaction rollback . The rollback of an individual transaction can be initiated either by the transaction itself by issuing a ROLLBACK command, or by the system. A DBMS can initiate a transaction rollback in the event of any error in the operation of a transaction (for example, division by zero) or if this transaction is selected as a victim when resolving an impasse.
• Mild system failure ( software crash ). Mild failure is characterized by loss of system memory. In this case, all transactions that are executed at the time of the failure of the transaction are affected, and the contents of all database buffers are lost. The data stored on the disk remains intact. A mild failure can occur, for example, as a result of an emergency power outage or as a result of a fatal processor failure.
• Hard system failure ( hardware failure ). Hard failure is characterized by damage to external storage media. Hard failure can occur, for example, as a result of breakage of the disk drive heads.

In all three cases, the basis for recovery is data redundancy provided by the transaction log.

Like the database pages, the data from the transaction log is not written directly to disk, but is pre-buffered in RAM. Thus, the system supports two kinds of buffers — database page buffers and transaction log buffers.

Database pages whose contents in the buffer (in RAM) differ from the contents on the disk are called “dirty” pages . The system constantly maintains the list of dirty pages - the dirty list . Writing dirty pages from buffer to disk is called popping pages into external memory . Obviously, it is necessary to provide such rules for pushing out database buffers and transaction log buffers that would provide two requirements:

1. Maximum transaction speed . To do this, you need to push the pages as rarely as possible. Ideally, if the RAM would be infinite, and failures would never occur, the best way would be to load the entire database into RAM, work with data only in RAM , and write changed pages to disk only at the moment of the completion of the entire system .
2. Ensuring that in the event of a failure (of any type), the data of completed transactions could be recovered, and the data of incomplete transactions completely removed, i.e. ensuring the recovery of the last consistent state of the database. To do this, pushing something onto the disk is still necessary, even if we would have infinite RAM.

Thus, there are two reasons for periodically pushing pages into external memory — a lack of RAM and the possibility of failures.

The basic principle of a consistent policy of pushing out a log buffer and database page buffers is that the record about changing a database object must go into the external log memory before the changed object is in the external memory of the database. The corresponding logging protocol (and buffering management) is called Write Ahead Log ( WAL ) - “ write to the log first, ” and if you need to push a modified database object to external memory, you must ensure that the external log is pushed to external memory. records of its change. This means that if there is an object in the external memory of the database to which some modification command has been applied, then the external memory of the transaction log contains a record of this operation. The reverse is not true - if the external memory of the journal contains a record of some change in the object, then the external object itself may not have the changed object in the external memory.

An additional condition for ejecting buffers is imposed by the requirement that every successfully completed transaction must actually be recorded in external memory. Whatever failure occurs, the system must be able to restore the state of the database containing the results of all transactions recorded at the time of the failure.

The third condition for ejecting buffers is that the database and transaction log buffers are limited. Periodically or upon the occurrence of a certain event (for example, the number of pages in the dirty list exceeded a certain threshold, or the number of free pages in the buffer decreased and reached a critical value), the system receives a so-called control point . Accepting a checkpoint includes pushing the contents of the database buffers to an external memory and a special physical record of the checkpoint , which is a list of all the transactions currently being performed.

It turns out that the minimum requirement to guarantee the possibility of restoring the last consistent state of the database is to push all transactions to change the database when the transaction is committed to the external log memory . In this case, the last entry in the log, produced on behalf of this transaction, is a special record of the end of this transaction.

Individual transaction rollback

In order to be able to perform an individual transaction rollback on the transaction log, all entries in the log from this transaction are linked to the reverse list. The beginning of the list for non-expiring transactions is the record of the latest database change made by this transaction. For completed transactions (individual rollbacks of which are no longer possible), the beginning of the list is the record of the end of the transaction, which is necessarily pushed into the external log memory. The end of the list is always the first record of a database change made by this transaction. Each record has a unique transaction system number so that you can restore a direct list of database change records for a given transaction.

Individual transaction rollback is performed as follows:

• The list of records made by this transaction in the transaction log (from the last change to the first change) is viewed.
• The next entry is selected from the list of this transaction.
• The opposite operation is performed: instead of the INSERT operation, the corresponding DELETE operation is performed, instead of the DELETE operation, an INSERT operation is performed, and instead of the direct UPDATE operation, the inverse UPDATE operation, which restores the previous state of the database object.
• Any of these reverse operations are also logged. This should be done, because during the execution of an individual rollback, a mild failure can occur, after recovery after which you will need to roll back a transaction for which an individual rollback is not fully performed.
• Upon successful completion of a rollback, a record of the end of the transaction is recorded.

Recovery after a mild failure

Despite the WAL protocol, after a soft failure, not all physical database pages contain modified data, because Not all dirty database pages have been pushed into external memory.

The last moment when the dirty pages were pushed out guaranteed is the moment of the last checkpoint. There are 5 options for the status of transactions in relation to the time of the last checkpoint and the time of failure:

Figure 1 Five Transaction Options

The last test point was taken at time tc. A mild system crash occurred at time tf. T1-T5 transactions are characterized by the following properties:

• T1 - transaction completed successfully before accepting checkpoint. All data in this transaction is stored in long-term memory — both the log entries and the data pages modified by this transaction. For transaction T1 no recovery operations are required.
• T2 - transaction started before acceptance of the checkpoint and successfully completed after the checkpoint, but before the occurrence of the failure. The transaction log entries related to this transaction are pushed into external memory. Data pages modified by this transaction are only partially pushed into external memory. For this transaction, you need to repeat the operations that were performed after the acceptance of the checkpoint.
• T3 - The transaction started before the checkpoint was accepted and was not completed as a result of the failure. This transaction must be rolled back. The problem, however, is that part of the data pages modified by this transaction are already contained in the external memory — those pages that were updated before the checkpoint was accepted. There are no traces of changes made after the checkpoint in the database. Transaction log entries made before the checkpoint was pushed to external memory, those log entries made after the checkpoint are missing in the external log memory.
• T4 - Transaction started after acceptance of the checkpoint and successfully completed before the system crashes. The transaction log entries related to this transaction are pushed into the external log memory. Changes to the database made by this transaction are completely absent in the external memory of the database. This transaction must be repeated entirely.
• T5 - Transaction started after acceptance of checkpoint and not completed due to failure. There are no traces of this transaction either in the external memory of the transaction log or in the external memory of the database. For such a transaction, no action is required, as if it was not at all.

System recovery after a mild failure is performed as part of the system reboot procedure . When the system is rebooted, transactions T2 and T4 must be partially or completely repeated, transaction T3 - partially rolled back, and no actions need to be taken for transactions T1 and T5. When rebooting, the system performs the following actions:

• It creates two lists of transactions UNDO (cancel) and REDO (repeat). All transactions from the last checkpoint record (i.e., all transactions that were executed at the time the checkpoint was taken) are recorded in the UNDO list. The REDO list is empty. In our case, it will be: UNDO = {T2, T3}, REDO = {}.
• Starting with a checkpoint record, the transaction log is viewed ahead.
• If a transaction start entry is found in the transaction log, this transaction is added to the UNDO list. In our case, it will be: UNDO = {T2, T3, T4}, REDO = {}. Note that there is no trace of transaction T5 in the transaction log.
• If a COMMIT entry for the completion of a transaction is detected in the registration file, this transaction is added to the REDO list. In our case, it will be: UNDO = {T2, T3, T4}, REDO = {T2, T4}. Note that the end of these transaction records are in the external memory of the transaction log in accordance with the minimum requirement to push the log records when the transaction commits.
• When the end of the transaction log is reached, both lists are analyzed. At the same time, transactions that are on the REDO list are deleted from the UNDO list. In our case, it will be: UNDO = {T3}, REDO = {T2, T4}.
• After that, the system scans the transaction log back from the time of the checkpoint and rolls back all transactions from the UNDO list. In our case, those T3 transactions that were performed before the checkpoint was rolled back.
• Finally, the system scans the transaction log forward, starting at the time of the checkpoint, and re-executes all the transactions in the REDO list. In our case, the system will re-execute all operations of transaction T4 and those operations of transaction T2 that were executed after the acceptance of the control point.

Hard Failure Recovery

In case of a hard failure, the database on the disk is physically broken. The basis for recovery in this case is the transaction log and a backup copy of the database . An archive copy of the database should be created periodically, namely, taking into account the speed of filling the transaction log.

Recovery begins with a reverse copy of the database from an archive copy. It then scans the transaction log to identify all transactions that ended successfully before the failure. (Transactions that ended with a rollback before the occurrence of a failure can be disregarded). After that, the transaction log in the forward direction repeats all successfully completed transactions. At the same time, there is no need to roll back transactions that were interrupted as a result of a failure, since The changes made by these transactions are missing after the database is restored from a backup.

The worst case is when both the database and the transaction log are physically destroyed. In this case, the only thing that can be done is to restore the state of the database at the time of the last backup. In order to prevent such a situation from occurring, the database and transaction log are usually located on physically different disks managed by physically different controllers.

Data Recovery and SQL Standard

The SQL language standard does not contain data recovery requirements, leaving these questions to the discretion of database developers.

findings

The main requirement for the longevity of these transactions is that the data of committed transactions must be stored in the system, even if the next time the system fails. The redundancy of data storage, allowing to recover the system after a failure, is usually provided by the transaction log .

Database recovery can be performed in the following cases:

• Individual transaction rollback .
• Mild system failure ( software crash ).
• Hard system failure ( hardware failure ).

Pages of the database and transaction log are not written directly to disk, but previously buffered in RAM. Database pages whose contents in the buffer are different from those on disk are called dirty pages . Writing dirty pages from buffer to disk is called popping pages into external memory .

The basic principle of a consistent policy of pushing out a log buffer and database page buffers is the Write Ahead Log ( WAL ) logging protocol — write to a log first .

The minimum requirement to ensure that the last consistent state of the database can be restored is to push all records of database changes by this transaction while committing a transaction to the external log memory .

Individual transaction rollback is performed using the transaction log.

System recovery after a mild failure is performed as part of the system reboot procedure . When the system is rebooted, the transactions go through an identification procedure to identify completed and interrupted transactions as a result of a failure. Transactions that successfully completed before the occurrence of a failure, and data about which are missing in the database, are repeated again. Transactions that did not have time to complete by the time of the failure, and data about which are available in the database, are rolled back.

System recovery after a hard failure is performed using a backup copy of the database and transaction log.