Implementing Serializability

Three ways a database makes concurrent transactions behave as if they ran one at a time: actual serial execution, two-phase locking and serializable snapshot isolation, and what each one costs.

Overview

The goal and the three routes

Serializable isolation promises that the result of running transactions concurrently equals the result of running them in some order, one at a time. It is the only level that rules out every race, including write skew. Databases get there by one of three routes.

Actual serial execution — No concurrency — Cannot happen — Throughput of one thread per partition
Two-phase locking (2PL) — Pessimistic — The later transaction waits — Waiting and deadlocks
Serializable snapshot isolation (SSI) — Optimistic — One transaction is aborted — Retries under contention

Route 1: actual serial execution

Here the database runs a single thread that takes one transaction, finishes it, then takes the next. With nothing running in parallel, there is nothing to lock or check.

It only works when each transaction is short and never waits: the data it needs is in memory, and it does not stop halfway to ask the application what to do next. So these systems send the whole transaction to the server at once, as a stored procedure or a script.

Redis — Commands in a MULTI/EXEC block run in sequence; no other client's request runs in the middle
VoltDB (Volt Active Data) — Each stored procedure is one transaction; each partition runs them one at a time, without locks

In an interview, mention two details. First, Redis transactions have no rollback: if one command fails at run time, the rest still run. Second, a transaction that touches several partitions needs coordination between them, which is much slower than the single-partition case.

Route 2: two-phase locking

Two-phase locking (2PL) makes transactions wait for each other. A reader takes a shared lock on what it reads; a writer takes an exclusive lock on what it writes.

Shared — Granted — Waits
Exclusive — Waits — Waits

The two phases are the rule that gives the name. In the growing phase a transaction only acquires locks; once it releases any lock it enters the shrinking phase and may not take another. Databases normally go further and hold every lock until commit or abort (strict, or more precisely strong strict, 2PL), so no one ever sees uncommitted data. Eswaran, Gray, Lorie and Traiger showed in 1976 that consistency requires this rule: a transaction cannot request new locks after releasing a lock.

Readers blocking writers is the price. A long report that reads many rows holds shared locks on all of them, and every writer to those rows waits.

Locking also brings deadlocks: two transactions each hold a lock the other wants, and neither can move. The database finds the cycle and aborts one of them.

Locking rows that do not exist yet

Row locks cannot stop phantoms: a search that found nothing locked nothing. Serializable locking therefore needs to lock the search condition itself. A true predicate lock (lock 'all bookings for room 12 in May'), proposed in the same 1976 paper, is costly to check, so databases lock ranges of an index instead. InnoDB uses next-key locks, which lock an index record plus the gap before it, so no one can insert into a range another transaction has scanned. A range lock may cover more than the exact condition, which is safe but can block more than needed.

Row (record) lock — One existing row — Writes to that row
Gap lock — The space between two index entries — Inserts into that space
Next-key lock — A row plus the gap before it — Both of the above

InnoDB's SERIALIZABLE level is built this way: plain SELECTs become SELECT ... FOR SHARE when autocommit is off, so reads take shared locks.

Route 3: serializable snapshot isolation

Serializable snapshot isolation (SSI) is optimistic. Transactions run on snapshots, as under snapshot isolation, and nobody waits for readers. The database also tracks who read what. When one transaction writes data that a concurrent transaction read, it records a read-write dependency. Research by Fekete and colleagues showed that every non-serializable run under snapshot isolation contains a particular pattern: two such dependencies in a row, among concurrent transactions. Cahill, Röhm and Fekete turned that into SSI (2008), which aborts a transaction when the pattern appears.

PostgreSQL has used SSI for SERIALIZABLE since version 9.1. Its version works like this.

SIRead locks — Record what each serializable transaction read; they never block and cannot cause deadlocks
Conflict check — Spots the dangerous pattern and fails one transaction with SQLSTATE 40001
False positives — Some aborted transactions would have been fine; the check is conservative
Read-only transactions — Often need no read tracking at all; READ ONLY DEFERRABLE waits for a safe snapshot and then can never fail

Ports and Grittner report that PostgreSQL's SSI performs only slightly below plain snapshot isolation and well above two-phase locking on read-heavy workloads.

A long report is a good fit for the deferrable mode. First a small table, then the report.

Every client needs a retry loop

Under SSI any read-write transaction may be aborted. The client must rerun the whole transaction, including the reads that led to its decisions, not only the failing statement.

Choosing between them

Short transactions, data in memory, one partition each — Serial execution — No locks or aborts at all
Heavy contention on a few hot rows — 2PL — Waiting beats repeated aborts and wasted work
Mostly reads, occasional conflicting writes — SSI — Readers never block; aborts are rare
Long read-only reports — SSI with READ ONLY DEFERRABLE — No locks, and no risk of being aborted

In practice you choose a database and an isolation level; the mechanism comes with the product.

What you will be able to do

Name the three ways to implement serializability and the cost of each.
Explain the two phases of 2PL, why strict 2PL holds locks until commit, and how deadlocks are resolved.
Explain how index-range and next-key locks stop phantoms.
Explain how SSI detects unsafe patterns and why clients must retry on 40001.
Pick a mechanism for a given workload and defend the choice.

Key concepts

Serializability: The result of concurrent transactions equals the result of some order of running them one at a time.
Actual serial execution: One thread runs one transaction at a time, start to finish. Needs short transactions, data in memory and whole transactions sent at once.
Two-phase locking (2PL): Transactions take shared locks to read and exclusive locks to write, and never take a new lock after releasing one. Most databases hold all locks until the transaction ends (strong strict 2PL).
Deadlock: Two or more transactions each wait for a lock another one holds. The database detects the cycle and aborts one of them.
Next-key lock: An InnoDB lock on an index record plus the gap before it, which blocks inserts into a scanned range and so prevents phantoms.
Serializable snapshot isolation (SSI): Snapshot isolation plus tracking of read-write dependencies; a transaction is aborted when a pattern that could break serializability appears.
Read-write dependency: One transaction writes data that a concurrent transaction read, so the reader must come before the writer in any serial order.
SQLSTATE 40001: PostgreSQL's serialization_failure code. The client must roll back and rerun the whole transaction.

When to use it

Comparing pessimistic locking and optimistic conflict detection in a database internals question.
Explaining when single-threaded execution is enough, as in Redis or VoltDB.
Deciding whether a hot-row workload will suffer more from waiting or from aborts.
Designing client code that runs at SERIALIZABLE and must retry.

Interview questions

When would you choose SSI over 2PL?
Explain two-phase locking and why it prevents phantoms only with range locks.
When is actual serial execution a good design?
How does PostgreSQL implement SERIALIZABLE, and what must the application do?