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$

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 |

- 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

- need to use Undo Logging for this or Undo/Redo Logging

$\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)

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

$\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

$\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

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

- (-) 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 is the combination of Undo Logging and Redo Logging

- Main Article:
*Database Transaction Log Exercises*