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


*Part of the* [*Nothing is magic*](https://blog.jatin510.dev) *series, where we build database internals from scratch until they stop being magic.*

* * *

Open two `psql` sessions.

**Session A:**

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

**Session B:**

```sql
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**:

```plaintext
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:
    

```typescript
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:
    

```typescript
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:

```typescript
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**:

```typescript
// 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:

```typescript
// 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:

```typescript
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:

```typescript
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:

```sql
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?

```sql
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.](https://drkp.net/papers/ssi-vldb12.pdf)) 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*](https://blog.jatin510.dev) *— where these versions would actually get persisted.*