Bài giảng Thiết kế và quản trị cơ sở dữ liệu - Bài 12: Crash Recovery - Vũ Tuyết Trinh

1 
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 Consistent DB’ T 
IF T starts with consistent state + 
 T executes in isolation 
THEN T leaves consistent state 
with assumption 
2 
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 
memory disk 
CPU 
M D 
3 
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 
Log the beginning of the transaction execution 
 transaction is already finished 
Transaction is calcel 
Transaction makes an update actio, before update X=v, after 
update x = w 
4 
Transaction Log 
 Handled in main memory and put to external 
memory (disk) when possible 
Actions Log 
Data 
Memory 
A = 8 16 
B = 8 16 
Log 
Disk 
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 
 or 
5 
Undo-logging 
Action 
Read(A,t) 
t:=t*2 
Write(A,t) 
Read(B,t) 
t:=t*2 
Write(B,t) 
Output(A) 
Output(B) 
t 
8 
16 
16 
8 
16 
16 
16 
16 
Mem A Mem B Disk B Disk A 
8 
8 
16 
16 
16 
16 
16 
16 
8 
8 
16 
16 
16 
8 
8 
8 
8 
8 
8 
16 
16 
8 
8 
8 
8 
8 
8 
8 
16 
Step
1 
2 
3 
4 
5 
Mem Log 
6 
7 
8 
9 
10 
11 
12 
Flush log 
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 
6 
Undo Logging Recovery Rules 
 Let S is set of unfinished transactions 
 in log 
 or is not in log 
 For each in log 
 If Ti S then - Write(X, v) 
 - Output(X) 
 For each Ti S 
 Write to log 
Undo-Logging & Checkpoint 
scan 
scan 
7 
Redo-logging 
Action 
Read(A,t) 
t:=t*2 
Write(A,t) 
Read(B,t) 
t:=t*2 
Write(B,t) 
Output(A) 
Output(B) 
t 
8 
16 
16 
8 
16 
16 
16 
16 
Mem A Mem B Disk B Disk A 
8 
8 
16 
16 
16 
16 
16 
16 
8 
8 
16 
16 
16 
8 
8 
8 
8 
8 
8 
16 
16 
8 
8 
8 
8 
8 
8 
8 
16 
Step 
1 
2 
3 
4 
5 
Mem Log 
6 
7 
8 
9 
10 
11 
Flush log 
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 
8 
Redo-logging Recovery Rules 
 Let S = set of transactions with 
 in log 
 no in log 
 For each in log, in forward order (earliest 
latest) 
 If Ti S then write(X, v) 
 output(X) 
 For each Ti S 
 write 
Redo Logging & Checkpoint 
scan 
scan 
9 
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 
Action 
Read(A,t) 
t:=t*2 
Write(A,t) 
Read(B,t) 
t:=t*2 
Write(B,t) 
Output(A) 
Output(B) 
t 
8 
16 
16 
8 
16 
16 
16 
16 
Mem A Mem B Disk B Disk A 
8 
8 
16 
16 
16 
16 
16 
16 
8 
8 
16 
16 
16 
8 
8 
8 
8 
8 
8 
16 
16 
8 
8 
8 
8 
8 
8 
8 
16 
Step 
1 
2 
3 
4 
5 
Mem Log 
6 
7 
8 
9 
10 
11 
Flush log 
10 
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 
scan 
scan 
11 
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