Log-Based Recovery

Crashes happen

Power cuts, kernel panics and hardware faults can stop a database at any moment. When that happens, some changes may already be on disk and others only in memory. The ACID promises still have to hold after a restart:

• Atomicity: a transaction that never committed must leave no trace.
• Durability: a transaction that did commit must keep all its changes.

The tool for both is the log.

The write-ahead log

Every change is first described in an append-only log on stable storage:

The write-ahead logging (WAL) rule: a change’s log record must reach the disk before the changed data page does. A commit is complete only once its <T commit> record is on disk. So anything on disk can be undone, and anything committed can be redone.

Recovery in two passes

1. Redo (forward, from the last checkpoint). Start with undo-list = the checkpoint’s list L.

• <T, X, old, new>: set X = new, whatever T’s fate (repeating history).
• <T start>: add T to the undo-list.
• <T commit> or <T abort>: remove T.

2. Undo (backward, from the end of the log).

• <T, X, old, new> with T in the undo-list: set X = old, and write a compensation record <T, X, old>.
• <T start> with T in the undo-list: write <T abort>, and remove T.
• Stop when the undo-list is empty.

Worked example

Initial values: A = 1000, B = 2000, C = 700, D = 500. The crash comes after record 10:

• Redo from record 7: T1 commits, so the undo-list becomes {T2}. T3 starts, giving {T2, T3}. Set A = 900 and D = 550.
• Undo backwards, for the losers T2 and T3:
  • D = 500, write <T2, D, 500>.
  • A = 950, write <T3, A, 950>.
  • Reach <T3 start>: write <T3 abort>.
  • T1 committed, so skip its commit record.
  • C = 700, write <T2, C, 700>.
  • Reach <T2 start>: write <T2 abort>.
• Result: A = 950, B = 2050, C = 700, D = 500. Only T1’s committed transfer survives.

Why checkpoints and CLRs?

• Without checkpoints, recovery would have to read the whole log from the very beginning. A checkpoint flushes dirty pages, so redo can safely start there.
• If the system crashes again during recovery, the compensation records written so far are redone like any other update, and undo carries on where it stopped. Recovery is idempotent: running it twice gives the same result.

Real systems such as PostgreSQL, MySQL InnoDB and SQL Server use refinements of this scheme. The best known is ARIES (analysis, redo, undo).

Code

def recover(log, db):
    """Undo/redo recovery after a crash. log: list of records, db: values on disk."""
    cp = max(i for i, r in enumerate(log) if r[0] == 'checkpoint')
    undo = set(log[cp][1])                       # transactions active at the checkpoint
    for r in log[cp + 1:]:                       # REDO: repeat history from the checkpoint
        if r[0] == 'update':
            db[r[2]] = r[4]
        elif r[0] == 'start':
            undo.add(r[1])
        elif r[0] in ('commit', 'abort'):
            undo.discard(r[1])
    for r in reversed(log[:]):                   # UNDO: roll back the losers
        if not undo:
            break
        if r[0] == 'update' and r[1] in undo:
            db[r[2]] = r[3]
            log.append(('clr', r[1], r[2], r[3]))   # compensation record
        elif r[0] == 'start' and r[1] in undo:
            log.append(('abort', r[1]))
            undo.discard(r[1])
    return db

log = [('start', 'T1'), ('update', 'T1', 'A', 1000, 950), ('start', 'T2'),
       ('update', 'T1', 'B', 2000, 2050), ('update', 'T2', 'C', 700, 600),
       ('checkpoint', ['T1', 'T2']), ('commit', 'T1'), ('start', 'T3'),
       ('update', 'T3', 'A', 950, 900), ('update', 'T2', 'D', 500, 550)]
disk = {'A': 900, 'B': 2050, 'C': 600, 'D': 500}   # what happened to reach the disk
print(recover(log, disk))     # {'A': 950, 'B': 2050, 'C': 700, 'D': 500}

We checked this against every crash point in the model: the recovered values always equal the effect of the committed transactions alone.

Common mistakes

• Undoing committed transactions. Only transactions without a commit (or abort) record are losers.
• Starting redo from the beginning of the log. Start from the last checkpoint.
• Stopping undo at the checkpoint. A loser that started before the checkpoint has older updates that must be undone too.
• Skipping redo for losers. Repeating history first makes the undo pass simple and correct.
• Forgetting that a transaction counts as committed only once its commit record is on disk.