Serializability
The only isolation level with no anomalies to memorise. Databases get there in three very different ways, by running one transaction at a time, by locking, or by letting everything run and checking afterwards, and each one fails in its own way.
The whole idea
What serializable means
The weak isolation levels each come with a list of anomalies you have to design around: lost updates, write skew, phantoms. That list is hard to apply. You have to look at every transaction in the application, imagine every other transaction that might run beside it, and spot the dangerous interleavings. Nobody does that reliably: the 2017 ACIDRain study found 22 exploitable races in 12 widely deployed e-commerce platforms.
Serializability throws the list away. It guarantees that the outcome of concurrent transactions is the same as if they had run one at a time, in some order. The database still runs them concurrently; it just promises you can’t tell. Postgres’s documentation puts the payoff well: if a transaction does the right thing when run by itself, it will do the right thing in any mix of serializable transactions, “or it will not successfully commit”.
The way to check a history is the one the hero diagram uses. Draw an arrow between two transactions whenever one must come before the other: T1 wrote something T2 then read, T1 overwrote something T2 had written, or T1 read something T2 later overwrote (a read-write dependency, the kind weak isolation forgets about). If the arrows never form a cycle, any topological order of them is an equivalent serial order. If they do, no serial order exists, and a serializable database must abort one of the transactions in the cycle.
There are three ways to build it, and almost every serializable database uses one of them or a hybrid:
- Actually run transactions one at a time.
- Two-phase locking: block anything that could create a cycle, before it happens.
- Optimistic schemes (serializable snapshot isolation, OCC): let everything run, and abort a transaction at commit if it took part in a conflict.
Actual serial execution
The bluntest answer is to remove concurrency altogether: one thread, one transaction at a time. For decades that was unthinkable, because transactions waited on disk. Two things changed. RAM became cheap enough to hold a whole OLTP data set, and OLTP transactions turned out to be short: a few reads and writes by key.
In 2007, Michael Stonebraker and colleagues argued in “The End of an Architectural Era” that a traditional database spends most of its time on machinery that exists only to juggle concurrent, disk-bound transactions. A 2008 study by Harizopoulos and colleagues measured it: starting from the Shore database running a subset of TPC-C in memory, they stripped out logging, latching, locking and buffer management one at a time and found about a 20× difference in raw performance, with “no single high pole in the tent”. The 2007 paper’s prototype, H-Store, became the commercial VoltDB (now Volt Active Data).
One thread per partition
It only works under strict conditions:
- Transactions must be submitted whole, as stored procedures (in VoltDB, Java or SQL). An interactive transaction that waits for the application between statements would leave the single thread idle and every other transaction queued behind it.
- Every transaction must be short. One slow transaction stalls the whole partition.
- The working set must fit in memory, or the thread waits on disk.
- Most transactions must touch one partition. Throughput scales with cores only if partitions run independently. A multi-partition transaction must be coordinated across all of them, and in VoltDB those are ordered through a single cluster-wide initiator, so they don’t get faster as the cluster grows.
- Stored procedures must be deterministic, because replicas re-execute them and must reach the same result.
You’ve probably used the idea without naming it. Redis executes commands on a single thread, so a Lua script
or a MULTI/EXEC block runs with nothing else interleaved, and a slow script stalls the entire server.
Two-phase locking
For about 30 years, two-phase locking (2PL), described by Eswaran, Gray, Lorie and Traiger in 1976, was the way to provide serializability. It strengthens the row locks that prevent dirty writes:
- Reading an object takes a shared lock. Many transactions can hold one at once.
- Writing takes an exclusive lock. Nobody else may hold any lock on the object.
- A transaction acquires locks as it goes (the growing phase) and releases them only at the end (the shrinking phase). In practice, databases use strong strict 2PL, which holds every lock, shared and exclusive, until commit or abort.
Two-phase locking
Snapshot isolation’s rule is “readers never block writers”. 2PL’s rule is the opposite, and that’s exactly what closes the write-skew hole: a transaction that has read a row holds a shared lock, so nobody can change the premise of its decision until it commits.
Phantoms need locks on things that don’t exist yet. The ideal is a predicate lock on the search condition
itself (show_id = 7, or room 12 AND 14:00–15:00), which conflicts with any write that would match it. Checking
every write against every active predicate is slow, so real databases approximate it with index-range locks,
also called next-key locks: lock the range of index entries the query scanned, or the gaps between them. If
there’s no suitable index, they fall back to locking the whole table. InnoDB uses next-key and gap locks this
way, and its SERIALIZABLE level turns every plain SELECT into SELECT … FOR SHARE when autocommit is off.
SQL Server’s SERIALIZABLE uses key-range locks.
The cost is performance, especially latency under contention. Transactions queue behind each other, and one slow transaction holding a lock on a hot row stalls everything that touches it. Because 2PL holds read locks, even an hour-long report blocks every writer to the rows it read.
Deadlocks
With so much locking, transactions often end up waiting on each other in a circle.
Deadlock
Databases handle this in one of two ways:
- Detect and break. The lock manager keeps a waits-for graph and looks for cycles. Postgres runs the check
after a transaction has waited
deadlock_timeout(1 second by default) and aborts a victim with SQLSTATE 40P01. InnoDB checks as soon as a transaction would wait; under very high concurrency the detector itself can become a bottleneck, so it can be turned off withinnodb_deadlock_detectin favour ofinnodb_lock_wait_timeout(50 seconds by default). - Prevent by priority. Give each transaction a timestamp and only let waits run in one direction between old and young, so a cycle can never form. In wait-die, a younger transaction that would wait aborts itself; in wound-wait, an older transaction that would wait aborts the younger lock holder. Google’s Spanner uses wound-wait for its read-write transactions.
Either way, the application sees an error and must retry the transaction. You can make deadlocks rarer by acquiring locks in a consistent order, for example always updating accounts in ascending ID order, and by keeping transactions short.
Serializable snapshot isolation
For a long time it looked like a forced choice: serializable but slow (2PL), or fast but weak (snapshot isolation). Serializable snapshot isolation (SSI), published by Michael Cahill, Uwe Röhm and Alan Fekete in 2008, removed most of that trade-off.
SSI keeps everything good about snapshot isolation: every transaction reads from a snapshot, and reads never block writes. On top, it watches for the one pattern snapshot isolation can’t see. Fekete and colleagues had proved in 2005 that every non-serializable history under snapshot isolation contains a dangerous structure: two consecutive read-write dependencies, T1 → T2 → T3, where T3 commits first (T1 and T3 may be the same transaction, as in write skew). SSI detects those and aborts.
SSI catches write skew
How Postgres implements it, since version 9.1 (2011), the first production implementation:
- Every read under Serializable leaves an SIRead lock on the tuples, pages or relation it read, and on index
ranges for phantoms. Despite the name, SIRead locks never block anyone; they show up in
pg_lockswith modeSIReadLock. - A write that lands on another transaction’s SIRead lock records a read-write dependency between them.
- When a transaction ends up with a dependency in and out, and the commit order makes it dangerous, Postgres aborts one of them with SQLSTATE 40001.
- SIRead locks must outlive the reader’s commit, because a dependency can form after the reader has committed.
Because SSI looks for the structure rather than the full cycle, it has false positives: it sometimes aborts a transaction that was actually safe. That rate rises when Postgres runs short of predicate-lock memory and promotes many tuple locks into one page or relation lock, and whenever a query does a sequential scan, which takes a lock on the entire relation.
Postgres’s SSI was built by Kevin Grittner and Dan Ports, who described it in a 2012 VLDB paper. Grittner’s motivation was the Wisconsin court system’s databases: hundreds of tables, more than 20 programmers writing new queries, and warrant data where a silent snapshot-isolation anomaly was unacceptable. Their benchmarks showed SSI costing less than 7% relative to snapshot isolation, and significantly outperforming two-phase locking on read-heavy workloads.
Read-only transactions get special treatment. A SERIALIZABLE READ ONLY DEFERRABLE transaction waits until it
can take a safe snapshot, one no concurrent transaction can turn into an anomaly, and then runs with no SSI
overhead and no risk of aborting: ideal for long reports and pg_dump.Even a read-only transaction can
observe a non-serializable state under plain snapshot isolation; Fekete, O’Neil and O’Neil published the example
in 2004. That’s why, under Postgres Serializable, data read by a transaction isn’t trustworthy until it commits,
unless it’s DEFERRABLE.
Optimistic concurrency control
SSI is one member of a broader family. Optimistic concurrency control (OCC), described by H. T. Kung and John Robinson in 1981, splits a transaction into three phases: a read phase that runs without locks and buffers writes privately, a validation phase at commit that checks whether anything it read has changed, and a write phase that publishes the buffered writes if validation passed.
Validate at commit
The design choice between pessimistic (2PL) and optimistic (OCC, SSI) concurrency control comes down to contention:
Waiting vs retrying
With little contention, optimism wins: nobody waits for locks that turned out not to be needed. With heavy contention on the same rows, optimistic transactions keep failing validation and redoing work, and if the system is near capacity, those retries add load exactly when there’s none to spare.
Two production systems show the range:
- FoundationDB provides strict serializability across a cluster with pure OCC. Each transaction reads at a
version, and at commit the cluster checks the key ranges it read against writes committed since; a conflict
fails the commit with
not_committed, and the client library’s retry loop runs the transaction again. Transactions are limited to five seconds, which keeps validation windows short and the abort rate down. - CockroachDB defaults to
SERIALIZABLE. It’s a hybrid. Writes leave write intents, provisional values that double as exclusive locks, and a timestamp cache remembers the latest read of each key. A write that lands under a later read is pushed to a later timestamp; the transaction then refreshes its reads to check they’re still valid at the new timestamp, and if they aren’t, it fails with a retryable 40001 error. CockroachDB retries single statements, and statements sent as one batch, automatically while their results still fit in the server-side results buffer (512 KiB by default since v24.1, 16 KiB before); anything else needs a retry loop in the client. Since 2024 it has also offeredREAD COMMITTED, which accepts some anomalies in exchange for fewer aborts and no client-side retries.
Trade-offs
| Actual serial execution | Two-phase locking | SSI / OCC | |
|---|---|---|---|
| Conflicting transactions | queue on one thread | block each other | run in parallel; one aborts at commit |
| Reads block writes? | everything waits its turn | yes | no |
| Failure mode | one slow or cross-partition transaction stalls everything | lock queues, deadlocks, long tail latency | abort and retry storms under contention, false positives |
| Works best when | short, in-memory, single-partition | contention is high | reads dominate and contention is low or moderate |
| Examples | VoltDB, Redis scripts | MySQL and SQL Server SERIALIZABLE, Spanner read-write transactions |
Postgres SERIALIZABLE, FoundationDB, CockroachDB |
In the real world
- Postgres’s SSI had a bug for nine years. In 2020, Jepsen tested Postgres 12.3 and found that Serializable transactions on a single healthy node could exhibit G2-item, the write-skew cycle Serializable exists to prevent. Peter Geoghegan traced it to a corner of conflict detection, present since SSI shipped in 2011, that could attribute a tuple to the wrong transaction. It was fixed in the August 2020 minor releases. The same report pointed out that Repeatable Read is snapshot isolation and incomparable with ANSI Repeatable Read.
- VoltDB under faults. Jepsen’s 2016 analysis of VoltDB 6.3 found stale reads, dirty reads and lost updates during network partitions and recovery, for example a read served by a node that had been cut off from the majority. VoltDB 6.4 fixed them, and Jepsen judged that it “appears to provide strict serializability”. A correct serial executor is only as safe as the replication and recovery around it.
- MySQL’s Serializable is the safe one. Jepsen’s 2023 MySQL analysis found its Repeatable Read violated
snapshot isolation, while Read Uncommitted, Read Committed and Serializable appeared to meet their definitions
on a healthy single node. On AWS RDS MySQL clusters, though, even Serializable showed read skew and write skew,
likely because replicas applied transactions in a different order (
replica_preserve_commit_orderwas off by default). - Retries are part of the contract. Postgres, CockroachDB and FoundationDB all report conflicts as errors the client must handle by rerunning the whole transaction. FoundationDB’s client bindings build the retry loop in, so application code is written as a function the library may call more than once.
Pitfalls
- Serializable without a retry loop. At this level, aborts are the mechanism, not a malfunction. Catch SQLSTATE 40001 (and 40P01 for deadlocks) and rerun the whole transaction, with backoff.
- Side effects inside the transaction. If a retried transaction sends an email or calls a payment API, the retry does it twice. Do side effects after commit, or make them idempotent.
- Long transactions. Under 2PL they hold locks; under SSI they accumulate dependencies and false positives; under OCC they’re more likely to fail validation (FoundationDB simply refuses them past five seconds).
- Mixing isolation levels. SSI protects transactions that run at Serializable. A Read Committed transaction writing the same rows isn’t tracked, and can still break the invariant.
- Trusting reads from an aborted transaction. Under Postgres Serializable, data a transaction read isn’t valid
until it commits, unless the transaction is
READ ONLY DEFERRABLE. - Assuming serializable means fresh. It guarantees some serial order, not real-time order. Use a strictly serializable system, or read from the leader, when a read must reflect every earlier commit.
- Inconsistent lock order. Two code paths updating the same rows in different orders are a deadlock waiting to happen. Sort before you lock.
Recall
Go deeper
- Cahill, Röhm & Fekete, “Serializable Isolation for Snapshot Databases” (SIGMOD 2008): the SSI algorithm, and why detecting dangerous structures is enough.
- Ports & Grittner, “Serializable Snapshot Isolation in PostgreSQL” (VLDB 2012): how SSI was built into a real database, with its read-only optimisations and benchmarks against 2PL.
- Harizopoulos et al., “OLTP Through the Looking Glass, and What We Found There” (SIGMOD 2008): where the time goes in a traditional OLTP engine, and the case for serial execution.
- Kung & Robinson, “On Optimistic Methods for Concurrency Control” (ACM TODS 1981): the read, validate, write phases that every optimistic system still follows.
- PostgreSQL docs: Serializable Isolation Level: how SSI behaves in practice and how to keep false aborts down.
- CockroachDB docs: Transaction Layer: write intents, the timestamp cache, read refreshing and parallel commits.
- Jepsen, “PostgreSQL 12.3” (2020): how a serializability bug was found with the Elle checker, and what Postgres’s levels really are.
- FoundationDB docs: Developer Guide: optimistic concurrency, conflict ranges and the five-second limit, from the user’s side.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Distributed Transactions (committing atomically across machines, two-phase commit and sagas) and Consistency Models (linearizability, and how it differs from serializability).