Table of Contents
There are different other logging techniques which are more efficient than above methods. Let us see some of them below :
Logical Undo Logging
Logging and checkpoints will work effectively in normal types of executions. But when records are inserted and deleted in a B+ tree form, then we have challenges. B+ tree structure will release the locks early. Those records will be locked by other transactions in the tree as soon as they are released. Hence rolling back those record values are not so easy using above techniques i.e.; physical undo is impossible. Hence we need an alternative technique to undo these types of insertion and deletion. i.e.; rather than physical undo techniques, we need to have logical undo techniques. In physical undo method, it will see the logs for previous values or commit, the record value will be updated to old value or re-executed.
In Logical undo method; a separate undo log file is created along with log file. In undo file, for any insertion operation, respective deletion operation will be mentioned to rollback the changes. Similarly for each deletion operation, respective insertion operation will be described. This method is called as logical undo logging.
For example, suppose a transaction T1 is adding X = X + 5. Then in our physical logging method, we will have log like <T1, X, 10, 15> indicating X value is changed from 10 to 15. In case of failure, we know what the previous value of X was and we can easily undo X to 10.But it will not work in case of B+ trees. We will have to maintain how to undo X to 10. i.e.; a separate logical undo file is created where we will mention undo for X= X+5 as X = X-5.
Suppose we have inserted a new entry for student as ‘INSERT INTO STUDENT VALUES (200, …..’. The logical undo file will contain undo operation for this as ‘DELETE FROM STUDENT WHERE STD_ID = 200’
Redo for the transaction can be done by following the log file – physical log. We will not maintain logical log for redoing the transaction. This is because; the state of the record would have changes by the time system is recovered. Some other transactions would have already executed and will lead to logical redo log to be wrong. Hence the physical log itself is re-executed to redo the operations.
Operation Logging
In any transaction, we can have multiple operations involved as shown in below snippet. Here two operations are involved – one to update X and another to update Y.
When we maintain the logs for the transaction, we can modify it to store the logs for each operation. Hence during the crash, we will have rollback information for each operation. Here in this method, apart from physical undo and redo logs, we will have logical undo logs too. Each one of them is useful and is used depending on when the crash has occurred.
Let Ti be the transaction and Oj be the operation in Ti. Let U be the logical undo information. Then operation logging for an operation in a transaction is done as follows :
- When an operation begins in the transaction, an operation log <Ti, Oj, Operartion_begin> is logged. It indicated the beginning of operation.
- When the operation is executed, logs for them are inserted as any other normal logging method. It will contain physical undo and redo informations.
- When the operation is complete, it will log <Ti, Oj, Operartion_end, U>. This will have logical undo information for reverting the changes.
Suppose we have to insert values for (X, Y) as (‘ABC’, 20) at index I5 (this is an arbitrary; we can even consider this as inserting values into table). Then operation log for this will be as follows :
When abort or crash occurs in the system while transaction is executing :
- If it crashes before operation_end, then the physical undo information is used to revert the operation. Here log will not have operation_end; hence system will automatically take physical undo from the log. i.e.; X and Y will be reverted to its old values ‘MNO’ and 100 respectively.
- If the system crashes after operation_end, then physical undo is ignored and logical undo is used to revert the changes. i.e.; DELETE (I5, ‘ABC’, 20> is used to revert the changes and it will delete newly added information from index I5.
- In both the cases above, physical redo information is used to re-execute the changes. i.e.; values of X and Y are updated to (‘ABC’, 20).
Transaction Rollback
When a system crashes while performing the transaction, log entries are used to recover from failure. We know that logs will have information on how it has to be rolled back or re-executed. But whenever there is a failure, the log files will be updated with logs to perform the undo and redo using the already entered information. i.e.; if undo of <T1, X, ‘MNO’,’ABC’> has to be done then it will enter another log after the crash as <T1, X, ‘MNO’ >.
Whenever there is crash and system is trying to recover by rolling back, it will scan the logs in reverse order and log entries are updated as below :
- If there is log entry <Ti, variable, Old_Value, New_Value>, then enter undo log as <Ti, variable, Old_Value>. This undo log entry is known as redo-only log entry. While recovering, if it finds redo-only record, it ignores it.
- If it finds <Ti, Oj, Operartion_end, U> while traversing log, then rollback the operation using logical undo, U. This logical undo operation is also logged into log file as normal operation execution, but at the end instead of <Ti, Oj, Operartion_end, U>, <Ti, Oj, Operartion_Abort> is logged. Then skip all the operations till <Ti, Oj, Operartion_begin>is reached. i.e.; it performs all the logical undo operation like any other normal operation and its logs are entered into log file, and all the physical undo operations are ignored.
Let us consider the transaction as below. We can observe that T1 has two operations O1 and O2, where O1 is completed fully and while performing O2, system crashes. While recovering it starts scan in reverse from the point where it failed and starts entering the logs for recovering. Hence it finds only <T1, Z, ‘abc’, ‘xyz’> entry in the log while recovering, and redo-only entry <T1, Z, ‘abc’> for O2 is entered. Then it finds operation end for O1. Hence it uses logical undo to rollback the changes by O1. Though it finds logical undo as ‘DELETE’, it starts inserting the redo logs for performing ‘DELETE’. This redo logs for delete will in turn delete the changes done by the operation O1. It then traverses back the physical redo of O1 without executing it (ignores it) till it reaches <T1, Start>, and stops. It adds <T1, Start> to the log file to indicate the end of reverting transaction T1. We can see this in below log file- after logical undo of O1, we do not have any logs of physical undo or redo, it jumps to Abort log entries.
Crash Recovery
Whenever there is a system crash, the transactions which were in execution phase has to be recovered and DB has to be brought to consistent state. Log files are checked to do redo and undo operations. It has two phases.
Redo Phase
Though the transactions and operations are rolled back in reverse order of log file entries, the recovery system maintains the recovery log list for undoing and redoing the operations by scanning the logs from the last checkpoint to the end of file.
That means, undo / redo logs will have list of operations and how to execute them, and are entered into the log file itself. A separate list of entries will be created for maintaining the list of transactions/ operations which needs to be undone while recovering. This will be created by scanning the log files from last checkpoint to the end of the file (forward direction). While creating the undo list, all other operations which are not part of undo list are redone.
While performing the forward scan to create undo list, L, it checks if
- <Ti, Start> found, then adds Ti to undo list L
- <Ti, Commit> or <Ti, Abort> is found, then it deletes Ti entry from undo list, L
Hence undo list will have all the transactions which are partially performed and all other committed transactions are re-done (redoing the transaction is not exactly as re-executing them. This forward scanning assumes that those transactions are already performed and committed, and lists only those transactions that are not committed yet and in partial execution state.)
Undo Phase
In this phase, the log files are scanned backward for the transactions in the undo list. Undoing of transactions are performed as described in transaction rollback. It checks for the end log for each operations, if found then it performs logical undo, else physical undo by entering the logs in log files.
This how a transaction is redone and undone, to maintain the consistency and atomicity of the transaction.
Check pointing
Check pointing is the mechanism to mark the entries in the log file that those changes are permanently updated into database, and if there is any failure, log files need not be traversed beyond that point. Only those entries after check point are not written to DB, and have to be redone / undone. This is done at periodic intervals or as per the schedule. It checks for the log records after the last check point and outputs it to the stable memory / disks. If the buffer blocks in main memory is full, then it outputs the logs into disks. If there is any new checkpoint is defined, then all the entries from last checkpoint to the new check points are written to disks. But any transactions will not get executed during this check pointing process.
Fuzzy Check pointing
Fuzzy check pointing, in contrast to normal check pointing allows transactions to execute while logs are being copied to disk. During fuzzy check pointing it follows below steps :
- Temporarily stops the transactions to make note of blocks to be copied.
- Marks the new checkpoint L in the log.
- Creates a list M for all the logs between the last checkpoint to new checkpoint, i.e.; M is the list of log records which are yet to be written to disk.
- Once all M is listed, it allows the transaction to execute. Now the transaction will start entering the logs after the new checkpoint L. It should not enter the logs into the blocks that are in M or old checkpoints.
- The buffer blocks in list M are written to the disk or stable storage. No transactions should update these blocks. In addition, all the records in these blocks in list M are written to the disk first, and then the block is updated to the disk.
- Disk should have pointer to the last checkpoint – last_checkpoint in the main memory at fixed location. This will help to read the blocks for the next update and maintain new list M.
Whenever there is recovery from failure, the logs are read from the last_checkpoint stored in DB. This is because logs before last_checkpoint are already updated to DB and those after these points have to be written. These logs are recovered as described in above methods.