Chapter 5: Multiversion Concurrency Control (Concurrency Control Book)

Chapter 5 of Concurrency Control and Recovery in Database Systems (1987) introduces multiversion concurrency control (MVCC), a fundamental advance over single-version techniques. Instead of overwriting data, each write operation creates a new version of the data item. Readers can access older committed versions without blocking concurrent writes or being blocked by concurrent writes.

MVCC removes read-write conflicts and increases concurrency significantly. Having multiple versions around gives the scheduler flexibility: if a read arrives "too late" to see the latest write, it can still proceed by accessing an older version. This avoids unnecessary aborts. Writes may still abort due to write-write conflicts, but reads are largely unimpeded. This is especially beneficial in read-heavy workloads.

This chapter presents three broad classes of multiversion methods: Multiversion Timestamp Ordering (MVTO), Multiversion Two-Phase Locking (MV2PL), and Multiversion Mixed Methods.

For all the benefits MVCC provides, the trade-off is additional storage and complexity in managing versions and garbage collection. This is a good tradeoff to take, and  MVCC is the dominant concurrency control approach today. Oracle uses MV2PL. PostgreSQL uses MVCC natively. MySQL uses MVCC in InnoDB. For both of them, reads get a consistent snapshot without locking and writes create new versions and require locking at commit time. Microsoft Hekaton implements an MVTO-style engine in its in-memory OLTP system (see my 2022 post on Hekaton). Pavlo's VLDB'17 paper on evaluation of in-memory MVCC is also a good read here. Spanner may be best viewed as MVTO plus external certification: it uses multiversion reads and assigns commit timestamps via TrueTime, while writes acquire locks and are certified at commit to ensure strict serializability. Unlike MV2PL, reads never block, and unlike pure MVTO, writes are serialized through locking and timestamp-based validation.

Let's dig in to the sections.

Multiversion Serializability Theory

To reason about the correctness of multiversion schemes, this section extends classical serializability theory. It defines MV histories (which include explicit version metadata) and 1V histories, which reflect what users see: a single logical version per item. The key challenge is to ensure that MV histories are equivalent to 1-serial 1V histories. A 1-serial MV history is one in which each read observes the latest committed version at the read's logical time. This avoids anomalies like fractured reads (e.g., reading stale x and fresh y from the same transaction).

Correctness is characterized using a Multiversion Serialization Graph (MVSG). An MV history is 1-serial iff its MVSG is acyclic. This parallels the classical serializability theory, and extends it with versioning. The rest of the section develops the correctness proof via MVSGs. 

Multiversion Timestamp Ordering (MVTO)

MVTO generalizes timestamp ordering by storing multiple versions. Each transaction is assigned a unique timestamp at start. When a transaction Ti reads x, it finds the latest version of x with a timestamp less than TS(Ti). When Ti writes x, it buffers the write and, at commit, creates a new version tagged with TS(Ti).

MVTO guarantees serializability: transactions appear to execute in timestamp order. The main difference from single-version TO is that MVTO avoids aborting reads. Since older versions are preserved, reads always succeed. However, MVTO still aborts transactions on write-write conflicts. Also if Ti tries to write x, but another transaction Tj with TS(Tj) > TS(Ti) has already read an older version of x, Ti must abort to preserve timestamp order.

MVTO is good for read-mostly workloads but struggles with high write contention. Garbage collection also becomes a concern. Old versions can be discarded only after all transactions that might read them complete.

Multiversion Two-Phase Locking (MV2PL)

MV2PL extends strict 2PL by adding versioning. Unlike 2PL, where transactions block when accessing locked items, MV2PL lets readers proceed by using older versions (e.g., accessing the latest committed version as of the lock time). While 2PL systems block on read-write conflicts; MV2PL avoids this by separating read and write versions.

MV2PL also extends 2PL for writes by introducing certify locks: Instead of overwriting in-place, the writers in MV2PL buffer and acquire certify locks at commit time to serialize version creation. A certify lock is exclusive: only one transaction can hold it on a data item at any time. This prevents races and ensures only one new version per item per commit. 

Multiversion Mixed Method

Multiversioning gives the scheduler more flexibility, especially for read-only transactions. If the system knows in advance which transactions are queries (read-only) and which are updaters (perform writes), it can increase concurrency by handling them differently. This method uses MVTO for queries and Strict 2PL for updaters.

Queries behave like in MVTO: they are assigned timestamps at start, read the latest version less than their timestamp, and never block. Updaters use Strict 2PL for mutual exclusion during execution. At commit, the transaction manager assigns each updater a timestamp consistent with its position in the serialization graph, ensuring global consistency. This resembles concurrency control in modern OLAP systems: large analytical reads proceed without blocking, while updates are carefully serialized.

A key innovation here is the commit list. Each transaction maintains a commit list of versions it plans to write. When committing, the transaction must check for conflicts: It cannot write a version if a transaction with a later timestamp has already read an earlier version of that item. This would violate timestamp order. In a centralized system, the commit list can be scanned at commit time to detect such anomalies. In distributed systems, where this check can’t be performed atomically, the system needs to use a distributed coordination protocol like 2PC.