Multi-Version Concurrency Control

At the end of the previous lesson a constraint was left standing: a checkpoint cannot overwrite pages currently visible to an in-progress read. A similar observation had been made in the Advanced SQL course — a read inside a transaction was unaffected by changes committed outside it. Both observations point to the same mechanism, and that mechanism has not been built yet.

The question is this: if a row is being updated while a transaction is reading that same row, what does the read see? There are two consistent answers. Either the reader makes the writer wait, or the row’s old state is kept somewhere. This lesson takes up the second path and measures its difference from the first.

Two Approaches

Lock-based control provides consistency by waiting. A transaction reading a row holds a shared lock on that row; a transaction wanting to change it requests an exclusive lock and waits until the read finishes. The result is correct, but the read and the write serialize each other.

Multi-version concurrency control provides consistency by keeping. When a row is updated, its old state is not deleted; a new version is added, and each version carries which transaction created it and which transaction invalidated it. A reading transaction picks the version that matches its own starting point. The writer does not wait, the reader does not wait; the two sides look at different versions.

This is what the snapshot concept introduced in the Advanced SQL course corresponds to. A snapshot is not a copied database; it is a criterion that determines which versions are seen.

The Measured Difference

The difference can be observed. The run below executes the same scenario under two log modes: a reader transaction opens and reads, then a writer on a separate connection tries to update the same table.

rm -f e.db e.db-wal e.db-shm e.db-journal
cat > blocking.mjs <<'JS'
import { DatabaseSync } from 'node:sqlite';
import { rmSync } from 'node:fs';

function attempt(mode) {
  for (const suffix of ['', '-wal', '-shm', '-journal']) rmSync('e.db' + suffix, { force: true });
  const setup = new DatabaseSync('e.db');
  setup.exec(`PRAGMA journal_mode = ${mode}`);
  setup.exec('CREATE TABLE loan(loan_id INTEGER PRIMARY KEY, member_id INT, return_date TEXT)');
  setup.exec("INSERT INTO loan VALUES (1,4,NULL),(2,4,NULL),(3,7,'2024-03-09')");
  setup.close();

  const reader = new DatabaseSync('e.db');
  const writer = new DatabaseSync('e.db');
  const open = (conn) => conn.prepare('SELECT count(*) AS c FROM loan WHERE return_date IS NULL').get().c;

  reader.exec('BEGIN');                        // the reader's transaction stays open
  const before = open(reader);
  let writeResult;
  try { writer.exec("UPDATE loan SET return_date = '2024-03-20' WHERE loan_id = 1"); writeResult = 'succeeded'; }
  catch (err) { writeResult = 'blocked: ' + err.message.split('\n')[0]; }
  const after = open(reader);
  reader.exec('COMMIT');
  const afterCommit = open(reader);
  reader.close(); writer.close();
  console.log(`[${mode}] reader inside transaction: ${before} → ${after} | writer: ${writeResult} | after commit: ${afterCommit}`);
}
attempt('delete');
attempt('wal');
JS
node blocking.mjs

[delete] reader inside transaction: 2 → 2 | writer: blocked: database is locked | after commit: 2
[wal] reader inside transaction: 2 → 2 | writer: succeeded | after commit: 1

What the reader sees does not change across the transaction in either case: 2 → 2. Isolation held under both arrangements. What changed is how it was achieved.

Under the rollback journal, the writer never got anywhere: the database is locked. A write cannot happen before the read finishes. Under the write-ahead log, the writer finished its work and committed; the reader kept seeing the old value regardless, and only saw the new value (1) once its own transaction ended. Neither side waited.

This observation confirms multi-versioning’s observed property: the reader and the writer do not block each other. How that property is actually delivered varies by engine; in the tool used here, the path is not per-row version chains but snapshots defined through the log. The mechanism itself will be built through a model in the next section.

The Version Chain and the Visibility Rule

In an engine that keeps versions per row, each version carries two extra fields: the number of the transaction that created it and the number of the transaction that deleted it. If the deleted field is empty, the version is still valid. An update does two things within a single transaction: it fills in the current version’s deleted field, and it appends a new version. A delete does only the first of these.

The visibility rule is one sentence: a version is visible in a snapshot if its creating transaction has committed and its deleting transaction has not committed. The model below runs the rule. Real engines’ rules are more elaborate — changes a transaction’s own uncommitted work has not seen yet, aborted transactions, and subtransactions are handled separately — but the core is the same.

cat > version.mjs <<'JS'
// Model: row versions and the visibility rule. Not the actual engine.
class Store {
  constructor() { this.versions = []; this.committed = new Set(); this.nextTxn = 10; }
  beginTxn() { const t = this.nextTxn; this.nextTxn += 10; return t; }
  commit(t) { this.committed.add(t); }
  snapshot() { return new Set(this.committed); }              // the committed transactions at that moment
  insert(t, rowId, value) { this.versions.push({ rowId, value, created: t, deleted: null }); }
  update(t, rowId, value) {
    const old = this.versions.find((s) => s.rowId === rowId && s.deleted === null);
    if (old) old.deleted = t;
    this.versions.push({ rowId, value, created: t, deleted: null });
  }
  visible(s, snap) { return snap.has(s.created) && (s.deleted === null || !snap.has(s.deleted)); }
  read(rowId, snap) {
    const s = this.versions.find((v) => v.rowId === rowId && this.visible(v, snap));
    return s ? s.value : '(none)';
  }
  reclaimable(snapshots) {                                    // versions no snapshot can see
    return this.versions.filter((s) => snapshots.every((a) => !this.visible(s, a)));
  }
}

const d = new Store();
const t1 = d.beginTxn();                          // the transaction that creates the loan record
d.insert(t1, 501, 'return_date = NULL'); d.commit(t1);

const readerSnap = d.snapshot();                  // the long read starts here
const t2 = d.beginTxn();
d.update(t2, 501, "return_date = '2024-03-20'"); d.commit(t2);
const newSnap = d.snapshot();
const t3 = d.beginTxn();
d.update(t3, 501, "return_date = '2024-03-21'"); d.commit(t3);
const newestSnap = d.snapshot();

console.log('version chain (row 501):');
for (const s of d.versions)
  console.log(`  created=${s.created}  deleted=${s.deleted ?? '—'}  ${s.value}`);
console.log('reader\'s snapshot       →', d.read(501, readerSnap));
console.log('second snapshot         →', d.read(501, newSnap));
console.log('newest snapshot         →', d.read(501, newestSnap));
console.log('reclaimable versions while the reader is open :',
            d.reclaimable([readerSnap, newestSnap]).length);
console.log('after the reader closes                        :',
            d.reclaimable([newestSnap]).length);
JS
node version.mjs

version chain (row 501):
  created=10  deleted=20  return_date = NULL
  created=20  deleted=30  return_date = '2024-03-20'
  created=30  deleted=—  return_date = '2024-03-21'
reader's snapshot       → return_date = NULL
second snapshot         → return_date = '2024-03-20'
newest snapshot         → return_date = '2024-03-21'
reclaimable versions while the reader is open : 1
after the reader closes                        : 2

Three versions of the same loan record sit in the store at the same time, and three separate snapshots each see a different one of them. No waiting anywhere; every reader finds the version that matches its own criterion.

One consequence of this arrangement is that an UPDATE statement is not physically an update. Even an update that changes a single byte of a single column writes a full new copy of the row. This is also behind the index cost the Advanced SQL course stated as “the same cost applies to an UPDATE that touches a key column”: the new version sits in a new place, and the index entries pointing to that row have to be updated too.

When Versions Can Go Away

The last two lines of the model show the actual administrative problem. Old versions cannot be kept forever; a version no longer seen by any snapshot can be removed. The criterion follows directly: a version older than the oldest open snapshot is reclaimable.

In the model, while the reader’s snapshot is open, only one version is reclaimable; once the reader closes, the count rises to two. A single long read is enough to keep two out of a three-version chain pinned in place.

The scale of this result matters. A transaction left open for hours keeps the old versions of every update made during that time alive. The table’s row count may not change, yet the space it occupies on disk keeps growing. The previous lesson’s observation that a checkpoint can be delayed by readers is another face of this same rule.

The Conflict Multi-Versioning Does Not Remove

The reader and the writer not blocking each other does not mean every conflict is gone. The run below shows two points together: two writers conflicting, and an open read stalling a checkpoint.

rm -f conflict.db conflict.db-wal conflict.db-shm
cat > blocking2.mjs <<'JS'
import { DatabaseSync } from 'node:sqlite';
import { rmSync } from 'node:fs';
for (const suffix of ['', '-wal', '-shm']) rmSync('conflict.db' + suffix, { force: true });
const setup = new DatabaseSync('conflict.db');
setup.exec('PRAGMA journal_mode = WAL');
setup.exec('CREATE TABLE loan(loan_id INTEGER PRIMARY KEY, member_id INT, return_date TEXT)');
setup.exec(`INSERT INTO loan SELECT n, 1+(n*13)%500, NULL
          FROM (WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n<20000) SELECT n FROM s)`);
setup.exec('PRAGMA wal_checkpoint(TRUNCATE)');
setup.close();

const writerA = new DatabaseSync('conflict.db'), writerB = new DatabaseSync('conflict.db');
writerA.exec('BEGIN IMMEDIATE');
writerA.exec("UPDATE loan SET return_date = '2024-04-01' WHERE loan_id = 1");
try { writerB.exec('BEGIN IMMEDIATE'); writerB.exec("UPDATE loan SET return_date = '2024-04-02' WHERE loan_id = 2"); console.log('two writers: both proceeded'); }
catch (err) { console.log('two writers → second writer:', err.message.split('\n')[0]); }
writerA.exec('COMMIT');
writerA.close(); writerB.close();

// does a long read delay the checkpoint
const reader = new DatabaseSync('conflict.db'), writer = new DatabaseSync('conflict.db');
writer.exec('PRAGMA wal_autocheckpoint = 0');
reader.exec('BEGIN');
reader.prepare('SELECT count(*) AS c FROM loan').get();
for (let i = 1; i <= 3000; i++) writer.exec(`UPDATE loan SET return_date='2024-05-01' WHERE loan_id=${1+(i*37)%20000}`);
console.log('checkpoint while the reader is open :', JSON.stringify(writer.prepare('PRAGMA wal_checkpoint(PASSIVE)').get()));
reader.exec('COMMIT');
console.log('checkpoint once the reader is done  :', JSON.stringify(writer.prepare('PRAGMA wal_checkpoint(PASSIVE)').get()));
reader.close(); writer.close();
JS
node blocking2.mjs

two writers → second writer: database is locked
checkpoint while the reader is open : {"busy":0,"log":3532,"checkpointed":0}
checkpoint once the reader is done  : {"busy":0,"log":3532,"checkpointed":3532}

The first line shows the boundary: when two transactions try to write at the same time, the second one cannot proceed. In the tool used here, this limit applies to the whole database; in engines that resolve conflicts at row granularity, the limit applies only between transactions updating the same row. Either way, the principle is the same: versions free up reading, but two writes changing the same data still queue up. This is why the Advanced SQL course’s deadlock discussion still holds.

The second and third lines close the point the previous lesson left open. While the reader’s transaction was open, 3,532 frames had accumulated in the log, and the checkpoint was able to process zero of them. Once the reader finished its transaction, the same call processed all 3,532 frames. The reason is singular: those frames carry the versions the reader can see, and they cannot be overwritten before the reader is done.

Summary

• Lock-based control provides consistency by waiting; multi-version control provides it by keeping the row’s old state.
• In the measurement, the writer was blocked under the rollback journal; under the write-ahead log, the same writer completed and the reader kept seeing the old value throughout its transaction.
• Each version carries the transactions that created and deleted it; a version is visible in a snapshot if its creator has committed and its deleter has not.
• A version can be removed only once no open snapshot sees it; a single long read kept two of the model’s three versions pinned in place.
• Multi-versioning separates reading from writing, not two writes that change the same data; an open read also stalls a checkpoint (zero of 3,532 frames could be processed).

Next Step

Old versions becoming reclaimable does not mean they are reclaimed on their own. A separate process does the reclaiming, and if that process cannot keep up, a table keeps growing even when its row count never rises: every update leaves a new version behind, and the old one stays in place. The next lesson takes up this buildup: measuring dead rows, reclaiming space, why reclaimed space does not always return to the operating system, and the balance between the cleanup process and the bloat ratio.