Serializability

The problem serializability solves

Imagine two bank transfers hitting the same account at the same moment. Transaction A reads the balance ($100), adds a $50 deposit, and writes $150. Transaction B reads the balance ($100), subtracts a $30 withdrawal, and writes $70. If they interleave so that both read $100 before either writes, one update is silently lost — the final balance is either $150 or $70 instead of the correct $120. This is the lost update anomaly, and it is exactly the kind of corruption that concurrency introduces.

The safest possible execution is a serial one: run A completely, then B completely (or B then A). No interleaving, no anomalies — but also no concurrency, which on a modern multi-core server throws away orders of magnitude of throughput. Databases need to interleave thousands of transactions to keep CPUs and disks busy.

Serializability is the bridge. A concurrent schedule — an interleaving of the read and write operations of several transactions — is defined as correct if and only if it produces the same final database state as some serial schedule of those same transactions. You get the throughput of interleaving with the provable correctness of running one transaction at a time. The order does not have to be the one the transactions were submitted in; it only has to be some serial order.

Conflicts and the precedence graph

Two operations conflict when they belong to different transactions, act on the same data item, and at least one of them is a write. There are exactly three conflicting pairs: write–write, read–write, and write–read. Two reads never conflict, because reordering them cannot change any value. This is the entire basis of conflict serializability: a schedule is conflict-equivalent to a serial schedule if you can transform one into the other by swapping only adjacent non-conflicting operations.

Testing this directly would be exponential, so we use a clever reduction. Build a precedence graph (also called a serialization graph):

• One node per transaction.
• An edge Ti → Tj whenever an operation of Ti conflicts with and comes before a conflicting operation of Tj in the schedule.

The edge means "in any equivalent serial order, Ti must come before Tj." Now the theorem: a schedule is conflict-serializable if and only if its precedence graph is acyclic. A cycle Ti → Tj → … → Ti means each transaction must run before the next and also after the last — an impossible ordering, so no serial schedule matches. If the graph is acyclic, a topological sort of it hands you the equivalent serial order directly.

Detecting a cycle in a directed graph is a depth-first search in O(V + E), where V is the number of transactions and E the number of conflict edges. Since E ≤ V², the worst case is O(V²), but in practice the graph is sparse and the test is effectively linear in the number of transactions involved.

Conflict vs view serializability

Conflict serializability is the workhorse because it is cheap to test, but it is conservative: it rejects some schedules that are actually correct. View serializability is the more permissive criterion. Two schedules are view-equivalent if they agree on three things: the initial reads (each read sees the same writer it would in the serial schedule), the reads-from relationships, and the final write to each data item.

The gap between them is blind writes — a transaction that writes a value without first reading it. Consider three transactions where T2 and T3 both blind-write the same item; the final-write semantics can match a serial order even when the conflict graph has a cycle. Every conflict-serializable schedule is view-serializable, but the converse fails. The catch is the price: testing view serializability is NP-complete (proven by Papadimitriou in 1979), so no production system actually enforces it. They settle for the polynomial, slightly-too-strict conflict criterion.

Where serializability sits among isolation levels

The ANSI SQL standard defines four isolation levels by which anomalies they forbid. Serializability is the top of the ladder.

Isolation level	Dirty read	Non-repeatable read	Phantom	Write skew	Typical cost
READ UNCOMMITTED	Possible	Possible	Possible	Possible	Lowest
READ COMMITTED	Prevented	Possible	Possible	Possible	Low (most defaults)
REPEATABLE READ	Prevented	Prevented	Possible*	Possible	Moderate
SNAPSHOT ISOLATION	Prevented	Prevented	Prevented	Possible	Moderate (MVCC)
SERIALIZABLE	Prevented	Prevented	Prevented	Prevented	Highest

*Under the ANSI definition REPEATABLE READ permits phantoms; some engines (MySQL InnoDB) block them with gap locks. The headline insight is the snapshot-isolation row: it looks almost as strong as serializable but leaves the write-skew hole open, and that single gap is why "serializable" is its own distinct level rather than a synonym for "very strong isolation."

What it costs in real systems

• The precedence-graph test is O(V + E) per committed batch of transactions. For a batch of 1,000 concurrent transactions with a typical conflict density, that is a few microseconds of graph work — negligible next to the locking or validation it gates.
• Strict two-phase locking throughput collapses under contention. Holding write locks until commit means hot rows serialize completely; on a workload where 90% of transactions touch one counter, throughput is bounded by that row's commit latency no matter how many cores you have.
• PostgreSQL's Serializable Snapshot Isolation (SSI) adds roughly 5–15% overhead over plain snapshot isolation in the original 2008–2012 benchmarks (Cahill, Fekete, Röhm, Ports), versus the 2×–3× slowdown traditional strict-2PL serializable engines suffered. SSI was the breakthrough that made true serializability affordable.
• Serializable transactions can abort and retry. Optimistic schemes (SSI, validation-based concurrency control) detect a non-serializable interleaving only at commit and roll one transaction back. Under high contention the retry rate climbs and effective throughput can fall below READ COMMITTED — which is why most production databases default to a weaker level.

JavaScript: precedence-graph serializability test

This builds the precedence graph from a schedule and reports whether it is conflict-serializable, returning an equivalent serial order when it is.

// A schedule is a list of operations: { txn, op: 'r'|'w', item }
function isConflictSerializable(schedule) {
  const txns = [...new Set(schedule.map(o => o.txn))];
  const adj = new Map(txns.map(t => [t, new Set()]));

  // Add edge Ti -> Tj for every conflicting pair where i precedes j.
  for (let i = 0; i < schedule.length; i++) {
    for (let j = i + 1; j < schedule.length; j++) {
      const a = schedule[i], b = schedule[j];
      if (a.txn === b.txn) continue;
      if (a.item !== b.item) continue;
      if (a.op === 'r' && b.op === 'r') continue;   // reads never conflict
      adj.get(a.txn).add(b.txn);                      // a precedes b
    }
  }

  // Kahn's topological sort: detect a cycle and emit a serial order.
  const indeg = new Map(txns.map(t => [t, 0]));
  for (const [, outs] of adj) for (const v of outs) indeg.set(v, indeg.get(v) + 1);

  const queue = txns.filter(t => indeg.get(t) === 0);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj.get(u)) {
      indeg.set(v, indeg.get(v) - 1);
      if (indeg.get(v) === 0) queue.push(v);
    }
  }

  return order.length === txns.length
    ? { serializable: true, serialOrder: order }   // acyclic
    : { serializable: false, serialOrder: null };   // cycle remains
}

// Lost-update interleaving — NOT serializable (cycle T1 -> T2 -> T1)
console.log(isConflictSerializable([
  { txn: 'T1', op: 'r', item: 'X' },
  { txn: 'T2', op: 'r', item: 'X' },
  { txn: 'T1', op: 'w', item: 'X' },
  { txn: 'T2', op: 'w', item: 'X' },
]));
// => { serializable: false, serialOrder: null }

The double loop is O(n²) in the number of operations because it inspects every pair; a smarter pass keyed by data item brings edge construction down to roughly O(n) per item. The cycle check itself — Kahn's algorithm — is O(V + E).

Python: the same test, and why the cycle means failure

from collections import defaultdict, deque

def is_conflict_serializable(schedule):
    """schedule: list of (txn, op, item) with op in {'r', 'w'}."""
    txns = list(dict.fromkeys(t for t, _, _ in schedule))
    adj = defaultdict(set)

    for i in range(len(schedule)):
        ti, oi, xi = schedule[i]
        for j in range(i + 1, len(schedule)):
            tj, oj, xj = schedule[j]
            if ti == tj or xi != xj:
                continue
            if oi == 'r' and oj == 'r':      # reads never conflict
                continue
            adj[ti].add(tj)                  # ti precedes tj

    # Kahn's topological sort over the precedence graph.
    indeg = {t: 0 for t in txns}
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1

    queue = deque(t for t in txns if indeg[t] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    if len(order) == len(txns):
        return True, order        # acyclic -> equivalent serial order
    return False, None            # cycle -> no serial order exists

# A serializable interleave: T1 fully on X before T2 touches X.
print(is_conflict_serializable([
    ('T1', 'r', 'X'), ('T1', 'w', 'X'),
    ('T2', 'r', 'X'), ('T2', 'w', 'X'),
]))  # (True, ['T1', 'T2'])

The asymmetry to internalize: an acyclic graph yields a serial order via topological sort, so the schedule is provably correct. A cyclic graph means the transactions impose contradictory ordering constraints on each other — there is no way to line them up serially, so the schedule is rejected. The cycle is the formal fingerprint of a concurrency anomaly.

How databases enforce it

Detecting non-serializable schedules after the fact is one thing; guaranteeing only serializable schedules occur is the engineering problem. There are two families.

Pessimistic — locking. Two-phase locking (2PL) divides each transaction into a growing phase (acquire locks, never release) and a shrinking phase (release locks, never acquire). This discipline provably produces only conflict-serializable schedules. Strict 2PL holds all exclusive locks until commit, which additionally guarantees recoverability and avoids cascading aborts. The downside is reduced concurrency and the risk of deadlock, which the scheduler must detect and break by aborting a victim.

Optimistic — validation. Transactions run against a consistent snapshot without taking locks, then validate at commit. Snapshot isolation alone is not serializable (write skew), so PostgreSQL's Serializable Snapshot Isolation tracks read–write dependencies at runtime and aborts a transaction when it spots the "dangerous structure" — two consecutive rw-antidependency edges — that signals a possible cycle. This catches non-serializable interleavings without the lock contention of 2PL, at the cost of occasional false-positive aborts.

Variants and related correctness notions

Strict serializability. Serializability says the result equals some serial order. Strict serializability (also called external consistency, and the guarantee Google Spanner provides via TrueTime) adds that the serial order respects real-time: if transaction A committed before B started, A must precede B in the equivalent serial order. It is serializability plus linearizability.

Recoverability, ACA, and strictness. A separate axis from serializability. A schedule is recoverable if no transaction commits before the transactions whose data it read commit first; it avoids cascading aborts if it only reads committed data; it is strict if it neither reads nor overwrites uncommitted data. A schedule can be serializable but not recoverable, which is why real systems demand both.

Order-preserving conflict serializability (OCSR). A subclass requiring that the commit order of non-interleaved transactions be preserved — relevant in distributed settings.

One-copy serializability (1SR). The replication analogue: a schedule over a replicated database is correct if it is equivalent to a serial schedule on a single logical copy. The benchmark for distributed databases.

Common misconceptions and edge cases

• Assuming the serial order is the submission order. Serializability only requires equivalence to some serial order — possibly the reverse of submission. Code that depends on "first-come-first-served" semantics needs strict serializability, not plain serializability.
• Confusing serializable with serial. A serializable schedule is highly concurrent; only its result matches a serial run. Treating the words as synonyms leads people to believe serializability kills all parallelism.
• Trusting REPEATABLE READ to stop phantoms. Under the ANSI definition it does not. Range or predicate locks (or SSI) are required to forbid phantom rows that appear in a re-run of a range query.
• Believing snapshot isolation is serializable. The write-skew anomaly — two doctors each going off-call because each reads that the other is still on-call — is consistent under SI yet violates the "at least one on-call" invariant. Use SSI or explicit locking.
• Ignoring blind writes when testing. Conflict serializability rejects some view-serializable schedules built from blind writes. That is by design and acceptable, but do not conclude such a schedule is "incorrect" — it is merely not conflict-serializable.
• Forgetting that reads conflict with writes both ways. A read-then-write on the same item produces an edge; so does write-then-read. Only read-read is conflict-free. Dropping the read-write direction silently misses cycles.