MVCC Explained: Build Postgres-Style Snapshots in 100 Lines of TypeScript

Part of the Nothing is magic series, where we build database internals from scratch until they stop being magic.

---

Open two psql sessions.

Session A:

BEGIN;
DELETE FROM users;  -- deletes all 1 million rows
-- don't commit yet

Session B:

SELECT count(*) FROM users;
-- count: 1000000

Session A deleted every row. Session B sees every row. Neither session is waiting on the other. No locks, no blocking, no errors.

So... where are the rows? Deleted, or not?

The answer is both, and by the end of this post you'll have built the machinery that makes that answer make sense — in about 100 lines of TypeScript. This machinery is called MVCC (Multi-Version Concurrency Control), and it's how Postgres, MySQL/InnoDB, Oracle, and SQLite (in WAL mode) all let readers and writers ignore each other.

As always in this series: no hand-waving. We'll build it one problem at a time, and at each step we'll only add the minimum code needed to fix the problem in front of us. Then we'll point our toy at real Postgres and show that the columns match, one to one.

---

The wrong mental model

Most of us carry around a mental model of a database table as a big mutable array. UPDATE overwrites a slot. DELETE removes one.

If that were true, the demo above would be impossible. The moment Session A deletes a row in place, that row is gone — Session B has nothing left to read. The only way to make in-place mutation safe is locks: readers wait for writers, writers wait for readers. Databases worked this way for years, and it was miserable — one long-running report could freeze every write to the table.

So here is the founding decision of MVCC, the thesis of this whole post:

Nothing is ever updated. Nothing is ever deleted. The database only ever appends.

Every "problem" we hit from here on is a consequence of this decision, and every piece of MVCC is the minimal fix for one of those problems. Let's start hitting them.

---

Problem 1: If we never delete, what does DELETE even mean?

If data is append-only, an UPDATE can't overwrite and a DELETE can't remove. So a "row" can't be one thing. It has to be a chain of versions:

logical row "alice":
 
  ┌─────────────────────┐    ┌─────────────────────┐
  │ v1: balance = 100   │ →  │ v2: balance = 50    │
  │ (old version)       │    │ (current version)   │
  └─────────────────────┘    └─────────────────────┘

• INSERT appends the first version.

• UPDATE appends a new version. The old one stays.

• DELETE appends... nothing. It just marks the latest version as dead. That solves writing. But it immediately creates the next problem: if both v1 and v2 physically exist, which one do you see when you read?

We need every version to answer two questions:

1. Who created me?

2. Who killed me? So we stamp every version with two transaction IDs. Postgres calls them xmin and xmax, and so will we:

type Txid = number;
 
interface Version {
  xmin: Txid;         // birth certificate: which transaction created this version
  xmax: Txid | null;  // death certificate: which transaction deleted it.
                      // null = no one has (yet). Note: a *stamp*, not a removal —
                      // dead versions stay physically present.
  value: unknown;
}
 
interface Row {
  // A "row" is not a value — it's the full history of values,
  // oldest first. Nothing in this array is ever removed or overwritten.
  versions: Version[];
}

Now the three write operations are almost embarrassingly simple:

• INSERT → push { xmin: me, xmax: null, value }

• DELETE → set xmax = me on the live version

• UPDATE → DELETE + INSERT. That's it. An update is literally a delete and an insert stapled together. (Run SELECT ctid FROM t before and after an UPDATE in Postgres and watch the row's physical address change — same trick.) Transactions themselves are just an incrementing counter:

class Database {
  // A "transaction" is nothing more than a number from this counter.
  // Because it only ever increases, txids double as timestamps:
  // smaller txid = started earlier. We'll lean on that ordering constantly.
  private nextTxid: Txid = 1;
  private rows = new Map<string, Row>();
 
  begin(): Txid {
    return this.nextTxid++;
  }
}

Have we solved MVCC? Let's check against the demo. Session A (txid 2) deletes everything: it sets xmax = 2 on every version. Session B (txid 3) reads: it sees versions with xmax = 2 set and... does what, exactly?

We stamped the versions, but we never said what the stamps mean for a reader. Next problem.

---

Problem 2: Reading uncommitted data (the dirty read)

Naive rule: "a version is visible if xmax is null."

Watch it fail. Session A has deleted everything but hasn't committed. Under the naive rule, Session B sees an empty table. Then Session A runs ROLLBACK — the delete never happened — and Session B has read a state of the world that never existed. This anomaly has a name: the dirty read.

The fix: a stamp only counts if the transaction that made it committed. Which means we need to track, for every txid, whether it committed, aborted, or is still running. Postgres keeps this in a structure called the commit log — pg_xact, historically clog. Ours is a Map:

type TxStatus = "in_progress" | "committed" | "aborted";
 
// The commit log: the single source of truth for "did txid N really happen?"
// Postgres calls this pg_xact (historically: clog).
type Clog = Map<Txid, TxStatus>;
 
class Database {
  private clog: Clog = new Map();
 
  begin(): Txid {
    const txid = this.nextTxid++;
    this.clog.set(txid, "in_progress");
    return txid;
  }
 
  // Commit touches ZERO rows. One map write flips the meaning of every
  // xmin/xmax stamp this transaction ever made, all at once, retroactively.
  commit(txid: Txid) { this.clog.set(txid, "committed"); }
 
  // Rollback is the same trick: nothing gets undone, because nothing
  // was done in place. The stamps stay — they just stop counting.
  abort(txid: Txid)  { this.clog.set(txid, "aborted"); }
}

Notice what commit is: one map write. It doesn't touch a single row. Session A deleted a million rows, and committing that is O(1) — we just flip 2 → "committed" and instantly, retroactively, all million xmax = 2 stamps start counting. Abort is the same trick in reverse: flip one entry and a million stamps become void. This is why ROLLBACK in Postgres is cheap even after a huge write — nothing gets undone, because nothing was done in place.

Improved rule: a version is visible if its xmin committed, and its xmax is null or belongs to a transaction that didn't commit.

Have we solved MVCC? Better — no more dirty reads. But run the demo again with a twist: Session B reads the count (1,000,000), then Session A commits, then Session B — still inside the same transaction — reads again and gets 0. B's world changed under its feet mid-transaction. That's the non-repeatable read, and it's the next problem.

---

Problem 3: The world moves while I'm reading it

What Session B actually wants is: "show me the database as it was at the moment I started, and keep showing me that, no matter what anyone else does."

It wants a snapshot.

Here's the moment the magic dissolves, so read this sentence twice: a snapshot is not a copy of the data. Copying a million rows per transaction would be insane. A snapshot is two numbers and a set:

// A frozen view of the world. NOT a copy of any data —
// just the two facts needed to judge any stamp, forever:
interface Snapshot {
  nextTxid: Txid;         // where the counter stood at my begin().
                          // Anything >= this is from my future: invisible.
  activeTxids: Set<Txid>; // who was still running at my begin().
                          // Their fate was undecided in my world — so even if
                          // they commit later, for me they never happened.
}
 
begin(): Txid {
  const txid = this.nextTxid++;
 
  // Photograph the in-flight transactions at this exact instant.
  // This set never changes for the life of the transaction —
  // that immutability IS the "repeatable" in repeatable reads.
  const activeTxids = new Set(
    [...this.clog].filter(([, s]) => s === "in_progress").map(([id]) => id)
  );
 
  this.snapshots.set(txid, { nextTxid: this.nextTxid, activeTxids });
  this.clog.set(txid, "in_progress");
  return txid;
}

That's the entire cost of "freeze the world": record where the txid counter was, and who was in flight. The data doesn't get frozen — the rules for judging stamps do.

The first rule the snapshot gives us: xmin < snap.nextTxid. If a version was created by a transaction that started after mine, it doesn't exist in my universe — even if it has already committed. My world ends at the counter value I saw at begin().

Have we solved MVCC? Almost — and the last gap is the subtle one that separates people who've read about MVCC from people who've built it.

---

Problem 4: The transaction from the past that commits in the future

Suppose transaction 5 is running when I (transaction 8) begin. Transaction 5 has a txid lower than my snapshot's nextTxid, so the rule from Problem 3 — xmin < 9 — says its writes are in my past.

But at the moment I took my snapshot, transaction 5 hadn't committed yet. If it commits while I'm running, the commit-status check from Problem 2 starts passing, the counter check from Problem 3 already passes, and transaction 5's writes leak into my snapshot mid-flight. The non-repeatable read is back, through the side door.

This is exactly what activeTxids is for. Third rule: a stamp from any transaction that was in flight when I began doesn't count for me — no matter what it does later. It can commit five milliseconds after my begin(); as far as I'm concerned, it never happened.

And with that, we have all three conditions for a stamp to "count," and no more problems left to solve. Time to assemble.

---

The visibility function: 20 lines that are the whole point

Every question in MVCC reduces to one question: given a version and a snapshot, can this transaction see it? Every rule we derived above becomes one condition:

// The one question all of MVCC reduces to:
// "Given this version and my snapshot, does it exist — for me?"
// Every line below is load-bearing: delete it, and a named anomaly returns.
function isVisible(v: Version, snap: Snapshot, clog: Clog, myTxid: Txid): boolean {
 
  // ── Part 1: was this version BORN, from my point of view? ──
  const xminVisible =
    // My own writes are always visible to me. Remove this and your own
    // INSERT vanishes from your own SELECT. (Not isolation — amnesia.)
    v.xmin === myTxid ||
 
    // A stranger's write counts only if ALL THREE hold:
    (clog.get(v.xmin) === "committed" &&   // it really happened
                                           //   (remove → DIRTY READS: you see
                                           //    data that later rolls back)
      v.xmin < snap.nextTxid &&            // it happened in my past
                                           //   (remove → transactions from your
                                           //    FUTURE appear in your present)
      !snap.activeTxids.has(v.xmin));      // its author wasn't mid-flight at my begin()
                                           //   (remove → a "past" txid commits late
                                           //    and leaks in: NON-REPEATABLE READS)
 
  if (!xminVisible) return false;   // never born (for me) → nothing to see
 
  // ── Part 2: has this version DIED, from my point of view? ──
 
  // No death certificate at all: alive for everyone.
  if (v.xmax === null) return true;
 
  // I stamped it myself → dead to me, instantly. (My DELETE must take
  // effect for ME before I commit — but for no one else. Same stamp,
  // different verdict per observer.)
  if (v.xmax === myTxid) return false;
 
  // A stranger's delete is judged by the SAME three conditions as a birth:
  // really happened, in my past, author not in flight at my begin().
  // Symmetry is the punchline: death plays by birth's rules.
  const xmaxApplies =
    clog.get(v.xmax) === "committed" &&
    v.xmax < snap.nextTxid &&
    !snap.activeTxids.has(v.xmax);
 
  // A delete that (for me) never happened leaves the version alive (for me).
  return !xmaxApplies;
}

Read the comments and notice that this function is our whole journey, compressed: the three conditions on xmin are exactly the fixes for Problems 2, 3, and 4 — really happened, in my past, author not in flight. And the punchline is the symmetry: the xmax half is the same three conditions, judging death instead of birth. A delete from an uncommitted transaction, a delete from your future, a delete from a transaction that was mid-flight when you began — none of them happened, for you.

A version is visible when its birth is inside your snapshot and its death is not.

That sentence is MVCC. Everything else is bookkeeping.

Break it yourself: the best way to convince yourself every condition is load-bearing is to delete one and watch its anomaly reappear. The full repo (linked at the end) has a test per condition — comment out a line, run the tests, and see exactly which guarantee falls over.

---

The operations become trivial

Here's the payoff for doing the hard thinking in one function — every operation is now a one-liner over version chains:

class Database {
  // ... nextTxid, rows, clog, snapshots from above ...
 
  // Reading = filtering history through a pure function.
  // No locks taken, no waiting, no coordination with writers —
  // which is exactly WHY readers never block anyone.
  read(txid: Txid, key: string): unknown | undefined {
    const snap = this.snapshots.get(txid)!;
    const row = this.rows.get(key);
    return row?.versions.find(v => isVisible(v, snap, this.clog, txid))?.value;
  }
 
  // INSERT = append a version stamped with my birth certificate.
  // Invisible to everyone else until my txid flips to "committed" in the clog.
  insert(txid: Txid, key: string, value: unknown) {
    const row = this.rows.get(key) ?? { versions: [] };
    row.versions.push({ xmin: txid, xmax: null, value });
    this.rows.set(key, row);
  }
 
  // DELETE = find the version *I* can see, stamp its death certificate.
  // One integer write. The data itself is untouched — still fully
  // readable by every snapshot that predates me.
  delete(txid: Txid, key: string) {
    const snap = this.snapshots.get(txid)!;
    const v = this.rows.get(key)?.versions
      .find(v => isVisible(v, snap, this.clog, txid));
    if (v) v.xmax = txid;
  }
 
  // UPDATE doesn't exist. It has never existed. It is a DELETE and an
  // INSERT wearing a trench coat — in our toy AND in Postgres
  // (that's why ctid changes on every UPDATE).
  update(txid: Txid, key: string, value: unknown) {
    this.delete(txid, key);
    this.insert(txid, key, value);
  }
}

read doesn't scan a lock table, doesn't wait, doesn't coordinate with anyone. It filters version chains through a pure function. That's why readers never block writers: reading is just math over stamps.

---

Replay the impossible demo — on our database

Back to the opening mystery, now against our 100 lines:

const db = new Database();
 
const setup = db.begin();                 // txid 1
db.insert(setup, "alice", { balance: 100 });
db.commit(setup);
 
const sessionA = db.begin();              // txid 2
const sessionB = db.begin();              // txid 3 — snapshot: { nextTxid: 4,
                                          //   activeTxids: {2} }  ← remember this set
 
db.delete(sessionA, "alice");             // alice's version is now:
                                          //   { xmin: 1, xmax: 2, balance: 100 }
                                          // ONE version. Watch it give two answers:
 
db.read(sessionB, "alice");  // → { balance: 100 }
                             //   B judges the death stamp: txid 2 is in B's
                             //   activeTxids → "that delete never happened" → alive
 
db.read(sessionA, "alice");  // → undefined
                             //   A judges the SAME stamp: xmax === myTxid
                             //   → my own delete → dead (to me alone)
 
db.commit(sessionA);         // one clog write: 2 → "committed"
 
db.read(sessionB, "alice");  // → { balance: 100 } — STILL alive for B!
                             //   B's snapshot froze at begin(); txid 2 stays in
                             //   activeTxids forever. A's commit changes the clog,
                             //   not B's snapshot. THIS is repeatable reads.

Look at the state after the delete: alice's version is { xmin: 1, xmax: 2, balance: 100 }. One physical version, two different answers:

• For A (txid 2): xmax === myTxid → rule 5 → dead.

• For B (txid 3): txid 2 was in B's activeTxids at begin → rule 6 fails → the delete never happened → alive. And it stays alive for B even after A commits, because B's snapshot doesn't change. The rows are deleted and not deleted — because "deleted" was never a property of the data. It's a property of the observer. The opening question wasn't a paradox; it was just the wrong question.

---

Don't take my word for it — ask Postgres

Our toy isn't "inspired by" Postgres. It's the same design, and Postgres will show you its stamps if you ask:

CREATE TABLE t (id int, val text);
INSERT INTO t VALUES (1, 'hello');
 
SELECT xmin, xmax, ctid, * FROM t;
--  xmin | xmax | ctid  | id | val
--   748 |    0 | (0,1) |  1 | hello
 
UPDATE t SET val = 'world';
 
SELECT xmin, xmax, ctid, * FROM t;
--  xmin | xmax | ctid  | id | val
--   749 |    0 | (0,2) |  1 | world

Every column maps to something we built:

Postgres	Our toy	Meaning
xmin	Version.xmin	txid that created the version
xmax	Version.xmax	txid that deleted it (0 = our null)
ctid	position in versions[]	physical location — note it changed on UPDATE: new version, new address
pg_xact	our clog Map	commit status per txid
pg_current_snapshot()	our Snapshot	literally prints xmin:xmax:xip_list — the two numbers and the set

Run SELECT pg_current_snapshot(); inside a transaction and you'll see something like 748:752:749,750 — "everything before 748 is my past, everything from 752 on is my future, and 749/750 were in flight when I began." Two numbers and a set. Nothing is magic.

Now the fun one. After the UPDATE above, where did version (0,1) — the 'hello' version — go?

VACUUM VERBOSE t;
-- INFO:  vacuuming "public.t"
-- INFO:  table "t": removed 1 dead item identifiers in 1 pages

It was still there. Dead, invisible to every current snapshot — but physically present until VACUUM reaped it.

---

What we deliberately punted

An honest accounting of the gap between our 100 lines and production Postgres:

• Write-write conflicts. Two transactions updating the same row: our toy lets the second one clobber the first's xmax. Postgres blocks the second writer until the first commits/aborts, then applies first-updater-wins. It's the one place MVCC does lock — writers against writers, never against readers.

• Command IDs (cmin/cmax). Postgres tracks visibility per statement within a transaction, not just per transaction, so a DELETE doesn't hide rows from itself mid-scan.

• SERIALIZABLE. Snapshot isolation — what we built — still permits an anomaly called write skew. Postgres's fix (SSI) is a genuinely great paper (Cahill et al.) and out of scope here.

• Hint bits and performance. Real Postgres doesn't consult the clog on every visibility check; it caches commit status in bits on the tuple itself. Same logic, heavy optimization.

• Garbage. The big one. Our founding decision — never update, never delete, only append — has a bill attached: dead versions pile up forever. Every UPDATE leaves a corpse. Postgres's answer is autovacuum, easily its most feared subsystem, and the source of half the Postgres war stories you've read. That bill, and how it gets paid, is the next post: MVCC's dirty secret — garbage.

---

The whole architecture, in one breath

Look back at what happened. We made one decision — append-only — and then fixed the problems it created, one at a time, adding only what each problem demanded:

1. Can't overwrite → version chains with xmin/xmax stamps

2. Stamps from uncommitted transactions → the clog

3. The world moving mid-read → snapshots (two numbers and a set)

4. In-flight transactions committing late → activeTxids

5. All four rules composed → the visibility function

6. Every operation → a trivial wrapper around it At no point did we design "MVCC." We just refused to update data in place and then dealt with the consequences honestly — and the entire architecture of Postgres's concurrency control fell out, in 100 lines.

Nothing is magic.

---

Previously in this series: Write-Ahead Log Explained: Build One in 30 Lines — where these versions would actually get persisted.