Failures, buffer policies and log-based recovery

A database makes two promises that a crash puts to the test: a committed transaction stays committed, and a transaction that did not finish leaves no trace. Log-based recovery keeps both. While the DBMS changes its data, it appends a record of every change to a log, and it makes sure the log reaches the disk before the changes it describes. After a failure, the log tells the DBMS which committed changes never reached the data files, so it can redo them, and which changes of unfinished transactions did reach them, so it can undo them. Which of the two jobs is needed depends on two choices of the buffer manager, called steal and force, and checkpoints in the log bound how much of it recovery has to read.

This lesson sorts failures by what they destroy, works out what steal and force demand, recovers a database from a log in a simulator you can edit, and opens SQLite’s own journal and write-ahead log on disk. It assumes you know what BEGIN, COMMIT and ROLLBACK do, from the lesson on transactions and ACID, and that a buffer manager keeps pages in memory and writes them back later, as the inside of a database engine described.

Three kinds of failure

Each kind of failure destroys something different, and so each needs a different remedy:

• Transaction failure: a constraint violation, a deadlock victim, an explicit ROLLBACK, or a client that disconnects mid-transaction. Only that transaction’s work is lost, and it must disappear: the old values in the log undo it while every other transaction keeps running.
• System failure: a power cut, an operating-system crash, or the DBMS process killed. Everything in memory is lost, the buffer pool, the lock table and any log records not yet written; restart recovery rebuilds the right state from the log and the data files, which survive.
• Media failure: a dead SSD, a corrupted file system, or a deleted data directory. Data on disk is lost, and perhaps the log stored next to it; only a backup, plus the log archived somewhere else since that backup was taken, brings the data back.

A transaction failure is the everyday case. A system failure is what most of this module is about: memory is gone and the disks are intact, so the DBMS must bring the data files to a state that contains every committed transaction and nothing else, using only what reached the disk. A media failure is different in kind, because the log may have been on the failed device too. No algorithm can replay a log that is gone; the remedy is a copy kept elsewhere, the subject of this module’s last lesson.

Recovery theory calls the place where the log lives stable storage: storage that survives the failures being planned for. One disk survives a power cut but not its own death, so real systems approximate stable storage with flushed writes, mirrored disks and copies on other machines. One mishap is missing from that list on purpose: a transaction that commits a mistake, such as a DELETE without a WHERE clause. To the DBMS that is a committed transaction, and recovery will faithfully keep it. Taking back a committed mistake is a job for backups and point-in-time recovery.

Steal and force: what the buffer manager may do

A transaction changes pages in the buffer pool, and the buffer manager decides when those pages go back to disk. Theo Härder and Andreas Reuter gave the two decisive rules their names in a survey of database recovery published in 1983:

• Steal: may the buffer manager write a page holding changes of a transaction that has not committed, for example to free a frame for another page? If it may, a crash can leave uncommitted changes on disk. Recovery must then undo them, so the log has to carry old values.
• Force: must every page a transaction changed reach the disk before its commit completes? If it must, committed work is always on disk and nothing is ever redone. If it need not, which is called no force, a committed change may exist only in memory when the crash comes. Recovery must then redo it, so the log has to carry new values.

The corner with no steal and force is less restful than it looks. A commit that writes ten pages can be cut off after four of them, so even there a journal or shadow pages are needed to make the forced writes atomic. The other corners trade recovery work against the cost of running, and a simulation can put numbers on that trade. The program below runs one seeded workload through a buffer pool of 50 frames four times, once per policy: 300 short transactions that each change 6 pages, 80 % of those changes landing on 40 hot pages, and half-way through, one batch that changes 120 pages. Before every update it notes what a crash at that moment would leave to recovery.

"""One workload under the four buffer policies: what each writes, and what a crash would leave to recovery."""
import random
from collections import OrderedDict

PAGES, HOT, FRAMES = 400, 40, 50   # database pages, the hot ones among them, frames in the buffer pool
SHORT, BATCH = 300, 120            # transactions of 6 updates (80 % of them to hot pages), and one batch


def workload(seed=7):
    rng = random.Random(seed)
    txns = [[rng.randrange(HOT) if rng.random() < 0.8 else rng.randrange(HOT, PAGES) for _ in range(6)] for _ in range(SHORT)]
    txns.insert(SHORT // 2, rng.sample(range(PAGES), BATCH))   # the batch runs half-way through
    return txns


def run(steal, force):
    pool = OrderedDict()   # pages in memory, least recently used first
    dirty = set()          # pages whose copy in memory is newer than the disk
    mine = set()           # pages changed by the running transaction
    late = set()           # pages with a committed change that is not on disk: redo after a crash
    stolen = set()         # pages on disk holding changes of the running transaction: undo after a crash
    stats = {"writes": 0, "at commit": 0, "stolen": 0, "frames": 0}
    redo, undo = [], []    # recovery work if the crash came just before each update

    def write(p, committing=False):
        stats["writes"] += 1
        stats["at commit"] += committing
        if p in mine and not committing:
            stats["stolen"] += 1
            stolen.add(p)
        dirty.discard(p)
        late.discard(p)

    for pages in workload():
        for p in pages:
            redo.append(len(late))
            undo.append(len(stolen))
            if p in pool:
                pool.move_to_end(p)
            else:
                if len(pool) >= FRAMES:
                    victim = next((v for v in pool if steal or v not in mine), None)
                    if victim is not None:      # no steal, and every frame holds a change of the transaction: grow
                        if victim in dirty:
                            write(victim)
                        del pool[victim]
                pool[p] = True
                stats["frames"] = max(stats["frames"], len(pool))
            dirty.add(p)
            mine.add(p)
        for p in mine:                          # COMMIT
            if force:
                write(p, committing=True)
            elif p in dirty:
                late.add(p)
        mine.clear()
        stolen.clear()
    return stats, redo, undo


print(f"{PAGES} pages ({HOT} hot), {FRAMES} frames, {SHORT} transactions of 6 updates and a batch of {BATCH}")
print("Recovery work: pages to redo and to undo if the crash came just before an update (average / worst)\n")
print(f"{'policy':<19}{'writes':>7}{'at commit':>10}{'stolen':>7}{'frames':>7}{'redo':>12}{'undo':>12}")
for steal in (True, False):
    for force in (False, True):
        stats, redo, undo = run(steal, force)
        name = f"{'steal' if steal else 'no steal'}, {'force' if force else 'no force'}"
        r = f"{sum(redo) / len(redo):.1f} / {max(redo)}"
        u = f"{sum(undo) / len(undo):.1f} / {max(undo)}"
        print(f"{name:<19}{stats['writes']:>7}{stats['at commit']:>10}{stats['stolen']:>7}{stats['frames']:>7}{r:>12}{u:>12}")

400 pages (40 hot), 50 frames, 300 transactions of 6 updates and a batch of 120
Recovery work: pages to redo and to undo if the crash came just before an update (average / worst)

policy              writes at commit stolen frames        redo        undo
steal, no force        705         0     70     50   45.6 / 50    1.3 / 69
steal, force          1918      1848     70     50     0.0 / 0    1.3 / 69
no steal, no force     497         0      0    120  78.6 / 120     0.0 / 0
no steal, force       1848      1848      0    120     0.0 / 0     0.0 / 0

Force wrote 1,918 pages, 1,848 of them at commit, so every commit waited for about six page writes. Without force the same work cost 705 writes and none of them was on the commit path: the hot pages stayed in memory and went to disk only when they were evicted. Steal let the batch push 70 of its changed pages to disk before it committed. Without steal the pool had to grow to 120 frames to hold the batch at once, and a batch larger than the memory could not run at all. The last two columns are the bill for that freedom. With steal and no force, a crash finds on average 45.6 pages whose committed changes never reached the disk (78.6 without steal, whose larger pool held more of them back), and a crash during the batch finds up to 69 pages carrying its uncommitted changes.

That is why most engines choose steal and no force, and pay for it with a log that supports both undo and redo. MySQL’s InnoDB, restarting after a crash, applies its redo log and then rolls back the transactions that were active, using its undo logs. PostgreSQL flushes only its write-ahead log at commit, never the data pages, and after a crash it redoes the missing changes from that log. SQLite sits in two other corners, as the last section shows.

Log records and two ways to update

A log is a file of records appended in order, each with a log sequence number (LSN) that grows with every record. Textbooks and exam papers write the records like this:

• <T1 start>: transaction T1 has begun.
• <T1, A, 1000, 900>: T1 changed data item A from 1000 to 900, the old value first, then the new one.
• <T1 commit> or <T1 abort>: T1 has ended, one way or the other.
• <checkpoint {T2, T3}>: a checkpoint was taken while T2 and T3 were running.

With immediate database modification, a transaction may change the data in place, in the buffer pool and perhaps on disk, before it commits. That is steal, so the record of each change carries both values. Redo writes the new value and undo writes the old one, and both are idempotent: doing either twice gives the same result as doing it once, which matters when recovery itself is interrupted. With deferred database modification, a transaction’s changes are held back and applied only after its commit record is in the log. Nothing uncommitted ever reaches the data, so the records need only new values and recovery never undoes anything. The price is that every change must wait somewhere until its transaction commits.

Undo is itself logged. When recovery, or an ordinary ROLLBACK, puts A back to its old value, it appends a redo-only record such as <T3, A, 1000>, and once the whole transaction is undone, <T3 abort>. If the system crashes again, replaying those records repeats the rollback instead of losing it. The ARIES lesson of this module builds a complete recovery method on that idea.

Recovering from a log with a checkpoint

Without a checkpoint, recovery would have to read the whole log from its first record. A checkpoint puts a bound on that. In the simple form used here, the DBMS pauses new updates for a moment, writes every buffered log record and every dirty page to disk, then appends <checkpoint L>, where L lists the transactions still running. Everything logged before the checkpoint is now on disk. After a crash, recovery finds the last checkpoint and makes two passes:

1. Redo, forward from the checkpoint: replay every update and every redo-only record, which repeats history, and keep an undo list that starts as L, gains each transaction that starts and loses each one that commits or aborts.
2. Undo, backward from the end of the log: put back the old value of every update by a transaction on the undo list, appending a redo-only record for each, and append an abort record when a transaction’s start record is reached. The pass ends when every transaction on the list is rolled back, which can be far behind the checkpoint if a long transaction was running.

The simulator makes both passes over an 18-record log of six data items. The checkpoint at LSN 9 finds T2 and T3 running, and two of the later updates reached the disk before the crash. Change CRASH_AFTER or FLUSHED and run it again: the last lines compare the result with what the committed transactions alone would produce.

"""Recovery from a log with a checkpoint: redo forward from the checkpoint, then undo what never committed.

Change CRASH_AFTER (where the log on disk ends) or FLUSHED (which later updates reached the disk) and run it again:
the last line checks the result against the committed transactions alone.
"""

INITIAL = {"A": 1000, "B": 2000, "C": 700, "D": 500, "E": 300, "F": 400}
LOG = [  # LSN 1, 2, 3, ... in order
    ("start", "T1"), ("update", "T1", "A", 1000, 900), ("update", "T1", "B", 2000, 2100), ("commit", "T1"),
    ("start", "T2"), ("update", "T2", "C", 700, 600),
    ("start", "T3"), ("update", "T3", "E", 300, 350),
    ("checkpoint", ("T2", "T3")),  # LSN 9: every change logged before it is on disk; T2 and T3 are running
    ("update", "T3", "D", 500, 800), ("update", "T2", "A", 900, 850), ("commit", "T2"),
    ("start", "T4"), ("update", "T4", "F", 400, 0), ("update", "T3", "B", 2100, 1900),
    ("start", "T5"), ("update", "T5", "C", 600, 650), ("commit", "T5"),
]
CRASH_AFTER = 18  # the log on disk ends with this LSN
FLUSHED = {10, 14}  # updates after the checkpoint whose page reached the disk before the crash


def show(r):
    """A record in the usual notation: <T1 start>, <T1, A, 1000, 900>, <T3, B, 2100> (redo-only), <checkpoint {T2, T3}>."""
    if r[0] == "update":
        return f"<{r[1]}, {r[2]}, {r[3]}, {r[4]}>"
    if r[0] == "compensate":
        return f"<{r[1]}, {r[2]}, {r[3]}>"
    if r[0] == "checkpoint":
        return "<checkpoint {" + ", ".join(r[1]) + "}>"
    return f"<{r[1]} {r[0]}>"


def disk_at_crash(log):
    """The data on disk: every change logged before the checkpoint, plus the flushed ones after it."""
    cp = max(i for i, r in enumerate(log, 1) if r[0] == "checkpoint")
    disk = dict(INITIAL)
    for lsn, r in enumerate(log, 1):
        if r[0] == "update" and (lsn < cp or lsn in FLUSHED):
            disk[r[2]] = r[4]
    return disk


def recover(log, db):
    cp = max(i for i, r in enumerate(log, 1) if r[0] == "checkpoint")
    undo_list = set(log[cp - 1][1])
    replayed = 0
    for r in log[cp:]:  # redo pass: repeat history from the checkpoint
        if r[0] == "update":
            db[r[2]] = r[4]
            replayed += 1
        elif r[0] == "compensate":
            db[r[2]] = r[3]
            replayed += 1
        elif r[0] == "start":
            undo_list.add(r[1])
        elif r[0] in ("commit", "abort"):
            undo_list.discard(r[1])
    print(f"redo pass, LSN {cp + 1} to {len(log)}: {replayed} changes replayed; undo list: {', '.join(sorted(undo_list))}")
    appended = []
    for lsn in range(len(log), 0, -1):  # undo pass: newest first, until every undo-list start is reached
        if not undo_list:
            break
        r = log[lsn - 1]
        if r[0] == "update" and r[1] in undo_list:
            db[r[2]] = r[3]
            appended.append(("compensate", r[1], r[2], r[3]))
            print(f"  LSN {lsn:>2} {show(r):<20} undone: {r[2]} = {r[3]}")
        elif r[0] == "start" and r[1] in undo_list:
            undo_list.discard(r[1])
            appended.append(("abort", r[1]))
            print(f"  LSN {lsn:>2} {show(r):<20} reached: {r[1]} is rolled back")
    print("appended to the log:", " ".join(show(a) for a in appended))
    return db


def committed_only(log):
    """What a correct recovery must reach: the changes of committed transactions and nothing else."""
    done = {r[1] for r in log if r[0] == "commit"}
    db = dict(INITIAL)
    for r in log:
        if r[0] == "update" and r[1] in done:
            db[r[2]] = r[4]
    return db


log = LOG[:CRASH_AFTER]
cp = max(i for i, r in enumerate(log, 1) if r[0] == "checkpoint")
before = {r[1] for r in log[: cp - 1] if r[0] == "commit"}
after = {r[1] for r in log[cp:] if r[0] == "commit"}
disk = disk_at_crash(log)
print("on disk at the crash:", " ".join(f"{k}={v}" for k, v in disk.items()))
db = recover(log, dict(disk))
print("recovered:           ", " ".join(f"{k}={v}" for k, v in db.items()))
print("same as running only the committed transactions:", db == committed_only(log))
print(f"committed before the checkpoint, left alone: {', '.join(sorted(before)) or '-'}; committed after it: {', '.join(sorted(after)) or '-'}")

on disk at the crash: A=900 B=2100 C=600 D=800 E=350 F=0
redo pass, LSN 10 to 18: 5 changes replayed; undo list: T3, T4
  LSN 15 <T3, B, 2100, 1900>  undone: B = 2100
  LSN 14 <T4, F, 400, 0>      undone: F = 400
  LSN 13 <T4 start>           reached: T4 is rolled back
  LSN 10 <T3, D, 500, 800>    undone: D = 500
  LSN  8 <T3, E, 300, 350>    undone: E = 300
  LSN  7 <T3 start>           reached: T3 is rolled back
appended to the log: <T3, B, 2100> <T4, F, 400> <T4 abort> <T3, D, 500> <T3, E, 300> <T3 abort>
recovered:            A=850 B=2100 C=650 D=500 E=300 F=400
same as running only the committed transactions: True
committed before the checkpoint, left alone: T1; committed after it: T2, T5

The five transactions cover every case:

Exam questions usually ask only for the two sets: redo the transactions that committed after the last checkpoint, and undo the ones that were running at it or started after it and never committed. Read the scheme each question states before you apply that rule. Under deferred modification the undo set costs no work, because nothing uncommitted was ever applied. With a fuzzy checkpoint, which does not flush every dirty page, redo may have to start before the checkpoint record.

SQLite’s rollback journal and its write-ahead log

SQLite ships both styles of logging, so two corners of the steal and force table can be opened on disk. In its default rollback journal mode, it copies the original content of each page it is about to change into a journal file next to the database, makes sure the journal is on disk, and only then writes changed pages into the database file. Its documentation names the moment of commit: the deletion of the journal, after the changed pages have been flushed. In WAL mode it works the other way round. The database file keeps the old pages, the new ones are appended to a write-ahead log, and a commit is a frame in that log marked as the end of a transaction.

The program runs the same update, adding 1 to all 2,000 balances of a 108-page table, once in each mode, with a page cache of only 10 pages and spilling switched on, so that changed pages have to leave memory early. It then reads the journal and the log byte by byte, with the layouts that SQLite’s file-format documentation gives.

"""One update, two ways of making it atomic: SQLite's rollback journal, then its write-ahead log."""
import os
import sqlite3
import struct

MAGIC = bytes.fromhex("d9d505f920a163d7")  # the first 8 bytes of a valid rollback-journal header


def pages(path):
    """The 4,096-byte pages of a file."""
    data = open(path, "rb").read()
    return [data[i : i + 4096] for i in range(0, len(data), 4096)]


def changed(before, path):
    """Numbers of the pages that differ from `before`."""
    now = pages(path)
    return {i + 1 for i, page in enumerate(before) if i >= len(now) or now[i] != page}


def journal_segments(path):
    """Each segment of a rollback journal: (its header is valid, its page records as (page number, image))."""
    data = open(path, "rb").read()
    off = 0
    while off + 28 <= len(data):
        magic = data[off : off + 8]
        count, _nonce, _size, sector, page_size = struct.unpack(">iIIII", data[off + 8 : off + 28])
        off += sector
        if magic != MAGIC:  # a header that was never synced: nothing after it counts
            yield False, []
            return
        records = []
        for _ in range(count):
            pgno = struct.unpack(">I", data[off : off + 4])[0]
            records.append((pgno, data[off + 4 : off + 4 + page_size]))
            off += page_size + 8  # page number, image, checksum
        yield True, records
        off = -(-off // sector) * sector  # the next header starts at a sector boundary


def new_bank(name, mode):
    db = sqlite3.connect(name, autocommit=True)
    db.execute(f"PRAGMA journal_mode = {mode}")
    db.execute("CREATE TABLE accounts (id INTEGER PRIMARY KEY, balance INTEGER NOT NULL, note TEXT)")
    db.executemany("INSERT INTO accounts VALUES (?, ?, ?)", [(i, 1000, "-" * 200) for i in range(1, 2001)])
    db.execute("PRAGMA wal_checkpoint")  # in WAL mode, start from a database file that holds everything
    db.execute("PRAGMA cache_size = 10")  # a tiny page cache, and spilling allowed: changed pages leave memory early
    db.execute("PRAGMA cache_spill = ON")
    return db


print("SQLite", sqlite3.sqlite_version)

# 1. Rollback journal, the default: original pages go to bank.db-journal, changes go into bank.db itself.
db = new_bank("bank.db", "DELETE")
before = pages("bank.db")
db.execute("BEGIN")
db.execute("UPDATE accounts SET balance = balance + 1")  # 2,000 rows, every page of the table
early = changed(before, "bank.db")
segments = list(journal_segments("bank.db-journal"))
saved = [rec for ok, recs in segments if ok for rec in recs]
print(f"\n[journal] database pages: {len(before)}, rewritten in bank.db before COMMIT: {len(early)}")
print(f"[journal] segments: {len(segments)}, synced: {sum(ok for ok, _ in segments)}, page images in them: {len(saved)}")
print("[journal] every saved image is the page as it was before the transaction:", all(before[p - 1] == img for p, img in saved))
print("[journal] every page rewritten early has its image in a synced segment:", early <= {p for p, _ in saved})
undone = pages("bank.db")
for pgno, image in saved:
    undone[pgno - 1] = image
print("[journal] bank.db with the saved images put back equals the original:", undone == before)
db.execute("COMMIT")
print(f"[journal] after COMMIT: journal exists: {os.path.exists('bank.db-journal')}, pages changed: {len(changed(before, 'bank.db'))}")
db.close()

# 2. Write-ahead log: bank2.db keeps its pages; new page images are appended to bank2.db-wal.
db = new_bank("bank2.db", "WAL")
before = pages("bank2.db")
db.execute("UPDATE accounts SET balance = balance + 1")  # one transaction, committed
wal = open("bank2.db-wal", "rb").read()
frames = [struct.unpack(">II", wal[off : off + 8]) for off in range(32, len(wal), 24 + 4096)]
print(f"\n[wal] pages changed in bank2.db after COMMIT: {len(changed(before, 'bank2.db'))}")
print(f"[wal] frames in bank2.db-wal: {len(frames)}, commit frames: {sum(1 for _, size in frames if size)}")
print("[wal] the last frame is the commit frame; database size it records, in pages:", frames[-1][1])
db.execute("PRAGMA wal_checkpoint")
print(f"[wal] after a checkpoint, pages changed in bank2.db: {len(changed(before, 'bank2.db'))}")
db.close()

SQLite 3.51.0

[journal] database pages: 108, rewritten in bank.db before COMMIT: 78
[journal] segments: 4, synced: 3, page images in them: 84
[journal] every saved image is the page as it was before the transaction: True
[journal] every page rewritten early has its image in a synced segment: True
[journal] bank.db with the saved images put back equals the original: True
[journal] after COMMIT: journal exists: False, pages changed: 107

[wal] pages changed in bank2.db after COMMIT: 0
[wal] frames in bank2.db-wal: 106, commit frames: 1
[wal] the last frame is the commit frame; database size it records, in pages: 108
[wal] after a checkpoint, pages changed in bank2.db: 106

In journal mode, 78 pages of the uncommitted transaction were rewritten in the database file before COMMIT: SQLite steals. Every one of them had its original image in a journal segment whose header was already valid. The fourth segment’s header was still blank, because a header is written only once the pages behind it are synced, so a crash at that moment would simply have ignored that segment. Putting the saved images back by hand reproduced the original file exactly, which is what SQLite itself does when it finds a journal left by a crash. At COMMIT, all 107 changed pages were in the file and the journal was gone: SQLite forces. Steal with force needs undo only, and the rollback journal is an undo log of whole pages.

In WAL mode the database file was untouched after COMMIT. Even the pages that had to leave the small cache went to the log, as frames without a commit mark. The log held 106 new page images, and only the last frame recorded the database size, the mark of a commit. The database file changed only at the checkpoint. As far as the database file is concerned, that is no steal and no force, and the write-ahead log is a redo log. The next lesson reads its frames one by one.

The two modes differ point by point:

• What the log holds: the journal keeps original page images, for undo; the write-ahead log keeps new page images, for redo.
• Where changes go first: with a journal, into the database file, some even before COMMIT; with a write-ahead log, into the log, and into the database file only at a checkpoint.
• The moment of commit: the journal is deleted; or a frame marked as a commit reaches the log.
• After a crash: the journal’s pages are copied back into the file; or committed frames are kept and frames without a commit are ignored.
• Readers during a commit: shut out while the writer holds its exclusive lock; or not blocked at all, because they keep reading the pages they started with.

Shadow paging is a third way to make an update atomic, with no log at all. A transaction writes the pages it changes to new places on disk, and one write of the pointer to the current page table switches every change on at once, or none. It needs neither undo nor redo, but it scatters each table’s pages across the disk, leaves old copies to be collected, and fits badly with many writers working at once. Härder and Reuter’s survey compares it with logging, and the engines in wide use today log.

Exercise

"""Which transactions does recovery redo, and which does it undo?

A log is a list of records, oldest first:
    ("start", "T1")
    ("update", "T1", "A", 1000, 900)   T1 changed A from 1000 to 900
    ("commit", "T1")
    ("abort", "T1")
    ("checkpoint", ("T2", "T3"))       taken while T2 and T3 were running
"""


def recovery_sets(log):
    """Return (redo, undo), two sets of transaction names, decided from the last checkpoint."""
    redo, undo = set(), set()
    return redo, undo

from recovery import recovery_sets

# Transfers between the accounts of a small bank; the power failed after the last record of each log.
BANK_1 = [
    ("start", "T1"), ("update", "T1", "A", 500, 400), ("update", "T1", "B", 300, 400), ("commit", "T1"),
    ("start", "T2"), ("update", "T2", "C", 900, 850),
    ("checkpoint", ("T2",)),
    ("start", "T3"), ("update", "T3", "A", 400, 450), ("update", "T2", "D", 100, 150), ("commit", "T2"),
    ("start", "T4"), ("update", "T4", "B", 400, 380),
]

BANK_2 = [
    ("start", "T1"), ("update", "T1", "A", 500, 520), ("start", "T2"), ("update", "T2", "B", 300, 250),
    ("checkpoint", ("T1", "T2")),
    ("commit", "T1"), ("start", "T3"), ("update", "T3", "C", 900, 870),
    ("checkpoint", ("T2", "T3")),
    ("start", "T4"), ("update", "T4", "A", 520, 600), ("commit", "T4"), ("update", "T2", "D", 100, 90),
    ("start", "T5"), ("update", "T5", "E", 700, 640), ("commit", "T3"),
]

NO_CHECKPOINT = [
    ("start", "T1"), ("update", "T1", "A", 10, 20), ("commit", "T1"),
    ("start", "T2"), ("update", "T2", "B", 30, 40),
]


def test_one_checkpoint():
    """One checkpoint: T2 commits after it, T3 and T4 never commit"""
    assert recovery_sets(BANK_1) == ({"T2"}, {"T3", "T4"})


def test_last_checkpoint_counts():
    """Two checkpoints: only the second one decides"""
    assert recovery_sets(BANK_2) == ({"T3", "T4"}, {"T2", "T5"})


def test_no_checkpoint():
    """No checkpoint: the whole log is read"""
    assert recovery_sets(NO_CHECKPOINT) == ({"T1"}, {"T2"})

Check yourself

Interview questions

Fresher · What do steal and force mean, and which combination do most database engines use?

Both are rules of the buffer manager. Steal means it may write a page holding changes of a transaction that has not committed, usually to free a frame; force means every page a transaction changed must be on disk before its commit completes. Steal makes recovery undo uncommitted changes that reached the disk, so the log needs old values; no force makes it redo committed changes that never reached the disk, so the log needs new values. Most engines choose steal and no force: a transaction may change more pages than memory holds, and a commit costs one sequential log flush instead of many page writes. The price is a log that supports both undo and redo. SQLite’s rollback-journal mode is a well-known exception: it steals and forces, so it needs undo only.

Fresher · After a crash, which transactions are redone and which are undone when the log has a checkpoint?

Recovery goes back to the last checkpoint record, whose list names the transactions running when it was taken. A transaction that committed before the checkpoint needs nothing, because the checkpoint wrote its changes to disk. One that committed after the checkpoint is redone from its update records. One that was on the list or started after the checkpoint, and has no commit or abort record, is undone, newest change first, even if that takes recovery back past the checkpoint. Real engines redo every logged change after the checkpoint, uncommitted ones included, then undo the incomplete transactions, appending a redo-only record for each undone change and an abort record for each transaction. Exam questions state their scheme: under deferred modification, nothing is ever undone.

Key takeaways

• Transaction, system and media failures destroy one transaction’s work, the contents of memory and the stored data respectively; only the last one needs a copy kept on other storage.
• Steal makes recovery undo, so the log must carry old values; no force makes it redo, so the log must carry new values. Most engines steal and do not force, and their logs support both.
• A checkpoint bounds recovery: redo forward from it, undo backward until every unfinished transaction is rolled back, logging each undone change as a redo-only record.
• Committed before the last checkpoint: nothing. Committed after it: redo. Never committed: undo.
• SQLite’s rollback journal holds original pages and is deleted at commit; its write-ahead log holds new pages and commits with a marked frame, leaving the database file alone until a checkpoint.