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 | UndoNextLSN |
| 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!
DB Geek Girl 