Recovery & Durability

A database system mediates between two worlds: volatile memory (RAM, the buffer pool) where computation happens fast, and persistent storage (disk or SSD) where data survives across reboots. The fundamental tension is that writing to disk is orders of magnitude slower than writing to RAM, so the database holds modified pages in a buffer pool and flushes them to disk lazily — batching writes for efficiency.

This creates the recovery problem. At any moment, the database may have:

• Dirty pages in the buffer pool (modified in RAM, not yet on disk)
• Committed transactions whose changes are still only in RAM
• Aborted or in-flight transactions whose partial changes may already be on disk

When a crash occurs (power failure, OS panic, process kill), RAM vanishes instantly. On restart, the disk may reflect a mixture of committed and uncommitted changes with no consistent snapshot. The database must reconstruct a correct state.

Two properties must be restored:

1. Durability: Every committed transaction's effects survive the crash
2. Atomicity: No uncommitted transaction's effects are visible

Restoring durability requires redo — re-applying lost committed changes. Restoring atomicity requires undo — rolling back changes from transactions that were running at crash time. The recovery algorithm must do both, correctly, using only what survived on disk.

# The recovery problem in miniature:
# Suppose T1 commits, T2 is in-flight at crash time.
# After crash, disk may look like:

# Scenario A: committed T1 changes NOT on disk yet → need REDO T1
# Scenario B: in-flight T2 changes ARE on disk already → need UNDO T2
# Scenario C: both A and B simultaneously → need REDO T1 AND UNDO T2

# The log is the only source of truth about what happened before the crash.

The recovery complexity depends critically on two buffer pool management policies:

FORCE means: when a transaction commits, all its dirty pages must be flushed to disk before the commit acknowledgment is sent. FORCE makes redo unnecessary after a crash — if it committed, it is on disk. But FORCE kills performance: every commit triggers potentially many random disk writes.

NO-STEAL means: dirty pages from uncommitted transactions may never be flushed to disk. NO-STEAL makes undo unnecessary — uncommitted changes can never reach disk. But NO-STEAL means the entire write set of every active transaction must fit in the buffer pool simultaneously, which is impractical for large transactions.

The optimal production policy is STEAL + NO-FORCE:

• STEAL: dirty pages from any transaction (even uncommitted ones) can be evicted to disk to free buffer pool space
• NO-FORCE: at commit time, dirty pages need not be flushed; only the log record need be written

STEAL + NO-FORCE gives the best runtime performance (small buffer pool is fine; commits are cheap) but requires both undo (because stolen uncommitted pages may be on disk) and redo (because force is not used). This is the regime ARIES is designed for, and it is what PostgreSQL, MySQL InnoDB, SQL Server, and DB2 all use.

# Policy matrix:
#
#           | FORCE             | NO-FORCE          |
# ----------|-------------------|-------------------|
# NO-STEAL  | easy (no undo,    | need redo only    |
#           | no redo) but      | (impractical:     |
#           | slow commits      | large buf needed) |
# ----------|-------------------|-------------------|
# STEAL     | need undo only    | need BOTH undo    |
#           | (impractical:     | and redo ← ARIES  |
#           | slow commits)     | targets this      |

# PostgreSQL wal_buffers + bgwriter = STEAL + NO-FORCE in practice

Write-Ahead Logging is a simple, powerful idea: before any change is written to disk (the database pages), the log record describing that change must first be written to disk (the log).

More precisely, WAL has two rules:

1. The undo WAL rule: Before a dirty page is written to disk, all log records describing changes on that page must be on disk (so we can undo if needed)
2. The redo WAL rule: Before a transaction commits, all log records for all of its changes must be on disk (so we can redo if a committed change never made it to the page)

The log is a sequential, append-only structure on disk. Sequential writes are much faster than random writes, so flushing the log at commit is cheap. Dirty pages can be flushed lazily in the background.

Each log record gets a Log Sequence Number (LSN) — a monotonically increasing identifier (often a byte offset into the log file). LSNs are the universal currency of recovery. Each page stores the LSN of the most recent log record that modified it (pageLSN). The relationship pageLSN >= LSN(r) for all records r that modified that page tells the recovery algorithm what has already been applied.

The WAL invariant can be stated precisely: a dirty page with pageLSN = X may not be written to disk until the log has been flushed at least through LSN X.

# Log record structure (simplified)
@dataclass
class LogRecord:
    lsn: int          # Log Sequence Number (byte offset in log)
    prev_lsn: int     # LSN of previous record from same transaction
    txn_id: int       # Which transaction
    type: str         # 'UPDATE', 'COMMIT', 'ABORT', 'CLR', 'BEGIN_CHKPT', ...
    page_id: int      # Which page (for UPDATE records)
    offset: int       # Where on the page
    before_image: bytes  # Old value (for undo)
    after_image: bytes   # New value (for redo)

# WAL invariant enforced in buffer manager:
def flush_page(page):
    # Rule: log must be flushed at least through page.pageLSN
    log.flush_up_to(page.pageLSN)  # flush log first!
    disk.write(page)               # only then write the page

The log is not just a list of page modifications — it is a complete audit trail of all transaction activity. Key record types:

• BEGIN: marks the start of a transaction
• UPDATE (or WRITE): records both the before-image (for undo) and after-image (for redo) of a change
• COMMIT: marks that a transaction has committed — once this is on disk, the transaction is durable
• ABORT: marks that a transaction rolled back
• CLR (Compensation Log Record): written when an undo action is performed during rollback or recovery, to prevent re-undoing the same action (explained in the ARIES section)
• END: marks completion of all undo work for a transaction

During normal operation, the database maintains an in-memory Transaction Table (also called the active transaction table) mapping each active transaction to its most recent LSN (lastLSN) and its status. This table is used during checkpointing and is the seed for recovery.

Similarly, a Dirty Page Table (DPT) tracks which pages in the buffer pool have been modified but not yet written to disk, along with the recLSN (recovery LSN) — the LSN of the first log record that dirtied that page. The recLSN is critical: it marks how far back in the log we must go to redo changes for that page.

# Transaction Table entry
@dataclass
class TxnEntry:
    txn_id: int
    status: str      # 'running', 'committing', 'aborting'
    last_lsn: int    # most recent log record for this txn

# Dirty Page Table entry
@dataclass
class DPTEntry:
    page_id: int
    rec_lsn: int     # LSN of first log record that dirtied this page
                     # = earliest log record needed to redo this page

# When a page is first dirtied:
def on_page_first_dirtied(page_id, current_lsn):
    if page_id not in dirty_page_table:
        dirty_page_table[page_id] = DPTEntry(
            page_id=page_id,
            rec_lsn=current_lsn  # <- remember when it first got dirty
        )

# When a page is flushed:
def on_page_flushed(page_id):
    dirty_page_table.pop(page_id, None)  # no longer dirty

In principle, recovery could be performed by replaying the log from the very beginning. But logs grow indefinitely, and replaying years of history on restart is intolerable. Checkpointing periodically captures a consistent snapshot of database state on disk so that recovery only needs to process a bounded suffix of the log.

The naive checkpoint (sharp checkpoint) pauses all transactions, flushes all dirty pages to disk, and writes a CHECKPOINT record. After a sharp checkpoint, all changes before that point are safely on disk; the log before it is irrelevant. But stopping all transactions for a checkpoint is expensive in a production system.

ARIES uses a fuzzy checkpoint (also called non-blocking checkpoint):

1. Write a BEGIN_CHECKPOINT log record
2. Snapshot the current Transaction Table and Dirty Page Table into a END_CHECKPOINT log record (without pausing transactions or flushing pages)
3. Write END_CHECKPOINT to the log
4. Record the LSN of BEGIN_CHECKPOINT in a stable master record (or checkpoint log pointer)

During recovery, we start from the master record's BEGIN_CHECKPOINT LSN and use the snapshotted tables to know which transactions were active and which pages were dirty at checkpoint time. We then scan forward from there. The fuzzy checkpoint does not require dirty pages to be flushed — they may still be dirty after checkpointing — but it establishes a safe starting point for log analysis.

The redo scan must start from the minimum recLSN across all pages in the dirty page table at checkpoint time (because any of those pages might have been flushed and re-dirtied before the crash). This is called the redo LSN or RedoLSN.

# Fuzzy checkpoint procedure
def do_fuzzy_checkpoint():
    # Step 1: BEGIN_CHECKPOINT record
    begin_lsn = log.append(LogRecord(
        type='BEGIN_CHECKPOINT',
        txn_id=None
    ))

    # Step 2: snapshot in-memory tables
    txn_snapshot = dict(transaction_table)   # copy — live txns keep running
    dpt_snapshot = dict(dirty_page_table)    # copy — pages not flushed yet

    # Step 3: END_CHECKPOINT with snapshots
    end_lsn = log.append(LogRecord(
        type='END_CHECKPOINT',
        txn_table=txn_snapshot,
        dirty_page_table=dpt_snapshot
    ))
    log.flush()  # must reach disk before we update master record

    # Step 4: update master record (pointer to BEGIN_CHECKPOINT)
    master_record.checkpoint_lsn = begin_lsn
    master_record.flush_to_disk()

# On recovery, start analysis from master_record.checkpoint_lsn

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) solves the full recovery problem under STEAL + NO-FORCE with fuzzy checkpointing. It proceeds in exactly three passes over the log:

Phase 1: Analysis Start at the BEGIN_CHECKPOINT LSN from the master record. Scan forward to the end of the log. The goal is to reconstruct, as accurately as possible, the Transaction Table and Dirty Page Table as they stood at the moment of the crash.

• When a BEGIN record is seen for transaction T: add T to the Transaction Table as running
• When an UPDATE record for page P is seen: if P is not in the DPT, add it with recLSN = this record's LSN
• When a COMMIT record for T is seen: mark T as committing in the Transaction Table
• When an END record for T is seen: remove T from the Transaction Table
• When an ABORT record for T is seen: mark T as aborting

At the end of Phase 1, the Transaction Table contains all transactions that were active or committing at crash time. The DPT contains all pages that were likely dirty at crash time.

Phase 2: Redo Start from the RedoLSN = minimum recLSN in the DPT after Phase 1. Scan forward to end of log. For each UPDATE or CLR record:

• Check if the page is in the DPT and the record's LSN >= recLSN for that page
• Fetch the page from disk; check if pageLSN < this record's LSN
• If so, re-apply the change (redo it) and update pageLSN
• If pageLSN >= record LSN, the change is already on disk — skip

This correctly handles pages that were written to disk after the checkpoint but before the crash (they won't need redo), and pages that were dirty but never made it to disk (they will need redo). The key insight: ARIES repeats history — it redoes ALL logged actions, including those of uncommitted transactions, to restore the exact state at crash time. Undo comes later.

Phase 3: Undo Undo all transactions that were running or aborting in the Transaction Table (those that had not committed). Undo is performed in reverse LSN order (most recent first, using the prevLSN chain). For each undo action, a Compensation Log Record (CLR) is written to the log, recording that this undo step was performed. CLRs are redo-only records (they are never themselves undone), which prevents re-undoing the same step if a crash occurs during recovery itself. This makes ARIES restartable after a failure during recovery — a crucial property.

def aries_recovery():
    # ── Phase 1: Analysis ────────────────────────────────────────
    chkpt_lsn = master_record.checkpoint_lsn
    txn_table, dpt = load_checkpoint_snapshot(chkpt_lsn)

    for record in log.scan_from(chkpt_lsn):
        if record.type == 'BEGIN':
            txn_table[record.txn_id] = TxnEntry(record.txn_id, 'running', record.lsn)
        elif record.type in ('UPDATE', 'CLR'):
            txn_table[record.txn_id].last_lsn = record.lsn
            if record.page_id not in dpt:
                dpt[record.page_id] = DPTEntry(record.page_id, record.lsn)
        elif record.type == 'COMMIT':
            txn_table[record.txn_id].status = 'committing'
        elif record.type == 'END':
            del txn_table[record.txn_id]
        elif record.type == 'ABORT':
            txn_table[record.txn_id].status = 'aborting'

    # ── Phase 2: Redo ────────────────────────────────────────────
    redo_lsn = min(e.rec_lsn for e in dpt.values()) if dpt else END_OF_LOG

    for record in log.scan_from(redo_lsn):
        if record.type not in ('UPDATE', 'CLR'):
            continue
        if record.page_id not in dpt:
            continue  # page was clean at crash time — already on disk
        if dpt[record.page_id].rec_lsn > record.lsn:
            continue  # this update predates when page became dirty
        page = buffer_pool.fetch(record.page_id)
        if page.page_lsn < record.lsn:
            apply_redo(page, record)  # re-apply the change
            page.page_lsn = record.lsn

    # ── Phase 3: Undo ────────────────────────────────────────────
    # Collect losers: txns that did not commit
    losers = {tid: e for tid, e in txn_table.items()
              if e.status in ('running', 'aborting')}

    # Priority queue: undo in reverse LSN order
    import heapq
    pq = [(-e.last_lsn, tid) for tid, e in losers.items()]
    heapq.heapify(pq)

    while pq:
        neg_lsn, tid = heapq.heappop(pq)
        lsn = -neg_lsn
        record = log.fetch(lsn)

        if record.type == 'UPDATE':
            # Undo the change, write a CLR
            page = buffer_pool.fetch(record.page_id)
            apply_undo(page, record)  # restore before-image
            clr_lsn = log.append(LogRecord(
                type='CLR',
                txn_id=tid,
                page_id=record.page_id,
                undo_next_lsn=record.prev_lsn,  # where to continue undoing
                redo_info=record.before_image
            ))
            losers[tid].last_lsn = clr_lsn
            # Continue undoing this transaction at prevLSN
            if record.prev_lsn != NULL_LSN:
                heapq.heappush(pq, (-record.prev_lsn, tid))
            else:
                log.append(LogRecord(type='END', txn_id=tid))

        elif record.type == 'CLR':
            # CLRs are never undone; jump to undo_next_lsn
            if record.undo_next_lsn != NULL_LSN:
                heapq.heappush(pq, (-record.undo_next_lsn, tid))
            else:
                log.append(LogRecord(type='END', txn_id=tid))

One of ARIES's most elegant properties is that it can survive a crash during recovery itself. This is not a theoretical curiosity — a large database may take minutes to recover, and a second power failure is plausible.

The mechanism is the Compensation Log Record (CLR). When Phase 3 undoes an UPDATE with LSN X for transaction T, it writes a CLR to the log. The CLR has two key fields:

• Redo information: the before-image of the page (so the undo action can be redone if the page didn't make it to disk)
• undoNextLSN: the prevLSN of the record that was just undone — this tells recovery "if you need to undo this transaction further, start from this LSN"

CLRs are redo-only — they are never themselves undone. This is enforced in Phase 3: when the undo scan reaches a CLR, it jumps directly to undoNextLSN without undoing the CLR's action again.

If a crash occurs mid-undo (say, after some CLRs were written but before the transaction was finished), ARIES on the next restart will:

1. Phase 1: reconstruct the transaction table (the transaction is still a loser, but its lastLSN now points to a CLR)
2. Phase 2: redo the CLR's undo action (in case the page wasn't flushed)
3. Phase 3: use undoNextLSN to correctly resume undoing from where it left off, without redoing already-undone steps

This is why ARIES is described as repeating history: Phase 2 redo is applied even to uncommitted transactions, restoring the exact crash state, so that Phase 3 undo starts from a clean, well-defined point.

# CLR structure and how undoNextLSN enables idempotent undo

# Suppose transaction T has log chain:
#   LSN 10: BEGIN T
#   LSN 20: UPDATE page 5, A→B  (prevLSN=10)
#   LSN 30: UPDATE page 7, X→Y  (prevLSN=20)
#   -- crash before commit --

# Phase 3 starts undoing T from LSN 30:
#   Undo LSN 30 (page 7: Y→X), write CLR at LSN 40:
#     CLR(txn=T, page=7, redo=Y→X, undoNextLSN=20, prevLSN=30)

#   -- SECOND CRASH HERE --

# On restart, Phase 1 reconstructs T as loser with lastLSN=40
# Phase 2 redoes CLR at LSN 40 (re-applies Y→X if page was dirty)
# Phase 3: T's lastLSN=40 is a CLR, so jump to undoNextLSN=20
#   Undo LSN 20 (page 5: B→A), write CLR at LSN 50:
#     CLR(txn=T, page=5, redo=B→A, undoNextLSN=10, prevLSN=40)
#   LSN 10 is a BEGIN (prevLSN=NULL), so write END for T
# -- T is completely rolled back, no action was undone twice --

A central guarantee in ARIES Phase 2 is that redo is idempotent: applying a log record to a page that already reflects that change has no effect. This is enforced by the pageLSN check.

Every page on disk stores a pageLSN — the LSN of the most recent log record that successfully modified and was durably applied to that page. Before redoing a log record with LSN X on page P:

• Fetch P from disk
• If P.pageLSN >= X: the change is already reflected on this disk copy of P — skip the redo
• If P.pageLSN < X: the change has not been applied (the page was not flushed after this update) — apply the redo

This check is what allows ARIES to start redo at the RedoLSN (minimum recLSN) rather than at the beginning of time. Some pages in the DPT may have been flushed to disk after the checkpoint but before the crash, so their on-disk version already reflects certain updates. The pageLSN check detects and skips those.

For the redo to be correct, the after-image in the log record must be a physical (or physiological) description of the change — not a logical one. A purely logical redo (e.g., "increment counter by 1") would be wrong if the page already had the increment applied. ARIES uses physiological logging: physical redo (exact byte changes within a page) combined with logical undo (operation-level undo, e.g., "delete the record I inserted"). This gives the correctness of physical redo with the compactness of logical undo.

# The pageLSN check in Phase 2 redo
def redo_record(record, dpt):
    if record.page_id not in dpt:
        return  # page was not dirty at crash time — already reflected on disk

    if dpt[record.page_id].rec_lsn > record.lsn:
        return  # this record predates the page's first dirty-ing — skip

    page = buffer_pool.fetch_from_disk(record.page_id)

    if page.page_lsn >= record.lsn:
        # Change already on disk — idempotent skip
        return

    # Apply the after-image (physical redo)
    page.data[record.offset:record.offset + len(record.after_image)] = \
        record.after_image
    page.page_lsn = record.lsn
    # Page is now dirty in buffer pool; will be flushed later

# Physiological log record example:
# Physical redo:  write bytes [42, 43, 44] at offset 128 of page 7
# Logical undo:   delete the record with key=42 from page 7
# Compact and correct: undo handles page reorganization correctly

The log cannot grow forever. Once portions of the log are no longer needed for recovery, they can be truncated. The question is: what is the minimum LSN that we must retain?

The log is needed for three purposes:

1. Undo ongoing transactions: We need all log records back to the BEGIN of the oldest active transaction
2. Redo dirty pages: We need all log records back to the minimum recLSN in the Dirty Page Table
3. Recovery from the last checkpoint: We need the checkpoint and everything after it

The log tail that must be retained is thus from min(oldest active txn BEGIN LSN, min recLSN in DPT, checkpoint LSN) to the current end.

In practice, the dominant factor is usually the minimum recLSN — dirty pages that have been sitting in the buffer pool for a long time force the log to be retained. This is why database systems periodically flush dirty pages (via the background writer or checkpointer in PostgreSQL) — not just to limit crash recovery time, but also to allow log truncation.

PostgreSQL calls this the WAL segment system: the log is divided into fixed-size segments (default 16 MB in older versions, configurable), and segments before the recovery horizon can be recycled. The parameter min_wal_size / max_wal_size controls how much WAL is retained.

# Determining the log truncation point
def compute_log_horizon(txn_table, dpt, last_checkpoint_lsn):
    candidates = [last_checkpoint_lsn]

    # Earliest LSN needed for undo of active transactions
    for txn in txn_table.values():
        if txn.status == 'running':
            candidates.append(txn.begin_lsn)

    # Earliest LSN needed for redo of dirty pages
    for entry in dpt.values():
        candidates.append(entry.rec_lsn)

    return min(candidates)  # cannot truncate log before this LSN

# In PostgreSQL:
# SELECT pg_current_wal_lsn();           -- current log position
# SELECT pg_walfile_name(pg_current_wal_lsn());  -- current WAL file
# checkpoint_completion_target controls how aggressively pages are
# flushed during a checkpoint to spread I/O load

The theoretical guarantee of WAL requires that log records are durable on disk before a commit is acknowledged. In the real world, this means the data must survive not just an OS crash, but a power failure — meaning the bytes must reach the physical storage medium, not just an OS buffer or a disk write cache.

The Unix fsync() system call flushes the OS page cache to the storage device and waits for acknowledgment from the device that the write is persistent. This is what PostgreSQL calls on every transaction commit (with synchronous_commit = on). Without fsync, the OS might buffer log writes in RAM and lose them on power failure — which caused the PostgreSQL/ext4 bug where data loss could occur without even a crash in PostgreSQL itself.

Group commit amortizes fsync cost by batching multiple commits: transactions that complete during the same fsync interval share a single disk flush. PostgreSQL's commit_delay and commit_siblings parameters implement this. WAL writers accumulate log records; a single fsync of the WAL file durably commits all of them at once.

Most SSDs have a non-volatile write buffer (a capacitor-backed cache), which means a single fsync is genuinely durable even on power failure. Enterprise systems may use battery-backed RAID controllers that make fsync effectively free. Cloud databases often replicate the WAL to multiple availability zones synchronously, achieving durability through replication rather than a single slow fsync.

The synchronous_commit = off option in PostgreSQL deliberately violates the durability guarantee in exchange for performance: commits are acknowledged before the WAL is flushed. This risks losing the last few transactions on crash, but does not risk corruption — the recovery will correctly undo incomplete transactions.

-- PostgreSQL durability knobs:

-- Full durability (default): wait for WAL fsync before commit ack
SET synchronous_commit = on;

-- Commit ack after WAL write to OS buffer, before fsync
-- Risk: lose last ~1 wal_writer_delay ms of commits on power failure
SET synchronous_commit = off;

-- For read replicas / streaming replication:
SET synchronous_commit = remote_write;  -- ack after replica OS write
SET synchronous_commit = remote_apply;  -- ack after replica applies WAL

-- Checkpoint tuning (controls recovery time / I/O smoothing):
-- checkpoint_timeout = 5min   -- how often to checkpoint
-- max_wal_size = 1GB          -- max WAL before forced checkpoint
-- checkpoint_completion_target = 0.9  -- spread checkpoint I/O

-- Check WAL activity:
SELECT * FROM pg_stat_bgwriter;

ARIES's correctness rests on a set of invariants maintained throughout normal operation and recovery. It is worth understanding why the algorithm is correct, not just how it works.

Correctness of Redo Phase: Any committed transaction's changes that did not make it to disk will be found in the log (because of WAL rule 2: COMMIT log record is only written after all update records are on disk). The redo scan starts at RedoLSN = min recLSN in DPT; any dirty page with recLSN below this was clean at checkpoint, so it either (a) was flushed later and is already on disk, or (b) is in the DPT. The pageLSN check correctly identifies which changes have been applied. Therefore, after Phase 2, every committed change is on disk.

Correctness of Undo Phase: Any uncommitted transaction appears in the loser set from Phase 1. Phase 2 has restored the exact pre-crash state (including all uncommitted changes that were on disk), so Phase 3 undo is starting from the correct state. CLRs are redo-only and carry undoNextLSN, so even if Phase 3 is interrupted by another crash, restart will correctly resume. After Phase 3, no uncommitted change is visible.

No lost updates, no phantom undos: The combination of these two properties gives us exactly what we want: the database reflects all and only committed transactions.

A subtle point: ARIES requires that pages are not written to disk during recovery (until Phase 2 explicitly does so). If the buffer manager evicted pages during recovery, the pageLSN check could be violated. In practice, recovery pins the pages it fetches or uses a dedicated recovery buffer pool.

# Invariants maintained by ARIES:
#
# 1. WAL invariant (normal operation):
#    page.pageLSN >= X  must hold before page is written to disk,
#    where X is the LSN of every update to that page
#    => log.flush_up_to(page.pageLSN) before writing the page
#
# 2. Commit durability (normal operation):
#    COMMIT log record is written and flushed before txn is acked
#    => all update records for the txn are already in the log
#
# 3. Redo completeness:
#    After Phase 2, for every committed txn T and every page P
#    modified by T: P.pageLSN >= last_update_lsn(T, P)
#
# 4. Undo completeness:
#    After Phase 3, no page contains changes from a loser txn
#    (CLRs ensure idempotency across multiple crashes)
#
# Together: database reflects exactly the set of committed transactions