Database Recovery (theory)

A Recovery Manager protects the DBMS from failures. It keeps two logs:

  1. REDO: committed transactions not saved in the disk yet
  2. UNDO: non-commited transactions already saved to the disk

Thefore a complete log will contain at least:

  • REDO information for each update
  • UNDO information for each update
  • Commit for each transaction

REDO example log:

b1, r1[b56], w1[b56], r1[b34], w1[b34], c1

Log b1 
REDO w1[b56, value = blabla]
REDO w1[b34, value = blabla]
Log c1

When b56 is written on disk it is removed from the REDO log, and so on. UNDO example log:

b1, w[b34], w1[b56]

Log b1
UNDO w1[b56, value = blabla]
UNDO w1[b34, value = blabla]
Log c1

Until a T has not committed, there is an UNDO log for every object the T wrote, so if the T aborts we can roll back everything

Basic Recovery Procedure

  1. UNDO: Scan backward through the log and perform UNDO on every uncommitted transaction
  2. REDO: Scan forward through the log and perform REDO on every committed transaction

Example

wv[o1], cv, wx[o2], wy[o1], cy, wz[o2]

UNDO z[o2], x[o2]
REDO v[o1], y[o1]

If NO REDO log is kept, must flush committed Ts to disk If NO UNDO log is kept, Ts mus never write uncommitted data

Cache Consistent Checkpoints

Forces the db in some known state, speeds up the recovery procedure, and limits the log size. Suspend all Ts, write a checkpoint + active Ts. The recovery goes this way:

  1. perform UNDOs back to cp
  2. perform UNDOs of non-committed Ts from cp backward
  3. perform REDOs after cp

The idea behind 2 is: say I have checkpoint(1, 3):

  • T1 commits after the checkpoint, so nothing to be done
  • T3 will never commit, I have to UNDO T3 transactions before the checkpoint

in other words, UNDO every T in (cp – Committed Ts) before the checkpoint.