Recovery and Atomicity

DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).

Recovery and Atomicity

How the DBMS undoes a half-finished transaction after a crash — and why the log must be written before the data.

🌍 Where this lives: pull the power cable mid-transaction and the database comes back consistent. That is not luck — it is the single rule below (write the log first) plus a recovery pass on restart. The same idea appears everywhere durability matters: journaling filesystems (ext4, NTFS) write a journal before touching file blocks, and Git writes objects before moving refs. Once you understand write-ahead logging you understand why fsync is the most performance-critical system call in a database, and why cloud providers charge extra for disks that honour it. Search "write-ahead logging ARIES".

The problem

A transaction modifies pages in the BUFFER POOL (memory). Those pages are written to disk LAZILY, whenever the buffer manager chooses. So at the moment of a crash the disk may hold: · changes from a transaction that COMMITTED → must survive · changes from a transaction that did NOT → must vanish · no changes from a transaction that committed → must be re-applied All three at once, with no way to tell which is which from the data pages alone. TWO DANGEROUS BUFFER POLICIES, and both are used because both are fast: STEAL — a dirty page belonging to an UNCOMMITTED transaction may be written to disk (to free a buffer frame) → the disk can contain uncommitted changes → recovery needs UNDO NO-FORCE — a COMMITTED transaction's pages need NOT be written to disk before commit returns → the disk can be missing committed changes → recovery needs REDO The safe-but-slow alternatives: NO-STEAL never write uncommitted pages → no UNDO needed, but a transaction cannot exceed the buffer pool FORCE flush all pages at commit → no REDO needed, but commit costs many random writes Real systems choose STEAL + NO-FORCE for speed, and pay for it with a recovery algorithm that does BOTH undo and redo.

The log, and the one rule that makes it work

The LOG is an append-only sequence of records on stable storage describing every change. <T1, START> <T1, A, 1000, 700> T1 changed item A from 1000 to 700 ^ ^ ^ ^ txn item old new value value <T1, COMMIT> The OLD value enables UNDO. The NEW value enables REDO. A log record carrying both is an UNDO/REDO record. THE WRITE-AHEAD LOGGING RULE: the log record describing a change must reach STABLE STORAGE **before** the changed data page does. Why it is sufficient: if the data page made it to disk, its log record certainly did, so recovery can undo it. If the log record is absent, the data page cannot have been written either, so there is nothing to undo. THE COMMIT RULE: a transaction is COMMITTED at the instant its <T, COMMIT> record is on stable storage — not when its data pages are written. This is what makes NO-FORCE safe, and it is why commit costs ONE sequential log flush rather than many random page writes. WHY SEQUENTIAL WRITING IS THE WHOLE TRICK: writing one 8 KB log block sequentially ≈ 0.1 ms (SSD) writing 30 scattered 8 KB data pages ≈ 3 ms → the log turns random I/O into sequential I/O, which is the same optimisation as the bitmap heap scan from the query-cost topic.

The two recovery operations

UNDO(T) — restore the OLD value of every change T made, working BACKWARDS through the log. Applied to transactions with no <T, COMMIT> record. Writes an <T, ABORT> record when finished. REDO(T) — re-apply the NEW value of every change T made, working FORWARDS through the log. Applied to transactions WITH a <T, COMMIT> record. BOTH MUST BE IDEMPOTENT. Recovery itself can crash, so running it twice must give the same result as running it once. That is why log records store VALUES, not operations: <T1, A, 1000, 700> idempotent — set A to 700 <T1, A, "subtract 300"> NOT idempotent — running it twice gives 400 THE RECOVERY ALGORITHM (deferred-modification variant omitted; this is the general immediate-modification case): PASS 1 — ANALYSIS, scanning forward from the last checkpoint build two lists: REDO list transactions with a COMMIT record UNDO list transactions with START but no COMMIT/ABORT PASS 2 — REDO, scanning FORWARD to the end of the log re-apply every change of every transaction on the REDO list. Note: redo is applied to ALL committed transactions, even ones whose pages are already on disk — that is cheaper than checking, and idempotence makes it safe. PASS 3 — UNDO, scanning BACKWARD to the start roll back every change of every transaction on the UNDO list, in reverse order. Redo goes FORWARD (replay history); undo goes BACKWARD (unwind it). Getting that direction wrong is the classic exam error. WORKED EXAMPLE — a log at the moment of a crash: <T1, START> <T1, A, 1000, 700> <T1, COMMIT> <T2, START> <T2, B, 500, 300> <T3, START> <T3, C, 200, 900> <T2, B, 300, 250> ⟵ CRASH HERE ANALYSIS: T1 has COMMIT → REDO list T2 has START, no COMMIT → UNDO list T3 has START, no COMMIT → UNDO list REDO (forward): A := 700 UNDO (backward): B := 300 (undo the second T2 change) C := 200 (undo T3) B := 500 (undo the first T2 change) FINAL STATE: A = 700, B = 500, C = 200 T1's work survives; T2 and T3 leave no trace. ✔ Note the undo of B happens TWICE, in reverse order, ending at the original 500. Undoing forwards would leave B = 300 — which is why the direction matters.

Checkpoints — bounding the work

Without checkpoints, recovery would scan the log from the beginning of time. A CHECKPOINT is a marker saying "everything before this point is already on disk". TAKING A CHECKPOINT: 1. stop accepting new updates (briefly) 2. flush all log records in memory to the log file 3. flush all dirty data pages to disk 4. write a <CHECKPOINT L> record, where L is the list of transactions active at that instant 5. resume AFTER A CRASH: recovery starts at the LAST checkpoint, not at the log's start. Everything before it is known to be on disk. Recovery still needs the ACTIVE transaction list L, because a transaction that started before the checkpoint and had not committed must still be undone — and its earliest log records are BEFORE the checkpoint. So undo may have to scan back past the checkpoint to find that transaction's START. FUZZY CHECKPOINTS avoid the pause in step 1: record the checkpoint position, then flush pages in the background while normal work continues. Every production system does this — a checkpoint that stops the database would be unacceptable. MEASURED on PostgreSQL 18: SELECT checkpoint_lsn, redo_lsn FROM pg_control_checkpoint(); -- checkpoint_lsn | redo_lsn -- ---------------+------------ -- 0/10320650 | 0/103205F8 -- -- redo_lsn is where recovery WOULD start. The control file -- stores it, which is why the startup log prints -- "redo starts at 0/1A2B3C40" -- The gap between redo_lsn and the current LSN is exactly -- how much work a crash right now would cost. THE TUNING TRADE-OFF: frequent checkpoints → fast recovery, more I/O during normal operation rare checkpoints → less steady I/O, slower recovery checkpoint_timeout = 5min (PostgreSQL default) max_wal_size = 1GB checkpoint sooner if WAL grows past this So the default caps crash recovery at roughly five minutes' worth of WAL — a deliberate bound on downtime.

The reason redo is applied to every committed transaction, even those whose pages are demonstrably already on disk, is worth understanding: checking whether each page needs redo would require reading the page to compare its LSN, which is exactly the random I/O the log exists to avoid. Blind idempotent replay is cheaper than being selective.

Verified behaviour — undo in a live database

recovery.sql

-- Measured on PostgreSQL 18.

-- ===== WAL is written BEFORE data pages =====
SELECT pg_current_wal_lsn() AS before_insert;
--  before_insert
--  ---------------
--  0/103C0E88

INSERT INTO waldemo (payload)
    SELECT repeat('x',200) FROM generate_series(1,5000);

SELECT pg_current_wal_lsn() AS after_5000_rows;
--  after_5000_rows
--  -----------------
--  0/1055AD50

SELECT pg_size_pretty(
    pg_wal_lsn_diff('0/1055AD50','0/103C0E88')) AS wal_written;
--  wal_written
--  -------------
--  1830 kB
--
-- 1.8 MB of WAL for 5,000 rows — written and fsync'd at
-- commit, while the DATA pages may still be sitting dirty in
-- the buffer pool. That asymmetry IS write-ahead logging.

-- ===== UNDO: an aborted transaction leaves nothing =====
BEGIN;
  INSERT INTO waldemo (payload)
      SELECT repeat('y',200) FROM generate_series(1,2000);
  SELECT count(*) AS visible_inside FROM waldemo
   WHERE payload LIKE 'y%';
--  visible_inside
--  ----------------
--            2000     <- visible to THIS transaction
ROLLBACK;

SELECT count(*) AS visible_after_rollback FROM waldemo
 WHERE payload LIKE 'y%';
--  visible_after_rollback
--  ------------------------
--                       0     <- gone ✔

-- ===== HOW the undo happened: MVCC, not physical erasure ==
SELECT xmin, xmax, left(payload,3) AS p FROM waldemo LIMIT 3;
--  xmin  | xmax |  p
--  -------+------+-----
--  22765 |    0 | xxx
--  22765 |    0 | xxx
--  22765 |    0 | xxx
--
-- Every row version carries xmin — the transaction that
-- created it. PostgreSQL does not overwrite or erase on
-- rollback: it marks the aborting transaction's id as
-- ABORTED in the commit log (pg_xact), and every future
-- reader then treats rows with that xmin as invisible.
--
-- CONSEQUENCE: rollback in PostgreSQL is O(1) regardless of
-- how much the transaction did — it is one status flag.
-- The dead row versions are reclaimed later by VACUUM.
--
-- Compare a system with a physical UNDO log (Oracle, MySQL
-- InnoDB): rollback there must actually restore before-images,
-- so a large transaction's rollback takes proportional time.
-- That is a real operational difference: "the rollback has
-- been running for an hour" is an Oracle sentence, not a
-- PostgreSQL one.

The MVCC observation deserves emphasis because it changes the answer to a standard exam question. CLASSICAL (textbook) UNDO: read the log backwards, restore each old value, write an ABORT record. → cost proportional to the transaction's size POSTGRESQL'S UNDO: set one bit in the commit-status map. Row versions created by the aborted transaction are simply never visible again. → cost is constant Both satisfy atomicity. They differ in WHERE the cost lands: · classical undo pays at ROLLBACK time · MVCC pays later, at VACUUM time, cleaning dead tuples Neither is free. MVCC's deferred cost is why a long-running transaction causes TABLE BLOAT — it prevents VACUUM from reclaiming versions that might still be visible to it. For an exam, describe the classical undo/redo algorithm — it is what the syllabus means. Knowing that a real system may implement atomicity differently is the extra mark.

🌍 Go further: the algorithm above is a simplified ARIES (Algorithms for Recovery and Isolation Exploiting Semantics), the 1992 IBM design that essentially every relational database uses. Its two refinements worth knowing are page LSNs — each page stores the LSN of the last log record applied to it, so redo can skip pages already up to date — and compensation log records, which log the undo work itself so that a crash during recovery does not repeat it. Search "ARIES recovery algorithm paper"; it is dense but the abstract and section 1 repay the effort.

💡 Exam angle: state the write-ahead logging rule (log record to stable storage before the data page) and the commit rule (committed when the COMMIT record is durable), and explain why each is sufficient. Know the log-record format <T, item, old, new> and that redo goes forward, undo goes backward. The guaranteed question is a worked recovery: given a log with a crash point, list the REDO and UNDO sets and the final values. Explain checkpoints as bounding recovery work, including why the active-transaction list is needed. Mention idempotence as the reason log records store values rather than operations.

Syllabus points

Ensuring atomicity during recovery

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.