Undo and Redo Operations Undo of a log record <Ti,X,V1,V2>writes the old value Vi to X Redo of a log record <Ti,X,V1,V2>writes the new value V2 to X Undo and Redo of Transactions undo(Ti)restores the value of all data items updated by T;to their old values,going backwards from the last log record for 7; each time a data item X is restored to its old value V a special log record <Ti,X,V>is written out when undo of a transaction is complete,a log record <T;abort>is written out. redo(T)sets the value of all data items updated by T;to the new values,going forward from the first log record for 7; No logging is done in this case Database System Concepts-6th Edition 16.17 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 16.17 ©Silberschatz, Korth and Sudarshan th Edition Undo and Redo Operations Undo of a log record <Ti , X, V1 , V2> writes the old value V1 to X Redo of a log record <Ti , X, V1 , V2> writes the new value V2 to X Undo and Redo of Transactions undo(Ti ) restores the value of all data items updated by Ti to their old values, going backwards from the last log record for Ti each time a data item X is restored to its old value V a special log record <Ti , X, V> is written out when undo of a transaction is complete, a log record <Ti abort> is written out. redo(Ti ) sets the value of all data items updated by Ti to the new values, going forward from the first log record for Ti No logging is done in this case
Undo and Redo on Recovering from Failure When recovering after failure: Transaction 7;needs to be undone if the log contains the record <T;start>. but does not contain either the record <Ti commit>or <Ti abort>. Transaction T;needs to be redone if the log contains the records <7 start> and contains the record <T commit>or <T abort> Note that If transaction T;was undone earlier and the <T;abort>record written to the log,and then a failure occurs,on recovery from failure 7;is redone such a redo redoes all the original actions including the steps that restored old values Known as repeating history Seems wasteful,but simplifies recovery greatly Database System Concepts-6th Edition 16.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 16.18 ©Silberschatz, Korth and Sudarshan th Edition Undo and Redo on Recovering from Failure When recovering after failure: Transaction Ti needs to be undone if the log contains the record <Ti start>, but does not contain either the record <Ti commit> or <Ti abort>. Transaction Ti needs to be redone if the log contains the records <Ti start> and contains the record <Ti commit> or <Ti abort> Note that If transaction Ti was undone earlier and the <Ti abort> record written to the log, and then a failure occurs, on recovery from failure Ti is redone such a redo redoes all the original actions including the steps that restored old values Known as repeating history Seems wasteful, but simplifies recovery greatly
Immediate DB Modification Recovery Example Below we show the log as it appears at three instances of time. <To start> <To start> <To start> <T0,A,1000,950> <T0,A,1000,950> <T0,A,1000,950> <T0,B,2000,2050> <T0,B,2000,2050> <T0,B,2000,2050> <To commit> <To commit> <T1 start> <T start> <T1,C,700,600> <T1,C,700,600> <T commit> (a) (b) (c) Recovery actions in each case above are: (a) undo(To):B is restored to 2000 and A to 1000,and log records <To,B,2000>,<To,A,1000>,<To,abort>are written out (b)redo (To)and undo(T1):A and B are set to 950 and 2050 and C is restored to 700.Log records <T1,C,700>,<T1,abort>are written out. (c)redo(To)and redo(T):A and B are set to 950 and 2050 respectively.Then C is set to 600 Database System Concepts-6th Edition 16.19 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 16.19 ©Silberschatz, Korth and Sudarshan th Edition Immediate DB Modification Recovery Example Below we show the log as it appears at three instances of time. Recovery actions in each case above are: (a) undo (T0 ): B is restored to 2000 and A to 1000, and log records <T0 , B, 2000>, <T0 , A, 1000>, <T0 , abort> are written out (b) redo (T0 ) and undo (T1 ): A and B are set to 950 and 2050 and C is restored to 700. Log records <T1 , C, 700>, <T1 , abort> are written out. (c) redo (T0 ) and redo (T1 ): A and B are set to 950 and 2050 respectively. Then C is set to 600
Checkpoints Redoing/undoing all transactions recorded in the log can be very slow 1.processing the entire log is time-consuming if the system has run for a long time 2.we might unnecessarily redo transactions which have already output their updates to the database. Streamline recovery procedure by periodically performing checkpointing 1.( Output all log records currently residing in main memory onto stable storage. 2.Output all modified buffer blocks to the disk. 3. Write a log record checkpoint L>onto stable storage where L is a list of all transactions active at the time of checkpoint. All updates are stopped while doing checkpointing Database System Concepts-6th Edition 16.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 16.20 ©Silberschatz, Korth and Sudarshan th Edition Checkpoints Redoing/undoing all transactions recorded in the log can be very slow 1. processing the entire log is time-consuming if the system has run for a long time 2. we might unnecessarily redo transactions which have already output their updates to the database. Streamline recovery procedure by periodically performing checkpointing 1. Output all log records currently residing in main memory onto stable storage. 2. Output all modified buffer blocks to the disk. 3. Write a log record < checkpoint L> onto stable storage where L is a list of all transactions active at the time of checkpoint. All updates are stopped while doing checkpointing
Checkpoints(Cont.) During recovery we need to consider only the most recent transaction Ti that started before the checkpoint,and transactions that started after T. 1. Scan backwards from end of log to find the most recent <checkpoint L>record Only transactions that are in L or started after the checkpoint need to be redone or undone Transactions that committed or aborted before the checkpoint already have all their updates output to stable storage. Some earlier part of the log may be needed for undo operations 1.Continue scanning backwards till a record <T start>is found for every transaction T;in L. Parts of log prior to earliest <T;start>record above are not needed for recovery,and can be erased whenever desired. Database System Concepts-6th Edition 16.21 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 16.21 ©Silberschatz, Korth and Sudarshan th Edition Checkpoints (Cont.) During recovery we need to consider only the most recent transaction Ti that started before the checkpoint, and transactions that started after Ti . 1. Scan backwards from end of log to find the most recent <checkpoint L> record Only transactions that are in L or started after the checkpoint need to be redone or undone Transactions that committed or aborted before the checkpoint already have all their updates output to stable storage. Some earlier part of the log may be needed for undo operations 1. Continue scanning backwards till a record <Ti start> is found for every transaction Ti in L. Parts of log prior to earliest <Ti start> record above are not needed for recovery, and can be erased whenever desired