Unit 4.7 · about 5 h
263 / 324Two-phase locking, timestamp ordering and MVCC
Assume Programming's transactions-isolation and synchronization-hazards units. The new job is proving histories and tracing tuple visibility, not another barrier lost update or application lock-order deadlock.
- explain
- derive
You can now
- Derive a conflict graph and distinguish it from a waits-for graph.
- Explain growing/shrinking lock phases, strict locking, predicate protection and deadlock handling.
- Trace PostgreSQL tuple versions using
xmin,xmax, transaction status and snapshots without treating XIDs as timestamps. - Explain timestamp ordering as an enforced serialization order, separate from MVCC storage.
Covers
- Locking, two-phase locking and deadlock behavior
- Timestamp ordering and MVCC vocabulary
- Serializable isolation proofs
Study, in this order
5 steps
- Lectures 17, 18 and 20: histories, locks and versionsCMU 15-445/645 - database and storage core
Lecture 17 notes, section 6, Conflict Serializability, p. 4; Lecture 18 notes, sections 1-4, pp. 1-4; Lecture 20 notes, sections 1-3, pp. 1-3
Depth · In Lecture 18 section 2, skip the sentence claiming strict 2PL reintroduces dirty reads and cascading aborts. Holding exclusive locks to commit prevents both; rigorous 2PL also holds shared locks. The fixed-object conflict-graph theorem needs predicate protection when rows can be inserted.
- Lecture 19: Timestamp Ordering Concurrency ControlCMU Lecture 19: Timestamp Ordering Concurrency Control
Section 1, Timestamp Ordering Concurrency Control, p. 1
Depth · Stop before the OCC validation algorithm; only timestamp-ordering vocabulary is required here.
- DDIA, second edition: predicate protection and SSIDesigning Data-Intensive Applications, 2nd edition - storage and transactions
Chapter 8, Two-Phase Locking through Serializable Snapshot Isolation, printed pp. 313-322
Depth · Use the mechanism comparison. SSI does not abort on every stale read; it detects dangerous dependency combinations, and ordinary write locks remain.
- PostgreSQL 18: System ColumnsPostgreSQL - EXPLAIN and transaction isolation lab
Section 5.6:
xmin,xmaxandctid - PostgreSQL 18: Snapshot functionsPostgreSQL - EXPLAIN and transaction isolation lab
Section 9.27.8, Transaction ID and Snapshot Information Functions:
pg_current_snapshotand thexmin:xmax:xip_listsnapshot representation
Focus on
- Basic 2PL acquires no new locks after its first release. Strict 2PL retains exclusive locks until commit/abort; rigorous 2PL retains shared locks too. Locking existing rows alone does not protect absent matches.
- A precedence graph orders conflicting operations on fixed objects; a waits-for graph records blocked lock requests. A serializable history can still encounter a lock deadlock.
- MVCC is version storage plus visibility rules, not an isolation level. Tuple
xmin/xmaxneed transaction status, snapshot membership and special-case handling; a nonzeroxmaxdoes not prove a row is invisible. - Timestamp ordering enforces a chosen serial order, often using a logical counter. PostgreSQL XIDs are neither wall-clock times nor commit-order counters; long-lived snapshots can prevent reclamation.
Reproduce closed-book
visibility(id int PRIMARY KEY,v int), insert (1,10). Session A: BEGIN; UPDATE visibility SET v=20 WHERE id=1; leave it uncommitted. Session B, in default READ COMMITTED: SELECT v,xmin,xmax,ctid FROM visibility; SELECT pg_current_snapshot(); it sees the old value 10 although its xmax is nonzero in this simple update. Record A's in-progress XID and explain the snapshot bounds; equality of the snapshot's xmin and xmax bounds is possible. Commit A, then rerun B's SELECT: value 20 comes from a new tuple version with a different xmin and ctid. Exact XIDs and offsets are not targets. Draw visibility before and after commit without relying on numeric XID comparison alone.Traps
- Calling two-phase locking two-phase commit. One is a concurrency protocol; the other coordinates atomic commit across participants.
- Assuming strict 2PL is deadlock-free, or applying a fixed-item graph proof to a predicate without accounting for inserts.
- Using
xminorctidas a durable application identity. XIDs wrap and physical row locations can change.
Practice
The section mini-project covers this: annotate the anomaly's dependency graph, trace committed and uncommitted tuple visibility, and distinguish transaction waits from buffer latches in the evidence dossier.
Self-test
-
Why is the old value visible in B while A updates it?
A's replacement version is uncommitted. B's statement snapshot still sees the committed old version; the old version's deletion by A is not yet effective for B. -
Can basic 2PL permit dirty reads?
Yes. Releasing an exclusive lock before commit can expose an uncommitted write. Strict 2PL holds that lock until commit or abort. -
Why must a serializable lock protocol protect gaps or predicates?
New matching rows can change a read's result even though none of its existing rows was overwritten. -
Does the graph cycle prove every MVCC history is invalid?
No. The fixed-object single-version conflict graph theorem has stated assumptions. MVCC serialization analysis must account for which versions were read and their dependencies.
Completion criterion
Stop when
You derive both graph edges and explain the two observed tuple versions, including why a nonzero xmax did not hide the old row.
Leads to
- 4.8 Write-ahead logging, recovery, checksums and durability Separate version visibility and commit status from persistence.
Comes after
- 4.6 Transactions and isolation anomaliesExplain the locks, snapshots and dependency graph underneath this history.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
Also in this section
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.