Database Systems | Transactions, Recovery, and Logging Strategies

CSCE-608 Database Systems Spring 2024 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 35: Undo-logging

lock table DDL complier concurrency control file logging & recovery manager User-1 DDL User-2 transaction manager User-3 index/file manager buffer manager query execution engine DML User-n DML complier main memory buffers secondary storage (disks) DBMS

Tranactions What is a transaction? A sequence of actions that we want to be done as a single logic step What is a logic step (what do we want a transaction to be)? ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist.

We will be focused on: How to prevent/fix constraint violations due to system failures How do we recover from system failures? due to concurrent executed transactions due to both

System Failure Recovery What we want to recover? Undesired changes made by transactions How can a transaction make undesired changes? Partial changes made by an incomplete transaction whose execution is interrupted because of system failure.

Coping with System Failures Therefore, the logging strategy must be carefully designed to ensure Atomicity and Durability. If you are going to be in the logging business, one of the things that you have to do is to learn about heavy equipment. Robert VanNatta, Logging History of Columbia County We will study three logging strategies: Undo-logging Redo-logging Undo/Redo-logging

Coping with System Failures Therefore, the logging strategy must be carefully designed to ensure Atomicity and Durability. If you are going to be in the logging business, one of the things that you have to do is to learn about heavy equipment. Robert VanNatta, Logging History of Columbia County We will study three logging strategies: Undo-logging Redo-logging Undo/Redo-logging

Undo-Logging The format of the Undo-log: <T, start> <T, A, aold> <T, B, bold> <T, commit> (or <T, abort>) transaction T starts transaction T wrote on A/B, and A/B had an old value aold/bold transaction T commits/abort

Undo-Logging The format of the Undo-log: <T, start> <T, A, aold> <T, B, bold> <T, commit> (or <T, abort>) transaction T starts transaction T wrote on A/B, and A/B had an old value aold/bold transaction T commits/abort Main idea of Undo-logging: When log record <T, commit> reaches disk, all changes made by T have reached disk.

Undo-Logging Main idea of Undo-logging: When <T, commit> reaches disk, all changes made by T have reached disk. <T, start> Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. The order in which the values reach disk <T,V1, a1> New V1 <T,V2, a2> <T,V3, a3> New V3 <T,V4, a4> New V4 New V2 <T, commit>

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log.

Undo-Logging Undo-logging rules: U1. The log record <T, V, aold> reaches disk before the change of V reaches disk; U2. The log record <T, commit> reaches disk after all changes made by T reach disk. Algorithms for undo-logging Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log.

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: Example T1: A A 3 B B 3 read (A,t); t t 3; write (A,t); read (B,t); t t 3; write (B,t); output (A); output (B); CPU C=30 B=10 A=10 memory disk 18 18

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> flush-log output (A); read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (B); add-log: <T, commit> CPU C=30 B=10 A=10 memory disk 19 19

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 memory disk 20 20

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 <T, start> memory disk 21 21

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> memory disk 22 22

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 memory disk 23 23

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> <T, B, 10> <T, start> <T, A, 10> B=30 <T, start> <T, A, 10> <T, B, 10> memory disk 24 24

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 B=30 <T, start> <T, A, 10> <T, B, 10> memory disk 25 25

Log recording 1. When T writes on A, add a log-record <T, A, aold> (in memory-log); 2. Before output(A), make sure the memory-log is flushed to disk-log at least once; 3. Add log-record <T, commit> to memory-log only when all output(A) related to T are done. Undo-logging: log recording T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=30 A=30 A=30 <T, start> <T, A, 10> <T, B, 10> <T, start> <T, A, 10> <T, B, 10> <T, commit> <T, commit> B=30 <T, start> <T, A, 10> <T, B, 10> <T, A, 10> <T, B, 10> <T, start> memory disk 26 26

Undo-logging: Failure Recovery CPU C=30 B=10 A=10 memory disk 27 27

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 memory disk 28 28

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 crash occurs after this point, memory disk 29 29

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=30 A=30 A=30 <T, start> <T, A, 10> <T, B, 10> <T, commit> B=30 <T, start> <T, A, 10> <T, B, 10> <T, commit> crash occurs after this point, memory disk 30 30

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=30 A=30 <T, start> <T, A, 10> <T, B, 10> <T, commit> crash occurs after this point, memory disk 31 31

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=30 A=30 <T, start> <T, A, 10> <T, B, 10> <T, commit> crash occurs after this point, memory disk 32 32

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=30 A=30 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 <T, start> <T, A, 10> <T, B, 10> memory crash occurs at this point disk 33 33

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=30 A=30 <T, start> <T, A, 10> <T, B, 10> memory crash occurs at this point disk 34 34

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 <T, start> <T, A, 10> <T, B, 10> <T, abort> memory crash occurs at this point disk 35 35

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=30 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 <T, start> <T, A, 10> <T, B, 10> crash occurs at this point memory disk 36 36

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 <T, start> <T, A, 10> <T, B, 10> <T, abort> crash occurs at this point memory disk 37 37

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 <T, start> <T, A, 10> <T, B, 10> crash occurs at this point memory disk 38 38

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 <T, start> <T, A, 10> <T, B, 10> <T, abort> crash occurs at this point memory disk 39 39

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 crash occurs before this point memory disk 40 40

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 log B=10 A=10 A=30 <T, start> <T, A, 10> <T, B, 10> B=30 crash occurs before this point <T, start> <T, A, 10> memory disk 41 41

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 crash occurs before this point <T, start> <T, A, 10> memory disk 42 42

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 crash occurs before this point <T, start> <T, A, 10> memory disk 43 43

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery T: A A 3 B B 3 add-log: <T, start> read (A,t); t t 3; write (A,t); add-log: <T, A, 10> read (B,t); t t 3; write (B,t); add-log: <T, B, 10> flush-log output (A); output (B); add-log: <T, commit> CPU C=30 B=10 A=10 crash occurs before this point <T, start> <T, A, 10> <T, abort> memory disk 44 44

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to 45 45

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to A.1 Read the disk-log into the main memory; 46 46

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to A.1 Read the disk-log into the main memory; A.2 FOR each <T, A, aold> in step 3 DO write(A, aold); output(A); 47 47

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to A.1 Read the disk-log into the main memory; A.2 FOR each <T, A, aold> in step 3 DO write(A, aold); output(A); B. What if the system crashes again during Undo? 48 48

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to A.1 Read the disk-log into the main memory; A.2 FOR each <T, A, aold> in step 3 DO write(A, aold); output(A); B. What if the system crashes again during Undo? * The disk-log remains; 49 49

System recovery with disk-log 1. Scan the disk-log backwards; 2. Ignore T if see <T, commit>; 3. For each T with no <T, commit> For each log-record <T, A, aold> Undo the action by restoring the value of A back to aold; Add <T, abort> to disk-log. Undo-logging: Failure Recovery Remarks: A. To execute the recovery algorithm, we need to A.1 Read the disk-log into the main memory; A.2 FOR each <T, A, aold> in step 3 DO write(A, aold); output(A); B. What if the system crashes again during Undo? * The disk-log remains; * We can simply repeat steps A.1 and A.2; 50 50