1 of 57

2 of 57

3 of 57

4 of 57

5 of 57

6 of 57

7 of 57

8 of 57

9 of 57

10 of 57

11 of 57

12 of 57

13 of 57

14 of 57

15 of 57

16 of 57

17 of 57

18 of 57

19 of 57

20 of 57

21 of 57

22 of 57

23 of 57

24 of 57

25 of 57

26 of 57

27 of 57

28 of 57

29 of 57

30 of 57

31 of 57

32 of 57

33 of 57

34 of 57

35 of 57

36 of 57

37 of 57

38 of 57

39 of 57

40 of 57

41 of 57

42 of 57

43 of 57

44 of 57

45 of 57

46 of 57

47 of 57

48 of 57

49 of 57

50 of 57

51 of 57

52 of 57

53 of 57

54 of 57

55 of 57

56 of 57

57 of 57

CSE 444: Database Internals

Section 8:

Transactions – Recovery with ARIES

1

Review in this section

Recovery for ARIES

Follows homework closely

2

ARIES

A popular protocol for UNDO-REDO logging

Steal (like UNDO)

Changes by uncommitted transactions can be written to disk when a dirty page is flushed

No-force (like REDO)

Changes by committed transactions may not have been written to disk

Write-ahead logging:

Any changes to a database object is first recorded in the log, and the log is written to disk, before the change to database object is written to disk
A record of every change to the database is available while recovering from a crash

3

ARIES Data Structures

4

pageID	recLSN

Dirty page table

Log

transID	lastLSN	status

Transaction table

Log Record “Types”

Update: easy

Commit: log-tail forced-written to disk, up to & including commit

(note that still no-force, the actual modified pages may not be written, and much smaller cost)

Abort: abort type log record is written + undo is initiated for this transaction

End: when a transaction is aborted or committed, some additional actions are performed, after that an end record is written

CLR:

Undoing updates (during abort or recovery from crash),

for every update record undone, write a CLR (Compensation Log Record)

5

Example.

T₁₀₀₀ changes the value of A from “abc” to “def” on page P500
T₂₀₀₀ changes the value of B from “hij” to “klm” on page P600
T₂₀₀₀ changes the value of D from “mnp” to “qrs” on page P500
T₁₀₀₀ changes the value of C from “tuv” to “wxy” on page P505
T₂₀₀₀ commits and the end log record is written
T₁₀₀₀ changes the value of E from “pq” to “rs” on page P700
P600 is flushed to disk
Crash!!

Example is adopted from Ramakrishnan-Gehrke book

6

Same as in Section 6

ARIES Data Structures

7

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

pageID	recLSN

Dirty page table

Log

transID	lastLSN	status

Transaction table

Buffer Pool

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

First operation:�1. T₁₀₀₀ changes the value of A from “abc” to “def” on page P500?

8

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

pageID	recLSN

Dirty page table

Log

transID	lastLSN	status

Transaction table

Buffer Pool

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes�1. T₁₀₀₀ changes the value of A from “abc” to “def” on page P500

9

P500�PageLSN= 101	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

pageID	recLSN
P500	101

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running

Transaction table

Buffer Pool

A = def D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

In hw4/lecture notes,��1. “Transaction T3 writes A”��If it is stored in LSN8 (say), and A is not written earlier, �then log entry = “Write A, A -> A8”��2. Also, “page id” was not mentioned in log entries in some places (implied from the log entry)�� It is ok if you do not write page Id in hw4��3. Note the “status” column in transaction table� was omitted in some lecture 6 slides

10

Comments

Next:�2. T₂₀₀₀ changes the value of B from “hij” to “klm” on page P600 ?

11

P500�PageLSN= 101	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

pageID	recLSN
P500	101

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running

Transaction table

Buffer Pool

A = def D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�2. T₂₀₀₀ changes the value of B from “hij” to “klm” on page P600 ?

12

P500�PageLSN= 101	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running
T₂₀₀₀	102	Running

Transaction table

Buffer Pool

A = def D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�3. T₂₀₀₀ changes the value of D from “mnp” to “qrs” on page P500?

13

P500�PageLSN= 101	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running
T₂₀₀₀	102	Running

Transaction table

Buffer Pool

A = def D = mnp

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�3. T₂₀₀₀ changes the value of D from “mnp” to “qrs” on page P500

14

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running
T₂₀₀₀	103	Running

Transaction table

Buffer Pool

A = def D = qrs

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�4. T₁₀₀₀ changes the value of C from “tuv” to “wxy” on page P505?

15

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	101	Running
T₂₀₀₀	103	Running

Transaction table

Buffer Pool

A = def D = qrs

C = tuv

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�4. T₁₀₀₀ changes the value of C from “tuv” to “wxy” on page P505?

16

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running
T₂₀₀₀	103	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�5. T₂₀₀₀ commits and the end log record is written

17

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running
T₂₀₀₀	103	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�5. T₂₀₀₀ commits and the end log record is written --- step 1

18

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running
T₂₀₀₀	103	Committed

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�5. T₂₀₀₀ commits and the end log record is written --- step 2

19

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running
T₂₀₀₀	103	Committed

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

T2000 removed from transaction table

Changes:�5. T₂₀₀₀ commits and the end log record is written --- step 2

20

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running
T₂₀₀₀	103	Committed

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Log written to disk

Note: no force = not the dirty pages changed by T₂₀₀₀!

�Whenever a transaction commits, �log is flushed to the disk == the log-tail is written to disk��NOTE:�1. The “Commit” record is required to be flushed (i.e. all logs up to and including that commit record)�2. The “End” record is not required to be flushed, in this case we are only assuming that it has been flushed as well (so that we have a good example while doing recovery ☺)��

21

Next:�6. T₁₀₀₀ changes the value of E from “pq” to “rs” on page P700

22

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= -

B = klm

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	104	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = pq

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Changes:�6. T₁₀₀₀ changes the value of E from “pq” to “rs” on page P700

23

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= 107

B = klm

pageID	recLSN
P500	101
P600	102
P505	104
P700	107

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	107	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = rs

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�7. Page P600 is flushed to disk

24

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= 107

B = klm

pageID	recLSN
P500	101
P600	102
P505	104
P700	107

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

Dirty page table

Log

transID	lastLSN	status
T₁₀₀₀	107	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = rs

P500�PageLSN= -	P600�PageLSN= -
P505�PageLSN= -	P700�PageLSN= -

B = hij

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�7. Page P600 is flushed to disk – Step 1

25

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= 107

B = klm

pageID	recLSN
P500	101
P600	102
P505	104
P700	107

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

Dirty page table

transID	lastLSN	status
T₁₀₀₀	107	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = rs

P500�PageLSN= -	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Next:�7. Page P600 is flushed to disk – Step 2

26

P500�PageLSN= 103	P600�PageLSN= 102
P505�PageLSN= 104	P700�PageLSN= 107

pageID	recLSN
P500	101
P505	104
P700	107

Dirty page table

transID	lastLSN	status
T₁₀₀₀	107	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = rs

P500�PageLSN= -	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

B = klm

��NOTE: Write Ahead Log – Keep track of all changes to a page��1. All LSNs changing that page must be written to disk�2. In this case it is okay, since the last log record involves P700 while P600 is being flushed�3. When a page is written, we need to ensure that all log records up to the lastLSN of the last transaction that ever wrote to that page are on disk�(Log is always written to disk in order, i.e. we can never skip some log entries in between!)�

27

28

8. CRASH!!

8. Crash!! ---- These are gone from memory

29

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

P500�PageLSN= 103
P505�PageLSN= 104	P700�PageLSN= 107

pageID	recLSN
P500	101
P505	104
P700	106

Dirty page table

transID	lastLSN	status
T₁₀₀₀	104	Running

Transaction table

Buffer Pool

A = def D = qrs

C = wxy

E = rs

P500�PageLSN= -	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Three Recovery Phases of ARIES

Analysis

Reconstructs Dirty page table (for Redo) + Transaction Table (for Undo, active transactions at crash)

Redo

Restores the database state at the time of crash by repeating Updates + CLR

Undo

Undoes the actions of uncommitted transactions
Only updates can be undone, No CLR is ever undone!

30

About Checkpointing

31

This example has no checkpointing == Checkpointing at the beginning (like hw 5 !)

Analysis phase in the recovery starts with empty Dirty Page table and empty Transaction Table

With checkpointing the latest copies of these tables have to be read from disk from the last checkpoint

Analysis Phase

Reconstruct (conservatively) Dirty Page Table and Transaction Table

Read the log from the last checkpoint

Actual pages are not used

32

Analysis Phase

33

pageID	recLSN

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status

Transaction table

Buffer Pool

P500�PageLSN= -	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Will not show the buffer pool from the next slide

Analysis Phase

34

pageID	recLSN
P500	101

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	101	U= Unknown

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

In hw5, you can also write “Running/In progress” instead of “Unknown”

Analysis Phase

35

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	101	U
T2000	102	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Analysis Phase

36

pageID	recLSN
P500	101
P600	102

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	101	U
T2000	103	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Analysis Phase

37

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U
T2000	103	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Analysis Phase

38

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U
T2000	105	C

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Write A or Abort if you see an Abort log instead

Analysis Phase

39

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Already written to disk, but reappears

Compare with Dirty Table and Transaction Table right before Crash!!

40

P500�PageLSN= 103
P505�PageLSN= 104	P700�PageLSN= 107

pageID	recLSN
P500	101
P505	104
P700	107

Dirty page table

transID	lastLSN	status
T₁₀₀₀	107	Running

Transaction table

Buffer Pool

A = def D = qrs

C = tuv

E = rs

P500�PageLSN= -	P600�PageLSN= 102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107	104	T₁₀₀₀	P700	Write E “pq” -> “rs”	Update	-

Lost update during crash, but write ahead log, so safe!

Analysis Phase

41

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U
T2000	105	C

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

Remove entry from Transaction Table if you see an End record (both for Aborted and Committed transactions)

REDO Phase

42

“Repeating history” (including actions by transactions that would be aborted in the undo phase)

Work with the Dirty Page Table

Find the smallest recLSN in the dirty page table = FirstLSN

Redo the “Update/CLR” action, unless (in this order)

Affected page is not in the dirty page table
Or, recLSN > LSN being checked (i.e. the page was dirtied later than this LSN)
Or, pageLSN >= LSN being checked (i.e. LSN still not at most recent change)

End/Commit/Abort LSNs are “skipped”

In HW, write “Redone” or “Skipped” for each LSN

Analysis Phase

43

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

REDO Phase: find firstLSN

44

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

REDO Phase

45

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= “-” to 101

A = def D = mnp

Buffer Pool

Affected page is not in the dirty page table: N
Else, recLSN > LSN being checked: N
Else, pageLSN >= LSN being checked: N
REDO

REDO Phase

46

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 101	P600 PageLSN= 102

A = def D = mnp

Buffer Pool

B = klm

Affected page is not in the dirty page table: N
Else, recLSN > LSN being checked: N
Else, pageLSN >= LSN being checked: Y
NO REDO = SKIPPED

REDO Phase

47

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 101 to 103	P600 PageLSN=102

A = def D = qrs

Buffer Pool

B = klm

Affected page is not in the dirty page table: N
Else, recLSN > LSN being checked: N
Else, pageLSN >= LSN being checked: N
REDO

REDO Phase

48

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 103	P600 PageLSN=102
P505�PageLSN=“” to 104

A = def D = qrs

Buffer Pool

B = klm

Affected page is not in the dirty page table: N
Else, recLSN > LSN being checked: N
Else, pageLSN >= LSN being checked: N
REDO

C =wxy

UNDO Phase

49

Work with the Transaction table in the analysis phase

“Loser transactions” must be undone
Changes during undo phases are written (CLR) so that it is not repeated at the time of repeated restarts

Scan backward

Maintain a set ToUndo

Initialize to lastLSNs of all “U” transactions at Transaction Table
undo the “largest LSN” in ToUndo at each step (the latest one in bottom-up order)

UNDO Phase

50

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 103	P600 PageLSN=102
P505�PageLSN= 104

A = def D = qrs

Buffer Pool

B = klm

C =wxy

ToUNDO = {104}

CLR

51

CLR is added so that no “Undo” action is undone
If a CLR is encountered during UNDO phase, goes to the LSN in UndoNextLSN

UNDO Phase

52

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107		T₁₀₀₀		UndoT₁₀₀₀ LSN104	CLR	101

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 103	P600 PageLSN=102
P505�PageLSN= 107

A = def D = qrs

Buffer Pool

B = klm

C =tuv

ToUNDO = {101}

A CLR is written
PageLSN = LSN (CLR)
Value of C is undone

UNDO Phase

53

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107		T₁₀₀₀		UndoT₁₀₀₀ LSN104	CLR	101
108		T₁₀₀₀		UndoT₁₀₀₀ LSN101	CLR	-

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 108	P600 PageLSN=102
P505�PageLSN= 107

A = abc D = qrs

Buffer Pool

B = klm

C =tuv

ToUNDO = {}

UNDO Phase

54

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107		T₁₀₀₀		UndoT₁₀₀₀ LSN104	CLR	101

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 103	P600 PageLSN=102
P505�PageLSN= 107

A = def D = qrs

Buffer Pool

B = klm

C =tuv

ToUNDO = {101}

UNDO Phase

pageID	recLSN
P500	101
P600	102
P505	104

LSN	prevLSN	tID	pID	Log entry	Type	undoNextLSN
101	-	T1000	P500	Write A “abc” -> “def”	Update	-
102	-	T₂₀₀₀	P600	Write B “hij” -> “klm”	Update	-
103	102	T₂₀₀₀	P500	Write D “mnp” -> “qrs”	Update	-
104	101	T₁₀₀₀	P505	Write C “tuv” -> “wxy”	Update	-
105	103	T₂₀₀₀			Commit
106	105	T₂₀₀₀			End
107		T₁₀₀₀		UndoT₁₀₀₀ LSN104	CLR	101
108		T₁₀₀₀		UndoT₁₀₀₀ LSN101	CLR	-
109		T₁₀₀₀			End	-

Dirty page table

Log

transID	lastLSN	status
T1000	104	U

Transaction table

P500�PageLSN= -	P600 PageLSN=102
P505�PageLSN= -	P700�PageLSN= -

B = klm

Disk

A = abc D = mnp

C = tuv

E = pq

P500�PageLSN= 108	P600 PageLSN=102
P505�PageLSN= 107

A = abc D = qrs

Buffer Pool

B = klm

C =tuv

Write an END record

(explicitly mentioned in hw 4 for the aborted transaction)

What happens if T aborts?

56

Write an “abort” log record for T

Like “commit”
Also the status in Transaction table from “Running” to “Aborted”

2 Follow “prevLSN” to undo all updates by T

Like the “UNDO” phase
Undo page content in buffer pool, pageLSN changed to that LSN(CLR)
Write the CLR records

Log entry like “Undo T3 LSN5”
No prevLSN, but undoNextLSN field present
Until undoNextLSN is null

3. Write an “End” log record for T

undoNextLSN

Handling Crashes during Undo

57

[Figure 4 from Franklin97]

In general, for every single crash (even for crash during Analysis/Redo/Undo phases), start again with Analysis

If some CLR records are written to disk during an UNDO phase, then a crash happens (e.g. here LSN 40, 50 are written to disk before the second crash), then the next UNDO phase will skip undoing those CLRs.