Wednesday, January 10, 2018

Crash Recovery : Scratching the surface : Part 2

Continuing where we left off in the last post, we saw why database systems use logs for recovery. Besides logs there are other supporting data structures that are needed for recovery.
Broadly speaking there are three data structures that are part of a recovery mechanism (We’ll discuss the ARIES mechanism here)
  • Log
  • Transaction Table
  • Dirty Page Table

What exactly is a log record?


As we discussed in the post before  log is nothing but a history of actions executed by the database system. It is divided into two parts log tail and log file. Log tail is most recent portion of the log that is kept in main memory and is periodically forced to stable storage (for example, when a transaction commits) Log file is a file stored on stable storage.

The structure of a log can be summarized as shown in the table below

LSN
prevLSN
transID
type
pageID
length
offset
Before-
image
After-
image


LSN is log sequence number, generally it is a monotonically increasing unique identifier. prevLSN is the LSN of the previous log record in the transaction, implementing the sequence of logs in a transactions as a linked list. It contains the transaction ID of the transaction and pageID of the page being changed, along with the before and after values.

Based on different type of log records, that we will discuss further certain fields may be missing but typically any log record written on an update should have this format.

Transaction table 

A transaction table can be conceptually depicted as -

TransID
LastLSN
Status

It contains a record for all the active transactions in the system. It contains the transaction id, status of the transaction (in progress, committed or aborted) and LastLSN the LSN of the most recent log record belonging to this transaction.



Dirty Page table

A dirty page is, a page with changes that are not yet written to disk. Dirty Page Table contains one entry for each dirty page and recLSN which is the LSN of the first log record that caused the page to become dirty.

A dirty page table can be conceptually depicted as -


pageID
recLSN
Status


What do logs look like when a transaction happens in the database?

Consider updating a value in database - 

Transaction T1 changes value of X from ABC to DEF. Suppose the data lives on page P500 at offset 21-23. The system will make an entry into the log, transaction table, and dirty page table.


Log


LSN
prevLSN
transID
type
pageID
Length
offset
Before
After
1
-
T1
update
P500

21
ABC
DEF

Transaction Table


transID
lastLSN
T1
1

Dirty Page Table


pageID
recLSN
P500
1

Transaction T2 changes ‘HIJ’ to ‘KLM’ on page P600

Log


LSN
prevLSN
transID
type
pageID
Length
offset
Before
After
1
-
T1
update
P500

21
ABC
DEF
2
-
T2
update
P600


HIJ
KLM

Transaction Table

transID
lastLSN
T1
1
T2
2

Dirty Page Table


pageID
recLSN
P500
1
P600
2


Transaction T2 changes bytes 20 through 22 from GDE to QRS on page P500 and Transaction T1 changes ‘TUV’ to ‘WXY’ on P505

Log

LSN
prevLSN
transID
type
pageID
Length
offset
Before
After
1
-
T1
update
P500
3
21
ABC
DEF
2
-
T2
update
P600
3

HIJ
KLM
3
2
T2
update
P500
3
20
GDE
QRS
4
1
T1
update
P505
3

TUV
WXY

Transaction Table


transID
lastLSN
T1
1
T2
4

Dirty Page Table


pageID
recLSN
P500
1
P600
2
P505
4



What happens when you commit a transaction?

If a system issues a  T2 commit, a commit type log record is written to the log. After this the log tail is flushed to disk and the transaction is considered committed. After this additional actions need to be taken like removing entry for T2 from transaction tables, when these actions are complete an end type log record is written to the log.

Log

LSN
prevLSN
transID
type
pageID
Length
offset
Before
After
1
-
T1
update
P500
3
21
ABC
DEF
2
-
T2
update
P600
3

HIJ
KLM
3
2
T2
update
P500
3
20
GDE
QRS
4
1
T1
update
P505
3

TUV
WXY
5
3
T2
commit
-
-
-
-
-
..








7
5
T2
end
-
-
-
-
-

What happens if you rollback or abort a transaction?


If a system issues a  T1 rollback or if T1 is aborted, the system would read the last log record belonging to T1, that is log record 4, it would then undo the changes made by T1, and write a log record of type “compensation log record” (CLR). CLR in addition to information fields of update records contain another field called undoNextLSN which points to the next record that has to be reversed as a part of the undo process.

LSN
prevLSN
transID
type
pageID
Length
offset
Before
After
Undo
NextLSN
1
-
T1
update
P500
3
21
ABC
DEF

2
-
T2
update
P600
3

HIJ
KLM

3
2
T2
update
P500
3
20
GDE
QRS

4
1
T1
update
P505
3

TUV
WXY

5
4
T1
abort
-
-
-
-
-

6
5
T1
CLR
P505
3

WXY
TUV
1
7
6
T1
CLR
P500
3

DEF
ABC
NULL
8
7
T1
end
-
-
-
-
-
-


Compensation log records are an integral part of a crash recovery mechanism because with write-ahead logging, it is very much possible that the log undoing the transaction that was aborted is written to stable storage but the actual pages have not been flushed to disk. It is also possible that a system crashes in the middle of recovery, when it has undone few changes of a transaction but not all. In such cases,  during crash recovery CLR contains the information needed to redo the rollback / undo. We will see more about this during the overview of the recovery process.  

In summary a log record is written whenever a page is updated or transaction is committed or aborted. Once a transaction is aborted or rolled back the updates are undone and the undo is written to the log in the form of a CLR. In the next post, I’ll try to unravel the crash recovery process. Till then, So long!
Pingback

No comments:

Post a Comment

LDAP Authentication for MySQL

Why LDAP? LDAP stands for Lightweight Directory Access Protocol. It is based on a client server model. A client queries LDAP server, whi...