Undo/Redo Logging

This is a Database Transaction Log for dealing with Crash Recovery.

Undo/Redo Logging is a combination of two logging approaches:


Log Record

Each log record has the following form:

  • $\langle T_i, X, v_\text{new}, v_\text{old} \rangle$
  • $T_i$ - transaction identifier
  • $X$ - id of database object
  • $v_\text{new}$ - new value of $X$ (like in Redo Logging)
  • $v_\text{old}$ - old value of $X$ (like in Undo Logging)


Rules

  • object $X$ can be flushed either before or after $\langle T_i, \text{commit} \rangle$ - it doesn't matter
  • all the log records should be flushed before corresponding modifications are written to disk (write-ahead logging, WAL)
  • flush at commit: once there's $\langle T_i, \text{commit} \rangle$, flush the log


Non-Quiescent Checkpoint

Algorithm

  • write $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$ and flush the log
    • $(T_1, ..., T_k)$ - all active transactions
  • write to disk all dirty memory buffers
    • a memory buffer is dirty if it contains a modified item
    • no matter whether it was committed or not
  • write $\langle \text{end ckpt} \rangle$ and flush the log


Recovery

The recovery procedure happens in two passes

  • backwards pass
    • undo not committed
    • end $\to$ last valid $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$
  • forwards pass
    • redo committed but not flushed
    • last valid $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$ $\to$ end

Notation:

  • let $S^+$ be all committed transactions and $S^-$ all not-committed transactions

Backwards Pass

  • undo transactions $T_i \in S^-$ - ones that have not committed
  • for doing that may have to go little bit further than the last valid $\langle \text{start ckpt} (T_1, ..., T_k) \rangle$


Forwards Pass

  • redo all transactions $T_j \in S^+$


Drawbacks and Benefits

  • (-) requires more memory - need to store both old and new values
  • (+) can flush to disk whenever we want - gives us more flexibility


Exercises

Main Article: Database Transaction Log Exercises


See also

Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion