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