Crash Recovery Vu Tuyet Trinh trinhvt@it-hut.edu.vn Department of Information Systems, Faculty of Information Technology Hanoi University of Technology Transaction collection of action that preserve consistency Consistent DB T Consistent DB’ with assumption IF T starts with consistent state + T executes in isolation THEN T leaves consistent state goupee.com fb.com/groups/goupee 1
How can constraints be violated? Transaction bug DBMS bug Hardware failure e.g., disk crash Data sharing e.g., T1 and T2 in parallel Failures Events Desired Undesired Expected Unexpected processor CPU memory disk M D goupee.com fb.com/groups/goupee 2
Recovery Maintaining the consistency of DB by ROLLBACK to the last consistency state. Ensuring 2 properties Atomic Durability Using LOG Transaction Log A sequence of log record keeping trace of actions executed by DBMS <start T> Log the beginning of the transaction execution <commit T> transaction is already finished <abort T> Transaction is calcel <T, X, v, w> Transaction makes an update actio, before update X=v, after update x = w goupee.com fb.com/groups/goupee 3
Transaction Log Handled in main memory and put to external memory (disk) when possible A = 8 16 B = 8 16 Data Actions Log Log Disk Memory Checkpoint Definition: moment where intermediate results and a log record are saved to disk. being initiated at specified intervals Objective minimize the amount of time and effort wasted when restart the process can be restarted from the latest checkpoint rather than from the beginning. Log record <checkpoint> or <ckpt> goupee.com fb.com/groups/goupee 4
Undo-logging Step Action t Mem A Mem B Disk A Disk B Mem Log 1 <start T> 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 <T, A, 8> 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 <T, B, 8> 8 Flush log 9 Output(A) 16 16 16 16 8 10 Output(B) 16 16 16 16 16 11 <commit T> 12 Flush log Undo-Logging Rules (1) For every action generate undo log record (containing old value) (2) Before X is modified on disk, log records pertaining to X must be on disk (write ahead logging: WAL) (3) Before commit is flushed to log, all writes of transaction must be reflected on disk goupee.com fb.com/groups/goupee 5
Undo Logging Recovery Rules Let S is set of unfinished transactions <start Ti> in log <commit Ti> or <abort Ti> is not in log For each <Ti, X, v> in log If Ti S then - Write(X, v) - Output(X) For each Ti S Write <abort Ti> to log Undo-Logging & Checkpoint <start T > <start T1> 1 <T , A, 5> <T1, A, 5> 1 <start T > <start T2> 2 <T , B, 10> <T2, B, 10> 2 <T , C, 15> <start ckpt (T1,T2)> 2 <T , C, 15> <T2, D, 20> 2 <commit T > <start T3> 1 <T , D, 20> <commit T2> 1 <checkpoint> <commit T1> <start T > <T3, E, 25> 3 <commit T > <T3, E, 25> 2 <T , F, 30> <end ckpt> 3 <T , F, 30> 3 scan scan goupee.com fb.com/groups/goupee 6
Redo-logging Step Action t Mem A Mem B Disk A Disk B Mem Log 1 <start T> 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 <T, A, 16> 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 <T, B, 16> 8 <commit T> 9 Flush log 10 Output(A) 16 16 16 16 8 11 Output(B) 16 16 16 16 16 <T, end> Redo-logging Rules (1) For every action, generate redo log record (containing new value) (2) Before X is modified on disk (DB),all log records for transaction that modified X (including commit) must be on disk (3) Flush log at commit (4) Write END record after DB updates flushed to disk goupee.com fb.com/groups/goupee 7
Redo-logging Recovery Rules Let S = set of transactions with <Ti, commit> in log no <Ti, end> in log For each <Ti, X, v> in log, in forward order (earliest latest) If Ti S then write(X, v) output(X) For each Ti S write <Ti, end> Redo Logging & Checkpoint <start T1> <start T1> <T , A, 5> <T , A, 5> 1 1 <start T2> <start T2> <commit T > <commit T > 1 1 <T2, B, 10> <T2, B, 10> <start ckpt (T )> <start ckpt (T )> 2 2 <T2, C, 15> <T2, C, 15> <start T > <start T > 3 3 <T3, D, 20> <T3, D, 20> <end ckpt> scan <commit T > 2 <commit T3> scan goupee.com fb.com/groups/goupee 8
Discussion Undo Logging need to write to disk as soon transaction finishes Access disk Redo Logging need to keep all modified blocks in memory until commit Use memory Undo/Redo Loggin Step Action t Mem A Mem B Disk A Disk B Mem Log 1 <start T> 2 Read(A,t) 8 8 8 8 3 t:=t*2 16 8 8 8 4 Write(A,t) 16 16 8 8 <T, A, 8, 16> 5 Read(B,t) 8 16 8 8 8 6 t:=t*2 16 16 8 8 8 7 Write(B,t) 16 16 16 8 8 <T, B, 8, 16> 8 Flush log 9 Output(A) 16 16 16 16 8 10 <commit T> 11 Output(B) 16 16 16 16 16 goupee.com fb.com/groups/goupee 9
Undo/Redo Logging Rules Page X can be flushed before or after T commit Log record flushed before corresponding updated page (WAL) Flush at commit (log only) Undo/Redo Logging & Checkpoint <start T1> <start T > <T1, A, 4, 5> 1 <T , A, 4, 5> <start T2> 1 <start T > <commit T1> 2 <commit T > <start T3> 1 <T , B, 9, 10> <T2, B, 9, 10> 2 <start ckpt (T )> <T3, E, 6, 7> 2 <T , C, 14, 15> <start ckpt (T2, T3)> 2 <start T > <T2, C, 14, 15> 3 <T , D, 19, 20> <T3, D, 19, 20> 3 <end ckpt> <end ckpt> <commit T > <commit T2> 2 scan scan goupee.com fb.com/groups/goupee 10
Undo/Redo Logging Recovery Rules Backwards pass (end of log latest valid checkpoint start) Constructing set S of committed transactions undo actions of transactions not in S undo pending transactions follow undo chains for transactions in (checkpoint active list) – S Forward pass (latest checkpoint start end of log) redo actions of S transactions goupee.com fb.com/groups/goupee 11
Showing the first 11 pages. Download the document to see it all.
No comments yet. Be the first!
Comments (0)
No comments yet. Be the first!