Reliability: Buffer, Log & Recovery

01 · Exam

What the papers say about this chapter

An honest word before you invest time here, because this chapter’s status is unusual.

Reliability and recovery is squarely in the syllabus: it gets two lecture decks and 45 slides, and it falls under exam topic 4, “DB architecture and technologies”. But across the fourteen sessions in the question bank — January 2024 to July 2026 — it has never once been the subject of an exercise. The architecture slot was contested fourteen times, and concurrency control took it every time. Its only appearance anywhere in the bank is a three-point theory sub-question in February 2025, asking why long-duration write locks are required.

The chapter is therefore complete but compact: full coverage, no padding.

02 · Foundation

Stable memory and the reliability manager

Durability promises that committed effects survive “forever”. Since every real storage medium can fail, that promise is an abstraction built on top of ones that can.

Three levels, of increasing (claimed) permanence:

• Main memory — not persistent.
• Mass memory — persistent, but can be damaged.
• Stable memory — cannot be damaged. Plainly an idealisation: in practice stability means a failure probability close to zero, achieved by replication and write protocols.

Replication comes in two forms. On-line: mirroring two disks, or the RAID architectures covered in Computing Infrastructures. Off-line: periodic backup to tape or equivalent — the dump.

The Reliability Manager sits alongside the data path (chapter 1’s diagram) and does three things: it realizes the transactional commands commit and abort, it orchestrates read/write access to both data and log pages, and it handles recovery after failures.

03 · Mechanism

Buffer management: STEAL and FORCE

The buffer exists for speed. Its two policy choices are what create the entire recovery problem — this is the most examinable idea in the chapter.

The buffer caches disk blocks as pages in main memory and defers writing them back. Each page carries a transaction counter (how many transactions are using it) and a dirty flag (whether it has been modified and must eventually be aligned to disk). On a dedicated database server, up to 80 % of physical memory may be given to the buffer.

Its primitives:

When fix finds no free page, it must evict one — and which page it is allowed to evict is the first policy question:

04 · Mechanism

The log and its records

A sequential file on stable memory recording, as state transitions, what every transaction did.

The log is written sequentially up to its top block — the current instant. If an update transforms object $O$ from $O_1$ to $O_2$, the log records the before-state $O_1$ and the after-state $O_2$. Inserts and deletes are logged identically, except that an insert record has no before-state and a delete record has no after-state.

Two operations use it, and they are exact inverses:

• UNDO a transaction: set $O = BS$.
• REDO a transaction: set $O = AS$.

A concrete log sequence, from a debit transaction:

<BEGIN T1>
<T1, Accounts.balance(account_id=1), old=500, new=400>
<T1, Transactions, inserted(account_id=1, amount=100, type='debit', date=2025-11-13)>
<COMMIT T1>

05 · Rules

Write-ahead log and the commit rule

Two rules govern the ordering of log writes against database writes. Between them they guarantee that whatever the crash timing, recovery has what it needs.

The commit log record itself is written synchronously, with a force — it is the one write the system cannot afford to defer, because it is what defines whether the transaction happened.

Since database writes are asynchronous, three timing regimes are possible, and each changes what recovery must do:

The third is what real systems do, which is why the general recovery algorithm needs both directions. Reading it against the previous section: writing before commit is the STEAL case, writing after commit is the FORCE case, and arbitrary timing is STEAL + NO-FORCE.

06 · Recovery

Checkpoint and dump

Recovery cannot scan the log back to the beginning of time. Two markers bound the work.

A checkpoint is performed periodically to identify a consistent time point. In the simple variant the lectures give:

1. Acceptance of all commit and abort requests is suspended.
2. All dirty buffer pages belonging to committed transactions are forced to disk — log entries first (if not already forced), then the page.
3. The identifiers of transactions still in progress are recorded in a CKPT record, forced to the log. No new transaction may start during this recording.
4. Normal operation resumes.

The guarantee is therefore: at the checkpoint, everything committed is on disk, and everything half-way is named in a record in stable memory. Real systems soften this — MySQL uses fuzzy checkpointing, gradually writing dirty pages while transactions continue running.

A dump is a complete backup copy of the database, taken typically at night or at weekends, stored in stable memory, with its availability recorded in the log. MySQL’s own backup taxonomy shows the dimensions that matter in practice: physical versus logical (file copy versus SQL export), hot versus cold (server live or stopped), local versus remote, snapshot versus full versus incremental, and full versus point-in-time recovery.

07 · Recovery

Warm restart

Recovery from a soft failure — main memory lost, disk intact. The log is replayed to resolve every in-doubt transaction.

The lectures’ worked example, which is the shape to reproduce:

B(T1) B(T2) U(T1,O1,B1,A1) I(T1,O2,A2) U(T2,O3,B3,A3) B(T3)
U(T3,O4,B4,A4) D(T3,O5,B5) CKPT(T1,T2,T3) C(T2) B(T4)
U(T4,O6,B6,A6) A(T4) ——— failure

  after CKPT:     UNDO = {T1,T2,T3}   REDO = {}
  after C(T2):    UNDO = {T1,T3}      REDO = {T2}
  after B(T4):    UNDO = {T1,T3,T4}   REDO = {T2}

  undo, backwards:  (1) O6 = B6   (2) re-insert O5 = B5   (3) O4 = B4
                    (4) delete O2  (5) O1 = B1
  redo, forwards:   (6) O3 = A3

Note that A(T4) does not remove T4 from UNDO — an aborted transaction still needs its effects rolled back, exactly like an unfinished one. And notice the delete/insert inversion in steps 2 and 4: undoing a delete re-inserts, undoing an insert deletes.

08 · Recovery

Cold restart, and why strict 2PL needs the log

The harder failure, and then the loop back to chapter 6.

Failures come in three severities:

• Soft failure — part of main memory lost. Requires a warm restart, using the log.
• Hard failure — part of the secondary memory devices lost or failed. Requires a cold restart.
• Disaster — stable memory itself lost, log and dump included. Out of scope here; the province of disaster recovery.

A cold restart proceeds in three moves: restore the data from the most recent dump; re-apply the operations recorded in the log, in log order, up to the failure time; then execute a warm restart from there, undoing whatever remains uncertain.

Which brings us back to where chapter 6 left an argument dangling. Strict two-phase locking holds write locks until commit or rollback, and the justification given there was that otherwise abort processing becomes impossible — the dirty write problem, where T1 aborts after T2 has overwritten the same object and neither transaction’s before-state can be correctly reinstalled.

That argument is really a statement about this chapter’s machinery. What “restoring the state prior to the aborted updates” means is applying the log’s before-states in reverse order. If two transactions’ updates to one object interleave, the log’s before-state for the second is the first’s uncommitted value, and UNDO produces nonsense. Long-duration write locks exist precisely so that the log’s chain of before-states per object never interleaves across transactions.