Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive)

The Transactions pages already give you the isolation-level table — which anomaly each level prevents. This page derives the machinery underneath that table: why a crash recovery needs both REDO and UNDO (not just one), what a "snapshot" actually is as a data structure, why two engines that both call themselves "serializable" behave completely differently under load, and why a lock taken on one row can silently become a lock on the whole table.

1. Recovery — why REDO and UNDO both exist

Mechanism: recovery machinery is not a design choice made for its own sake — it is forced by the buffer manager's policy on two independent questions. STEAL: may a dirty page (holding an uncommitted transaction's write) be evicted from the buffer pool and written to disk before that transaction commits? FORCE: must every page a transaction touched be flushed to disk at the moment it commits, before the commit can return?

A real engine answers STEAL = yes, FORCE = no, because the alternative is unusable: forbidding STEAL means the buffer pool can never evict a page that belongs to a still-running transaction, which starves memory under any long transaction; requiring FORCE means every commit blocks on random-access disk I/O for every page touched, which is ruinously slow compared to one sequential log write. STEAL+NO-FORCE is fast for exactly the reason the other three combinations are not — but it is precisely what forces both halves of recovery to exist:

• STEAL ⇒ need UNDO. Because an uncommitted transaction's dirty page can already be sitting on disk when the engine crashes, recovery cannot assume "whatever's on disk was committed." It must be able to roll back a partially-applied, never-committed change — that is UNDO.
• NO-FORCE ⇒ need REDO. Because a transaction can commit while its changed pages are still only in memory, a crash can wipe out a change the client was already told succeeded. Recovery must be able to replay a durably-logged, committed change that never reached disk — that is REDO.

Take away either half of STEAL+NO-FORCE and one recovery phase becomes unnecessary (see the diagram) — but you pay for it with a slower, less flexible buffer manager. This is the ARIES rationale in one sentence: STEAL+NO-FORCE buys write throughput at the cost of needing both REDO and UNDO on restart.

Traced example: STEAL+NO-FORCE crash recovery, second by second

Three transactions run against pages P_A, P_B, P_C (each holding one row). The write-ahead log (WAL) is fsync'd at every commit — that is the durability mechanism: the log record is guaranteed durable the instant COMMIT returns, regardless of whether the data page itself ever reached disk before the crash.

LSN	Event	Buffer pool / disk effect
10–12	T1: BEGIN; write A: 0→10; COMMIT (WAL fsync)	P_A dirty in buffer pool, not yet flushed to disk (NO-FORCE)
13–14	T2: BEGIN; write B: 0→20 (never commits)	Buffer pool under pressure evicts and flushes P_B to disk — an uncommitted page hits disk (STEAL)
15–17	T3: BEGIN; write C: 0→30; COMMIT (WAL fsync)	P_C dirty in buffer pool, not yet flushed (NO-FORCE)
—	CRASH. On-disk state at this instant: P_A=0 (committed, but not flushed), P_B=20 (uncommitted, but flushed), P_C=0 (committed, but not flushed).

Recovery (ARIES: Analysis → Redo → Undo):

1. Analysis pass. Scan the WAL forward from the last checkpoint. T1 and T3 have COMMIT records — they are winners. T2 has no COMMIT record — it is a loser and must be rolled back.
2. Redo pass. Replay every logged change in LSN order — T2's included — regardless of commit status ("repeating history"): apply LSN11 (A:0→10), LSN14 (B:0→20), LSN16 (C:0→30). Each page carries its own on-disk LSN, so a redo is skipped if the page's stored LSN is already ≥ the log record's LSN — this is what makes redo idempotent and safe to re-run after a second crash mid-recovery. Here, P_B's on-disk LSN is already 14 (it was flushed before the crash), so its redo is a no-op; P_A and P_C's redos actually apply. After this pass: P_A=10, P_B=20, P_C=30 — the exact state at the instant of the crash, winners and losers alike.
3. Undo pass. Now roll back every loser. T2 is the only one: undo LSN14, writing a compensation log record (CLR) B:20→0 so the undo itself is durable and will not be re-undone if the recovery process crashes again.

Final state: P_A=10 (T1's commit survived, thanks to REDO), P_B=0 (T2's uncommitted write was rolled back, thanks to UNDO), P_C=30 (T3's commit survived, thanks to REDO). Both halves of recovery were required by the same two pages that got flushed at the "wrong" time — exactly the STEAL/NO-FORCE consequence above.

Commit durability mechanics beyond the single fsync

• Group commit. Fsync is the expensive step (a real disk flush), so engines batch: several transactions that call COMMIT within a short window share one fsync call, and all are acknowledged together once it returns. This trades a few milliseconds of added commit latency for dramatically higher commit throughput under concurrent load.
• Checkpointing. Replaying the WAL from the beginning of time after every crash is unbounded. A checkpoint periodically records "every transaction and dirty page as of this point" so recovery's Analysis pass only needs to scan from the last checkpoint forward — bounding recovery time to "time since last checkpoint," not "time since the database was created."
• Lazy/background data-page flushing. Because of NO-FORCE, the buffer manager is free to write dirty pages back to disk on its own schedule (a background flusher, or checkpoint-driven), smoothing out I/O instead of forcing it synchronously on every commit.

2. MVCC internals & engine differences

Mechanism: a snapshot is not a single timestamp or counter — it is a small data structure: (xmin horizon, xmax, xip_list). xmin is the oldest transaction still running anywhere when the snapshot was taken; xmax is the next transaction id not yet assigned; xip_list is the exact set of transaction ids that were in progress at that instant. A row version is visible to a snapshot only if its creator committed before the snapshot AND its creator is not in the snapshot's in-progress list — the xip_list is the piece people forget, and it is exactly what lets a transaction that started earlier but committed later stay invisible to a snapshot taken in between. (The full step-by-step trace of this — xmin/xmax on a row as it's updated by one writer and read by two readers — is worked in "MVCC & Locking — Snapshots, Row Locks & Deadlocks"; this page assumes that visibility rule and focuses on what differs across engines.)

Where the old versions live is the deep engine-level difference:

• PostgreSQL keeps old versions in the heap itself. An UPDATE inserts a whole new tuple into the same table and marks the old one dead by setting its xmax. Nothing is overwritten in place. The direct consequence: dead tuples accumulate as real bytes in the table and every index, which is exactly the "bloat" that VACUUM exists to clean up — and why a single long-running transaction (holding the xmin horizon back) can stall cleanup cluster-wide.
• InnoDB and Oracle keep old versions in a separate undo/rollback segment. The clustered index always holds only the latest version; an older version a reader still needs is reconstructed by walking backward through undo records (InnoDB's roll pointer chain) and applying them as diffs. The table itself never bloats with old versions — but a long-running reader instead pins the undo segment, which grows ("history list length" in InnoDB) until that reader finishes.

Same guarantee (a stable, consistent snapshot with no read locks), opposite storage trade-off: Postgres pays in table/index bloat that a background process must reclaim; InnoDB/Oracle pay in undo-segment growth pinned by whichever reader is oldest. Neither cost disappears — it just shows up in a different place, which is why "keep transactions short" is a universal MVCC rule, not a Postgres-specific one.

3. Serializable is not one thing: 2PL vs SSI

Mechanism: "serializable" only promises that the outcome is equivalent to some serial order of the transactions — it says nothing about how that guarantee is enforced, and the two dominant mechanisms behave completely differently under load.

• Classic two-phase locking (2PL) serializes by blocking: a transaction takes a shared lock to read and an exclusive lock to write, holds every lock until commit, and any conflicting transaction simply waits. This prevents every anomaly, including write skew, by construction — but readers block writers, writers block readers, and a cycle of waits deadlocks (detected and resolved by aborting one victim).
• Serializable Snapshot Isolation (SSI — PostgreSQL's SERIALIZABLE) serializes by abort: transactions run optimistically on ordinary MVCC snapshots, taking no extra locks and never blocking each other, while the engine tracks read/write dependencies between concurrent transactions in the background. If it detects the specific "dangerous structure" — a cycle of rw-antidependencies that could not have arisen in any serial order — it aborts one of the transactions at commit time. The app must retry.

The cost/behavior difference is the whole judgment call: 2PL pays in reduced concurrency while waiting (and occasional deadlocks); SSI pays in wasted work and commit-time aborts under contention (and mandatory retry logic). Both are truly serializable — they just move the cost to a different moment. (The write-skew anomaly that plain Snapshot Isolation lets through, and exactly why SSI is what closes that specific hole, is traced in full in "Write Skew, Lost Update & Snapshot Isolation" — this page assumes that anomaly and focuses on the 2PL-vs-SSI mechanism choice.)

4. Isolation anomalies, grounded in mechanism

Each classic anomaly is a specific gap between "what a lock/snapshot covers" and "what the transaction actually depends on":

• Dirty read — a transaction reads a row another transaction wrote but has not committed. Mechanism gap: no rule stopping a read from seeing an uncommitted xmin. Every mainstream engine's lowest usable level (Read Committed) closes this by construction.
• Non-repeatable read — the same row, read twice in one transaction, returns two different values because another transaction committed an update to it in between. Mechanism gap: the reader's visibility check is re-evaluated fresh on each statement (Read Committed's per-statement snapshot) instead of being pinned once. Fixed by taking one snapshot per transaction (Repeatable Read / Snapshot Isolation).
• Phantom — a re-run WHERE query returns a different set of rows, because another transaction inserted or deleted a row matching the predicate. The critical distinction: this is not about a row you already hold — it is about a predicate/range gaining or losing membership. Under a pure locking engine, a lock on the rows you already read cannot stop a brand-new row from being inserted into that range, because that new row didn't exist yet to be locked.

Classic phantom reads vs serializability: engines close different gaps with different tools. Do not collapse "phantom prevention" into one mechanism and one isolation level — the answer depends on what you mean and which engine you are on.

• Classic phantom read (ANSI / the re-SELECT case). Transaction T1 runs SELECT * FROM seats WHERE flight='X' AND free, then later re-runs the same query and sees a newly committed free seat that T2 inserted. Under PostgreSQL REPEATABLE READ (which is Snapshot Isolation: one snapshot for the whole transaction), that re-SELECT cannot see T2's insert — the new row's xmin is not visible to T1's snapshot. No gap locks and no SSI are required for this. Snapshot lifetime alone freezes the set of visible rows for every statement in the transaction. That is the K12 trap: "Postgres needs SSI / predicate locks to stop phantoms" is incomplete; at RR, classic phantom reads are already gone.
• What SI still allows (why SERIALIZABLE exists). Snapshot Isolation does not guarantee serializability. Two concurrent RR transactions can each read "there are 0 free seats in the window," each insert one booking, and both commit — a write-skew / predicate-write anomaly: neither saw the other's write, neither re-read an inconsistent set of existing rows, yet the final state could not arise from any serial order. That is the hole SSI closes, not the classic "my second SELECT returned different rows" phantom.
• InnoDB: gap locks and next-key locks (lock-based RR). InnoDB's default REPEATABLE READ is not pure SI for writers: range scans take gap / next-key locks on the gaps between index keys so a concurrent INSERT into that range is blocked. A next-key lock = row lock + the gap immediately before it. That is how InnoDB stops both phantom reads and many predicate-based races without needing SSI — at the cost of insert blocking and deadlocks under concurrent range writers.
• PostgreSQL SERIALIZABLE: SSI + SIREAD (predicate) locks — abort, not block. At SERIALIZABLE, Postgres still runs on snapshots (no reader/writer blocking like 2PL). It additionally records SIREAD / predicate locks that track what each transaction read (range/condition conceptually), and if a concurrent write would have changed that predicate result in a way that creates a dangerous rw-antidependency cycle, one transaction aborts at commit. Predicate locks here are conflict-detection metadata for SSI, not InnoDB-style gap locks that stall inserts. Use them to reason about write skew and true serializability — do not cite them as "how Postgres RR stops phantom reads."

Traced contrast (same two transactions, two engines):

Step	T1	T2	PG RR (SI)	PG SERIALIZABLE (SSI)	InnoDB RR (gap locks)
1	SELECT COUNT(*) … WHERE free → 1		snapshot S1 sees 1 free	same + SIREAD on range	next-key locks gaps in free range
2		INSERT a matching free row; COMMIT	allowed; T1 still sees 1 on re-SELECT	INSERT ok; rw-edge recorded	T2 blocks on gap until T1 ends
3	re-SELECT COUNT		still 1 (classic phantom read blocked by snapshot)	still 1	still 1 (and T2 may still be waiting)
4	INSERT booking based on "only 1 left"; COMMIT	(if T2 also booked from "only 1")	both commits can succeed → write skew possible	one COMMIT aborts (serialization failure)	T2 runs only after T1; serial order forced by locks

Takeaway: Postgres RR already kills classic phantom reads via the transaction snapshot; SSI is for serializability (write skew and related multi-object anomalies); InnoDB RR kills range phantoms by locking gaps. Interview answers that say "Postgres prevents phantoms with SSI like InnoDB uses gap locks" conflate three different mechanisms.

5. Lock taxonomy & the ACID subtlety

Shared (S) vs exclusive (X): any number of transactions may hold a shared lock on the same row concurrently (compatible with each other) — that's what lets many readers proceed together; an exclusive lock is incompatible with every other lock, shared or exclusive, on that row.

Intent locks (IS/IX) and escalation. Before a transaction takes a row-level S or X lock, it first takes an intent lock (IS or IX) at the table level, announcing "I hold (or intend to hold) row-level locks somewhere inside this table." This lets a different transaction that wants a whole-table lock check compatibility in O(1) against the intent lock, instead of scanning every row lock in the table. Under memory pressure — too many individual row locks consuming lock-table memory — the engine can perform lock escalation: replace many fine-grained row locks with one coarse table-level lock. This bounds memory, but the concurrency cost is real and immediate — every other transaction that only needed a different, unrelated row in that table now blocks on the whole table instead of just its row. Escalation trades memory safety for a concurrency cliff, which is why it shows up in production as a sudden, hard-to-diagnose throughput collapse under load rather than a gradual slowdown.

The ACID subtlety: not all four letters live at the same layer. Atomicity, Isolation, and Durability are engine properties — the WAL/REDO/UNDO machinery (§1), the locking/MVCC machinery (§2–4), and the fsync/checkpoint machinery all deliver them regardless of what the application does. Consistency is different — it is largely an application concern. The database enforces the constraints it knows about (foreign keys, unique indexes, check constraints), but whether a transaction moves the database from one business-valid state to another (the on-call invariant, the inventory-never-negative invariant) depends entirely on the application writing correct transaction logic against those constraints — the engine cannot invent an invariant it was never told about.

Distributed atomic commit, briefly. A single-node transaction's atomicity is exactly §1's REDO/UNDO story. Across multiple nodes, atomicity needs two-phase commit (2PC): a coordinator asks every participant to prepare (durably log its half of the change and vote), and only issues the actual commit once every participant has voted yes — guaranteeing all-or-nothing across nodes at the cost of blocking every participant while the coordinator decides. This interacts with replication lag the same way single-node durability does: a participant that acks "prepared" but whose change hasn't yet replicated to its own followers can lose that change in a failover, which is the same RPO-window problem covered in the replication-lag/failover material — 2PC's cross-node atomicity and a single node's replication durability are two separate guarantees that both have to hold.

Pitfalls

• Assuming a crash-safe database only needs REDO ("just replay the log") — without STEAL, that would be true, but every real engine's buffer manager uses STEAL, so UNDO is not optional.
• Treating a snapshot as "a timestamp" — the in-progress list (xip_list) is what actually decides visibility for concurrently-running transactions; id order alone gives the wrong answer.
• Saying "Postgres stops phantoms with SSI/predicate locks" — classic phantom reads are already stopped at REPEATABLE READ by the transaction snapshot; SSI is for write skew / true serializability. Gap locks are the InnoDB story.
• Reaching for row locks alone (in a locking engine) to stop a range phantom — a row lock cannot block an INSERT of a row that didn't exist yet; InnoDB needs gap/next-key locks; pure SI engines freeze the read set by snapshot instead of blocking the insert.
• Assuming "SERIALIZABLE" means the same mechanism everywhere — SQL Server/MySQL's SERIALIZABLE is lock-based (2PL-like, blocking), PostgreSQL's is SSI (optimistic, abort-based); the failure modes under contention (stalls vs. retriable aborts) are opposite.
• Not budgeting for lock escalation — a bulk update that looks fine in isolation can flip to a table lock under memory pressure and stall every unrelated transaction on that table.
• Confusing engine-guaranteed Consistency with application correctness — a schema with no constraints gives the engine nothing to enforce; "C" in ACID does not mean "my business logic is bug-free."

Judgment layer

2PL vs SSI. Choose lock-based 2PL-style serializability when contention is low-to-moderate and you cannot tolerate application-level retry logic (or the engine doesn't offer SSI, e.g. MySQL, SQL Server). Choose SSI (PostgreSQL SERIALIZABLE) when reads dominate and you want near-snapshot-isolation concurrency with true serializable correctness — but only if the application is written to catch a serialization-failure error and retry the whole transaction; without that retry loop, SSI's aborts surface as user-facing failures.

Isolation level choice. Default to Read Committed for ordinary CRUD where each statement's own consistency is enough (Postgres and Oracle default here; MySQL/InnoDB defaults to REPEATABLE READ). Move to Repeatable Read / Snapshot Isolation when a transaction must see one consistent view across multiple statements (a report, a multi-step calculation) — on Postgres RR this already freezes the visible row set (no classic phantom reads), but write skew remains. Reach for full Serializable only when a cross-row invariant is genuinely business-critical (double-spend, capacity limits, scheduling) — SSI closes write skew and related predicate-write races that SI leaves open, at the cost of serialization-failure retries.

Postgres heap-MVCC vs. undo-segment MVCC. Neither storage strategy is free of long-transaction pain — they just fail differently. Postgres's heap-resident versions mean a long transaction bloats the table and every index on it, recovered later by (auto)vacuum; InnoDB/Oracle's undo-segment versions mean a long transaction pins the undo/history list, growing it until that reader finishes, with no separate cleanup pass needed once it does. If your workload has occasional very-long read transactions (reporting, batch export), that is a reason to route them to a replica or a snapshot export rather than an argument for choosing one engine over the other — both need the same operational discipline: keep transactions short.

Takeaways

• STEAL (dirty pages of uncommitted txns may hit disk) forces UNDO; NO-FORCE (committed txns' pages may not hit disk yet) forces REDO — real engines run both because STEAL+NO-FORCE is the only combination fast enough to use.
• A snapshot is (xmin, xmax, xip_list), not a single number — visibility is "creator committed before me AND creator not in my in-progress list." Postgres keeps old versions in the heap (bloat, VACUUM); InnoDB/Oracle keep them in undo (history-list growth) — same guarantee, opposite cost location.
• "Serializable" is a promise about outcome, not mechanism: 2PL enforces it by blocking (and risks deadlock); SSI enforces it by optimistic execution plus commit-time abort (and requires retry logic). Classic phantom reads on Postgres die at RR via snapshot SI; InnoDB RR uses gap/next-key locks; SSI is what closes write skew / non-serializable predicate races that SI still allows.
• Locking has its own cost cliff (intent locks → escalation → table-level stalls), and only A/I/D are the engine's job — Consistency is the application's constraints and transaction logic, not something the database invents on its own.

---

Synthesized from the ARIES recovery paper (Mohan et al.) and CMU 15-445/645 (Andy Pavlo) on buffer management and logging; PostgreSQL documentation on MVCC, snapshots, and Serializable Snapshot Isolation; Cahill, Röhm & Fekete, "Serializable Isolation for Snapshot Databases" (SIGMOD 2008); the InnoDB manual on gap/next-key locking and multi-versioning; M. Kleppmann, Designing Data-Intensive Applications ch. 7 & 9. Cross-references: "MVCC & Locking — Snapshots, Row Locks & Deadlocks," "Write Skew, Lost Update & Snapshot Isolation," "Isolation Levels & Anomalies," "Databases for System Design — Isolation Anomalies, B-Tree vs LSM, Join Planning, Quorum & Failover," "Replication Lag & Failover," "2PC vs Saga vs TCC." Re-authored/Deepened for this guide.

I just read a lesson on **Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive)** (Databases) and want to truly understand it. Explain Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Transactions & Concurrency — Recovery (REDO/UNDO), MVCC Internals, Serializability & Locking (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.