Multi-Version Concurrency Control: Non-Blocking Reads and Snapshot Isolation

Traditional concurrency control relies on Two-Phase Locking (2PL), where shared read locks block exclusive write locks and exclusive write locks block shared read locks. In read-heavy database workloads, pessimistic lock contention degrades throughput and causes frequent query stalling.

Introduced by David P. Reed in 1978 and formalized throughout relational database research in the 1980s and 1990s, **Multi-Version Concurrency Control (MVCC)** guarantees that **readers never block writers, and writers never block readers**. Instead of mutating rows in place or locking shared data, an MVCC engine maintains multiple historical versions of each tuple simultaneously, presenting each transaction with a consistent point-in-time snapshot of the database.

Tuple Versioning Architectures: In-Place vs. Undo-Log Chains

Database engines implement multi-version tuple storage using two primary architectural paradigms:

1. Append-Only / In-Table Versioning (PostgreSQL Style)

Every update writes an entirely new physical row (tuple) directly into the table heap pages. Each row header includes transaction metadata:

xmin: The transaction ID (XID) of the transaction that created/inserted this version of the row.
xmax: The transaction ID of the transaction that deleted or replaced this row version (set to 0 if currently live).
t_ctid: A physical pointer chaining obsolete row versions to newer successor versions in the table heap.

2. Rollback Segment / Undo-Log Versioning (MySQL InnoDB & Oracle Style)

Updates modify the primary table row in place within clustered index pages. The overwritten historical values are written sequentially to a dedicated **Undo Log** (rollback segment). Reconstructing an older snapshot version requires traversing the undo chain backward from the current row.

Snapshot Isolation and Read Visibility Rules

When a transaction begins under Snapshot Isolation (or Repeatable Read), it captures a **Read View / Snapshot** containing active transaction state:

snapshot_xmin: The lowest active transaction ID at the moment the snapshot was taken. All transactions with XID < snapshot_xmin are committed and visible.
snapshot_xmax: The highest transaction ID assigned so far + 1. All transactions with XID >= snapshot_xmax began after this snapshot was taken and are invisible.
active_xids: The explicit list of transaction IDs that were currently running (uncommitted) when the snapshot was generated.

Visibility Decision Matrix

For a tuple version created by transaction $X_{create}$ and deleted by $X_{delete}$ to be visible to transaction $T$:

$X_{create}$ must be committed and $X_{create} \notin \text{active\_xids}$.
$X_{create} < \text{snapshot\_xmax}$.
The tuple has not been deleted, OR $X_{delete}$ is uncommitted, OR $X_{delete} > \text{snapshot\_xmax}$, OR $X_{delete} \in \text{active\_xids}$ at snapshot creation time.

Dead Tuple Garbage Collection and Vacuuming

Because updates and deletes create new versions rather than immediately deleting old records, historical rows accumulate over time ('dead tuples' or table bloat):

PostgreSQL VACUUM: A background worker scans heap pages, identifying dead tuples whose `xmax` is older than the oldest running transaction's `xmin`. It reclaims that storage for future row inserts without locking the table.
InnoDB Purge Threads: Scans undo logs and truncates undo segments once no active transaction holds a snapshot old enough to require historical reconstruction.
Transaction ID Wraparound: 32-bit transaction IDs wrap around after 4 billion transactions. PostgreSQL mitigates this by 'freezing' old tuples with a special bit (`HEAP_XMIN_FROZEN`) to signify they are older than all past and future transactions.

Concurrency Anomalies: Write Skew and Serializable Snapshot Isolation (SSI)

While MVCC with Snapshot Isolation prevents Dirty Reads, Non-Repeatable Reads, and Phantom Reads, it remains vulnerable to **Write Skew** anomalies.

Example: Two on-call doctors query whether at least two doctors are on duty (both read count = 2). Both concurrently submit a request to take leave. Under Snapshot Isolation, both transactions commit successfully because their write sets (updating Doctor A and Doctor B) do not overlap, leaving zero doctors on duty and violating the business invariant.

To eliminate Write Skew without reverting to 2PL, modern relational databases implement **Serializable Snapshot Isolation (SSI)**, which tracks read-write dependency edges (rw-antidependencies) in memory to detect and abort cycles during commit.

C++ Conceptual Simulation Blueprint (MVCC Visibility Engine)

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

struct TupleVersion {
    uint64_t xmin; // Creating transaction ID
    uint64_t xmax; // Deleting transaction ID (0 = alive)
    std::string value;
};

struct Snapshot {
    uint64_t xmin; // Lower bound: all txns below this are committed
    uint64_t xmax; // Upper bound: all txns at/above this are invisible
    std::unordered_set<uint64_t> activeXids;

    bool isVisible(const TupleVersion& tuple) const {
        // 1. Check if creator is visible
        if (tuple.xmin >= xmax) return false;
        if (activeXids.count(tuple.xmin)) return false;

        // 2. Check if deleter is visible
        if (tuple.xmax == 0) return true;
        if (tuple.xmax >= xmax) return true;
        if (activeXids.count(tuple.xmax)) return true;

        // Deleted by a committed transaction prior to this snapshot
        return false;
    }
};

class MVCCStore {
private:
    uint64_t nextTxnId = 1;
    std::vector<TupleVersion> records;

public:
    uint64_t beginTxn() {
        return nextTxnId++;
    }

    void insert(uint64_t txnId, const std::string& val) {
        records.push_back({txnId, 0, val});
    }

    Snapshot createSnapshot(const std::unordered_set<uint64_t>& runningTxns) {
        uint64_t minActive = nextTxnId;
        for (uint64_t id : runningTxns) {
            if (id < minActive) minActive = id;
        }
        return {minActive, nextTxnId, runningTxns};
    }

    std::vector<std::string> readVisible(const Snapshot& snap) const {
        std::vector<std::string> results;
        for (const auto& tuple : records) {
            if (snap.isVisible(tuple)) {
                results.push_back(tuple.value);
            }
        }
        return results;
    }
};

Real-World Systems and Engineering Implementations

PostgreSQL: Heap-based MVCC with explicit `xmin`/`xmax` system columns, HOT (Heap-Only Tuples) optimization, autovacuum daemons, and full SSI support.
MySQL InnoDB: Clustered index in-place mutation backed by rollback segments in the undo tablespace and purge worker threads.
CockroachDB & TiKV: Distributed MVCC layering timestamps into key suffixes (`key@timestamp`) on top of underlying RocksDB/Pebble LSM engines to provide multi-region snapshot reads.
Oracle Database: Flashback Query enabling developers to query historical table states at specific System Change Numbers (SCNs) by traversing undo logs.