Recovery system in database

WE will use log and checkpoints to recover

Transaction roll back

If we try to rollback transaction Ti

Scan the log backward

We will try to scan each log record <Ti, Xj, V1, V2> that belongs to Ti.

Then we will write V1(the old value) to Xj.

Write a REDO-only log <Ti, Xj, V1> to the log. This is called the compensating log. ( we don’t need to store both old and new value here since during a undo, because if system crash during recovery, we only need to REDO these logs to finish the UNDO).

Once we found in our backward scan, we stop and add a in log.

Recovery after a crash

REDO phase

Scan the log forward from the last checkpoint. and replay all transactions.
This replay include both rollback and uncommitted transaction.

We also need to determine the list of incomplete transactions. They are either in ( active transactions during checkpoint ) or start after the checkpoint and didn’t have neither commit nor abort. This list is called undo-list and will be used to rollback during UNDO.

UNDO Phase

Rollback all transactions in the undo-list by scanning the log backward from the end

If DB finds a transaction Ti in the undo list, it will rollback to old value.

When DB sees a and Ti is in the undo list, that means we have undone all Ti’s change and can write a to the log to signified that this transaction is complete.

Undo terminate when we have seen all Ti’s

Fuzzy checkpoint

This will allow updates to start once has been written, but before the modified buffers are written to disk.

If a crash happened before all pages in the modified buffers are written to disk, we might have an incomplete checkpoint.
We will deal with this by storing a fixed position last-checkpoint ptr on disk and we will not update this ptr when we first write .

The will create a list of modified buffer blocks and last-checkpoint will only be updated once all modified blocks are written to disk.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax