Serializable snapshot isolation (SSI)
How does SSI turn cycle detection into a two-bit test, and what does it really cost?
The anomaly it fixes
Snapshot isolation allows write skew: two transactions read overlapping data, write disjoint items, and together break an invariant neither broke alone (at Kestrel, the two support agents who both left at 06:00). Which histories each level permits is consistency's subject; this page is about the mechanism that rules write skew out.
A structural theorem
The mechanism rests on a theorem (by Fekete, Adya and colleagues):
This is a strong and non-obvious restriction, and it turns cycle detection into something local.
The two-bit test
Because of the theorem, SSI does not build the graph. It keeps two booleans per transaction: do I have an incoming rw edge? and do I have an outgoing rw edge? A transaction with both is a possible pivot (the middle of T₁ → T₂ → T₃) and is aborted.
The price is false positives: not every pivot lies in a real cycle, so SSI aborts transactions that would have been serializable.
The conservative-approximation pattern appears again
This is the fourth time in Locking and this article that the same move shows up, and by now it is not a coincidence:
- Intention locks approximate "is anything below locked?"
- Next-key locks approximate predicate locks.
- Conflict serializability approximates view serializability.
- SSI approximates cycle detection.
Each replaces an expensive or intractable exact test with a cheap conservative one, and each pays in false conflicts.
The same pattern explains Bloom filters (they say "maybe present" to avoid an exact lookup) and zone maps (they say "maybe in this block"). Its diagnostic value is high: whenever you find a system doing something conservative and slightly wrong, ask what exact test it is approximating and what that test would have cost.
The honest cost of SSI
To detect rw edges, you must remember what each transaction read. Postgres does this with SIREAD "locks". They are not locks (they block nothing), but they are lock-manager entries with all the same granularity problems. They are taken at tuple, page or relation granularity and are bounded by max_pred_locks_per_transaction. When the bound is hit, they escalate to a coarser granularity, which raises the false-positive rate.
What you get
SSI never blocks a read and never blocks a write; it only aborts. Read-only transactions are nearly free, and Postgres can prove some snapshots safe and exempt read-only transactions from tracking entirely.
On the folklore again
"Serializable is too slow to use" is inherited from 1990s lock managers and is wrong as stated. SSI's mechanism overhead on low-contention workloads is small. What costs is the abort rate: the L²k²/2N term from Why concurrency is different plus the false positives. That is a workload property, not an implementation property. State the cost as an abort rate and the conversation becomes tractable.
SSI replaces cycle detection with a two-bit conservative test, and pays for it in false aborts whose rate is set by read-tracking granularity.