Serializable Snapshot Isolation When Reads Span Several Shards

Snapshot isolation permits a specific anomaly: two transactions read overlapping data, write disjoint data, and both commit, producing a state no serial execution could produce. The canonical example is two doctors each checking that at least one other doctor is on call, then each going off call, leaving nobody. Serializable snapshot isolation is the technique that keeps snapshot isolation’s lock-free reads and adds detection for exactly this pattern. Across shards, the detection has a structural problem: the evidence for the anomaly is split between nodes that never talk about reads.

The dependency edges SSI needs

SSI reasons about three kinds of dependency between transactions. A write-read dependency (wr) exists when one transaction reads a version written by another. A write-write dependency (ww) exists when one transaction overwrites a version written by another. A read-write antidependency (rw) exists when one transaction reads a version that another transaction later overwrites.

The first two are ordinary and appear in serial orders. The third is the one that makes anomalies possible: an rw-antidependency means the reader must be ordered before the writer, because the reader saw the old value. If two rw-antidependencies form a cycle, no serial order exists.

SSI’s theorem is that under snapshot isolation, every anomaly contains a “dangerous structure”: two consecutive rw-antidependencies, T1 →rw T2 →rw T3, where T1 and T3 are concurrent with each other. The detection rule is to abort one of the transactions when such a structure is found, which is why SSI is sometimes described as tracking a graph rather than enforcing a lock order.

In a single-node implementation the tracking is cheap because the state is local. PostgreSQL keeps, for each transaction, a list of the transactions it has read from and the transactions that have read from it, plus a flag for whether the transaction has written anything. At commit, the transaction checks whether it is the T2 of a dangerous structure: has it got an incoming rw edge from a concurrent transaction and an outgoing rw edge to a concurrent transaction, with those two concurrent with each other.

Why the graph cannot stay local

Put the data on two shards. Transaction T1 reads a row on shard A and writes a row on shard B. Transaction T2 reads a row on shard B and writes a row on shard A. Each shard sees half of each transaction’s edges. Shard A sees T1’s read of its row and T2’s write to it, giving an rw edge T1 →rw T2. Shard B sees T2’s read of its row and T1’s write to it, giving T2 →rw T1. The cycle exists, and neither shard can see it.

The obvious remedy is to centralise the conflict information: every shard reports its edges to a coordinator, which joins them and detects cycles. This is correct and it is expensive, because the edge volume is proportional to the number of reads that are later overwritten, which is proportional to concurrency. A busy system generates edges at the rate of its transaction throughput, and shipping all of them to one place makes that place a bottleneck whose load scales with the system’s success.

A second remedy is to make the reads visible to the shard that owns the written row. When T1 reads a row on shard A, shard A records the read against the row’s version. When T2 writes that row on shard A, shard A can see that T1 read it and create the edge locally. The problem is that T1’s read was of a version on shard A, and T2’s write is also on shard A, so this edge is local after all. The cross-shard edges only appear when a transaction reads on one shard and writes on another, and the write’s shard has no record of the read.

So the fundamental issue is read tracking: a read leaves a mark on the shard that holds the data, but the conflict that matters is with a write on a different shard. Either the read’s mark must be transported to every shard where a conflicting write might occur, which is unbounded, or the read must be validated against the written rows at commit, which requires the writer’s shard to ask the reader’s shard whether it read anything the writer touched.

Validation by asking, and its cost

The practical implementation is the second option, and it turns SSI’s local graph into a commit-time protocol. A transaction that wants to commit sends, to each shard it wrote on, the set of rows it wrote. Each shard checks whether any concurrent transaction read those rows at the snapshot the writer’s transaction used, and reports a conflict if so. The check requires the shard to keep a record of reads by version, which is exactly the read mark, and to be able to answer “did any transaction with a snapshot at or before S read this row and not yet commit”.

This makes commit a distributed operation with a round trip per shard, which is the same shape as the two-phase commit decision. The two protocols compose: validation is the first phase’s work, and the decision is the second phase’s. The composition is why systems that offer serializable cross-shard transactions pay two round trips rather than one, and why their commit latency is higher than a snapshot-isolated system’s even when no conflict exists.

The number of read marks that must be retained is the real cost. A read mark must live until the reading transaction commits or aborts, because until then a conflicting write must be able to find it. With long transactions, the mark set grows with the number of concurrent transactions times their read footprint. Systems bound this by limiting transaction duration or by summarising the marks: instead of recording each read row, the shard can record the set of transaction identifiers that read anything in a range, at the cost of more false positives.

The read-only optimisation and its distributed failure

SSI has a well-known optimisation for read-only transactions: they cannot be the T2 of a dangerous structure because they have no outgoing rw edge (they write nothing), so they can be exempted from most of the checking. A read-only transaction that starts before any concurrent writer and commits after can be declared safe without validating.

The optimisation depends on knowing the transaction’s snapshot relative to the writers it might conflict with. On one node this is a comparison of local counters. Across shards, the read-only transaction may have read from shards whose snapshots were acquired at different times, and its safety depends on all of them. A read-only transaction that is safe with respect to shard A’s writers may be unsafe with respect to shard B’s, because its snapshot on B was acquired later.

The safe approach is to validate the read-only transaction against every shard it read from, which removes most of the optimisation’s benefit. The alternative is to force a global snapshot across all shards, so that the transaction’s snapshot is comparable everywhere, which is the global snapshot problem from global snapshots across shards. The optimisation therefore pushes the cost into snapshot acquisition rather than into validation, and the total is roughly the same.

When serializability is worth the cost

The cost structure is clear enough to make the choice explicit. Snapshot isolation across shards needs a consistent snapshot for reads that span shards, plus a commit protocol for writes that span shards. SSI adds a read-mark retention cost, a validation round trip per written shard, and the risk of false-positive aborts when marks are summarised.

The benefit is the removal of write skew and the other anomalies that snapshot isolation permits. Whether that is worth it depends on whether the application’s invariants span rows that concurrent transactions read and write in the crossing pattern. A system that enforces “the sum of these two accounts is non-negative” by reading both and writing one has a write-skew hazard; a system that maintains a per-row invariant does not.

The alternative to SSI is to keep snapshot isolation and enforce the cross-row invariants with explicit locks or with a materialised conflict object. Taking a lock on a shared row that both transactions must touch serialises them without any detection machinery, at the cost of a contention point. For invariants that are genuinely global, such as a uniqueness constraint or a counter with a floor, the lock is often cheaper than the detection, because the lock’s cost is paid only by the transactions that touch the invariant, while SSI’s read marks are paid by all readers.

Failure modes specific to the distributed case

Two failure modes deserve naming because they are absent from the single-node description.

The first is an incomplete validation caused by a shard being unreachable at commit time. If the writer cannot ask shard B whether its read set conflicts, it cannot complete validation. Proceeding would risk an anomaly; waiting blocks the commit. The resolution is the same as for any commit protocol: wait, and accept that the transaction is in doubt. SSI does not add a new failure mode here, but it does add a new reason a commit can be blocked, which is that a shard holding only a read record is unreachable.

The second is a false negative caused by read marks being discarded too early. A read mark must live at least until the reading transaction can no longer be concurrent with any future writer. If a shard garbage-collects marks based on its local oldest snapshot while another shard’s transactions are still live at an older snapshot, a writer can validate successfully against a shard that has forgotten the read, and the anomaly slips through. The retention floor must be global, and computing it requires the same coordination as the snapshot itself. This is the same trap as version retention in global snapshots across shards, and it is the most common way an implementation that looks correct locally produces anomalies under distribution.