Transactions, when everyone writes at once

Two people buy the last ticket

One row, one counter, and the most ordinary code anybody writes:

SELECT seats FROM events WHERE id = 1;     -- 1
-- application decides there is a seat, and takes it
UPDATE events SET seats = 0 WHERE id = 1;  -- sold

Two customers run it at once. Both SELECT before either UPDATE. Both see one seat. Both sell it. Every statement succeeded, every transaction committed, no error was raised and nothing was written to a log — and you have sold a seat twice.

The size of the problem is set by how many clients have that window open at the same time. With a hundred clients incrementing, and ten of them overlapping at any moment, the counter finishes at 10 instead of a hundred: 90 increments silently gone. Not slow, not erroring — gone, with the only evidence being a number that is too small.

Can I not just be careful — check before writing, or keep the window short? No, and the reason is worth being exact about, because it is what makes this a database problem rather than an application one. Checking before writing is another read, with its own window. Shortening the window reduces the probability and changes nothing about correctness, which means the bug survives every test you write and appears at the traffic level where it costs the most. The application cannot fix this because the application does not control the interleaving. Only the thing that sees all the operations can.

The one idea: correct means “as if one at a time”

Run the transactions one after another, with no overlap at all, and there is no problem — the same observation the replication side of this subject starts from. Each transaction sees a database nobody else is touching, so any invariant it checks stays true while it acts on it.

That gives the standard of correctness directly. A concurrent schedule is correct if it produces the same result as some serial order of the same transactions. That property is called serializability, and note the word some: the database is not obliged to produce any particular order, only to produce an outcome that could have come from one.

Which raises the question the rest of the post answers: given a schedule, how would you know? You cannot try every order — there are n! of them. You need something local.

Anomalies are cycles

Here is the move that turns the whole subject from a list into a derivation.

Two operations conflict if they touch the same item and at least one of them is a write. Two reads do not conflict — swapping them changes nothing — which leaves exactly three kinds: write-then-write, write-then-read, and read-then-write.

Each conflict forces an order. If T1 read x and T2 then wrote it, any equivalent serial order has to put T1 first, because in the schedule T1 saw the world before T2 changed it. Draw an arrow for each conflict, from the transaction that must come first to the one that must come second.

Now the payoff: a schedule is serializable exactly when those arrows contain no cycle. Acyclic means a topological order exists, and that order is the serial execution the schedule is equivalent to. A cycle means every candidate order contradicts itself — T1 must precede T2 and T2 must precede T1 — so no serial execution could have produced this outcome.

Every anomaly in every textbook table is a named shape of cycle, and that is why the table can be derived instead of memorised. The read-then-write edge — the anti-dependency — deserves special attention, because it is the one a system that only tracks writes cannot see. Keep an eye on it; it explains snapshot isolation’s single famous weakness.

If cycle detection settles it, why does any database use anything else? Because tracking every read of every transaction to build that graph is expensive, and the graph must be maintained across every concurrent transaction in the system. The classical technique — serialization graph testing — is exactly what the engine further down does, and it is largely of theoretical interest for that reason. Real systems use cheaper approximations: locking prevents the conflicting operations from ever being concurrent, snapshots make some conflicts impossible by construction, and SSI watches for a specific two-edge pattern that every cycle must contain. All three are described below, and each is a different answer to “how do I avoid computing this graph?”.

Isolation levels: which cycles you decline to look for

An isolation level is a promise about which schedules the database will refuse to produce. Stronger levels refuse more, and the anomaly names are just the shapes each level still allows through.

• Read uncommitted — you may see values from transactions that have not committed and may never commit. A dirty read: you act on a number that gets rolled back and never existed.
• Read committed — every read sees only committed data, but each read gets the latest committed data. Two reads in one transaction can disagree, which is a non-repeatable read; and reading two rows can catch a transfer halfway, which is read skew.
• Repeatable read — a row read twice reads the same. Classically this meant holding read locks; in practice most systems deliver it with a snapshot.
• Snapshot isolation — the whole transaction sees the database as of the instant it began, and two transactions writing the same row cannot both commit (first committer wins). This kills dirty reads, non-repeatable reads, read skew, lost updates and phantoms.
• Serializable — no cycles at all, by whatever means. The only level that also stops write skew.

Rather than assert that, here is the engine below run over four schedules at three levels. Each cell is what actually committed:

Read the write-skew row across. Snapshot isolation commits both transactions; the dependency graph it produced contains a cycle all the same. The schedule was never serializable, and the level simply was not looking.

Read-your-writes is not repeatable read

This pair of terms is the single most common confusion in the area, and it is worth separating carefully because the two live on different axes, break for different reasons, and are fixed by different machinery.

Repeatable read is about one transaction. It promises that within your transaction, reading a row twice gives the same answer no matter who commits in between. It is broken by a concurrent writer, and it is delivered by a snapshot (or by holding read locks until commit). It is a concurrency-control property, and a database on a single machine with a single copy of the data can give it to you perfectly.

Read-your-writes is about one client, across separate requests. You post a comment, the page reloads, and the comment is there. It is broken by a stale replica — your write went to the leader and your read was served by a follower that has not caught up — and it is fixed by routing you back to something that has your write, or by carrying a version token so the replica knows to wait. It is a replication property, and it only exists as a problem once there is more than one copy.

So could I have repeatable read and still not read my own writes? Easily, and it is a common production shape. Your write commits on the leader. Your next request opens a perfectly isolated, perfectly repeatable-read transaction — on a read replica that is two seconds behind. That transaction is internally consistent and completely wrong about the world. Isolation is a promise about other transactions; it says nothing about which copy you are talking to. The replication half of this is the subject of the companion post on consistency.

How databases actually do it

Three families, and they are exhaustive in the sense that there are only three things you can do about a conflict: prevent it, make it impossible, or detect it after the fact.

Two-phase locking — prevent it

Take a shared lock to read, an exclusive lock to write, and — the part that makes the name — never acquire a lock after releasing one. A transaction has a growing phase and then a shrinking phase.

That one rule is what buys serializability, and it is worth seeing why. Between the two phases there is an instant at which a transaction holds every lock it will ever hold. No two conflicting transactions can be at that instant simultaneously, so those instants place all the transactions in a total order — and that order is a serial schedule equivalent to what ran. Strict 2PL holds every lock to commit, which additionally stops anyone reading uncommitted data.

Where it breaks: deadlock is not an edge case but a structural certainty — two transactions taking the same two rows in opposite orders will eventually wait on each other forever. Databases detect it by looking for a cycle in the wait-for graph (a cycle again) and shoot one transaction. Beyond that, readers block writers and writers block readers, so a single long analytical query can stall writes across the table, and lock convoys turn a brief spike into a long one. Phantoms need predicate or next-key locks, which lock rows that do not exist yet and cost more than they look like they should.

MVCC and snapshot isolation — make it impossible

Never overwrite a row; write a new version of it stamped with the transaction that made it. A transaction reads the versions that were committed when it began. Readers therefore never block writers and writers never block readers, which is the single biggest throughput win in the history of database engines.

Under a snapshot, two of the three conflict kinds simply cannot bite. A write-then-read conflict is impossible because you never see uncommitted versions. A repeated read cannot change because your snapshot does not move. Write-then-write is caught explicitly, by first committer wins: if someone committed a version of a row you are writing after your snapshot was taken, you abort.

Where it breaks: the read-then-write edge. Nothing in that scheme notices that you read something someone else then wrote, because your snapshot hid their write and you never wrote the row they touched. Two such edges in opposite directions is write skew, and SI permits it by construction — this is not an implementation gap, it is what SI is. Separately, versions must be garbage collected, and a single long-running reader pins every version newer than its snapshot, so an idle transaction left open in a console can bloat a table until the disk fills.

Optimistic and SSI — detect it

Run without taking anything, record what you read and wrote, and at commit time check whether what you read is still true. If it is not, abort and start over. Kung and Robinson’s optimistic concurrency control (1981), and the model behind every WHERE version = 7 you have ever written.

Serializable snapshot isolation is the refinement that made this practical, and it rests on a genuinely beautiful result. Fekete et al. proved that every cycle possible under snapshot isolation contains two adjacent read-then-write edges. So you do not need the graph: track rw dependencies only, watch for a transaction that has one incoming and one outgoing rw edge — the “dangerous structure” — and abort. Cahill et al. (2008) turned that into an algorithm, and it has been PostgreSQL’s SERIALIZABLE since 9.1.

Where it breaks: the pattern is necessary but not sufficient, so SSI aborts some transactions that would have been fine — false positives are the price of not building the graph. And the failure mode under contention is not graceful. As conflicts rise, aborts rise, retries add load, which raises conflicts: throughput does not degrade, it collapses. Every caller needs a retry loop, and the retry must re-read — replaying the writes alone reintroduces exactly the lost update you started with.

Deterministic execution — refuse to have the problem

Decide the order before executing anything, then have every node execute in that order. Since the order is agreed up front, there is nothing to detect, nothing to abort, and no two-phase commit. Calvin (Thomson et al., 2012) is the reference design. Where it breaks: you must declare the read and write set before running, which is awkward when the rows you touch depend on what you read — handled with a reconnaissance pass that can itself be invalidated.

// A multi-version store that runs a schedule under a chosen isolation level.
//
// Pure and deterministic (code_guidelines.md §2): "time" is the index of the
// step being executed, not a clock, so the same schedule always produces the
// same events and the post can print them.

import { cycle, type Edge } from './graph.ts'

export type Level = 'read committed' | 'snapshot isolation' | 'serializable'

export type Step =
  | { readonly t: number; readonly op: 'read'; readonly key: string }
  | { readonly t: number; readonly op: 'write'; readonly key: string; readonly value: number }
  | { readonly t: number; readonly op: 'commit' }

export type Event = {
  readonly step: Step
  readonly saw?: number
  readonly outcome: 'ok' | 'aborted'
  readonly why?: string
}

export type Result = {
  readonly events: readonly Event[]
  readonly edges: readonly Edge[]
  readonly cycle: readonly number[] | null
  readonly committed: readonly number[]
  readonly final: Readonly<Record<string, number>>
}

type Version = { key: string; value: number; by: number; at: number }
type Txn = { id: number; startedAt: number; reads: Map<string, number>; writes: Map<string, number>; live: boolean }

const INITIAL = 0

export function run(schedule: readonly Step[], level: Level): Result {
  const versions: Version[] = []           // committed only, in commit order
  const txns = new Map<number, Txn>()
  const events: Event[] = []
  const edges: Edge[] = []
  const committed: number[] = []

  const open = (id: number, at: number): Txn => {
    const existing = txns.get(id)
    if (existing !== undefined) return existing
    const fresh: Txn = { id, startedAt: at, reads: new Map(), writes: new Map(), live: true }
    txns.set(id, fresh)
    return fresh
  }

  // What a reader sees. The only difference between read committed and the
  // snapshot levels is which committed versions are visible: the latest, or
  // the latest as of when this transaction began.
  const visible = (txn: Txn, key: string): Version | undefined => {
    const candidates = versions.filter(
      (v) => v.key === key && (level === 'read committed' || v.at <= txn.startedAt),
    )
    return candidates[candidates.length - 1]
  }

  schedule.forEach((step, at) => {
    const txn = open(step.t, at)
    if (!txn.live) {
      events.push({ step, outcome: 'aborted', why: 'transaction already aborted' })
      return
    }

    if (step.op === 'read') {
      const own = txn.writes.get(step.key)
      const seen = own ?? visible(txn, step.key)?.value ?? INITIAL
      txn.reads.set(step.key, seen)
      // wr: this read took a value some other transaction committed.
      const from = visible(txn, step.key)
      if (own === undefined && from !== undefined && from.by !== txn.id) {
        edges.push({ from: from.by, to: txn.id, kind: 'wr', key: step.key })
      }
      events.push({ step, saw: seen, outcome: 'ok' })
      return
    }

    if (step.op === 'write') {
      txn.writes.set(step.key, step.value)
      // rw: everyone who already read this key must be ordered before us.
      for (const other of txns.values()) {
        if (other.id !== txn.id && other.reads.has(step.key)) {
          edges.push({ from: other.id, to: txn.id, kind: 'rw', key: step.key })
        }
      }
      events.push({ step, outcome: 'ok' })
      return
    }

    // Commit. First-committer-wins: under either snapshot level, a write
    // conflicts if someone committed the same key after we began.
    if (level !== 'read committed') {
      const clash = [...txn.writes.keys()].find((key) =>
        versions.some((v) => v.key === key && v.at > txn.startedAt && v.by !== txn.id),
      )
      if (clash !== undefined) {
        txn.live = false
        events.push({ step, outcome: 'aborted', why: `another transaction committed ${clash} first` })
        return
      }
    }

    // ww edges against whoever last committed each key we are about to write.
    for (const key of txn.writes.keys()) {
      const last = versions.filter((v) => v.key === key).at(-1)
      if (last !== undefined && last.by !== txn.id) {
        edges.push({ from: last.by, to: txn.id, kind: 'ww', key })
      }
    }

    // Serializability, tested directly: would committing close a cycle?
    //
    // Only among transactions that have actually committed, plus this one. An
    // edge pointing at a transaction still running is not yet part of any
    // serialization order, and counting it would abort the *first* of a
    // conflicting pair as well as the second — leaving neither able to make
    // progress.
    if (level === 'serializable') {
      const settled = new Set([...committed, txn.id])
      const found = cycle(edges.filter((e) => settled.has(e.from) && settled.has(e.to)))
      if (found !== null && found.includes(txn.id)) {
        txn.live = false
        events.push({ step, outcome: 'aborted', why: `committing would close the cycle ${found.join(' → ')}` })
        return
      }
    }

    for (const [key, value] of txn.writes) versions.push({ key, value, by: txn.id, at })
    txn.live = false
    committed.push(txn.id)
    events.push({ step, outcome: 'ok' })
  })

  const final: Record<string, number> = {}
  for (const v of versions) final[v.key] = v.value

  return { events, edges, cycle: cycle(edges), committed, final }
}

// Conflict dependencies between transactions, and the cycle that makes a
// schedule wrong. Pure (code_guidelines.md §2).
//
// Two operations conflict when they touch the same item and at least one is a
// write. That gives three edge kinds, and the whole theory of isolation is the
// observation that a schedule is serializable exactly when these edges form no
// cycle.

/** `ww` write-then-write · `wr` write-then-read · `rw` read-then-write
 *  (the "anti-dependency": T2 wrote what T1 had already read, so T1 must be
 *  ordered first, and rw edges are the ones snapshot isolation cannot see). */
export type Kind = 'ww' | 'wr' | 'rw'
export type Edge = { readonly from: number; readonly to: number; readonly kind: Kind; readonly key: string }

/** The first cycle found, as the sequence of transaction ids, or null.
 *  Depth-first with a recursion stack — the textbook cycle test, which is all
 *  serialization-graph testing is. */
export function cycle(edges: readonly Edge[]): readonly number[] | null {
  const out = new Map<number, number[]>()
  for (const e of edges) out.set(e.from, [...(out.get(e.from) ?? []), e.to])

  const state = new Map<number, 'open' | 'done'>()
  const path: number[] = []

  const walk = (node: number): readonly number[] | null => {
    state.set(node, 'open')
    path.push(node)
    for (const next of out.get(node) ?? []) {
      if (state.get(next) === 'open') return [...path.slice(path.indexOf(next)), next]
      if (state.get(next) === undefined) {
        const found = walk(next)
        if (found !== null) return found
      }
    }
    path.pop()
    state.set(node, 'done')
    return null
  }

  for (const node of out.keys()) {
    if (state.get(node) === undefined) {
      const found = walk(node)
      if (found !== null) return found
    }
  }
  return null
}

What to actually do when two people update one row

The practical question, and it has four good answers and one bad one. The bad one is the code at the top of this post.

SELECT n FROM c WHERE id=1;
-- ... application adds one ...
UPDATE c SET n = 42 WHERE id = 1;

Why does an atomic UPDATE not need a transaction? It is already one. Every statement in a SQL database runs in a transaction whether you asked for one or not — BEGIN only lets you put several statements inside the same one. An UPDATE … SET n = n + 1 therefore does its read and its write with nothing able to intervene. The lost update in this post exists solely because the read and the write were in different transactions with your application’s thinking in between.

Two rules that are worth more than the table. Retry the whole transaction, not the write — re-read everything, recompute, and try again, because replaying the write with the stale value you already had is precisely the bug. And do nothing irreversible inside a transaction that may retry: a charged card or a sent email does not roll back, and a transaction that aborts twice will do it three times.

When the rows are on different machines

Everything above assumed one database could see every operation. Split the data across shards and the atomic-commit problem appears: shard A is ready to commit and shard B is not, and neither may decide alone.

Two-phase commit is the answer and is simpler than its reputation. A coordinator asks every participant to prepare; a participant that answers yes has promised it can commit no matter what happens next, and must hold its locks until told. When all have said yes, the coordinator writes its decision and tells them to commit.

Where it breaks: the coordinator dies after the prepare votes and before the decision. The participants cannot commit — the decision might have been abort — and cannot abort — it might have been commit. They hold their locks and wait, indefinitely, and no timeout is safe. This is why 2PC is called a blocking protocol, and the fix is not a cleverer protocol but a more reliable coordinator: replicate the coordinator’s decision log with consensus so it always comes back. That is exactly what Spanner does — two-phase commit layered over Paxos groups — and why 2PC deserves its reputation only when the coordinator is a single machine.

Who does what

The one-pager below carries the table. Three things about it matter more than the rows.

The names lie. PostgreSQL’s REPEATABLE READ is snapshot isolation, which is stronger than the standard’s repeatable read. Oracle’s SERIALIZABLE is snapshot isolation, which is weaker than the standard’s serializable — it will let write skew through. Setting your isolation level by the name in the SQL standard is not sufficient anywhere.

The defaults are weak. Read committed is the default in PostgreSQL, Oracle and SQL Server, and it permits lost updates. Most applications run there and most never find out, because the window is small and the losses are silent.

The distributed ones default to serializable and mean it. CockroachDB, YugabyteDB and FoundationDB will hand you a serialization failure under contention as a matter of routine, and code written against a read-committed database will not have the retry loop it needs.

Where this is, as of September 2026

Dated, because it moves.

• Serializable by default has gone mainstream in new systems and is spreading in old ones. The distributed SQL generation shipped it as the default; CockroachDB added read committed in 23.2 for applications migrating from PostgreSQL that could not tolerate retries, which is a nice illustration of the pressure running both ways.
• Deterministic and leaderless designs are the active research front. Calvin’s lineage removed 2PC by agreeing the order first; Cassandra’s Accord (CEP-15) is pursuing general transactions with no designated leader and one round trip in the common case. The prize in both cases is the coordination round trip, which is the dominant cost in every mechanism on this page.
• Checking has caught up. Elle (Kingsbury and Alvaro, 2020) infers which anomalies a real system exhibits from observed histories, without needing to search for a serial order. It found violations in shipping databases that their documentation denied, and it made “does this system actually provide what it claims” an answerable question rather than an argument.
• What has not changed: the anomaly-is-a-cycle result from 1976, and the fact that write skew separates snapshot isolation from serializability. Everything above is an engineering response to those two facts, and neither is going to move. ◆

◆ Version-specific claims about shipping products were accurate to the best of my checking at the time of writing and are the first thing to verify against your own deployment. The papers are stable; the products are not.

The whole thing, on one page

For revision, and for the afternoon you need the table rather than the argument. It prints.

Check yourself

Quick reference

Every abbreviation this post used, expanded, plus the neighbouring terms you will meet in the papers below. Ordered for lookup, not for reading.