Undo Logging

This is a Database Transaction Log for dealing with Crash Recovery

Idea

Hansel and Gretel

  • poor parents dropped the children in the forest
  • the children trace the steps they take and recover the path back to parents

The same in databases:

Undo Logging or Immediate Modification log

  • before writing anything to disk, we record the old value to the log
  • and only after that write

Example

So the way we do it is:

  • we allow to modify things in memory
  • while modifying them we create corresponding records in the log that keeps the old value
  • all the log records have to already be on disk before writing database items back to disk

Example

Transaction $T_1$ Log Comment
$\langle T_1, \text{start} \rangle$ when the transaction starts
read($A, t$); $t \leftarrow t \times 2$;
write($A, t$) $\langle T_1, A, 8 \rangle$ now it's allowed to output($A$)
read($B, t$); $t \leftarrow t \times 2$;
write($B, t$) $\langle T_1, B, 8 \rangle$ now it's allowed to output($B$)
output($A$)
output($B$) now all modifications are on disk
$\langle T_1, \text{commit} \rangle$ transaction has finished


The log record's form is:

  • $\langle \text{transaction id}, \text{DB item}, \text{old value} \rangle$
  • $\langle T_1, B, 8 \rangle$ means $T_1$ made modification to database item $B$ and the old value is 8
  • $\langle T_1, \text{commit} \rangle$ means $T_1$ has successfully completed and it everything has been written to disk


Complications

  • Logs are as well first written to memory and then to disk
  • we cannot flush logs to disk on every action - it would result in too much I/O

Bad States we want to avoid:

  • A database item is modified on disk, but no corresponding log record is not yet written
  • The entire log is on disk (including $\langle T, \text{commit} \rangle$ record) but new values themselves are not


Rules

Undo Logging Rules

  • for every action generate an undo log record with the old value
  • before element $X$ is modified on disk, we write all log records that belong to $X$ to disk
    • this is called Write-Ahead Logging:
    • before writing a new value, write all corresponding log records
  • before you write commit to logs, all modifications should be already flushed on disk


Undo Logging Recovery Rules

How to recover from failures with Undo Logging:

  • we undo the failed transactions
  • i.e. we put the database in the state it was prior this transaction

Recover(log $L$)

  • for every transaction $T_i$ that has a $\langle T_i, \text{start} \rangle$ record in the log
    • if there's already $\langle T_i, \text{commit} \rangle$ or $\langle T_i, \text{abort} \rangle$
      • do nothing
    • otherwise - rollback:
    • for all $\langle T_i, X, v \rangle \in L$
      • write($X, v$)
      • output($X$)
    • write $\langle T_i, \text{abort} \rangle$ to $L$

$\langle T_i, \text{abort} \rangle$ record "commits" the abort of transaction

  • to avoid the situation when in the middle of abortion the power was cut again
  • it says if we undid a transaction successfully we never have to do it again

If during rollback the power was cut again - it's not really a problem

  • we will just overwrite the old value again - and that's it
  • writing the old value twice it's the same as writing it once (it's idempotent)
  • this way you're guaranteed to bet back to a consistent state

Problem:

  • what if a transaction changes a value of some variable several times?
  • in this case we should recover only the first one and ignore the rest

Recover(log $L$)

  • let $S^*$ be all set of transactions $T_i$ with $\langle T_i, \text{start} \rangle \in L$
  • (1) let $S$ be all transaction $T_i \in S^*$ without $\langle T_i, \text{commit} \rangle \in L$ or $\langle T_i, \text{abort} \rangle \in L$
  • (2) for each $\langle T_i, X, v \rangle \in \text{reverse}(L)$ (reverse order: latest $\to$ earliest)
    • if $T_i \in S$:
      • write($X, v$)
      • output($X$)
  • (3) for each $T_i \in S$
    • write $\langle T_i, \text{abort} \rangle$ to $L$


Several Transactions

Note that there can be several transactions that are happening at the same time.

  • Can writes of $\langle T_i, \text{abort} \rangle$ records to log be done in any order?

Example

  • $T_1$ and $T_2$ both write $A$, $T_1$ before $T_2$
  • suppose that both $T_1$ and $T_2$ are rolled back

Suppose we undo both, but write only $\langle T_1, \text{abort} \rangle$ (power was cut when writing $\langle T_2, \text{abort} \rangle$)

  • undoing something 2 times is not a problem, but here we have two transactions
  • recall that $\langle T_1, \text{abort} \rangle$ means the value on disk is the value $A$ had prior to $T_1$
  • we have undone $T_1$ and now trying to undo $T_2$
  • this will rollback to value that was there prior to $T_2$, overwriting value that was prior to $T_1$
  • (That actually could be the value written by $T_1$ which we rolled back)
  • BAD STATE

If we write $\langle T_2, \text{abort} \rangle$, but not $\langle T_1, \text{abort} \rangle$

  • no problems in this case

$\Rightarrow$

  • we must write the abort record in the reversed order of starting times of transactions
  • i.e. latest to start - the first to be undone, and its $\langle \text{abort} \rangle$ record should appear first in the log


Checkpoints

If we keep track on everything we do we'll quickly run out of log space

  • we can free some space by truncating the log
  • are there parts of the log we know for sure are not needed anymore and can be safely discarded?

Need to be careful:

  • just anything before a $\langle T_i, \text{commit} \rangle$?
  • will not work in case of multiple transactions:
  • one transaction could commit, but before this commit there may be records of another transaction that has not committed yet - we'd need to undo them as well


Stop the World

The simplest way

Periodically do the following

  • do not accept any transactions (say "stop" to everybody)
  • wait until all running transactions finish
  • flush their modification to disk (as well as their commit record)
  • commit all log records to disk
  • write a $\langle \text{ckpt} \rangle$ - checkpoint record - to logs
  • now can resume accepting all transactions again


Example

$\langle T_1, \text{start} \rangle$ this can
be removed
from logs
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle T_2, C, 15 \rangle$
$\langle T_1, D, 20 \rangle$
$\langle T_1, \text{commit} \rangle$
$\langle T_2, \text{commit} \rangle$
$\langle \text{ckpt} \rangle$
$\langle T_3, \text{start} \rangle$ undoing only
this part
$\langle T_3, E, 25 \rangle$
$\langle T_3, F, 30 \rangle$
FAILURE


Rollback:

  • If a failure occurs we know that it's enough just to get back to the latest successful checkpoint
  • everything started before the checkpoint had been committed

Problem:

  • we're shutting down the system while doing the checkpoint
  • especially bad when the number of transactions is very high
  • we'd like to avoid that


Non-Quiescent Checkpoint

This is a more complex technique

  • allow new transactions to enter the system during the checkpoint

Algorithm:

  • write to log
    • $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$
    • where $T_1, ..., T_k$ is the list of all active transactions that have not committed yet (and therefore not flushed their results to disk)
  • wait until all $T_1, ..., T_k$ commit or abort
    • and there should the corresponding records in the log
    • don't prohibit other transactions to start
  • when all $T_1, ..., T_k$ have finished
    • write $\langle \text{end ckpt} \rangle$ to log on dist


Idea:

  • to undo we scan backwards until we see the end checkpoint ($\langle \text{end ckpt} \rangle$)
  • at this point we know that all transaction that were active when the checkpoint started had committed
  • so everything before $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$ is already committed - no need to consider them
  • also: every $\langle \text{start ckpt} \rangle$ should have corresponding $\langle \text{end ckpt} \rangle$


So rollback:

  • undo till the latest start checkpoint $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$


Example 1

$\langle T_1, \text{start} \rangle$ can truncate this part
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle \text{start ckpt} (T_1, T_2) \rangle$ $T_1$ and $T_2$ are active
$\langle T_2, C, 15 \rangle$ undoing
only this part

note that $T_3$ started
after checkpoint
$\langle T_3, \text{start} \rangle$
$\langle T_1, D, 20 \rangle$
$\langle T_1, \text{commit} \rangle$
$\langle T_3, E, 25 \rangle$
$\langle T_2, \text{commit} \rangle$
$\langle \text{end ckpt} \rangle$
$\langle T_3, F, 30 \rangle$
FAILURE

In this case

  • we undo only $T_3$
  • $T_1$ and $T_2$ are not undone - we see their commit records


Example 2: Failure during checkpoint

$\langle T_1, \text{start} \rangle$ $\uparrow$
undo to
last
complete
checkpoint

only
not committed
transactions
($T_2$)
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle \text{start ckpt} (T_1, T_2) \rangle$
$\langle T_2, C, 15 \rangle$
$\langle T_3, \text{start} \rangle$
$\langle T_1, D, 20 \rangle$
$\langle T_1, \text{commit} \rangle$
$\langle T_3, E, 25 \rangle$
FAILURE (before $\text{ckpt}$)


In this case:

  • haven't seen $\langle T_3, \text{commit} \rangle$ - undoing $T_3$
  • also have to undo $T_2$
  • don't have to undo $T_1$ - it's committed
  • when going back, cannot stop at $\langle \text{start ckpt} (T_1, T_2) \rangle$:
    • still have to undo all active transactions from the list that haven't committed yet
    • the list is $(T_1, T_2)$, $T_1$ has committed - i.e. undoing only $T_2$
  • so it may be enough to go up until you see that all not-committed transactions start
    • but it can be as far as the last completed checkpoint
    • at this point you're certain that you've undone everything


Drawbacks and Benefits

  • (+) don't need much memory for logging - keep as much as you can, flush when there's no memory
  • (-) not good for backups - it goes back it time, not forward
    • backup with such logging approach: stop the world and do the backup
    • Redo Logging is another alternative without this drawback


Undo/Redo Logging

Undo/Redo Logging is the combination of Undo Logging and Redo Logging


Exercises

Main Article: Database Transaction Log Exercises


Sources

Share your opinion