Redo Logging

This is a Database Transaction Log for dealing with Crash Recovery

Also called deferred modification

  • we don't record the old value, but the new value
  • instead of undoing actions, we will do them
  • $\langle T_i, \text{commit} \rangle$ record may appear earlier than the actual modification is written to disk
  • but as soon as modified data is flushed, we write $\langle T_i, \text{end} \rangle$


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, 16 \rangle$ $A$'s new value is 16
read($B, t$); $t \leftarrow t \times 2$;
write($B, t$) $\langle T_1, B, 16 \rangle$ $B$'s new value is 16
$\langle T_1, \text{commit} \rangle$ record in log appear earlier then actual modification
output($A$)
output($B$) now all modifications are on disk
$\langle T_1, \text{end} \rangle$ transaction finishes


Rules

Redo Logging Rules

  • for every action we keep a redo log with new values
  • before a DB item $X$ is flushed to disk, all log records for transactions $T_i$ that have modified $X$ (including $\langle T_i, \text{commit} \rangle$) must be on disk
  • flush the log on commit
  • write $\langle T_i, \text{end} \rangle$ only when all modified BD items are on disk

Note that we cannot go to the previous state with this approach: no rollback


Redo Logging Recovery Rules

$\langle T_i, \text{commit} \rangle$ means

  • user knows that the transaction was executed correctly
  • even if now some error happens we have to ensure that the DB state is the state that the user expects after the transaction happens

$\langle T_i, \text{end} \rangle$ says

  • the results are on disk - no need to redo anything

Redo(log $L$)

  • let $S$ be set of all transactions $T_i$ with $\langle T_i, \text{commit} \rangle \in L$ but without $\langle T_i, \text{end} \rangle$
  • for each $T_i \in S$ and for each $\langle T_i, \text{commit} \rangle \in L$ in forward order (earliest $\to$ latest)
    • write($X, v$)
    • output($X$) (write and ensure the modifications appear on disk)


Non-Quiescent Checkpoint

Idea similar to Undo Logging, but different semantics

Algo for creating checkpoints:

  • write a log records $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$
    • $T_1, ..., T_k$ are active not-committed transactions
  • flush the log
  • write to disk modifications of all transactions T_i that have $\langle T_i, \text{commit} \rangle$ record, but don't have $\langle T_i, \text{end} \rangle$ records
    • it means the modifications are still in memory buffers and have not been flushed to disk yet
  • one the modifications are written to disk, write $\langle \text{end ckpt} \rangle$ and flush the log


Example

$\langle T_1, \text{start} \rangle$
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$ $\uparrow$
$\langle T_1, \text{commit} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle \text{start ckpt} (T_2) \rangle$ $T_2$ is the only active transaction (no $\langle T_2, \text{commit} \rangle$ record)
$\langle T_2, C, 15 \rangle$
$\langle T_3, \text{start} \rangle$
$\langle T_3, D, 20 \rangle$
$\langle T_1, \text{end} \rangle$ $T_1$ had $\langle T_1, \text{commit} \rangle$, but didn't have $\langle T_1, \text{end} \rangle$ when $\langle \text{start ckpt} \rangle$ was added
$\langle \text{end ckpt} \rangle$ now $T_1$ ended, it means we can end the checkpoint
$\langle T_2, \text{commit} \rangle$
$\langle T_3, \text{commit} \rangle$
FAILURE


We redo all transactions that:

  • were active and not-committed when the checkpoint begun
  • or started later - after the checkpoint begun

In this case

  • these transactions are $T_2$ and $T_3$
  • i.e. we need to read the log records till we see $\langle T_2, \text{start} \rangle$
    • which was before $\langle \text{start ckpt} (T_2) \rangle$
  • anything else is already on disk for sure

To recover, we :

  • scan backwards till we see the $\langle \text{end ckpt} \rangle$ and corresponding $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$
  • then we scan a little bit more upwards till we see all records $\langle T_1, \text{start} \rangle ... \langle T_k, \text{start} \rangle$
  • redo them from this point


If we see both $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$ and $\langle \text{end ckpt} \rangle$ it means

  • while scanning back when see $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$ after $\langle \text{end ckpt} \rangle$ it tells us that:
  • all transactions $T_j$ that
    • had committed before $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$
    • but their modifications had not been flushed to disk (they didn't have $\langle T_j, \text{end} \rangle$ records)
    • they would write all their modifications to disk
    • otherwise there would not be $\langle \text{end ckpt} \rangle$ record


Example 2

$\langle T_1, \text{start} \rangle$
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$ $\uparrow$
$\langle T_1, \text{commit} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle \text{start ckpt} (T_2) \rangle$
$\langle T_2, C, 15 \rangle$
$\langle T_3, \text{start} \rangle$
$\langle T_3, D, 20 \rangle$
$\langle T_1, \text{end} \rangle$
$\langle \text{end ckpt} \rangle$
$\langle T_2, \text{commit} \rangle$
FAILURE
$\langle T_3, \text{commit} \rangle$


This case a little bit different

  • we still have to re-do $T_2$, but not $T_3$
  • $T_3$'s commit record is not on disk - don't need to redo it


Example 3

If a failure occurs after $\langle \text{start ckpt} (T_2) \rangle$ but before $\langle \text{end ckpt} \rangle$

  • you'll have to redo from the previous complete $\langle \text{start ckpt} (...) \rangle$
  • (or from the beginning of the log)
$\langle T_1, \text{start} \rangle$ $\uparrow$
$\langle T_1, A, 5 \rangle$
$\langle T_2, \text{start} \rangle$
$\langle T_1, \text{commit} \rangle$
$\langle T_2, B, 10 \rangle$
$\langle \text{start ckpt} (T_2) \rangle$
$\langle T_2, C, 15 \rangle$
$\langle T_3, \text{start} \rangle$
$\langle T_3, D, 20 \rangle$
$\langle T_1, \text{end} \rangle$
FAILURE


Note:

  • for the Non-Quiescent Check Logging records $\langle T_i, \text{end} \rangle$ are redundant
  • the checkpoints give us the same information


Drawbacks and Benefits

  • (-) need to keep all modified blocks in memory until the commit happens
  • (+) good for backups: just replay the logs on another DB instance


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