Multiversion Concurrency Control

In a single-version database, a data item `X` has exactly one value at any instant. A transaction that wants to read `X` while another transaction is mid-write to `X` faces a genuine conflict: it must either wait, abort, or read an uncommitted (dirty) value. Multiversion Concurrency Control eliminates this conflict by storing a sequence of versions for each item, each version tagged with the timestamp of the transaction that created it. When transaction `T` reads `X`, the system does not read "the" value of `X`; it selects, from the version history, the specific version that was valid at `T`'s logical starting time. Formally, for data item `X` we maintain a list of versions ``` X1, X2, ..., Xk ``` where each version `Xi` carries three fields: `content(Xi)` (the value), `W-timestamp(Xi)` (the timestamp of the transaction that wrote it), and `R-timestamp(Xi)` (the largest timestamp among transactions that have read it). When a transaction with timestamp `TS(T)` issues `read(X)`, the system finds the version `Xi` with the largest `W-timestamp(Xi) ≤ TS(T)` and returns its content — updating `R-timestamp(Xi)` to `max(R-timestamp(Xi), TS(T))`. When `T` issues `write(X)`, the system must check that no transaction has already read a version that `T`'s write would have "should have" produced; if some `Xi` has `W-timestamp(Xi) ≤ TS(T) ≤ R-timestamp(Xi)`, then `T` is too late and must be rolled back. Otherwise, `T` creates a brand-new version `Xk+1` rather than overwriting anything. This is the crucial conceptual break from the single-version Timestamp-Ordering Protocol: because writes never destroy data that a reader might need, reads can never be rejected. A read only ever requires finding the right historical version, never waiting for one, and never conflicting with a concurrent writer. Writers still conflict with other writers (two transactions cannot both legitimately create "the" successor version for the same prior version), and a late writer can still conflict with an already-completed read — but read-write conflict, the dominant source of blocking in single-version locking protocols, is structurally impossible.

The multiversion timestamp-ordering algorithm (MV-TO) assigns each transaction `T` a unique timestamp `TS(T)` at start time, typically drawn from a monotonically increasing counter or synchronized clock. The version list for each item begins with a single "creation" version, often a dummy version written at time `−∞` (or time `0`) representing the initial database state.

Read rule. To execute `read(X)` for transaction `T`: ``` find the version Xi of X such that W-timestamp(Xi) is the largest write-timestamp <= TS(T) return content(Xi) set R-timestamp(Xi) = max(R-timestamp(Xi), TS(T)) ``` This always succeeds — there is always some version with `W-timestamp ≤ TS(T)`, because the initial dummy version has the smallest possible timestamp.

Write rule. To execute `write(X)` for transaction `T`: ``` find the version Xi of X such that W-timestamp(Xi) is the largest write-timestamp <= TS(T) if R-timestamp(Xi) > TS(T): // some transaction with a larger timestamp already read // a version older than the one T is trying to install — // T's write arrives "too late" to be consistent with that read abort T else if W-timestamp(Xi) == TS(T): // T already wrote this version earlier in its own execution; // overwrite it in place (no new version needed) content(Xi) = new value else: // safe to create a new version create new version Xk+1 with content(Xk+1) = new value W-timestamp(Xk+1) = TS(T) R-timestamp(Xk+1) = TS(T) ``` Why is the abort condition exactly `R-timestamp(Xi) > TS(T)`? Because `Xi` is the version that should have been visible to `T` had `T` run at its assigned logical time. If some other transaction with a larger timestamp already read `Xi` — meaning it read the value that existed before `T`'s write — then inserting `T`'s version between `Xi` and that reader would retroactively invalidate a read that has already happened. Since we cannot travel back in time to fix that read, `T` must abort. This is the multiversion analogue of the "reject late writes" rule in single-version timestamp ordering, generalized to a version chain instead of a single cell. Full pseudocode for the read/write dispatch, including version-chain maintenance and garbage collection, is given below. ``` function READ(T, X): Xi = version of X with max W-timestamp(Xi) <= TS(T) R-timestamp(Xi) = max(R-timestamp(Xi), TS(T)) return content(Xi) function WRITE(T, X, new_value): Xi = version of X with max W-timestamp(Xi) <= TS(T) if R-timestamp(Xi) > TS(T): abort(T) // late write, must retry with new TS return if W-timestamp(Xi) == TS(T): content(Xi) = new_value // overwrite T's own version else: create version Xk+1 of X content(Xk+1) = new_value W-timestamp(Xk+1) = TS(T) R-timestamp(Xk+1) = TS(T) function GARBAGE_COLLECT(X): let m = min(TS(T)) over all currently active transactions T // a version Xi can be reclaimed once no active or future // transaction could possibly need it: that is, once a // strictly newer version Xj (W-timestamp(Xj) < m) exists // and every version older than Xj is no longer the "current" // version for any transaction with timestamp < m remove any version Xi of X such that there exists a newer version Xj with W-timestamp(Xi) < W-timestamp(Xj) <= m ``` The garbage collector is essential in practice: without it, version chains grow without bound. It is safe to delete version `Xi` once a strictly newer version exists whose write-timestamp is still ≤ the oldest active transaction's timestamp `m`, because no active or future transaction (which will receive a timestamp ≥ current time > any currently active transaction's start) can ever need to read as of a time before `m` yet after `Xi`'s successor was written.

Time complexity. Each `read(X)` requires locating the correct version in `X`'s version chain. If versions are stored in a sorted structure (e.g., a balanced tree or a timestamp-ordered linked list with an index), this lookup costs `O(log v)` where `v` is the number of live versions of `X`; a naive unsorted linked list costs `O(v)`. Each `write(X)` costs the same lookup plus `O(1)` for version creation. Since reads never block, there is no wait-time cost analogous to lock queuing — the latency distribution of reads is dramatically more predictable than under two-phase locking, even though the asymptotic per-operation cost is comparable to an index lookup in a single-version system.

Space complexity. The dominant cost versus a single-version system is storage: `O(V)` extra space where `V` is the total number of live versions across all items, bounded by the write rate times the age of the oldest active transaction (the "vacuum horizon"). A long-running transaction that never commits can pin an unbounded number of old versions, causing bloat — this is the central operational tradeoff of MVCC.

Correctness (serializability). MV-TO produces a schedule equivalent to running transactions in an order consistent with their assigned timestamps — the same guarantee as single-version Timestamp-Ordering Protocol, lifted to a versioned store. The proof sketch: 1. Construct the multiversion serialization graph: draw an edge `Ti → Tj` whenever `Ti` writes a version that `Tj` reads, or whenever `Tj` writes a version immediately following one that `Ti` read (a read-then-overwrite ordering constraint), or whenever `Ti` writes before `Tj` writes to the same item. 2. Every such edge, by construction of the read/write rules above, points from the transaction with the smaller timestamp to the transaction with the larger timestamp. This is because: the read rule always selects a version whose writer has a smaller or equal timestamp; the write-rejection rule specifically aborts any transaction whose write would have to be inserted before a read already performed by a larger-timestamp transaction, which is precisely the scenario that would have created a "backward" edge. 3. A graph in which every edge respects a fixed total order (the timestamp order) cannot contain a cycle, since a cycle would require at least one edge violating that order. 4. Acyclicity of the (multiversion) serialization graph is a sufficient condition for serializability — this is the multiversion generalization of the classical serializability theorem used for single-version scheduling. Hence every schedule produced by MV-TO is serializable, equivalent to the serial order given by transaction timestamps. Note the subtlety versus single-version timestamp ordering: MV-TO never rejects a read, only late writes, because the existence of old versions gives every read a valid target. This is the formal reason "readers never block or abort due to writers" under pure MV-TO.

The honest tradeoff. Full MV-TO is rarely implemented exactly as above because assigning a fresh, globally meaningful timestamp per operation and checking `R-timestamp` on every write is expensive and can cause frequent aborts under contention. Real systems instead implement snapshot isolation (SI): each transaction reads a consistent snapshot of the database as of its start time (exactly per the MV-TO read rule), but write-write conflicts are detected only at commit time using a simpler first-committer-wins rule rather than fine-grained `R-timestamp` bookkeeping. ``` function SI_COMMIT(T): for each item X that T wrote: if some transaction T' committed after T's snapshot began, and T' also wrote X: abort(T) // first-committer-wins // otherwise commit T; its writes become new versions // visible to transactions whose snapshot starts after now ``` Snapshot isolation guarantees that no transaction ever sees another transaction's uncommitted writes, and no transaction overwrites a concurrently-modified item without detection — but it does not guarantee full serializability. The classic counterexample is write skew: two transactions each read overlapping data, each independently satisfy a global constraint based on what they read, and each writes to disjoint items — so first-committer-wins never fires, yet the combined effect violates the constraint. This gap between "snapshot isolation" and "true serializability" is precisely the subject that the study of Isolation Levels formalizes in full.

Consider a bank account item `X` starting at value `100`. Three transactions arrive with assigned timestamps `TS(T1)=10`, `TS(T2)=15`, `TS(T3)=20`.

This trace demonstrates the two essential behaviors. First, `T1`'s original write at step 4 is correctly rejected: `T2` (timestamp 15, larger than `T1`'s 10) already read the pre-write value of `X` in step 3, so inserting `T1`'s write at logical time 10 would silently invalidate a read that has already occurred — the system detects this and aborts `T1` rather than corrupting the serialization order. Second, after `T1` restarts with a larger timestamp (25), its write safely becomes the newest version, and subsequent transactions with timestamps below 25 (like `T3` at time 20) correctly continue to see the older value `100`, exactly matching what a serial execution in timestamp order would have produced. `T2`'s subsequent write attempt at step 7 fails for the same reason `T1`'s did originally — `T3` has by then also read `X0`, extending its `R-ts` beyond `T2`'s timestamp. Note that at no point did any read fail or block; every rejection was of a write, precisely as the correctness argument predicts.

The theoretical foundation for MVCC emerges from the same timestamp-ordering tradition used for single-version scheduling, extended to versioned histories by researchers studying concurrency control in the late 1970s and early 1980s — most notably work by Philip Bernstein and Nathan Goodman, who formalized multiversion timestamp ordering and proved its serializability properties rigorously, and David Reed, whose 1978 MIT dissertation on multiversion timestamping for a decentralized filesystem is often credited as the first systematic treatment.

MVCC is the default concurrency mechanism inside PostgreSQL, Oracle, MySQL/InnoDB, Microsoft SQL Server (under snapshot isolation), and SQLite's write-ahead-log mode. Every distributed SQL system built for global scale — Google Spanner, CockroachDB, YugabyteDB, TiDB — layers MVCC over a distributed timestamp or hybrid-logical-clock scheme to give transactions consistent snapshots across machines without global locking. Analytics engines that run long read queries against operational data (change-data-capture pipelines, HTAP systems) depend entirely on the "readers never block writers" property to coexist with transactional workloads. Version control systems, append-only log stores, and even blockchain state models echo the same core idea: never destroy history, always append, and let readers choose their vantage point in time. Any system description that begins "reads see a consistent snapshot as of transaction start" is, structurally, an MVCC system, and its precise guarantees are best understood as a point on the spectrum of Isolation Levels running underneath a foundation shared with the Timestamp-Ordering Protocol and standing in direct architectural contrast to Two-Phase Locking.

Ask the tutor: Can you walk through how serializable snapshot isolation (SSI) detects write skew that plain snapshot isolation misses?