db-13 — References

Foundational textbooks

  • Bernstein, Hadzilacos, Goodman — Concurrency Control and Recovery in Database Systems (Addison-Wesley, 1987). The canonical treatment of serialization theory: conflict-serializability, view-serializability, locking protocols, multi-version graphs. Chapter 5 ("Multiversion Concurrency Control") is the textbook derivation of the version-chain abstraction used in this lab. The whole book is freely available as a scanned PDF; the proofs of MVSR vs CSR equivalence are required reading for anyone who wants to know why SI is a thing.

  • Weikum & Vossen — Transactional Information Systems (Morgan Kaufmann, 2002). Modernizes the Bernstein treatment with page-model vs object-model schedules and chapter-length coverage of optimistic CC, snapshot isolation, and recovery. The treatment of the generalized SI anomaly catalog is the cleanest in print.

Snapshot isolation: definitional papers

  • Berenson, Bernstein, Gray, Melton, O'Neil, O'Neil — "A Critique of ANSI SQL Isolation Levels" (SIGMOD 1995). The paper that defines snapshot isolation precisely, names the anomalies (lost-update, dirty-read, fuzzy-read, phantom, A5A read-skew, A5B write-skew), and shows the ANSI standard's English-prose definitions are inadequate. Every claim in our CONCEPTS.md about what SI does and does not give you traces directly to this paper.

  • Fekete, Liarokapis, O'Neil, O'Neil, Shasha — "Making Snapshot Isolation Serializable" (TODS 2005). The dangerous-structure theorem that underpins Postgres's SSI. Required reading if you want to understand what the next lab over from this one would add.

Production MVCC engines

  • PostgreSQL 16 documentation, chapter 13 ("Concurrency Control"). https://www.postgresql.org/docs/16/mvcc.html. Postgres's xmin/xmax hidden columns are exactly our commit_ts / tombstone scheme, just with the tombstone collapsed into the next row's xmin. Chapter 13.6 ("Caveats") names write-skew explicitly.

  • PostgreSQL src/backend/access/heap/heapam.c and src/backend/utils/time/snapmgr.c. The C implementation of HeapTupleSatisfiesMVCC, GetOldestXmin, and VACUUM's visibility logic. Our gc(below_ts) is a faithful (single-tenant, single-shard) port of OldestXmin-based pruning.

  • Peng & Dabek — "Large-scale Incremental Processing Using Distributed Transactions and Notifications" (OSDI 2010). The Google Percolator paper. Defines the two-timestamp (start_ts, commit_ts) protocol on top of Bigtable that became the template for TiKV, CockroachDB's earliest design, and YugabyteDB. Our single-node oracle is the trivial special case of the Percolator TSO.

  • Diaconu, Freedman, Ismert, Larson, Mittal, Stonecipher, Verma, Zwilling — "Hekaton: SQL Server's Memory-Optimized OLTP Engine" (SIGMOD 2013). The deepest publicly available description of an in-memory MVCC engine. Section 3 ("Concurrency Control") describes their lock-free version installation, their GC ("oldest active transaction" again), and their decision to ship both optimistic and pessimistic SI variants. Our store is Hekaton with the locks added back and the latches removed.

  • Wu, Arulraj, Lin, Xian, Pavlo — "An Empirical Evaluation of In-Memory Multi-Version Concurrency Control" (VLDB 2017). The paper that catalogues, benchmarks, and ranks the MVCC design decisions (storage layout, version-chain ordering, GC strategy, index pointer to head vs tail). It is the single most useful paper for anyone designing an MVCC engine from scratch.

  • Kemper & Neumann — "HyPer: A Hybrid OLTP&OLAP Main Memory Database System Based on Virtual Memory Snapshots" (ICDE 2011). HyPer uses fork() for snapshots instead of version chains — a fascinating alternative that this lab does not implement but every engineer should know exists.

SI in distributed systems

  • Sovran, Power, Aguilera, Li — "Transactional Storage for Geo-Replicated Systems" (SOSP 2011) — the Walter paper. Defines parallel snapshot isolation (PSI), a weaker form of SI tractable across data centers. Useful framing if you ever wonder why CRDB doesn't just run plain SI.

  • Bailis, Davidson, Fekete, Ghodsi, Hellerstein, Stoica — "Highly Available Transactions: Virtues and Limitations" (VLDB 2014). Maps the entire CAP / isolation landscape onto availability. SI is provably unachievable under network partitions; this paper tells you exactly where the line is.

Lecture material worth the read

  • CMU 15-721 ("Advanced Database Systems") lectures by Andy Pavlo, Spring 2023. Lecture 04 "Multi-Version Concurrency Control" walks through Postgres / Hekaton / HyPer / Oracle in one hour. Slides + recording are on the CMU course page.

  • Joe Hellerstein's Berkeley CS 186 notes, "Concurrency Control II". Undergraduate-level but the diagrams of conflict graphs and the worked write-skew example are the clearest I have seen.

Lab cross-references

  • db-09 (LevelDB Complete) — the storage engine these transactions could one day be layered on top of. The LSM's sequence numbers are essentially commit_ts in disguise.
  • db-12 (SQL Frontend) — produces the AST that this engine would execute. The natural db-13.5 lab would wire them together.
  • db-14 (Indexes and Query Optimization) — adds secondary indexes; under MVCC, indexes need their own version chains or a pointer-to-head + tuple-side timestamp scheme. See Wu et al. §4.
  • db-16+ (Distributed Fundamentals, Raft, Paxos) — replace the single-node oracle with a distributed timestamp service. The semantic model carries over unchanged.