MVCC — multi-version concurrency control: Exercises

Before starting, keep these three earned symbols in front of you (all defined in the parent):

Figure — MVCC — multi-version concurrency control

Level 1 — Recognition

Exercise 1.1 (L1)

A row version carries (xmin = 74, xmax = ∞). In one sentence, what is the physical meaning of each number?

Recall Solution

$x min = 74$ : transaction 74 created this version — it is the birth certificate.
$x ma x = \infty$ : no transaction has replaced or deleted this version yet, so it is still the live "current truth" for anyone allowed to see txid 74.

Exercise 1.2 (L1)

True or false: "MVCC removes all locking from the database." Justify.

Recall Solution

False. MVCC removes only reader↔writer blocking (readers get an old version, so they never wait). Writer↔writer on the same row still serializes — two transactions cannot both claim to supersede the same version. See Worked Example 2 in the parent note.

Exercise 1.3 (L1)

Match each term to its role: xmin, xmax, active set. (a) list of txids in-progress when I took my snapshot; (b) creator of a version; (c) deleter of a version.

Recall Solution

$x min$ → (b) creator. $x ma x$ → (c) deleter. active set → (a) in-progress txids at snapshot time.

Level 2 — Application

For Level 2, apply the parent's visibility rule:

Exercise 2.1 (L2)

Transaction T90 holds snapshot $S$ : active set $= {}$ , $x_{ma x}^{s na p} = 90$ . A version has (xmin = 85, xmax = ∞) and txid 85 is committed. Visible?

Recall Solution

Birth test: committed(85) ✓, not active ✓, $85 < 90$ ✓ → birth visible. Death test: $x ma x = \infty$ → death not visible ✓. Both clauses hold → visible. T90 reads this version.

Exercise 2.2 (L2)

Same T90 ( $x_{ma x}^{s na p} = 90$ , active $= {}$ ). Version (xmin = 95, xmax = ∞), txid 95 committed. Visible?

Recall Solution

Birth test: $95 < 90$ ? No. Txid 95 started after T90's snapshot (it is in T90's future). Birth invisible → not visible, regardless of the death clause. T90 does not see this version.

Exercise 2.3 (L2)

T90 again. Version (xmin = 60, xmax = 88), both 60 and 88 committed, neither in the active set.

Recall Solution

Birth: committed(60) ✓, not active ✓, $60 < 90$ ✓ → birth visible. Death: apply the same test to $x ma x = 88$ : committed ✓, not active ✓, $88 < 90$ ✓ → death IS visible. So the "death I cannot see" clause fails. Result: not visible — for T90 this version is already deleted.

Exercise 2.4 (L2)

T90 with active set $= {88}$ this time (txid 88 is still running at snapshot). Version (xmin = 60, xmax = 88), 60 committed, 88 running.

Recall Solution

Birth: 60 committed, not active, $< 90$ → visible. Death: test $x ma x = 88$ : is 88 committed and not active? It is active (in T90's snapshot). So the death test fails → death not visible → the "I cannot see the death" clause is satisfied. Result: visible — the deleter was still in-flight when T90 snapped, so T90 pretends the deletion never happened and reads the row as alive.

Level 3 — Analysis

Exercise 3.1 (L3) — the no-block trace

Row balance = 100, clock at 50. T100 (reader) starts with active $= {}$ , $x_{ma x}^{s na p} = 100$ . Then T101 updates balance→200 and commits. Now T100 reads. What value? Did anyone wait?

Recall Solution

After T101's update there are two versions:

old: (xmin = ?, xmax = 101) value 100
new: (xmin = 101, xmax = ∞) value 200

New version birth test: $101 < 100$ ? No → invisible (T101 is in T100's future). Old version death test: deleter is 101, and $101 < 100$ ? No → death invisible → old version still alive. T100 reads 100. Nobody blocked: T101 wrote a new version while T100 read the old one.

Exercise 3.2 (L3) — write–write conflict

Row stock = 5. T200 reads 5, writes 4 (xmin=200) but has not committed. Concurrent T201 tries to update the same row to 4. What happens, and why is this different from the reader case?

Recall Solution

T201 must create a version that supersedes the latest one — but the latest one is being written by the uncommitted T200. Two versions cannot both claim to supersede the same parent, so T201 waits on a row-level write lock held by T200.

If T200 commits: T201, under Snapshot Isolation, hits "could not serialize access due to concurrent update" (first-committer-wins).
If T200 aborts: T201 proceeds. Different from the reader case because a read can be served from the old version, but a write must build on the current head — only one writer can own that head at a time.

Exercise 3.3 (L3) — spot the anomaly

On-call constraint: "≥1 doctor on-call." Alice & Bob both on. Concurrent T1 and T2, same snapshot. T1: sees Bob on → sets Alice off. T2: sees Alice on → sets Bob off. Both commit. Is there a write–write conflict? What is the final state, and what is this anomaly called?

Recall Solution

No write–write conflict: T1 writes Alice's row, T2 writes Bob's row — different rows, so MVCC detects nothing. Each read a frozen snapshot where the other doctor was still on. Final state: zero doctors on-call → constraint violated. This is write skew, an anomaly Snapshot Isolation permits but Serializability forbids. Fix: SSI or SELECT ... FOR UPDATE.

Level 4 — Synthesis

Exercise 4.1 (L4) — build the whole schedule

Row x = 10. Clock starts so the next txid is 300.

T300 begins (reader).
T301 begins, sets x→20, commits.
T302 begins, sets x→30, does not commit.
T300 reads x. T303 begins and reads x.

Give each version's (xmin, xmax), then each reader's result with full visibility reasoning.

Recall Solution

Version chain after step 3:

V0: (xmin=?, xmax=301) value 10
V1: (xmin=301, xmax=302) value 20
V2: (xmin=302, xmax=∞) value 30 (uncommitted)

T300 snapshot: active $= {}$ , $x_{ma x}^{s na p} = 300$ (it began before 301).

V2 birth $302 < 300$ ? No → invisible.
V1 birth $301 < 300$ ? No → invisible.
V0 death = 301, $301 < 300$ ? No → death invisible → V0 alive. T300 reads 10.

T303 snapshot: it began at step 4, so 301 has committed, 302 is still running → active $= {302}$ , $x_{ma x}^{s na p} = 303$ .

V2 birth: 302 committed? No (running/uncommitted) → invisible.
V1 birth: 301 committed ✓, not active ✓, $301 < 303$ ✓ → visible. Death = 302: is 302 visible? It is active → death test fails → death not visible → V1 alive & visible. T303 reads 20.

Two readers, same instant, two answers — each correct for its own snapshot.

Exercise 4.2 (L4) — design the GC horizon

Given the state above (T300 still open, T302 uncommitted), which versions are safe to garbage-collect right now? State the horizon rule you used.

Recall Solution

Rule: a version is dead (collectable) only when its $x ma x$ is committed and older than the oldest live snapshot's horizon — i.e., no currently-active transaction could ever see it. The horizon here is set by the oldest live txid, T300 (it can see V0).

V0 is needed by T300 → cannot collect.
V1's deleter (302) is not even committed → V1 may still be needed → cannot collect.
V2 is uncommitted → cannot collect. Nothing is collectable while T300 stays open. This is exactly why long-open transactions cause bloat (see VACUUM and Garbage Collection).

Level 5 — Mastery

Exercise 5.1 (L5) — the hour-long reporter

A reporting transaction T400 stays open for one hour while millions of rows are updated and committed by short transactions. Predict the two concrete harms, tie each to a specific mechanism, and give one mitigation.

Recall Solution

Version bloat. GC's horizon is pinned at T400's txid (Exercise 4.2 rule). Every old version any updated row leaves behind stays uncollectable for the full hour → tables balloon. Mechanism: the GC horizon = oldest live snapshot.
Slow scans everywhere. Queries must walk long version chains and skip dead-but-uncollected versions, doing extra I/O. Mechanism: visibility check runs per version, so more versions = more work. Mitigation: don't hold read transactions open across expensive work — snapshot the needed data quickly, or split the report; some systems offer a "snapshot too old" safety valve. See Transaction IDs and Wraparound for the related danger of the txid counter itself lapping.

Exercise 5.2 (L5) — choose the concurrency philosophy

A workload is 95% reads, 5% short writes, rare conflicts. Argue why MVCC (optimistic-leaning) beats classic Two-Phase Locking (2PL) (pessimistic) here — and name the one scenario where 2PL would win.

Recall Solution

With 95% reads and rare conflicts, optimistic MVCC lets nearly all readers run lock-free on snapshots → huge throughput, and the rare write conflict is cheap to retry. 2PL would force every reader to acquire shared locks, blocking behind writers and serializing the common path — wasted pessimism for conflicts that almost never happen. Where 2PL wins: a high-contention workload where the same hot rows are updated constantly. Then optimistic retries thrash (abort → retry → abort), and 2PL's up-front locking (or a queue) delivers steadier progress. Match the strategy to the conflict rate.

Exercise 5.3 (L5) — the full visibility verdict, hard case

Snapshot $S$ : active $= {500, 505}$ , $x_{ma x}^{s na p} = 510$ . Decide visibility for each version and explain: (a) (xmin=498, xmax=∞), 498 committed. (b) (xmin=500, xmax=∞), 500 committed after the snapshot. (c) (xmin=498, xmax=505), 498 committed, 505 still running. (d) (xmin=498, xmax=502), 498 and 502 committed, 502 not active.

Recall Solution

(a) Birth: committed, not active, $498 < 510$ → visible. Death $\infty$ → alive. Visible. (b) Birth: 500 is in the active set of $S$ → for consistency I pretend it never happened even though it later committed → birth invisible. Not visible. (c) Birth 498 visible. Death = 505: 505 is active → death test fails → death not visible → row still alive. Visible. (d) Birth 498 visible. Death = 502: committed ✓, not active ✓, $502 < 510$ ✓ → death visible → row deleted for me. Not visible.

Notice (c) vs (d): both born at 498, both have a real $x ma x$ , opposite verdicts — decided entirely by whether the deleter is visible.