Serializable snapshot isolation and retries

Serializable snapshot isolation (SSI) keeps the snapshots of snapshot isolation and adds one check. It watches for read-write dependencies between transactions that run at the same time, and when two of them meet at one transaction, a pattern called a dangerous structure, it aborts a transaction before the result can break serializability. Every anomaly that snapshot isolation allows, write skew included, contains such a structure. PostgreSQL’s SERIALIZABLE level is serializable snapshot isolation, and the aborted transaction receives SQLSTATE 40001. Retries are therefore part of using it: the application runs the whole transaction again. Retries are also how deadlock victims recover. The everyday patterns of application code, such as FOR UPDATE, SKIP LOCKED, advisory locks, unique constraints and version columns, decide where conflicts surface in the first place.

From write skew to a dangerous structure

Transaction A has a read-write antidependency on B when A reads an item and B, running at the same time, writes a newer version of it that A’s snapshot does not see: in any serial order equal to what happened, A must come before B. One such edge is harmless. Fekete and colleagues proved that every non-serializable execution under snapshot isolation contains two consecutive ones between concurrent transactions, T1 to T2 to T3, where T1 and T3 may be the same transaction (Making Snapshot Isolation Serializable). Cahill, Röhm and Fekete turned that into an algorithm: track the edges and abort when a transaction has one coming in and one going out (Serializable Isolation for Snapshot Databases).

The program finds the edges and the structure in two histories, the doctors who both go off call and a report that reads a closed batch before its last receipt arrives:

"""Serializable snapshot isolation in miniature: the dependencies between concurrent transactions, the dangerous
structure, and the transaction PostgreSQL's rules abort.

Each transaction reads from the snapshot taken when it starts and writes when it commits. Tin -rw-> Tout means Tin
read an item and the concurrent Tout wrote a newer version that Tin's snapshot did not see. A dangerous structure is
two such edges in a row, Tin -rw-> Tpivot -rw-> Tout, where Tout commits first. PostgreSQL's rules: abort nothing
until Tout commits, then abort the pivot if it has not committed, otherwise Tin.
"""

HISTORIES = {
    "two doctors go off call": [
        ("start", "T1"), ("start", "T2"),
        ("read", "T1", "Meera"), ("read", "T1", "Arjun"), ("read", "T2", "Meera"), ("read", "T2", "Arjun"),
        ("write", "T1", "Meera"), ("write", "T2", "Arjun"),
        ("commit", "T1"), ("commit", "T2"),
    ],
    "a report sees a closed batch without its last receipt": [
        ("start", "T2"), ("read", "T2", "batch"),                     # T2 adds a receipt to the current batch
        ("start", "T3"), ("read", "T3", "batch"), ("write", "T3", "batch"), ("commit", "T3"),   # T3 closes it
        ("start", "T1"), ("read", "T1", "batch"), ("read", "T1", "receipts"), ("commit", "T1"), # T1 reports
        ("write", "T2", "receipts"), ("commit", "T2"),
    ],
}


def analyse(events):
    start, commit, reads, writes = {}, {}, {}, {}
    for i, (kind, t, *item) in enumerate(events):
        if kind == "start":
            start[t] = i
        elif kind == "commit":
            commit[t] = i
        elif kind == "read":
            reads.setdefault(t, set()).add(item[0])
        else:
            writes.setdefault(t, set()).add(item[0])
    names = sorted(start)
    concurrent = lambda a, b: start[a] < commit[b] and start[b] < commit[a]
    rw = sorted((a, b, x) for a in names for b in names if a != b and concurrent(a, b)
                for x in sorted(reads.get(a, set()) & writes.get(b, set())))
    lines = [f"{a} -rw-> {b}   ({a} read {x}; {b} wrote a newer version of {x} that {a} did not see)" for a, b, x in rw]
    edges = {(a, b) for a, b, _ in rw}
    victims = set()
    for tin, pivot in sorted(edges):
        for p2, tout in sorted(edges):
            if p2 == pivot and commit[tout] < commit[pivot] and commit[tout] <= commit[tin]:
                victim = pivot if commit[pivot] > commit[tout] else tin
                lines.append(f"dangerous structure {tin} -rw-> {pivot} -rw-> {tout}, and {tout} committed first: "
                             f"abort {victim}")
                victims.add(victim)
    if not victims:
        lines.append("no dangerous structure: every transaction commits")
    return lines


for label, events in HISTORIES.items():
    print(label)
    for line in analyse(events):
        print(f"  {line}")

two doctors go off call
  T1 -rw-> T2   (T1 read Arjun; T2 wrote a newer version of Arjun that T1 did not see)
  T2 -rw-> T1   (T2 read Meera; T1 wrote a newer version of Meera that T2 did not see)
  dangerous structure T1 -rw-> T2 -rw-> T1, and T1 committed first: abort T2
a report sees a closed batch without its last receipt
  T1 -rw-> T2   (T1 read receipts; T2 wrote a newer version of receipts that T1 did not see)
  T2 -rw-> T3   (T2 read batch; T3 wrote a newer version of batch that T2 did not see)
  dangerous structure T1 -rw-> T2 -rw-> T3, and T3 committed first: abort T2

The doctors form the smallest structure, T1 to T2 and back to T1. The report is subtler: each pair of transactions alone could run in some order, but the three together cannot, although T1 only reads. In both histories the rule of Ports and Grittner applies: wait until the last transaction of the structure has committed, then abort the pivot if it has not committed yet (Serializable Snapshot Isolation in PostgreSQL).

SERIALIZABLE in PostgreSQL

PostgreSQL tracks what each serializable transaction read with SIReadLock predicate locks, which never block anybody. A transaction it aborts gets could not serialize access due to read/write dependencies among transactions, always with SQLSTATE 40001. The check can raise false alarms: some aborted transactions would have been serializable after all. Long reports can avoid the risk with SERIALIZABLE READ ONLY DEFERRABLE, which may wait once for a safe snapshot and then run without being able to cause or suffer a serialization failure (PostgreSQL 18: SET TRANSACTION).

Retries

The manual is clear on what a retry must repeat: the complete transaction, including the logic that decides which statements to run and with which values, which is why PostgreSQL does not retry on its own (PostgreSQL 18: Serialization Failure Handling). A retry wrapper therefore takes the transaction as a function, retries on 40001 and, as the manual also advises, on the deadlock code 40P01, waits a little longer before each new attempt, and gives up after a few. Retries must also be safe to repeat, so anything the transaction does outside the database needs an idempotency key.

The patterns that shape where conflicts appear, one sentence each:

• SELECT ... FOR UPDATE locks the rows it reads, so a concurrent writer waits instead of failing later.
• FOR UPDATE SKIP LOCKED passes over rows that other transactions have locked, which suits queue tables.
• Advisory locks are locks on numbers whose meaning the application chooses, such as one per customer.
• A unique constraint lets the database refuse the second of two conflicting inserts, whatever the isolation level.
• A version column turns a lost update into an update that changes no row.
• An idempotency key lets a retried request find the result of its earlier attempt instead of acting twice.

Exercise

"""Retry a whole transaction when the database reports a serialization failure (40001) or a deadlock (40P01).

work() runs the whole transaction and returns its result, or raises DatabaseError with .sqlstate.
sleep(seconds) is how the wrapper waits; the tests pass a fake that records the waits.
"""


class DatabaseError(Exception):
    def __init__(self, sqlstate):
        super().__init__(f"SQLSTATE {sqlstate}")
        self.sqlstate = sqlstate


def run_with_retries(work, attempts=5, base=0.05, sleep=None):
    return work()

from retry import DatabaseError, run_with_retries


def fake(*codes, result="committed"):
    """A transaction that fails with the given codes, one per call, and then succeeds."""
    calls = []

    def work():
        calls.append(len(calls) + 1)
        if len(calls) <= len(codes):
            raise DatabaseError(codes[len(calls) - 1])
        return result
    return work, calls


def test_two_serialization_failures_then_success():
    """40001 twice, then the third attempt commits"""
    work, calls = fake("40001", "40001")
    waits = []
    assert run_with_retries(work, sleep=waits.append) == "committed"
    assert len(calls) == 3
    assert waits == [0.05, 0.1]


def test_deadlock_is_retried():
    """40P01 is retried too"""
    work, calls = fake("40P01")
    assert run_with_retries(work, sleep=lambda s: None) == "committed"
    assert len(calls) == 2


def test_other_errors_are_not_retried():
    """A unique violation, 23505, is raised at once"""
    work, calls = fake("23505")
    waits = []
    try:
        run_with_retries(work, sleep=waits.append)
    except DatabaseError as e:
        assert e.sqlstate == "23505"
    else:
        assert False, "the unique violation should have been raised"
    assert len(calls) == 1 and waits == []


def test_gives_up_after_the_last_attempt():
    """After 3 failed attempts the last error is raised, with no wait after it"""
    work, calls = fake("40001", "40001", "40001", "40001")
    waits = []
    try:
        run_with_retries(work, attempts=3, sleep=waits.append)
    except DatabaseError as e:
        assert e.sqlstate == "40001"
    else:
        assert False, "the wrapper should give up after 3 attempts"
    assert len(calls) == 3
    assert waits == [0.05, 0.1]

Inside SSI: the commit-order rule, needless aborts and read-only transactions, measured Pro: opens with a Pro, Premium or Ultimate pass

Concurrency patterns in application code, with failures reproduced Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Serializable snapshot isolation runs on snapshots and aborts a transaction when two read-write dependencies between concurrent transactions meet; every snapshot-isolation anomaly contains such a structure.
• PostgreSQL’s SERIALIZABLE is SSI: its SIReadLock predicate locks never block, and its failures carry SQLSTATE 40001.
• Retry the whole transaction on 40001 and 40P01, with backoff and a cap, and make side effects idempotent.
• FOR UPDATE, SKIP LOCKED, advisory locks, unique constraints and version columns each move a conflict to a place where it is cheap to handle.