Multi-Version Concurrency Control

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 3: Locking and Two-Phase Locking Time to complete: ~20 minutes

The Idea
Row Versions and Visibility
Snapshots and Isolation Levels
Writers Still Conflict
The Cost — Bloat and Vacuum
Serializable Snapshot Isolation
Summary & Next Steps

1. The Idea

The Problem MVCC Solves
─────────────────────────────────────────
  Under pure locking (Chapter 3), a writer blocks
  every reader of that row.

  On a read-heavy workload — which is most
  workloads — this is the dominant source of
  contention.
─────────────────────────────────────────

The Solution
─────────────────────────────────────────
  Do not overwrite. Keep MULTIPLE VERSIONS of each
  row.

  A reader is shown the version that was current
  when its snapshot began. A writer creates a NEW
  version without destroying the old one.

  Therefore:

    READERS NEVER BLOCK WRITERS
    WRITERS NEVER BLOCK READERS

  This one property is why MVCC is used by
  PostgreSQL, InnoDB, Oracle and SQL Server's
  snapshot mode.
─────────────────────────────────────────

2. Row Versions and Visibility

PostgreSQL's Implementation
─────────────────────────────────────────
  Every row carries two hidden columns:

    xmin  the transaction id that CREATED it
    xmax  the transaction id that DELETED or
          superseded it (empty if still live)

  UPDATE = mark the old version's xmax, and INSERT
  a new version with a new xmin.

  DELETE = just set xmax. The row stays on disk.
─────────────────────────────────────────

-- The hidden columns are queryable.
SELECT xmin, xmax, id, balance FROM accounts WHERE id = 'A';
--  xmin  | xmax | id | balance
--  1042  |    0 | A  | 300

The Visibility Rule
─────────────────────────────────────────
  A version is visible to transaction T if:

    1. xmin committed BEFORE T's snapshot, AND
    2. xmin is not in T's list of concurrently-
       running transactions, AND
    3. xmax is empty, OR xmax had not committed
       when T's snapshot was taken

  In plain terms: "the row existed, and had not yet
  been deleted, at the instant my snapshot was
  taken."
─────────────────────────────────────────

def is_visible(row, snapshot):
    """A simplified visibility check — this runs for EVERY row a query touches."""
    if row.xmin > snapshot.xmax_boundary:      # created after our snapshot
        return False
    if row.xmin in snapshot.in_progress:       # creator was still running
        return False
    if row.xmax == 0:                          # never deleted
        return True
    if row.xmax > snapshot.xmax_boundary:      # deleted after our snapshot
        return True
    if row.xmax in snapshot.in_progress:       # deleter still running ──► still visible
        return True
    return False                               # deleted before our snapshot

3. Snapshots and Isolation Levels

The isolation levels from Chapter 2, re-explained as when the snapshot is taken.

The Whole Difference
─────────────────────────────────────────
  READ COMMITTED
    A NEW snapshot at the start of EVERY STATEMENT.
    So two statements in one transaction can see
    different data ──► non-repeatable reads and
    phantoms are permitted.

  REPEATABLE READ
    ONE snapshot, taken at the transaction's first
    read, held for the whole transaction.
    All rows are frozen as of that instant ──►
    no non-repeatable reads, and in PostgreSQL no
    phantoms either.

  That is the entire mechanism. The anomaly table
  in Chapter 2 falls straight out of it.
─────────────────────────────────────────

-- Watch it happen. Session 1:
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT balance FROM accounts WHERE id='A';        -- 300. Snapshot taken here.
 
-- Session 2 (concurrently):
UPDATE accounts SET balance = 999 WHERE id='A';
COMMIT;
 
-- Session 1, still in the same transaction:
SELECT balance FROM accounts WHERE id='A';        -- STILL 300
COMMIT;
SELECT balance FROM accounts WHERE id='A';        -- now 999

4. Writers Still Conflict

The Limit of MVCC
─────────────────────────────────────────
  Two transactions updating the SAME ROW still
  conflict. Versions cannot help — there must be
  one winner.

  The second writer WAITS for the first to commit
  or abort. Then, depending on the level:

    READ COMMITTED    re-reads the new version and
                      applies its update to it

    REPEATABLE READ   raises a SERIALIZATION
                      FAILURE, because the row it
                      based its decision on has
                      changed. The transaction must
                      RETRY.
─────────────────────────────────────────

The First-Updater-Wins Rule
─────────────────────────────────────────
  Under REPEATABLE READ, this is how the LOST
  UPDATE anomaly (Chapter 2) is prevented: rather
  than silently overwriting, the second transaction
  is aborted.

  Which is correct — and means your code must
  handle the abort. Same retry-loop requirement as
  SERIALIZABLE.
─────────────────────────────────────────

-- Read-modify-write done safely under MVCC:
 
-- Option A: let the database do the arithmetic. No read, no conflict window.
UPDATE accounts SET balance = balance - 100 WHERE id = 'A' AND balance >= 100;
-- Check the affected row count: 0 means insufficient funds.
 
-- Option B: lock the row explicitly, so the read participates in the conflict.
BEGIN;
    SELECT balance FROM accounts WHERE id='A' FOR UPDATE;   -- Chapter 3
    -- ... compute in application code ...
    UPDATE accounts SET balance = :new WHERE id='A';
COMMIT;

Option A is preferable whenever the logic can be expressed in SQL: there is no window between read and write at all.

5. The Cost — Bloat and Vacuum

Nothing Is Free
─────────────────────────────────────────
  Old row versions accumulate on disk. A table
  updated frequently grows even when its logical
  row count is constant.

  These DEAD TUPLES:
    - consume disk space
    - occupy buffer pool pages (Module 5, Chapter
      5), evicting live data
    - must be skipped during every scan, so scans
      get slower
─────────────────────────────────────────

Reclaiming Space
─────────────────────────────────────────
  POSTGRESQL   VACUUM removes versions no snapshot
               can still see. AUTOVACUUM does it in
               the background.

  INNODB       old versions live in the UNDO LOG,
               cleaned by a purge thread.

  ORACLE       undo tablespace, with a retention
               period.
─────────────────────────────────────────

-- Check for bloat (PostgreSQL).
SELECT relname, n_live_tup, n_dead_tup,
       ROUND(100.0 * n_dead_tup / NULLIF(n_live_tup + n_dead_tup, 0), 1) AS dead_pct,
       last_autovacuum
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY n_dead_tup DESC;

THE LONG TRANSACTION PROBLEM
─────────────────────────────────────────
  VACUUM cannot remove a version that ANY open
  snapshot might still need.

  So ONE transaction left open for hours prevents
  cleanup of every version created since it
  started — across the ENTIRE database.

  Symptoms: tables growing without bound, queries
  getting slower, disk filling. Cause: an idle
  connection in a transaction, usually an
  application that forgot to commit.

  This is the most important practical consequence
  of MVCC, and the strongest argument for
  Module 3, Chapter 6's "never leave a transaction
  open".
─────────────────────────────────────────

-- Find the culprit.
SELECT pid, state, age(clock_timestamp(), xact_start) AS txn_age, query
FROM pg_stat_activity
WHERE state IN ('idle in transaction', 'active') AND xact_start IS NOT NULL
ORDER BY xact_start;

6. Serializable Snapshot Isolation

The Gap SSI Closes
─────────────────────────────────────────
  Plain snapshot isolation permits WRITE SKEW
  (Chapter 2) — transactions reading rows that
  others then modify, while writing to different
  rows.

  SSI adds conflict TRACKING on top of snapshots:
  the database watches for the dangerous pattern of
  read-write dependencies that indicates a
  non-serialisable schedule, and ABORTS one
  transaction when it appears.
─────────────────────────────────────────

Why This Design Won
─────────────────────────────────────────
  It gives full serialisability while keeping
  MVCC's central benefit — readers still never
  block writers.

  The cost is moved to abort-and-retry under
  contention, rather than waiting.

  PostgreSQL's SERIALIZABLE is SSI. It is
  genuinely correct, unlike Oracle's similarly
  named level, and it is a realistic choice for
  correctness-critical workloads — provided the
  retry loop from Chapter 2 exists.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

MVCC keeps multiple row versions so readers see a consistent snapshot without locking, which is why readers never block writers and vice versa.
The isolation levels reduce to when the snapshot is taken: per statement for READ COMMITTED, once per transaction for REPEATABLE READ.
Writers to the same row still conflict, and under REPEATABLE READ the second is aborted rather than silently losing its update — so retries are required.
A single long-open transaction prevents vacuum from reclaiming any version created since it began, across the whole database; this is MVCC's most damaging practical failure mode.

Concept Check

Explain the difference between READ COMMITTED and REPEATABLE READ purely in terms of snapshots.
Why is UPDATE accounts SET balance = balance - 100 safer than reading, computing, and writing back?
Why does one idle-in-transaction connection cause unbounded table growth across unrelated tables?

Next Chapter

→ Chapter 5: Deadlocks and Practical Concurrency

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index