Dangerous Structures: Detecting Serialization Cycles Under Snapshot Isolation

Snapshot isolation prevents lost updates by checking write sets at commit. It does not prevent a transaction from acting on reads that another transaction has since invalidated, and that omission is the entire distance between snapshot isolation and serializability. Serializable snapshot isolation closes the distance by adding a second check, and the interesting part is that the check does not need to track read sets against all writers. It needs to detect one specific shape.

The shape that must not exist

A serialization cycle under snapshot isolation has a restricted form. Because snapshot isolation already forbids two overlapping transactions from writing the same item, a cycle cannot consist only of write-write edges. Fekete and colleagues proved that every nonserializable execution under snapshot isolation contains a structure with three transactions and two adjacent read-write dependencies, and Cahill and colleagues named the pattern a dangerous structure.

Write the dependency as an arrow from reader to writer: A → B means A read a version of some item that B later overwrote. The dangerous structure is T1 → T2 → T3, and the condition that makes it dangerous is that T3 is the first of the three to commit.

The commit-order condition carries the intuition. T1 read a version that T2 has since replaced, and T2 read a version that T3 has since replaced, so both T1’s and T2’s snapshots predate T3’s write. With T3 committing first, T1 and T2 are both still working from states that T3 has already superseded, and each of them will commit after the state it reasoned about was invalidated. The write-skew pair is the degenerate case in which T1 and T3 are the same transaction.

The practical consequence is that detection does not need to find cycles in a graph. It needs to find two adjacent read-write dependencies where the far writer committed first. That is a local check on a transaction’s own conflict sets.

Two sets per transaction

For a transaction acting as the pivot T2, two sets matter, and they are both about its own accesses.

Its in-writers are the transactions whose versions it read and which have since written a newer version of those items — the T3 side. Its out-readers are the transactions that read versions it has since overwritten — the T1 side.

At commit, the pivot looks for an out-reader that has not yet committed paired with an in-writer that has already committed. That combination means the far writer finished first while the reader is still in flight, which is the dangerous ordering. One of the three transactions must then be rolled back.

def check_commit(in_writers, out_readers, committed):
    """in_writers: txns that overwrote something this txn read.
    out_readers: txns that read something this txn overwrote.
    committed: predicate telling whether a txn has committed.
    Returns False if a dangerous structure is present."""
    for w in in_writers:                 # w plays T3
        if not committed(w):
            continue
        for r in out_readers:            # r plays T1
            if not committed(r):
                return False             # T3 committed first: abort pivot
    return True

The check is a nested loop over two per-transaction sets, which is why both stay small: they are bounded by the number of concurrent transactions that touched the same items, not by the size of the database. A transaction touching many items under contention accumulates larger sets and pays a larger check.

The sets are maintained during execution rather than reconstructed at commit. When a transaction writes an item, it inspects the read markers other transactions left on that item and records them as out-readers. When it reads an item, it inspects the write markers and records the writer as a potential in-writer if that writer has since produced a newer version. Every read and every write therefore pays a small constant cost for marker inspection, which is the price of the whole mechanism.

Aborting the reader instead of the pivot

The default response to a dangerous structure is to abort the transaction that detected it, which is the pivot. That works, and it is what the check above does, but it is not always the cheapest choice.

The far reader T1 is the other candidate. It has not committed, by construction, because T3 committed first and the pivot is only now validating. If T1 is read-only, aborting it costs nothing but the discarded reads: no undo of writes, no external effects, no retry of write work. Aborting the pivot instead throws away whatever the pivot wrote, which may be substantially more.

This asymmetry is why serializable snapshot isolation implementations track read-only transactions separately and offer them a deferrable mode. A read-only transaction can wait before taking its snapshot until it is guaranteed that no concurrent read-write transaction can invalidate it; at that point it can commit with no validation at all. The wait is the cost, and the benefit is that a long analytical query neither aborts itself nor forces a writer to abort.

When T1 has already committed and is not read-only, neither option is available: the engine cannot retract a committed transaction’s effects, so the pivot must be rolled back.

Where the test is stricter than necessary

The dangerous-structure test is conservative. It aborts some executions that are serializable, because two adjacent read-write dependencies with the far writer committing first are necessary for a cycle but not always sufficient. The three transactions can be arranged so that the specific items involved make the dependencies harmless, and the check cannot see the difference.

That false positive rate is the mechanism’s practical cost, and it is why the read-only optimization matters more than the arithmetic suggests. An analytical query that reads a large set accumulates out-readers on every item it touched, so it becomes the T1 of many potential structures; under a naive policy it is a candidate for abort in each one. Deferring its snapshot removes the entire class, and it is the class where aborts are most expensive, since the query has already done all of its work by the time it would be rolled back.

The trade is latency. A deferrable read-only transaction may wait for concurrent writers to finish before it starts, so its start time is not under the application’s control. For an interactive query that is unacceptable; for a batch report it is exactly right. The mechanism is a mode, and the application picks it.

What the markers cost in space

Every item carries markers for the transactions that read or wrote it, and the markers must be visible to other transactions inspecting the same item. In a heap-version engine, this means the tuple header needs space for a set of transaction identifiers, or a pointer to a side structure holding them.

The space problem is that a hot item accumulates markers from every concurrent reader. An item read by fifty concurrent transactions needs fifty entries, and the entries cannot be discarded until those transactions commit or abort. This is the same growth pattern as the in-progress list described in snapshot acquisition and commit ordering, and it has the same mitigation: keep the common case small and spill to a side table when the set grows.

The alternative used by some implementations is to track conflicts at a coarser granularity, such as a page or a relation, which reduces the marker count but increases false positives. The trade is the familiar one from gap locks and next-key locking: finer granularity means more bookkeeping and fewer false conflicts.

How the two mechanisms trade off

The competing mechanism for serializability is two-phase locking with predicate or range locks, which prevents cycles structurally rather than detecting them afterward. Its advantage is that it never aborts a transaction for a conflict it discovered late: a lock is granted only when the conflict is real, the holder proceeds in the order the locks establish, and the result is serializable by construction. Its cost is blocking, which is unbounded and can produce deadlocks that must be detected and resolved by aborting someone.

Serializable snapshot isolation inverts the trade. It never blocks a reader and never blocks a writer, except in the deferrable read-only case, and it converts every conflict into an abort. The abort is bounded in cost — the transaction’s work is discarded — but it is a cost paid after the work, not before it, which is worse for transactions that do a lot of work before their first conflict.

The choice between the two depends on the ratio of read to write work and on the tolerance for latency spikes. A workload of short write transactions with occasional analytical reads favours the snapshot approach, because the short transactions rarely conflict and the reads can be deferred. A workload of long transactions with heavy contention on a small set of items favours locking, because the abort rate under the snapshot approach would be high and the retries expensive.

There is a third option that some systems use: run snapshot isolation by default and expose serializable as an opt-in per transaction. The cost of the markers is then paid only by transactions that request the stronger level, at the price of a more complex engine that must maintain two sets of invariants. This is a common arrangement and it explains why serializable is often slower in a way that seems disproportionate: the overhead is concentrated in the transactions that use it, and those are usually the ones that most need the isolation.

The residual guarantee

Serializable snapshot isolation delivers serializability in the formal sense, subject to the correctness of the conflict tracking. If the markers miss a conflict, the guarantee is void, and the ways markers can miss are the interesting failure modes: a conflict on an item that was updated in place without leaving a marker, a conflict involving a predicate rather than an item, or a conflict whose edge was recorded but whose commit order was misjudged because the commit sequence was assigned before the transaction was actually durable.

The predicate case is the one that requires care. A transaction that reads a range and a transaction that inserts into that range have a conflict, but no item is shared. The mechanism must therefore record range reads as markers on the range, which is a form of predicate locking by another name, with the same granularity problems. Implementations handle this by tracking the pages or index ranges a scan touched, which is coarser than a predicate and produces false positives on ranges that were scanned but whose results did not matter.

That coarseness is the honest limit of the mechanism. It is exact for item-level conflicts and approximate for predicate conflicts, and the approximation errs toward aborting rather than toward permitting an anomaly. For an application that needs the guarantee, erring toward abort is the correct direction.