Wednesday, April 13, 2016

Writing log operations when restarting work

Pointers for writing log operations when restarting work using immediate update approach

Roll backward phase
Start from the end of the transaction log. Go backwards LSN by LSN (i.e. step by step). At each LSN, go down the following list:
  • Is the transaction associated with the LSN already in the committed or uncommitted list? If yes, ignore this step and skip to (2). If not, add transaction to committed list if you encounter “COMMIT” (because all actions would have been committed). Otherwise, add to uncommitted list.
  • If transaction is in committed list, take “No action”. If transaction is in uncommitted list, and it is INSERT or UPDATE, add “Undo” to log operations. If transaction is in uncommitted list, and it is START, remove transaction from list of uncommitted transactions
  • When encountering CKPT, note which transactions are uncommitted
  • Is the list of uncommitted transactions now empty? If so, roll backward phase ends. The roll forward phase begins: start reading the below text. If the list of uncommitted transactions is non-empty, restart (1) from using the next action.

Roll forward phase
The roll forward phase begins: start by reading the log at the most recent checkpoint record. Iterate forward through the list of LSNs. For each action, consider which bullet point is applicable:
  • Ignore actions on uncommitted transactions
  • When encountering INSERT or UPDATE on committed transactions, add “Redo” to log operations
  • When encountering COMMIT on committed transactions, remove that transaction from the commit list
  • End when committed transaction list is empty. (Uncommitted transaction list should already be non-empty).

Pointers for writing log operations when restarting work using deferred update approach

Roll backward phase
Start from the end of the transaction log. Go backwards LSN by LSN (i.e. step by step). At each LSN, go down the following list, taking whichever actions are necessary:

  1. Is transaction uncommitted and incomplete?
    1. If yes, take no action, since the transaction cannot possibly be complete
    2. If no, for COMMIT, add to “committed list” and “incomplete list” (Note: you are adding to two lists)
    3. If no, for UPDATE and INSERT, write down “take no action, redo during roll forward phase”
  2. At CKPT, note which committed transactions for which START records have not been found (i.e. committed transactions which are still on the incomplete list).
  3. If transaction is already on the incomplete list, remove from incomplete list when START is encountered.
  4. When incomplete list is empty, start roll forward.

Roll forward phase

Iterate through actions associated with transactions on the “committed list”, applying the below points where applicable:
  1. Redo actions were labelled “redo” during the rollback phase
  2. Remove transactions from committed list when COMMIT is reached.
  3. End when committed list is empty (incomplete list will also be empty)