DBMS

Recovery And Reliability

Checkpoints and Crash Recovery

The log grows forever. After a crash, how far

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 1: Failures and the Write-Ahead Log Time to complete: ~20 minutes

Table of Contents

  1. Why Checkpoints Exist
  2. Fuzzy Checkpoints
  3. The Three Recovery Phases
  4. Analysis
  5. Redo and Undo
  6. Crashing During Recovery
  7. Summary & Next Steps

1. Why Checkpoints Exist

The Problem Without Them
─────────────────────────────────────────
  The log grows forever. After a crash, how far
  back must recovery read?

  Without checkpoints: to the BEGINNING OF TIME.
  A database running for two years would take days
  to restart.
─────────────────────────────────────────

What a Checkpoint Records
─────────────────────────────────────────
  A CHECKPOINT record in the log stating:
    - which transactions were ACTIVE at this moment
    - which pages were DIRTY, and the LSN of the
      earliest change not yet on disk

  Recovery can then start from the checkpoint
  rather than from the start of the log.

  The checkpoint is a promise: everything before
  this point is either on disk or described here.
─────────────────────────────────────────

2. Fuzzy Checkpoints

The Naive Version, and Its Flaw
─────────────────────────────────────────
  A SHARP checkpoint:
    1. stop accepting new transactions
    2. wait for all active ones to finish
    3. flush every dirty page
    4. write the checkpoint record
    5. resume

  Correct, and the database is UNAVAILABLE for
  however long step 3 takes — which on a large
  buffer pool is seconds to minutes.

  Unacceptable.
─────────────────────────────────────────

The Fuzzy Checkpoint
─────────────────────────────────────────
  1. write a BEGIN_CHECKPOINT record
  2. record the active transaction list and the
     dirty page table
  3. write an END_CHECKPOINT record
  4. flush dirty pages GRADUALLY, in the
     background, over the next several minutes

  Transactions never stop. The checkpoint does not
  claim the pages are on disk — it records exactly
  WHICH ones are not, so recovery knows where to
  start.
─────────────────────────────────────────

The Tuning Trade-off
─────────────────────────────────────────
  FREQUENT checkpoints
    ──► short recovery, steady background I/O

  RARE checkpoints
    ──► less I/O, LONG recovery, and large write
        STORMS when one does happen

  PostgreSQL: checkpoint_timeout,
  max_wal_size, checkpoint_completion_target
  (which spreads the flushing across the interval,
  smoothing the I/O).
─────────────────────────────────────────

3. The Three Recovery Phases

The standard algorithm — ARIES — runs three passes over the log.

The Passes
─────────────────────────────────────────
  1. ANALYSIS   forward, from the last checkpoint
                Determine WHO was running and WHICH
                pages were dirty.

  2. REDO       forward, from the earliest dirty
                page LSN
                REPLAY EVERYTHING — including
                transactions that later aborted.

  3. UNDO       BACKWARD, to the start of the
                oldest loser
                Roll back every transaction that
                did not commit.
─────────────────────────────────────────

The Counter-Intuitive Part
─────────────────────────────────────────
  Phase 2 redoes changes from transactions that
  never committed — and phase 3 then undoes them.

  Why not skip them?

  BECAUSE recovery must first REPAIR THE STATE the
  crash left, before it can reason about it. The
  principle is "repeating history": reconstruct
  the exact state at the moment of the crash, then
  undo the losers from there.

  Trying to be selective during redo would require
  knowing which pages held which transactions'
  changes — which is the information the crash
  destroyed.
─────────────────────────────────────────

4. Analysis

def analysis(log, last_checkpoint):
    """Rebuild the state the crash destroyed: who was running, what was dirty."""
    ck = log.read(last_checkpoint)
    active = dict(ck.active_transactions)      # txn -> last LSN seen
    dirty  = dict(ck.dirty_page_table)         # page -> recovery LSN
 
    for record in log.scan_forward(from_lsn=last_checkpoint):
        if record.type == "BEGIN":
            active[record.txn] = record.lsn
        elif record.type in ("COMMIT", "ABORT"):
            active.pop(record.txn, None)       # finished ──► not a loser
        elif record.type == "UPDATE":
            active[record.txn] = record.lsn
            dirty.setdefault(record.page_id, record.lsn)   # first change since flush
 
    losers = set(active)                       # still active at the crash
    redo_start = min(dirty.values(), default=log.end_lsn)
    return losers, dirty, redo_start
The Two Outputs
─────────────────────────────────────────
  LOSERS      transactions with no COMMIT or ABORT
              record. They were in flight when the
              machine stopped and must be undone.

  REDO_START  the earliest LSN whose change might
              not be on disk. Everything before it
              is definitely durable, so redo starts
              here rather than at the checkpoint.
─────────────────────────────────────────

5. Redo and Undo

def redo(log, redo_start, buffer_pool):
    """Repeat history: reconstruct the exact state at the moment of the crash."""
    for record in log.scan_forward(from_lsn=redo_start):
        if record.type not in ("UPDATE", "CLR"):
            continue
        page = buffer_pool.get(record.page_id)
 
        if page.lsn >= record.lsn:
            continue                    # ← the IDEMPOTENCE check (Chapter 1, Sec.5)
                                        #   this change is already on the page
 
        page.apply(record.after_image)
        page.lsn = record.lsn
 
 
def undo(log, losers, buffer_pool):
    """Roll back the losers, newest change first, following prev_lsn chains."""
    to_undo = {t: log.last_lsn_of(t) for t in losers}
 
    while to_undo:
        txn = max(to_undo, key=lambda t: to_undo[t])       # highest LSN first
        record = log.read(to_undo[txn])
 
        if record.type == "UPDATE":
            page = buffer_pool.get(record.page_id)
            page.apply(record.before_image)                 # restore the OLD value
 
            clr = log.append(CLR(txn=txn, page=record.page_id,
                                 undone_lsn=record.lsn,
                                 next_undo=record.prev_lsn))
            page.lsn = clr                                  # ← log the undo itself
 
        if record.prev_lsn:
            to_undo[txn] = record.prev_lsn
        else:
            log.append(AbortRecord(txn))
            del to_undo[txn]
Compensation Log Records
─────────────────────────────────────────
  The CLR is the clever piece.

  When recovery undoes a change, it LOGS that undo
  — with a pointer to what to undo NEXT.

  So if the machine crashes again mid-undo, the
  next recovery reads the CLRs, sees which undos
  are already done, and continues from the right
  place.

  CLRs are REDO-ONLY: they are never themselves
  undone. Undo therefore always makes forward
  progress and can never loop.
─────────────────────────────────────────

6. Crashing During Recovery

The Requirement
─────────────────────────────────────────
  Recovery may be interrupted at any point and
  restarted from the beginning, any number of
  times, and must still produce the correct state.

  This is not a theoretical nicety — a machine that
  crashed once is often about to crash again
  (failing hardware, a bad power supply, an
  out-of-memory loop).
─────────────────────────────────────────

What Makes It Safe
─────────────────────────────────────────
  REDO IS IDEMPOTENT
    The page_lsn check skips changes already
    applied. Running redo five times equals running
    it once.

  UNDO IS RESUMABLE
    CLRs record progress durably. A restarted undo
    skips what is already undone.

  ANALYSIS IS PURE
    It only READS the log to compute two values. It
    modifies nothing.

  Each phase can therefore be re-run from scratch
  with no ill effect.
─────────────────────────────────────────

The Idea Worth Carrying Away
─────────────────────────────────────────
  "Log the intent before doing the work, and make
   replay idempotent."

  It is the same pattern as:
    - a filesystem journal
    - an idempotency key on a payment API
      (Module 3, Chapter 6's UPSERT)
    - completed_tool_calls in a durable agent
      (Agentic AI Notes, Module 6, Chapter 2)

  Learn it once here, where it is at its most
  rigorous, and you will recognise it everywhere.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • Checkpoints bound recovery time by recording which transactions were active and which pages were dirty, so recovery need not read the whole log.
  • Fuzzy checkpoints record that state without stopping transactions or waiting for flushes, trading a slightly longer recovery for continuous availability.
  • Recovery redoes everything including aborted transactions — repeating history first, then undoing losers — because being selective would need information the crash destroyed.
  • Compensation log records make undo resumable, and the page-LSN check makes redo idempotent, so recovery survives crashing during recovery.

Concept Check

  1. Why does a sharp checkpoint make the database unavailable, and how does a fuzzy checkpoint avoid it?
  2. Why does the redo phase replay changes from transactions that are about to be undone?
  3. What role do CLRs play, and why are they never themselves undone?

Next Chapter

→ Chapter 3: Backup, Replication and Availability

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index