Introduction

Databases need isolation: when dozens of transactions run at the same time, each one should feel as if it were the only one running. The gold standard is serializability — the outcome must be the same as if the transactions had run one by one, in some order.

The naive way to achieve this is to take a global lock: only one transaction at a time. That is safe but kills performance. The clever shortcut most modern databases use is Snapshot Isolation (SI): when a transaction starts, it gets a private, consistent snapshot of the database as it was at that moment. Reads never block; writes don't conflict unless two transactions touch the same row.

Snapshot Isolation is fast and handles most anomalies. But there is a subtle class it misses: write skew. Two transactions each read overlapping data, make decisions based on what they see, and each writes to different rows — so SI sees no conflict. Yet the combined result is something that could not have happened if they had run sequentially.

Serializable Snapshot Isolation (SSI), published by Cahill, Rühl, and Fekete in 2008 and shipped in PostgreSQL 9.1 (2011), fixes that gap without adding heavy locking. It watches the pattern of read and write dependencies between concurrent transactions and, if a dangerous cycle forms, aborts one transaction before the anomaly can land.

Try It: The Write-Skew Trap

The classic write-skew scenario: a hospital rule says at least one doctor must always be on call. Alice and Bob are both on call. Each checks the roster simultaneously (they each see a snapshot where both are on call), decides the other will cover, and takes themselves off duty.

<!-- Hospital on-call roster — SSI write-skew demo -->
<p class="hint">A hospital rule: at least one doctor must be on call. Alice and Bob are both on call. Each transaction reads the roster, decides the other will cover, and removes itself. Under plain SI both commits succeed and nobody is on call. SSI detects the dangerous rw-anti-dependency cycle and aborts one.</p>
<div class="scenario">
  <div class="db-state" id="db-state">
    <div class="db-title">Database — on-call roster</div>
    <div class="db-rows" id="db-rows"></div>
  </div>
  <div class="txn-grid">
    <div class="txn-card" id="card-t1">
      <div class="txn-title">T1 &mdash; Alice</div>
      <div class="txn-log" id="log-t1"></div>
      <div class="txn-actions" id="actions-t1">
        <button type="button" id="btn-t1-read">1. Read roster</button>
        <button type="button" id="btn-t1-write" disabled>2. Alice goes off</button>
        <button type="button" id="btn-t1-commit" disabled>3. Commit</button>
      </div>
      <div class="txn-status" id="status-t1"></div>
    </div>
    <div class="txn-card" id="card-t2">
      <div class="txn-title">T2 &mdash; Bob</div>
      <div class="txn-log" id="log-t2"></div>
      <div class="txn-actions" id="actions-t2">
        <button type="button" id="btn-t2-read">1. Read roster</button>
        <button type="button" id="btn-t2-write" disabled>2. Bob goes off</button>
        <button type="button" id="btn-t2-commit" disabled>3. Commit</button>
      </div>
      <div class="txn-status" id="status-t2"></div>
    </div>
  </div>
</div>
<div class="global-status" id="global-status"></div>
<div class="btns">
  <button type="button" id="btn-reset" class="ghost">Reset</button>
</div>

/* SSI demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.scenario { display: flex; flex-direction: column; gap: .6rem; }
.db-state { border: 1.5px solid #b0bec5; border-radius: 8px; padding: .5rem .8rem; background: #f5f8fa; }
.db-title { font-weight: 700; font-size: .8rem; color: #546e7a; text-transform: uppercase; letter-spacing: .04em; margin-bottom: .4rem; }
.db-rows { display: flex; gap: .6rem; flex-wrap: wrap; }
.db-row { padding: .25rem .6rem; border-radius: 6px; background: #e3f2fd; border: 1px solid #90caf9; font-weight: 600; font-size: .85rem; }
.db-row.off { background: #fce4ec; border-color: #f48fb1; }
.txn-grid { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
.txn-card { border: 1.5px solid #cfd8dc; border-radius: 8px; padding: .5rem .7rem; }
.txn-title { font-weight: 700; font-size: .8rem; color: #37474f; margin-bottom: .35rem; }
.txn-log { font-size: .78rem; color: #555; min-height: 3.2em; line-height: 1.6; }
.txn-log .entry { margin: 0; }
.txn-log .read { color: #1565c0; }
.txn-log .write { color: #6a1b9a; }
.txn-actions { display: flex; gap: .35rem; flex-wrap: wrap; margin-top: .4rem; }
.txn-status { font-size: .8rem; font-weight: 700; min-height: 1.2em; margin-top: .3rem; }
.txn-status.ok { color: #1b5e20; }
.txn-status.abort { color: #b71c1c; }
.global-status { font-size: .9rem; font-weight: 700; min-height: 1.4em; margin: .5rem 0; }
.global-status.anomaly { color: #b71c1c; }
.global-status.safe { color: #1b5e20; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 12px system-ui, sans-serif; padding: .35rem .7rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .35; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// SSI write-skew demo — two transactions, one dangerous rw-anti-dependency cycle

// Committed database state: both doctors start on call
const db = { alice: true, bob: true };

// Each transaction’s private snapshot taken at BEGIN
const snapshots = { T1: null, T2: null };

// rw-anti-dependency tracking: T1 reads a row T2 will write, and vice versa.
// When both flags are true and neither has committed yet, we have a dangerous pivot cycle.
const rw = { T1_reads_bob: false, T2_reads_alice: false };

// Commit and abort flags per transaction
const committed = { T1: false, T2: false };
const aborted   = { T1: false, T2: false };

function renderDb() {
  const el = document.getElementById('db-rows');
  el.innerHTML = '';
  for (const [name, on] of [['Alice', db.alice], ['Bob', db.bob]]) {
    const d = document.createElement('div');
    d.className = 'db-row' + (on ? '' : ' off');
    d.textContent = name + ': ' + (on ? `on call` : `off call`);
    el.appendChild(d);
  }
}

function log(txn, cls, msg) {
  const el = document.getElementById('log-' + txn.toLowerCase());
  const p = document.createElement('p');
  p.className = 'entry ' + cls;
  p.textContent = msg;
  el.appendChild(p);
}

function setTxnStatus(txn, cls, msg) {
  const el = document.getElementById('status-' + txn.toLowerCase());
  el.textContent = msg;
  el.className = 'txn-status ' + cls;
}

function setGlobal(cls, msg) {
  const el = document.getElementById('global-status');
  el.textContent = msg;
  el.className = 'global-status ' + cls;
}

// READ: take a snapshot and record rw-anti-dependencies
function doRead(txn) {
  const snap = { alice: db.alice, bob: db.bob };
  snapshots[txn] = snap;
  // T1 reads Bob’s row (T2 will write Bob); T2 reads Alice’s row (T1 will write Alice)
  if (txn === 'T1') rw.T1_reads_bob = true;
  if (txn === 'T2') rw.T2_reads_alice = true;
  const onCount = (snap.alice ? 1 : 0) + (snap.bob ? 1 : 0);
  log(txn, 'read', i18nFmt(`Snapshot: Alice=%alice%, Bob=%bob% (%n% on call)`, { alice: snap.alice ? `on call` : `off call`, bob: snap.bob ? `on call` : `off call`, n: onCount }));
  document.getElementById('btn-' + txn.toLowerCase() + '-read').disabled = true;
  document.getElementById('btn-' + txn.toLowerCase() + '-write').disabled = false;
  document.getElementById('btn-' + txn.toLowerCase() + '-commit').disabled = false;
}

// WRITE: stage the change on the local snapshot (only if safe in snapshot)
function doWrite(txn) {
  if (!snapshots[txn]) return;
  const snap = snapshots[txn];
  const onCount = (snap.alice ? 1 : 0) + (snap.bob ? 1 : 0);
  if (onCount < 2) {
    log(txn, 'write', `Cannot remove — only one doctor on call in snapshot!`);
    document.getElementById('btn-' + txn.toLowerCase() + '-write').disabled = true;
    return;
  }
  // Stage the write — mark row as pending-off in this transaction’s snapshot
  if (txn === 'T1') {
    snapshots['T1'].alice_pending = false;
    log('T1', 'write', `Pending write: set Alice = off call`);
  } else {
    snapshots['T2'].bob_pending = false;
    log('T2', 'write', `Pending write: set Bob = off call`);
  }
  document.getElementById('btn-' + txn.toLowerCase() + '-write').disabled = true;
}

// COMMIT: check for dangerous SSI cycle before applying
function doCommit(txn) {
  if (aborted[txn]) return;
  const snap = snapshots[txn];
  if (!snap) return;

  // SSI cycle check: T1 read Bob (anti-dep from T2) AND T2 read Alice (anti-dep from T1)
  // => both transactions are in a pivot cycle; abort the one committing first
  const dangerousCycle = rw.T1_reads_bob && rw.T2_reads_alice
    && !committed['T1'] && !committed['T2'];

  if (dangerousCycle) {
    // Abort this transaction — the cycle is dangerous
    aborted[txn] = true;
    setTxnStatus(txn, 'abort', `ABORTED by SSI (dangerous cycle)`);
    setGlobal('safe', `SSI caught the cycle and aborted one transaction. Retry it to get correct behavior.`);
    document.getElementById('btn-' + txn.toLowerCase() + '-commit').disabled = true;
    return;
  }

  // No cycle detected (or one side already committed); apply the write
  if (txn === 'T1' && snap.alice_pending === false) db.alice = false;
  if (txn === 'T2' && snap.bob_pending === false) db.bob = false;
  committed[txn] = true;
  setTxnStatus(txn, 'ok', `Committed`);
  document.getElementById('btn-' + txn.toLowerCase() + '-commit').disabled = true;
  renderDb();

  // If both committed, check whether the invariant is violated
  if (committed['T1'] && committed['T2']) {
    if (!db.alice && !db.bob) {
      setGlobal('anomaly', `ANOMALY: nobody is on call! (plain SI would allow this)`);
    } else {
      setGlobal('safe', `Safe: at least one doctor remains on call.`);
    }
  }
}

function reset() {
  db.alice = true; db.bob = true;
  snapshots.T1 = null; snapshots.T2 = null;
  rw.T1_reads_bob = false; rw.T2_reads_alice = false;
  committed.T1 = false; committed.T2 = false;
  aborted.T1 = false; aborted.T2 = false;
  renderDb();
  document.getElementById('log-t1').innerHTML = '';
  document.getElementById('log-t2').innerHTML = '';
  setTxnStatus('t1', '', '');
  setTxnStatus('t2', '', '');
  setGlobal('', '');
  ['t1', 't2'].forEach(t => {
    document.getElementById('btn-' + t + '-read').disabled = false;
    document.getElementById('btn-' + t + '-write').disabled = true;
    document.getElementById('btn-' + t + '-commit').disabled = true;
  });
}

document.getElementById('btn-t1-read').addEventListener('click', () => doRead('T1'));
document.getElementById('btn-t2-read').addEventListener('click', () => doRead('T2'));
document.getElementById('btn-t1-write').addEventListener('click', () => doWrite('T1'));
document.getElementById('btn-t2-write').addEventListener('click', () => doWrite('T2'));
document.getElementById('btn-t1-commit').addEventListener('click', () => doCommit('T1'));
document.getElementById('btn-t2-commit').addEventListener('click', () => doCommit('T2'));
document.getElementById('btn-reset').addEventListener('click', reset);
renderDb();
Result
Console

Under plain Snapshot Isolation both commits succeed and nobody is on call — a real anomaly. SSI tracks the dependency cycle (T1 read what T2 will overwrite; T2 read what T1 will overwrite) and aborts one transaction, forcing it to retry with fresh data.

The Real Complexity

Behind SSI is a graph called the Serialization History Graph (SHG). Each transaction is a node; edges represent dependencies:

  • wr-dependency (write-read): T1 writes a value, T2 reads it — T1 must come before T2.
  • ww-dependency (write-write): T1 and T2 both write the same row — one overwrites the other.
  • rw-anti-dependency: T1 reads a version of a row, T2 writes a newer version — T2 "overwrites T1's read." This is the subtle one.

A cycle in this graph means the transactions cannot be ordered sequentially. Snapshot Isolation already prevents wr and ww cycles. The only cycles it misses are those that involve two rw-anti-dependency edges in a row (a "dangerous structure"). SSI detects exactly that pattern.

The algorithm, due to Fekete et al. and later refined by Ports & Grittner (the PostgreSQL implementation), tracks which transactions have outgoing and incoming rw-anti-dependency edges. When a transaction commits, if it sits in a "pivot" position — it has an incoming rw edge from one concurrent transaction and an outgoing rw edge to another — one of the three transactions is aborted.

The overhead is modest: a small set of SIREAD locks records which rows were read (without blocking anyone), and the cycle check is O(n)O(n) in the number of concurrent transactions. Real-world benchmarks put the throughput cost at roughly 10–15 % compared to plain SI, with correctness fully guaranteed. That is a far smaller tax than two-phase locking, which can drop throughput by an order of magnitude under contention.

SSI is now the default isolation level in PostgreSQL (SERIALIZABLE) and is available in CockroachDB and YugabyteDB. It proves that P vs NP style hardness problems in theory do not always translate into intractable engineering costs in practice — sometimes a focused structural insight bypasses the brute-force wall entirely.

Where It Matters

Any time business logic reads data and then writes based on what it saw, write skew is a latent bug waiting to surface at scale:

  • Banking and finance: "transfer funds if the balance is sufficient" — two concurrent withdrawals can each see a passing balance and both succeed, overdrawing the account.
  • Medical scheduling: the on-call roster example from the demo is not hypothetical; real hospital systems have shipped this bug.
  • Inventory management: "reserve stock if units > 0" — two concurrent orders each see one unit available and both confirm, overselling the item.
  • Collaborative editing: two editors each read the document version, apply disjoint changes, and save — the version history becomes inconsistent.

The alternative to SSI is application-level locking: SELECT … FOR UPDATE, advisory locks, or serializing access through a queue. These work but push complexity onto the developer and hurt throughput. SSI lets you write straightforward BEGIN … COMMIT code and catch and retry only on the rare abort, which is cleaner and often faster.

For a deeper look at consistency models in distributed systems, see the article on max-flow for another graph-theoretic approach to resource limits, or sat to understand the constraint-satisfaction framing that underlies many anomaly-prevention proofs.

Conclusion

Serializable Snapshot Isolation is one of the neatest results in database systems: by noticing that only cycles involving two consecutive rw-anti-dependency edges can escape snapshot isolation, researchers designed an algorithm that catches exactly those cycles and nothing more — minimal overhead, maximum correctness.

The lesson generalizes. Many correctness problems that look like they need global coordination turn out to need only local structure detection. SSI found the one dangerous pattern, named it, and built a lightweight detector for it. The write-skew anomaly that once required application-level workarounds now quietly disappears inside the database engine — a reminder that the right abstraction often costs less than you think.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/serializable-snapshot-isolation/Content licensed under CC BY-NC 4.0.