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!

Next

Crash Recovery : Scratching the surface : Part 3

Pingback

Crash Recovery : Scratching the surface : Part 1