Serializable Snapshot Isolation

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.

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.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="scenario">
  <div class="db-state" id="db-state">
    <div class="db-title">{{lbl_db}}</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; {{lbl_alice}}</div>
      <div class="txn-log" id="log-t1"></div>
      <div class="txn-actions" id="actions-t1">
        <button type="button" id="btn-t1-read">{{btn_read}}</button>
        <button type="button" id="btn-t1-write" disabled>{{btn_write_alice}}</button>
        <button type="button" id="btn-t1-commit" disabled>{{btn_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; {{lbl_bob}}</div>
      <div class="txn-log" id="log-t2"></div>
      <div class="txn-actions" id="actions-t2">
        <button type="button" id="btn-t2-read">{{btn_read}}</button>
        <button type="button" id="btn-t2-write" disabled>{{btn_write_bob}}</button>
        <button type="button" id="btn-t2-commit" disabled>{{btn_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">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

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)$ 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.

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.

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.