MVCC (Multi-Version Concurrency Control)

Overview

Multi-Version Concurrency Control (MVCC) is the dominant concurrency control mechanism in modern database systems. The core idea is deceptively simple: instead of blocking readers when a writer modifies a row, the database maintains multiple versions of each row, each tagged with a transaction timestamp. Readers see a consistent snapshot of the database as of the time their transaction started, without acquiring locks and without being blocked by concurrent writers. Writers create new versions rather than overwriting in place.

MVCC solves a fundamental tension in database design: readers and writers should not block each other. Traditional lock-based concurrency control forces readers to wait for writers (and vice versa), creating contention that degrades throughput under concurrent workloads. MVCC eliminates this contention entirely for read operations—a read transaction never waits for a write lock, because it simply reads the version of the row that was current when the transaction began.

In a typical database engine, MVCC provides transaction isolation for concurrent operations on the search index and metadata store. Each write transaction is assigned a monotonically increasing timestamp, and all modifications are tagged with this timestamp. Read transactions receive a snapshot timestamp and see only versions committed before that timestamp. This enables lock-free reads while maintaining serializable isolation semantics through conflict detection at commit time.

Core Concepts

Version Chains

In an MVCC system, each logical row (or key) may have multiple physical versions. These versions are linked in a chain—either newest-to-oldest (N2O) or oldest-to-newest (O2N)—and each version carries metadata: the transaction ID that created it (begin_ts) and the transaction ID that deleted or superseded it (end_ts). A version is visible to a transaction with timestamp T if begin_ts ≤ T < end_ts.

Transaction Timestamps

MVCC requires a global ordering of transactions. This is typically achieved with a monotonically increasing counter (logical clock) or a hybrid logical clock (HLC) in distributed systems. When a transaction starts, it receives a read_ts (snapshot timestamp). When it commits, it receives a commit_ts that is strictly greater than any previously assigned timestamp. All versions created by the transaction are stamped with this commit_ts.

Visibility Rules

The visibility check is the core of MVCC. For a transaction with snapshot timestamp T, a version is visible if and only if:

• The version was created by a transaction that committed before T (i.e., begin_ts ≤ T).
• The version has not been deleted or superseded by a transaction that committed before T (i.e., end_ts > T or end_ts is unset).
• The creating transaction is not the reading transaction itself (unless it’s a self-read of uncommitted changes within the same transaction, which some systems support).

Garbage Collection (Version Cleanup)

Old versions that are no longer visible to any active transaction are dead weight—they consume storage and slow down version chain traversals. Garbage collection (GC) identifies the oldest active snapshot timestamp and reclaims all versions that are invisible to every current and future transaction. In PostgreSQL this is called VACUUM; in other systems it may be called purge or compaction.

How It Works

Append-Only vs. In-Place Update

MVCC implementations fall into two broad categories based on how they store versions:

• Append-only: New versions are appended to the same storage area as old versions. The version chain links them together. PostgreSQL uses this approach: each UPDATE creates a new tuple in the heap, and the old tuple is marked with a pointer to the new one. This simplifies writes (always append) but scatters versions across the heap, requiring VACUUM to reclaim space.
• In-place update with undo log: The latest version is stored in the main table, and previous versions are moved to a separate undo log (rollback segment). Oracle and MySQL/InnoDB use this approach. Reads of the current version are fast (no chain traversal), but reads of old snapshots must reconstruct the version from the undo log.

Version Storage in an LSM-Tree Engine

A database engine using an LSM-tree-based storage layer typically employs an append-only approach. Each key-value pair is written with its transaction timestamp as part of the key encoding: [user_key][timestamp] (with timestamps encoded in descending order so that the most recent version sorts first). A point read for a key at snapshot timestamp T seeks to [user_key][T] and reads the first entry found, which is the most recent version visible to the transaction.

Transaction Lifecycle

A typical MVCC transaction lifecycle in such a database engine:

1. Begin: The transaction obtains a snapshot timestamp from the global clock. All reads will use this timestamp for visibility checks.
2. Read: For each key read, the engine traverses the version chain (or seeks in the LSM tree) to find the version visible at the snapshot timestamp.
3. Write: Writes are buffered in a private write set (write-ahead buffer). No modifications are visible to other transactions until commit.
4. Validate: At commit time, the engine checks for write–write conflicts: has any key in the write set been modified by a transaction that committed after our snapshot timestamp? If so, abort.
5. Commit: Obtain a commit timestamp, write all buffered changes to the storage layer with this timestamp, and mark the transaction as committed in the transaction status table.

Serializable Snapshot Isolation (SSI)

Standard snapshot isolation permits a class of anomalies called write skew, where two transactions read overlapping data, each makes a write based on what it read, and the combined effect violates an integrity constraint. Serializable Snapshot Isolation (SSI), introduced by Cahill et al. (2008) and implemented in PostgreSQL 9.1+, detects dangerous patterns of read–write dependencies and aborts one of the conflicting transactions. SSI adds a modest overhead to track read sets but provides full serializability without the locking overhead of traditional two-phase locking.

Practical Applications

Concurrent Index and Metadata Operations

A database engine using MVCC allows search queries to execute against a consistent snapshot of the index while concurrent write operations (document inserts, updates, deletes) modify the index in the background. A search query that starts at time T1 sees a frozen view of the index and is unaffected by a bulk import that commits at T2. This is critical for search engines where query latency must be predictable regardless of write activity.

Point-in-Time Recovery

Because MVCC retains old versions, it naturally supports point-in-time queries: “what was the value of key X at time T?” This is useful for auditing, debugging, and regulatory compliance. Some systems (like CockroachDB) expose this as a SQL feature (AS OF SYSTEM TIME), allowing users to query historical snapshots directly.

Consistent Backups Without Downtime

Taking a consistent backup of a live database traditionally required either stopping writes or acquiring a global lock. With MVCC, a backup process simply opens a long-running read transaction at a specific snapshot timestamp and streams all data visible at that timestamp. Writes continue unimpeded during the backup. PostgreSQL’s pg_dump and MySQL’s mysqldump --single-transaction both rely on this property.

Distributed Transactions

MVCC extends naturally to distributed databases. Google Spanner uses TrueTime (GPS- synchronized clocks) to assign globally meaningful timestamps, enabling snapshot reads across datacenters without coordination. CockroachDB uses a hybrid logical clock (HLC) to achieve similar semantics. The version visibility rules remain the same; only the timestamp source changes.

Implementation Patterns

Timestamp Ordering in LSM Trees

In LSM-tree-based storage engines, MVCC versions are naturally ordered by encoding the timestamp as a suffix of the key. A descending timestamp encoding ensures that a seek to [key][snapshot_ts] lands on the most recent visible version. During compaction, the engine can drop versions that are older than the oldest active snapshot, performing garbage collection as a byproduct of the normal compaction process.

Transaction Status Table

Visibility checks require knowing whether a version’s creating transaction has committed. A transaction status table (or commit log) maps transaction IDs to their status (active, committed, aborted) and commit timestamps. This table is accessed on every read, so it must be fast—typically an in-memory hash map or concurrent skip list, with periodic persistence to disk.

Write Intent Tracking

To detect write–write conflicts efficiently, the engine maintains a write intent table that records which keys have pending (uncommitted) writes and which transaction owns them. When a transaction attempts to write a key that already has a pending intent from another transaction, it can either wait for the other transaction to complete or immediately abort, depending on the conflict resolution policy.

Code Examples

MVCC Key-Value Store in Go

This example implements a simplified in-memory MVCC store with snapshot reads, versioned writes, and conflict detection, similar to the patterns used in production database engines.

package mvcc

import (
	"fmt"
	"sync"
	"sync/atomic"
)

// Version represents a single version of a key-value pair.
type Version struct {
	Value    []byte
	BeginTS  uint64 // transaction that created this version
	EndTS    uint64 // transaction that superseded this version (0 = current)
	Deleted  bool   // tombstone marker
}

// Store is a simplified MVCC key-value store.
type Store struct {
	mu       sync.RWMutex
	versions map[string][]*Version // key -> version chain (newest first)
	clock    uint64                // monotonic timestamp counter
	active   map[uint64]bool       // active transaction IDs
}

// NewStore creates an empty MVCC store.
func NewStore() *Store {
	return &Store{
		versions: make(map[string][]*Version),
		active:   make(map[uint64]bool),
	}
}

// Begin starts a new transaction and returns its snapshot timestamp.
func (s *Store) Begin() *Txn {
	ts := atomic.AddUint64(&s.clock, 1)
	s.mu.Lock()
	s.active[ts] = true
	s.mu.Unlock()

	return &Txn{
		store:    s,
		readTS:   ts,
		writeSet: make(map[string]writeEntry),
	}
}

type writeEntry struct {
	value   []byte
	deleted bool
}

// Txn represents an MVCC transaction.
type Txn struct {
	store    *Store
	readTS   uint64
	writeSet map[string]writeEntry
}

// Get reads the value of a key at the transaction's snapshot timestamp.
func (t *Txn) Get(key string) ([]byte, error) {
	// Check the local write set first.
	if entry, ok := t.writeSet[key]; ok {
		if entry.deleted {
			return nil, fmt.Errorf("key not found: %s", key)
		}
		return entry.value, nil
	}

	t.store.mu.RLock()
	defer t.store.mu.RUnlock()

	chain := t.store.versions[key]
	for _, v := range chain {
		// Version is visible if: created before our snapshot,
		// and not yet superseded (or superseded after our snapshot).
		if v.BeginTS <= t.readTS &&
			(v.EndTS == 0 || v.EndTS > t.readTS) {
			if v.Deleted {
				return nil, fmt.Errorf("key not found: %s", key)
			}
			return v.Value, nil
		}
	}

	return nil, fmt.Errorf("key not found: %s", key)
}

// Set stages a write in the transaction's write buffer.
func (t *Txn) Set(key string, value []byte) {
	t.writeSet[key] = writeEntry{value: value}
}

// Delete stages a deletion in the transaction's write buffer.
func (t *Txn) Delete(key string) {
	t.writeSet[key] = writeEntry{deleted: true}
}

// Commit validates and applies the transaction's writes.
func (t *Txn) Commit() error {
	commitTS := atomic.AddUint64(&t.store.clock, 1)

	t.store.mu.Lock()
	defer t.store.mu.Unlock()

	// Check for write-write conflicts.
	for key := range t.writeSet {
		chain := t.store.versions[key]
		if len(chain) > 0 {
			latest := chain[0]
			// Conflict: another txn wrote this key after our snapshot.
			if latest.BeginTS > t.readTS {
				delete(t.store.active, t.readTS)
				return fmt.Errorf("write conflict on key %s", key)
			}
		}
	}

	// Apply all writes.
	for key, entry := range t.writeSet {
		// Mark the previous version as superseded.
		chain := t.store.versions[key]
		if len(chain) > 0 && chain[0].EndTS == 0 {
			chain[0].EndTS = commitTS
		}

		// Prepend the new version.
		newVersion := &Version{
			Value:   entry.value,
			BeginTS: commitTS,
			Deleted: entry.deleted,
		}
		t.store.versions[key] = append(
			[]*Version{newVersion}, chain...,
		)
	}

	delete(t.store.active, t.readTS)
	return nil
}

Visibility Check in Python

This example demonstrates the core visibility logic for MVCC reads, showing how a transaction selects the correct version from a version chain.

from dataclasses import dataclass
from typing import Optional


@dataclass
class Version:
    """A single version of a key-value pair."""
    value: bytes
    begin_ts: int    # timestamp of creating transaction
    end_ts: int = 0  # timestamp of superseding transaction (0 = current)
    deleted: bool = False


def find_visible_version(
    chain: list[Version],
    snapshot_ts: int,
    committed_txns: set[int],
) -> Optional[Version]:
    """
    Find the version visible to a transaction with the given snapshot.

    A version is visible if:
    1. Its creating transaction committed before our snapshot.
    2. It has not been superseded by a transaction that committed
       before our snapshot.

    Args:
        chain: Version chain, newest first.
        snapshot_ts: The reader's snapshot timestamp.
        committed_txns: Set of committed transaction timestamps.
    """
    for version in chain:
        # Skip versions from uncommitted transactions.
        if version.begin_ts not in committed_txns:
            continue

        # Skip versions created after our snapshot.
        if version.begin_ts > snapshot_ts:
            continue

        # Skip versions already superseded before our snapshot.
        if (version.end_ts != 0
                and version.end_ts in committed_txns
                and version.end_ts <= snapshot_ts):
            continue

        # This is the visible version.
        if version.deleted:
            return None  # Key was deleted at this snapshot.
        return version

    return None  # Key did not exist at this snapshot.


# Example: simulating concurrent transactions.
chain = [
    Version(b"v3", begin_ts=30, end_ts=0),      # current
    Version(b"v2", begin_ts=20, end_ts=30),      # superseded by ts=30
    Version(b"v1", begin_ts=10, end_ts=20),      # superseded by ts=20
]
committed = {10, 20, 30}

# Transaction at snapshot 25 sees v2 (ts=20 committed, ts=30 not yet).
v = find_visible_version(chain, snapshot_ts=25, committed_txns=committed)
assert v is not None and v.value == b"v2"

# Transaction at snapshot 35 sees v3 (latest committed version).
v = find_visible_version(chain, snapshot_ts=35, committed_txns=committed)
assert v is not None and v.value == b"v3"

# Transaction at snapshot 5 sees nothing (no version existed yet).
v = find_visible_version(chain, snapshot_ts=5, committed_txns=committed)
assert v is None

Common Pitfalls

1. Long-running transactions causing version bloat. A transaction that stays open for hours prevents garbage collection of all versions created after its snapshot. In PostgreSQL, this manifests as table bloat requiring aggressive VACUUM. Set statement and idle-in-transaction timeouts to prevent runaway transactions.
2. Assuming snapshot isolation prevents all anomalies. Snapshot isolation prevents dirty reads, non-repeatable reads, and phantom reads, but it allows write skew. Two transactions can each read a value, make a write decision based on it, and together produce a result that no serial execution would allow. Use serializable isolation or explicit locking (SELECT FOR UPDATE) for critical invariants.
3. Ignoring the cost of version chain traversal. Hot keys with many concurrent writers can accumulate long version chains. Each read must traverse the chain to find the visible version, adding latency. This is especially problematic with append-only MVCC (PostgreSQL) where dead tuples remain in the heap until VACUUM runs.
4. Stale reads after failover in distributed systems. In a distributed MVCC system, if a replica lags behind the primary, it may serve a snapshot that is behind the most recently committed data. Applications that require “read your own writes” consistency must route reads to the primary or use causal consistency protocols.
5. Underestimating garbage collection overhead. VACUUM in PostgreSQL, purge in InnoDB, and compaction in LSM-tree engines all perform MVCC garbage collection. Under heavy write workloads, GC can consume significant CPU and I/O. Tune GC frequency and concurrency based on the write rate and the acceptable level of storage overhead.

Key Takeaways