MVCC

Deep dive

How it works

Parts:

• version chain — per key, versions stamped with commit_ts (newest-first or oldest-first)
• timestamp clock — hands out start_ts and commit_ts
• active-transaction registry — start timestamps of running snapshots
• write set — a transaction's buffered writes, checked at commit
• garbage collector — drops versions older than the horizon (smallest active start_ts)

key "acct:7":  [ts=5 → 100] → [ts=9 → 80] → [ts=14 → 50]     (oldest → newest)
txn with start_ts=10 reads → 80        txn with start_ts=20 reads → 50

1. Begin: take start_ts = the last committed timestamp, and register it as active.
2. Read: own writes first. Otherwise walk the key's versions and return the newest with commit_ts ≤ start_ts. A tombstone version means "deleted".
3. Write: buffer in the transaction's write set.
4. Commit: for each written key, if the newest committed version has commit_ts > start_ts, someone committed a conflicting write after our snapshot: abort. Otherwise take commit_ts = clock + 1, install all versions, then publish the clock. Readers never see half a commit.
5. GC: horizon = smallest active start_ts. For each chain, keep the newest version ≤ horizon and everything newer; drop the rest.

Code

use std::collections::HashMap;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Mutex, RwLock};

struct Version { commit_ts: u64, val: Option<Vec<u8>> } // None = delete

pub struct Store {
    data: RwLock<HashMap<Vec<u8>, Vec<Version>>>, // per key, oldest → newest
    clock: AtomicU64,                             // last committed timestamp
    commit_lock: Mutex<()>,                       // serializes validate+install (real systems: per-row latches)
    active: Mutex<Vec<u64>>,                      // start_ts of open transactions
}

pub struct Txn<'a> { s: &'a Store, start_ts: u64, writes: HashMap<Vec<u8>, Option<Vec<u8>>> }

impl Store {
    pub fn new() -> Self {
        Store { data: RwLock::default(), clock: AtomicU64::new(0), commit_lock: Mutex::new(()), active: Mutex::default() }
    }
    pub fn begin(&self) -> Txn<'_> {
        let mut act = self.active.lock().unwrap(); // register atomically with reading the clock (GC horizon)
        let start_ts = self.clock.load(Ordering::Acquire);
        act.push(start_ts);
        Txn { s: self, start_ts, writes: HashMap::new() }
    }
    /// Drop versions that no active or future snapshot can read.
    pub fn gc(&self) {
        let horizon = {
            let act = self.active.lock().unwrap();
            act.iter().copied().min().unwrap_or(self.clock.load(Ordering::Acquire))
        };
        let mut data = self.data.write().unwrap();
        for chain in data.values_mut() {
            if let Some(i) = chain.iter().rposition(|v| v.commit_ts <= horizon) { chain.drain(..i); }
        }
        data.retain(|_, c| !(c.len() == 1 && c[0].val.is_none())); // fully deleted keys
    }
}

impl<'a> Txn<'a> {
    pub fn get(&self, k: &[u8]) -> Option<Vec<u8>> {
        if let Some(v) = self.writes.get(k) { return v.clone(); } // read your own writes
        let data = self.s.data.read().unwrap();
        data.get(k)?.iter().rev().find(|v| v.commit_ts <= self.start_ts)?.val.clone()
    }
    pub fn put(&mut self, k: &[u8], v: Option<Vec<u8>>) { self.writes.insert(k.to_vec(), v); }

    pub fn commit(mut self) -> Result<u64, &'static str> {
        let _g = self.s.commit_lock.lock().unwrap();
        let mut data = self.s.data.write().unwrap();
        for k in self.writes.keys() {
            let newest = data.get(k).and_then(|c| c.last());
            if newest.map_or(false, |v| v.commit_ts > self.start_ts) { return Err("write-write conflict"); }
        }
        let ts = self.s.clock.load(Ordering::Relaxed) + 1;
        for (k, v) in self.writes.drain() { data.entry(k).or_default().push(Version { commit_ts: ts, val: v }); }
        self.s.clock.store(ts, Ordering::Release); // publish only after every version is installed
        Ok(ts)
    }
}

impl Drop for Txn<'_> { // commit, abort and early return all end here
    fn drop(&mut self) {
        let mut act = self.s.active.lock().unwrap();
        if let Some(i) = act.iter().position(|&t| t == self.start_ts) { act.swap_remove(i); }
    }
}

Write skew under SI: on-call rule "at least one doctor on call". T1 and T2 both read {Alice, Bob on call}. T1 takes Alice off and T2 takes Bob off. The write sets are disjoint, so both commit and nobody is on call. Fix it with SSI, by materializing the conflict (both update a shared row), or with SELECT ... FOR UPDATE.

Complexity and constants

• Read cost = versions walked. Newest-to-oldest chains (InnoDB undo, Hekaton) make current reads O(1) and old snapshots slower. Oldest-to-newest (PostgreSQL heap with HOT chains) is the reverse.
• A global timestamp counter on one cache line tops out around order of 10-100 M increments/s across cores. Beyond that, use batched or per-core timestamp allocation, or HLC/TrueTime in distributed systems.
• Space: PostgreSQL stores a 23-byte tuple header (xmin, xmax, ctid…) per version. An update writes a whole new tuple, and its index entries too unless the update is HOT.
• PostgreSQL transaction IDs are 32-bit. Tables must be frozen by VACUUM before about 2³¹ transactions pass, or the database stops accepting writes (wraparound protection).

Efficiency

• Cost: a read walks the version chain to the snapshot; an update writes a whole new version (PostgreSQL: 23-byte tuple header plus index entries unless the update is HOT). A shared timestamp counter tops out at order of 10-100 M increments/s across cores. Bound: memory and I/O to write and reclaim versions, not CPU.
• Levers:
  • short transactions, no idle-in-transaction sessions or forgotten replication slots — GC horizon keeps moving — always (one old snapshot pins every newer version)
  • HOT updates and heap fillfactor below 100 — no index writes when no indexed column changes — PostgreSQL-style heaps
  • newest-first version chains — current reads O(1), cost moves to old snapshots — mostly-current reads
  • batched or per-core timestamp allocation — no single hot cache line — many-core engines
  • 2PL or OCC instead — no version storage — short single-row transactions on one node
• Naive → standard → state of the art:
  • readers take shared locks · readers block writers
  • versioned rows, snapshot at begin, background GC · readers never wait, version overhead
  • batched timestamps, in-place deltas, HOT-style updates · fewer version and index writes

Implementation notes

• PostgreSQL visibility: the snapshot is (xmin, xmax, in-progress xids). A version is visible if its creator committed and is not in the snapshot, and its deleter is not. Commit status lives in the CLOG, and hint bits cache it on the tuple.
• Index entries point at versions (PostgreSQL) or at the logical row (InnoDB secondary indexes store the primary key and check visibility via undo). PostgreSQL's HOT updates skip index writes when no indexed column changed and the new version fits on the same page.
• Read-only transactions at SI never abort. Make them cheap: no write set, no validation.
• GC cooperative or background: PostgreSQL autovacuum, InnoDB purge threads. In-memory engines can GC on access, and need epoch-based reclamation to free versions safely while readers traverse them.
• Distributed MVCC: Percolator-style timestamp oracle (TiDB), HLC (CockroachDB, YugabyteDB), TrueTime (Spanner).

Pitfalls

• Assuming SI is serializable. Write skew and read-only anomalies are real.
• "Idle in transaction" sessions and forgotten replication slots hold the GC horizon. Bloat grows until VACUUM can catch up.
• Hot counters: every increment makes a version and the conflicts abort. Use commutative updates or sharded counters.
• Long version chains make old snapshots slow (InnoDB history list length).
• Taking the snapshot per statement (READ COMMITTED, the PostgreSQL default) rather than per transaction changes what an application sees between statements.

Variants and alternatives

In production

• Relational databases: PostgreSQL, MySQL InnoDB, Oracle, SQL Server (snapshot isolation, RCSI), SQLite WAL mode (readers keep a snapshot).
• Distributed and key-value stores: CockroachDB, TiDB/TiKV (Percolator), Spanner, FoundationDB (5-second MVCC window), LMDB (copy-on-write snapshots).
• Language runtimes: Clojure's software transactional memory (refs) uses MVCC.

Implementations

Sources

• P. Bernstein, N. Goodman, Multiversion Concurrency Control—Theory and Algorithms, ACM TODS, 1983. paper
• H. Berenson et al., A Critique of ANSI SQL Isolation Levels, SIGMOD, 1995. paper · arXiv
• M. Cahill, U. Röhm, A. Fekete, Serializable Isolation for Snapshot Databases, SIGMOD, 2008. paper
• D. Ports, K. Grittner, Serializable Snapshot Isolation in PostgreSQL, VLDB, 2012. paper · pdf
• Y. Wu et al., An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, VLDB, 2017. paper
• D. Peng, F. Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications (Percolator), OSDI, 2010. pdf
• P.-Å. Larson et al., High-Performance Concurrency Control Mechanisms for Main-Memory Databases, VLDB 2011. paper · paper
• PostgreSQL documentation, Concurrency Control (MVCC chapter). docs