On this page

Concurrency Control: Schedules, Locking & Serializability

A database serving a thousand concurrent transactions has to make each of them believe it is alone. That illusion is isolation, the "I" in ACID, and the machinery that produces it is concurrency control. It is the part of a DBMS that decides, operation by operation, which transaction may proceed, which must wait, and which must be aborted.

The practical side of this, which isolation levels exist, what anomalies each permits and how to use SELECT ... FOR UPDATE, is covered in Transactions Basics and Isolation Levels. This page is the theory underneath: the formal definition of "correct" (serializability), how to test a schedule for it (precedence graphs), and the classic algorithms that guarantee it (two-phase locking, timestamp ordering, optimistic validation). It is the material in every university DBMS course and a common source of CS-fundamentals interview questions. At the end we map the theory onto what PostgreSQL and MySQL InnoDB actually run.

Why Concurrency Control Exists

Running transactions one after another (serially) is trivially correct and terribly slow: while one transaction waits for a disk read or a network round trip, the CPU and every other client sit idle. Interleaving transactions improves throughput and response time. But arbitrary interleaving produces wrong answers. The three classic problems:

ProblemInterleavingResult
Lost updateT1 reads X, T2 reads X, T1 writes X, T2 writes XT1's update is overwritten as if it never happened
Dirty read (temporary update)T1 writes X, T2 reads X, T1 abortsT2 acted on a value that never existed
Unrepeatable read / inconsistent analysisT1 reads X, T2 writes X and commits, T1 reads X againT1 sees two different values, or sums a mix of old and new

A fourth, the phantom, is a variant of the unrepeatable read where rows that match a predicate appear or disappear (another transaction inserts a new row matching WHERE dept = 'CS'). It needs special handling because there was no existing row to lock.

Transactions and Schedules

For analysis we abstract a transaction to the sequence of reads and writes it performs on data items, followed by commit or abort. We write:

  • R1(A): transaction T1 reads item A
  • W1(A): T1 writes item A
  • C1 / A1: T1 commits / aborts

An item can be a row, a page, a table, anything the system locks or versions. The computation between reads and writes is ignored; we assume the worst (that every write depends on every previous read).

A schedule (or history) is an interleaving of the operations of several transactions that preserves the order of operations within each transaction.

T1: R1(A) W1(A) R1(B) W1(B)          (transfer 100 from A to B)
T2: R2(A) W2(A) R2(B) W2(B)          (add 10% interest to A and B)

Serial schedule T1, T2:
  R1(A) W1(A) R1(B) W1(B) R2(A) W2(A) R2(B) W2(B)

An interleaved (concurrent) schedule:
  R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)

A serial schedule runs transactions one at a time with no interleaving. n transactions have n! serial schedules, and every serial schedule is considered correct, even though different serial orders can produce different final states (interest-then-transfer gives a different balance than transfer-then-interest). Correctness means "equivalent to some serial order", not "equivalent to a particular one".

Serializability

A schedule is serializable if its effect is equivalent to some serial schedule of the same transactions. That is the gold standard of correctness, and it is what the SQL SERIALIZABLE isolation level promises.

"Equivalent" needs a precise definition. There are two, and they lead to two classes of schedules.

Conflicts and Conflict Serializability

Two operations conflict if all three hold:

  1. They belong to different transactions,
  2. They access the same item,
  3. At least one is a write.
PairConflict?Why it matters
R1(A), R2(A)NoReads commute; order is irrelevant
R1(A), W2(A)Yes (read-write)Whether T1 sees T2's value depends on order
W1(A), R2(A)Yes (write-read)Whether T2 sees T1's value depends on order
W1(A), W2(A)Yes (write-write)The final value of A depends on order
R1(A), W2(B)NoDifferent items

Swapping two adjacent non-conflicting operations never changes the outcome. Two schedules are conflict equivalent if one can be turned into the other by a sequence of such swaps, or equivalently, if they order every pair of conflicting operations the same way. A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

The Precedence Graph Test

Swapping by hand is tedious. The standard test is the precedence graph (also called the serialization graph or conflict graph):

  1. One node per committed transaction.
  2. For each pair of conflicting operations Oi (from Ti) before Oj (from Tj) in the schedule, draw an edge Ti → Tj: "Ti must come before Tj in any equivalent serial order".
  3. The schedule is conflict serializable if and only if the graph is acyclic.
  4. If it is acyclic, any topological sort of the graph is an equivalent serial order.

Worked Example 1: Serializable, but Not in Index Order

Step:  1      2      3      4      5      6
       R1(A)  R2(B)  W2(A)  R3(B)  W3(C)  R1(C)

List every conflicting pair (same item, different transactions, at least one write):

ItemOperations in orderConflicting pairsEdge
AR1(A) at 1, W2(A) at 3R1(A) before W2(A)T1 → T2
BR2(B) at 2, R3(B) at 4Two reads: no conflictnone
CW3(C) at 5, R1(C) at 6W3(C) before R1(C)T3 → T1
flowchart LR
  T3(("T3")) --> T1(("T1"))
  T1 --> T2(("T2"))

The graph is acyclic, so the schedule is conflict serializable. The only topological order is T3, T1, T2. Notice this is not T1, T2, T3: the equivalent serial order has nothing to do with transaction numbering or start time. T1 started first, but it read C after T3 wrote it, so T3 must logically precede T1.

Worked Example 2: Adding One Operation Creates a Cycle

Append one more operation to the same schedule:

Step:  1      2      3      4      5      6      7
       R1(A)  R2(B)  W2(A)  R3(B)  W3(C)  R1(C)  W1(B)

New conflicts on B: R2(B) at 2 before W1(B) at 7 gives T2 → T1, and R3(B) at 4 before W1(B) at 7 gives T3 → T1 (already present).

flowchart LR
  T3(("T3")) --> T1(("T1"))
  T1 -->|"R1(A) before W2(A)"| T2(("T2"))
  T2 -->|"R2(B) before W1(B)"| T1

T1 → T2 → T1 is a cycle. No serial order can put T1 both before and after T2, so the schedule is not conflict serializable. Concretely: T2 read B before T1 changed it (so T2 "saw the world before T1"), but T1 read A before T2 changed it (so T1 "saw the world before T2"). Each transaction saw a state without the other's effects, which no serial execution can produce. This is the shape of write skew.

Worked Example 3: The Interleaved Transfer

The interleaved schedule from earlier, R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B):

  • On A: W1(A) before R2(A), W1(A) before W2(A), R1(A) before W2(A). All give T1 → T2.
  • On B: the same pattern. All give T1 → T2.

The graph is the single edge T1 → T2, so the schedule is conflict equivalent to T1, T2. Interleaving was harmless here because T2 always touched each item after T1 finished with it. Now try R1(A) R2(A) W1(A) W2(A) ...: R2(A) before W1(A) gives T2 → T1, and W1(A) before W2(A) gives T1 → T2. A cycle: that is the lost update.

View Serializability

Conflict serializability is sufficient but slightly too strict. View serializability is a weaker (more permissive) definition. Two schedules S and S' over the same transactions are view equivalent if:

  1. Same initial reads. If Ti reads the initial value of A in S, it does so in S'.
  2. Same reads-from. If Ti reads a value of A written by Tj in S, it reads the value written by Tj in S'.
  3. Same final writes. The transaction that performs the last write on A in S does so in S'.

Intuitively, every transaction sees the same values and the database ends in the same state. A schedule is view serializable if it is view equivalent to some serial schedule.

Every conflict-serializable schedule is view serializable, but not vice versa. The difference is entirely due to blind writes, writes of an item the transaction never read.

Worked Example 4: View Serializable but Not Conflict Serializable

R1(A)  W2(A)  W1(A)  W3(A)

Precedence graph: R1(A) before W2(A) gives T1 → T2; W2(A) before W1(A) gives T2 → T1. Cycle, so not conflict serializable.

Now check view equivalence against the serial schedule T1, T2, T3 = R1(A) W1(A) W2(A) W3(A):

ConditionConcurrent scheduleSerial T1, T2, T3Same?
Initial read of AT1T1Yes
Reads-fromNone otherNone otherYes
Final write of AT3T3Yes

So it is view serializable. T2's and T1's writes are both overwritten by T3 without anyone reading them, so their order does not matter. The precedence graph cannot see that.

Why Databases Use Conflict Serializability Anyway

Conflict serializabilityView serializability
TestPrecedence graph cycle check, polynomial timeNP-complete in general
RelationshipStrict subsetSuperset (adds schedules with blind writes)
Used in practiceYes: 2PL, SSI and timestamp ordering all target itNo; theoretical, except that the Thomas write rule produces some view-serializable schedules
flowchart TB
  subgraph ALL["All schedules"]
    subgraph VS["View serializable"]
      subgraph CS["Conflict serializable"]
        SER["Serial"]
      end
    end
  end

Recoverability

Serializability is about concurrent correct transactions. Recoverability is about what happens when a transaction aborts. A serializable schedule can still be unacceptable if it lets a committed transaction depend on one that later aborts.

Say Tj reads from Ti if Tj reads a value of an item that Ti wrote, and Ti has not aborted in between.

ClassDefinitionExampleProblem it avoids
RecoverableIf Tj reads from Ti, then Ti commits before Tj commitsW1(A) R2(A) C1 C2A committed transaction depending on an aborted one, which would have to be "un-committed"
Cascadeless (avoids cascading aborts, ACA)Transactions only read values written by committed transactionsW1(A) C1 R2(A) C2One abort forcing a chain of other aborts
StrictNo transaction reads or writes an item until the last transaction that wrote it has committed or abortedW1(A) C1 W2(A) C2Undo by restoring before-images becomes correct

Non-recoverable example:

W1(A)  R2(A)  W2(B)  C2  A1

T2 read A from T1 and committed. Then T1 aborts, so the value T2 read never existed. T2 is already committed and durable; the system cannot undo it. This schedule must be forbidden.

Recoverable but cascading:

W1(A)  R2(A)  W2(B)  A1  ...

T2 has not committed yet, so when T1 aborts, T2 can (and must) be aborted too. If T3 had read B from T2, T3 must also abort. That is a cascading abort, potentially unbounded work.

Cascadeless but not strict:

W1(A)  W2(A)  A1

No one read uncommitted data, so there are no cascades. But T2 overwrote T1's uncommitted value. If T1 now aborts and the system "undoes" W1(A) by restoring the before-image (A's value before T1), it erases T2's write too. Strictness forbids W2(A) until T1 finishes, which is what makes simple before-image undo in the log correct. See Write-Ahead Logging for how recovery uses those images.

The classes nest: Strict ⊂ Cascadeless ⊂ Recoverable. They are independent of serializability: a schedule can be serializable and non-recoverable, or strict and non-serializable. Real systems want both properties at once, and strict two-phase locking delivers both.

Locking

The most common way to enforce serializability is to make transactions lock items before touching them, so that conflicting operations cannot interleave.

Shared and Exclusive Locks

LockAlso calledNeeded toOthers may also hold
SShared, read lockRead the itemS
XExclusive, write lockWrite (or read and write) the itemNothing

Lock compatibility matrix (can a transaction be granted the requested lock when another transaction holds the existing one?):

Requested ↓ / Held →SX
SYesNo
XNoNo

A transaction that holds S and wants to write must upgrade to X, which is granted only if no one else holds S. Two transactions both holding S on the same item and both trying to upgrade will deadlock: this "upgrade deadlock" is why some systems offer update (U) locks, which are compatible with S but not with other U locks, so only one transaction can be waiting to upgrade.

Locking Alone Is Not Enough

Locking each item just for the duration of each operation does not guarantee serializability:

T1: X-lock(A) R1(A) W1(A) unlock(A)                       X-lock(B) R1(B) W1(B) unlock(B)
T2:                                  S-lock(A) S-lock(B) R2(A) R2(B) unlock(A,B)

T2 sees A after the transfer debit and B before the credit: money has vanished from its view. Every individual access was properly locked. The problem is that T1 released a lock and then acquired another, letting T2 slip in between.

Two-Phase Locking (2PL)

Two-phase locking fixes this with one rule: a transaction may not acquire any lock after it has released any lock. Each transaction therefore has two phases:

  1. Growing phase: acquire locks, release none.
  2. Shrinking phase: release locks, acquire none.

The moment of the last acquisition is the transaction's lock point.

xychart-beta
  title "Locks held over time under basic 2PL"
  x-axis ["t1", "t2", "t3", "t4", "t5", "t6", "t7", "t8"]
  y-axis "Locks held" 0 --> 5
  line [1, 2, 3, 4, 4, 3, 1, 0]

Theorem: every schedule produced by 2PL is conflict serializable, and an equivalent serial order is the order of the transactions' lock points.

Proof sketch: suppose the precedence graph had a cycle T1 → T2 → ... → Tn → T1. An edge Ti → Tj means Ti released a lock on some item that Tj later acquired, so Ti's lock point comes before Tj's. Following the cycle, T1's lock point precedes itself. Contradiction.

The Variants

VariantRuleSerializableRecoverable / strictDeadlock-freeNotes
Basic 2PLGrowing then shrinkingYesNo: can release an X lock before commit, letting others read dirty dataNoRarely used as-is
Strict 2PLBasic 2PL + hold all X locks until commit/abortYesYes, schedules are strictNoThe textbook standard
Rigorous 2PL (strong strict)Hold all locks (S and X) until commit/abortYesYes, strictNoSerial order = commit order, which simplifies distributed commit and replication
Conservative 2PL (static)Acquire every lock needed before starting; take all or noneYesDepends on release policyYesNeeds to know the read/write set in advance; low concurrency
flowchart LR
  B["Basic 2PL: serializable, but cascading aborts possible"] --> S["Strict 2PL: X locks held to commit, strict schedules"]
  S --> R["Rigorous 2PL: all locks held to commit, order = commit order"]
  B --> C["Conservative 2PL: lock everything up front, no deadlocks"]

In practice, "2PL" in a real database almost always means strict or rigorous 2PL, because releasing locks before commit buys little and costs recoverability. MySQL InnoDB holds row locks until commit; so does PostgreSQL for row locks taken by UPDATE, DELETE and SELECT ... FOR UPDATE.

Worked Example: 2PL Preventing the Lost Update

Time  T1                         T2
 1    X-lock(A)  granted
 2    R1(A) = 500
 3                               X-lock(A)  WAIT (T1 holds X)
 4    W1(A) = 400
 5    COMMIT, release X(A)
 6                               X-lock(A)  granted
 7                               R2(A) = 400
 8                               W2(A) = 450
 9                               COMMIT

T2 waits at step 3 and then reads the committed 400, not the stale 500. In SQL, this is exactly what SELECT ... FOR UPDATE does:

BEGIN;
SELECT balance FROM account WHERE account_id = 1 FOR UPDATE;   -- X lock on the row
UPDATE account SET balance = balance - 100 WHERE account_id = 1;
COMMIT;                                                         -- lock released here

Useful locking clauses (PostgreSQL; MySQL 8.0 supports the same FOR UPDATE / FOR SHARE / NOWAIT / SKIP LOCKED):

ClauseLockBehaviour on conflict
FOR UPDATEExclusive row lockWait
FOR NO KEY UPDATE (PostgreSQL)Weaker exclusive lock that does not block FK checksWait
FOR SHAREShared row lock (MySQL also accepts LOCK IN SHARE MODE)Wait
FOR KEY SHARE (PostgreSQL)Blocks only key changes and deletes; taken by FK checksWait
... NOWAITas aboveError immediately
... SKIP LOCKEDas aboveSkip locked rows (job queues)

Lock Granularity and Intention Locks

What is "an item"? Locking at row level maximizes concurrency but means a transaction scanning a billion-row table needs a billion locks. Locking at table level is cheap but serializes everything. Real systems lock at several granularities in a hierarchy:

flowchart TD
  DB["Database"] --> T1["Table: account"]
  DB --> T2["Table: orders"]
  T1 --> P1["Page 1"]
  T1 --> P2["Page 2"]
  P1 --> R1["Row 1"]
  P1 --> R2["Row 2"]
  P2 --> R3["Row 3"]

The problem: if T1 holds an X lock on row 3 and T2 wants an S lock on the whole account table, how does T2 find out about the conflict without checking every row lock? Multiple-granularity locking (Gray et al., 1975) solves this with intention locks placed on ancestors:

ModeMeaning
IS (intention shared)I intend to take S locks on some descendants
IX (intention exclusive)I intend to take X (or S) locks on some descendants
SShared lock on this node and, implicitly, all descendants
SIX (shared + intention exclusive)S on the whole node, plus I will X-lock some descendants. Typical for "scan the table, update a few rows"
XExclusive lock on this node and all descendants

Compatibility matrix:

Requested ↓ / Held →ISIXSSIXX
ISYesYesYesYesNo
IXYesYesNoNoNo
SYesNoYesNoNo
SIXYesNoNoNoNo
XNoNoNoNoNo

Protocol:

  1. Lock the root first, then go down the hierarchy.
  2. To get S or IS on a node, hold IS or IX on its parent.
  3. To get X, IX or SIX on a node, hold IX or SIX on its parent.
  4. Release bottom-up (children before parents), following 2PL.

Now T1 updating row 3 takes IX on the database, IX on account, IX on page 2, X on row 3. T2 asking for S on account checks the table node, sees IX, and the matrix says S vs IX is incompatible: wait. One check instead of a billion.

Two ideas often paired with granularity:

  • Lock escalation. When a transaction accumulates too many fine-grained locks, the system replaces them with one coarser lock. SQL Server escalates at around 5,000 locks on one object. PostgreSQL and InnoDB do not escalate row locks: PostgreSQL stores row locks in the tuple header itself (not in shared memory), and InnoDB stores them as compact bitmaps per page, so both can hold millions cheaply.
  • Table-level intention locks in practice. InnoDB takes IS/IX table locks automatically before row locks, exactly as above. PostgreSQL has eight table lock modes (from ACCESS SHARE for SELECT up to ACCESS EXCLUSIVE for DROP TABLE and most ALTER TABLE); ROW SHARE and ROW EXCLUSIVE play the role of IS and IX.
-- PostgreSQL: who holds or waits for which locks right now
SELECT l.locktype, l.relation::regclass, l.mode, l.granted, a.pid, a.query
FROM pg_locks l
JOIN pg_stat_activity a ON a.pid = l.pid
WHERE a.datname = current_database()
ORDER BY l.granted, a.pid;

-- MySQL 8.0
SELECT * FROM performance_schema.data_locks;
SELECT * FROM performance_schema.data_lock_waits;

ALTER TABLE and the lock queue

In PostgreSQL, most ALTER TABLE forms need ACCESS EXCLUSIVE, which conflicts with everything, including plain SELECT. If a long-running query holds ACCESS SHARE, the ALTER waits, and every new query behind it queues behind the ALTER. A two-millisecond schema change can take the table offline for as long as the slowest open transaction. Always set lock_timeout before DDL on busy tables. See Database Migrations.

The Phantom Problem

Row locks protect rows that exist. They cannot protect rows that do not exist yet.

T1: SELECT count(*) FROM enrolled WHERE cid = 'CS340';     -- 30, S-locks those 30 rows
T2: INSERT INTO enrolled VALUES (77, 'CS340', NULL);       -- new row, nothing to conflict with
T2: COMMIT;
T1: SELECT count(*) FROM enrolled WHERE cid = 'CS340';     -- 31: a phantom

Even with strict 2PL on rows, this schedule is not serializable. The fix is to lock the predicate "cid = 'CS340'" rather than individual rows:

  • Predicate locking in its general form (lock arbitrary logical conditions, check every write against every held predicate) is expensive and practically unused.
  • Index-range locking (key-range locking) is the practical version: lock the range in an index that the predicate covers, including the gaps between keys, so inserts into that range block. This is what InnoDB's next-key locks do.
  • Table locking works too, at the cost of concurrency.

PostgreSQL's SSI uses a variant called SIREAD locks on index ranges and pages, which do not block but are used to detect dangerous patterns (more below).

Deadlocks

Locking introduces waiting, and waiting introduces cycles.

sequenceDiagram
  participant T1
  participant DB as Lock manager
  participant T2
  T1->>DB: X-lock row A
  DB-->>T1: granted
  T2->>DB: X-lock row B
  DB-->>T2: granted
  T1->>DB: X-lock row B
  Note over T1,DB: T1 waits for T2
  T2->>DB: X-lock row A
  Note over DB,T2: T2 waits for T1, a cycle
  DB-->>T2: ERROR deadlock detected, T2 aborted
  DB-->>T1: granted row B

In SQL:

-- Session 1                                  -- Session 2
BEGIN;                                        BEGIN;
UPDATE account SET balance = balance - 10
  WHERE account_id = 1;
                                              UPDATE account SET balance = balance - 10
                                                WHERE account_id = 2;
UPDATE account SET balance = balance + 10
  WHERE account_id = 2;      -- waits
                                              UPDATE account SET balance = balance + 10
                                                WHERE account_id = 1;  -- deadlock
-- PostgreSQL: ERROR: deadlock detected
--   DETAIL: Process 4211 waits for ShareLock on transaction 9012; blocked by process 4219.
-- MySQL: ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

The four Coffman conditions for deadlock are mutual exclusion, hold-and-wait, no preemption and circular wait. Every strategy below breaks one of them.

Detection: The Wait-For Graph

The lock manager maintains a wait-for graph: a node per active transaction, an edge Ti → Tj when Ti waits for a lock Tj holds. A deadlock exists if and only if the graph has a cycle.

flowchart LR
  T1(("T1")) -->|"waits for row B"| T2(("T2"))
  T2 -->|"waits for row C"| T3(("T3"))
  T3 -->|"waits for row A"| T1
  T4(("T4")) -->|"waits for row C"| T3

T1, T2 and T3 form a cycle. T4 is waiting but not deadlocked: it will proceed once T3 finishes. To break the cycle, the system picks a victim in it and aborts it. Common victim-selection criteria: the youngest transaction, the one that has done the least work (fewest log records or locks), the one closest to the cheapest rollback, or one that has not already been a victim many times (to prevent starvation).

When to run detection is a trade-off. PostgreSQL waits deadlock_timeout (default 1 s) before checking, on the theory that most lock waits resolve on their own and graph searches are not free. InnoDB checks immediately on every wait (innodb_deadlock_detect = ON), which under extremely high contention on one row can itself become a bottleneck; some high-throughput deployments turn it off and rely on innodb_lock_wait_timeout (default 50 s) instead.

Prevention: Wait-Die and Wound-Wait

Prevention schemes ensure a cycle can never form, by giving each transaction a timestamp when it starts (older = smaller timestamp) and only allowing waits in one direction of age. Suppose Ti requests a lock held by Tj:

SchemeIf Ti is older than TjIf Ti is younger than TjPreemptive?
Wait-dieTi waitsTi dies (aborts, restarts later)No: only the requester is ever aborted
Wound-waitTi wounds Tj (Tj aborts)Ti waitsYes: the holder may be aborted

Mnemonic: the first word says what an older requester does. In wait-die, the old wait and the young die. In wound-wait, the old wound and the young wait.

In both schemes, waits only go one way by age (wait-die: old waits for young; wound-wait: young waits for old), so the wait-for graph can never have a cycle. A restarted transaction keeps its original timestamp, so it gets older relative to newcomers and eventually becomes the oldest, guaranteeing it will not starve.

Worked example. T5 (timestamp 5), T10 and T15 (younger). T10 holds a lock on A.

RequestWait-dieWound-wait
T5 requests A (older than holder T10)T5 waitsT10 is wounded and aborts; T5 gets A
T15 requests A (younger than holder T10)T15 dies, restarts with timestamp 15T15 waits

Wait-die tends to abort more transactions (young ones die repeatedly while an old one holds the lock) but each abort is cheap, since the dying transaction has usually done little. Wound-wait aborts fewer but may abort a transaction that has done a lot of work. Google Spanner uses wound-wait.

Other Approaches

ApproachHowTrade-off
TimeoutAbort any transaction that waits longer than N secondsSimple; may abort transactions that were not deadlocked, and real deadlocks wait the full timeout
Lock orderingAll transactions acquire locks in a global order (e.g. by primary key)Breaks circular wait entirely; needs application discipline
Conservative 2PLTake all locks up frontBreaks hold-and-wait; needs the full read/write set in advance
No-waitAbort immediately on any conflict (NOWAIT)Never deadlocks; high abort rate under contention

The practical rule

Applications should lock rows in a consistent order (sort the account IDs before updating them), keep transactions short, and retry on deadlock errors (40P01 in PostgreSQL, 1213 in MySQL), because the database will abort a victim and expects the client to try again. Treat a deadlock as a retryable conflict, not a crash.

-- Lock both accounts in id order, regardless of transfer direction
BEGIN;
SELECT account_id FROM account
WHERE account_id IN (7, 3)
ORDER BY account_id
FOR UPDATE;
UPDATE account SET balance = balance - 100 WHERE account_id = 7;
UPDATE account SET balance = balance + 100 WHERE account_id = 3;
COMMIT;

Timestamp Ordering

Locking decides the serial order dynamically (by lock points). Timestamp ordering (TO) decides it in advance: each transaction gets a unique timestamp TS(T) when it starts, and the schedule must be equivalent to the serial order of timestamps. No locks, so no deadlocks; instead, transactions that would violate the order are aborted and restarted with a new timestamp.

Each item X carries two values:

  • R-TS(X): the largest timestamp of any transaction that has read X
  • W-TS(X): the largest timestamp of any transaction that has written X

Rules for transaction T:

T wants toCheckIf check failsIf check passes
Read XTS(T) < W-TS(X)? (a younger transaction already wrote X, so T would read "the future")Abort T, restart with new timestampRead; R-TS(X) = max(R-TS(X), TS(T))
Write XTS(T) < R-TS(X)? (a younger transaction already read the old value, and needed T's write)Abort Tcontinue to the next check
TS(T) < W-TS(X)? (a younger transaction already wrote X)Abort T (basic TO), or ignore the write (Thomas write rule)Write; W-TS(X) = TS(T)

Worked Example

TS(T1) = 10, TS(T2) = 20. Initially R-TS(A) = W-TS(A) = 0.

StepOperationCheckOutcomeR-TS(A)W-TS(A)
1R1(A)10 < W-TS 0? NoRead OK100
2R2(A)20 < 0? NoRead OK200
3W2(A)20 < R-TS 20? No. 20 < W-TS 0? NoWrite OK2020
4W1(A)10 < R-TS 20? YesAbort T12020

T1 is older, so in the timestamp serial order it comes first. But T2 already read A expecting to see T1's write (because in the serial order T1 precedes T2), and T1's write is now too late. T1 must abort and restart as, say, T30.

The Thomas Write Rule

Change the scenario: T2 writes A without reading it, and T1 writes later.

StepOperationBasic TOThomas write rule
1W2(A), TS 20OK, W-TS = 20OK, W-TS = 20
2W1(A), TS 1010 < W-TS 20: abort T110 < R-TS 0? No. 10 < W-TS 20: skip the write, T1 continues

In the serial order (T1 then T2), T1's write would have been immediately overwritten by T2's, and nobody read it in between (R-TS check passed). So the write is obsolete and can safely be discarded. The Thomas write rule allows some schedules that are view serializable but not conflict serializable, the blind-write case from Example 4.

Properties of Timestamp Ordering

  • Serializable: equivalent to the timestamp order.
  • Deadlock-free: nobody waits.
  • Not recoverable by default: T2 can read a value written by T1 and commit before T1 commits. Real implementations add a commit bit and make readers of uncommitted data wait (strict TO), which reintroduces waiting.
  • Starvation: a long transaction can be aborted repeatedly by short younger ones.
  • Overhead: every read updates R-TS, turning reads into writes on shared metadata.

Pure TO is rare in mainstream databases, but its core idea (order transactions by timestamp, keep per-item timestamps) is the foundation of multiversion timestamp ordering (MVTO) and of MVCC generally.

Optimistic Concurrency Control (OCC)

Locking is pessimistic: it assumes conflicts are likely and prevents them up front. Optimistic concurrency control (Kung and Robinson, 1981) assumes conflicts are rare and checks for them only at the end. Each transaction runs in three phases:

  1. Read phase. Execute, reading from the database and writing into a private workspace. Track the read set RS(T) and write set WS(T).
  2. Validation phase. At commit, check whether T conflicts with transactions that committed while it ran.
  3. Write phase. If validation succeeded, apply the private writes to the database. Otherwise abort and restart.

Each transaction gets its timestamp at the start of validation, and the serial order is the validation order.

stateDiagram-v2
  [*] --> Read: BEGIN
  Read --> Validate: COMMIT requested
  Validate --> Write: no conflicts
  Validate --> Read: conflict, abort and restart
  Write --> [*]: committed

Backward validation. For transaction Tj validating, check each Ti that validated earlier and overlapped with Tj. Tj passes if, for every such Ti, one of these holds:

  1. Ti finished its write phase before Tj started its read phase (no overlap at all), or
  2. Ti finished its write phase before Tj starts its write phase, and WS(Ti) ∩ RS(Tj) = ∅ (Tj did not read anything Ti wrote), or
  3. Ti finished its read phase before Tj finished its read phase, and WS(Ti) ∩ RS(Tj) = ∅ and WS(Ti) ∩ WS(Tj) = ∅.

Worked example. T1 and T2 start together. T1 reads {A, B}, writes {A}. T2 reads {B, C}, writes {C}. T1 validates first and commits. T2 validates: WS(T1) ∩ RS(T2) = {A} ∩ {B, C} = ∅. Pass. Now change T2 to read {A, C}: {A} ∩ {A, C} = {A}. T2 read a value T1 has since overwritten; abort T2.

Pessimistic (2PL)Optimistic (OCC)
Conflict handlingPrevent by waitingDetect at commit, abort
DeadlocksPossibleImpossible
Wasted workWaiting timeEntire aborted transactions
Best whenContention is highContention is low, transactions are short, reads dominate
Worst whenLong transactions holding locksHot items: repeated aborts, possibly livelock

The application-level version of OCC is the version column pattern, a compressed validation phase in one statement:

-- Read phase: remember the version
SELECT title, body, version FROM document WHERE doc_id = 42;    -- version = 7

-- Validation + write phase in one atomic statement
UPDATE document
SET body = 'new text', version = version + 1
WHERE doc_id = 42 AND version = 7;
-- 1 row updated: success. 0 rows: someone else committed first; re-read and retry.

Many in-memory and distributed databases use OCC variants internally (Silo, FoundationDB, CockroachDB's transaction layer has optimistic elements), and PostgreSQL's SSI is optimistic in spirit: it lets transactions run and aborts at commit if a dangerous pattern formed.

Multiversion Concurrency Control (MVCC)

All the schemes so far keep one version of each item, so readers and writers must coordinate. MVCC keeps several: a write creates a new version instead of overwriting, and each transaction reads the versions that were committed as of its snapshot. The headline benefit:

Readers never block writers, and writers never block readers.

Only write-write conflicts remain to be resolved, typically with row locks.

flowchart LR
  V1["A v1 = 500, created by T5"] --> V2["A v2 = 400, created by T8"]
  V2 --> V3["A v3 = 450, created by T12, uncommitted"]
  R1["T9 snapshot sees v2"] -.-> V2
  R2["T6 snapshot sees v1"] -.-> V1

The theory has a multiversion counterpart of each scheme: multiversion timestamp ordering (reads are never rejected, they just pick the right version), multiversion 2PL, and snapshot isolation (SI). Snapshot isolation is what most "MVCC databases" provide by default at their higher isolation levels, and it is important to know that SI is not serializable: it permits write skew, the cycle from Worked Example 2, where two transactions each read something the other writes. The canonical example: two doctors are on call, each transaction checks "is at least one other doctor on call?", both see yes in their snapshots, both go off call.

How versions are stored, how visibility is decided (xmin/xmax in PostgreSQL, undo logs and read views in InnoDB), and how old versions are garbage-collected (VACUUM, purge) is covered in depth in MVCC.

How Real Databases Do It

PostgreSQLMySQL InnoDBClassic textbook
Base mechanismMVCC (versions in the heap) + row locks for writesMVCC (undo log) + row locks for writes and locking readsStrict 2PL
Default isolationRead committedRepeatable readSerializable
Plain SELECTSnapshot read, no locksSnapshot read, no locks (except at SERIALIZABLE)S locks
Write-write conflictsRow lock; at RR/SERIALIZABLE, the second writer aborts if the first committedRow lock; second writer waits, then updates the latest versionX locks
PhantomsPrevented by snapshot at RR; SIREAD locks at SERIALIZABLENext-key / gap locks for locking reads and writesPredicate or index-range locks
SerializableSSI: optimistic, aborts on dangerous structures2PL-ish: plain SELECT becomes SELECT ... FOR SHARE2PL
DeadlocksDetected after deadlock_timeout (1 s)Detected immediately; innodb_lock_wait_timeout 50 sWait-for graph

PostgreSQL: Snapshot Isolation and SSI

PostgreSQL's REPEATABLE READ is snapshot isolation: the transaction sees a snapshot taken at its first statement, and if it tries to update a row that a concurrent transaction has updated and committed since, it fails with ERROR: could not serialize access due to concurrent update (SQLSTATE 40001). This "first committer wins" rule prevents lost updates. It does not prevent write skew.

SERIALIZABLE adds Serializable Snapshot Isolation (Cahill et al., 2008; in PostgreSQL since 9.1). SSI keeps snapshot reads but tracks rw-antidependencies: T1 reads a version, and T2 concurrently writes a newer version of the same data. Reads are recorded as non-blocking SIREAD locks (on tuples, pages or whole relations, coarsening as memory fills). The key theorem from the SSI paper: every non-serializable execution under SI contains a "dangerous structure", two consecutive rw-antidependency edges T1 → T2 → T3 among concurrent transactions (T1 and T3 may be the same transaction). PostgreSQL aborts a transaction when such a structure forms.

flowchart LR
  TA(("T_in")) -->|"rw: reads what T_pivot writes"| TP(("T_pivot"))
  TP -->|"rw: reads what T_out writes"| TO(("T_out"))

The check is conservative: it may abort transactions that were in fact serializable (false positives), but never misses a real anomaly. Applications must retry on 40001.

-- Write skew: on-call doctors. Two sessions run this at the same time.
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM doctor WHERE on_call;                -- both see 2
UPDATE doctor SET on_call = false WHERE name = 'alice';   -- session 2 updates 'bob'
COMMIT;
-- Under REPEATABLE READ: both commit, nobody is on call.
-- Under SERIALIZABLE:    one commit fails with
--   ERROR: could not serialize access due to read/write dependencies among transactions

Make SSI cheap

SSI's overhead is mostly false-positive aborts. Declare read-only transactions as READ ONLY (they can use safe snapshots and never cause aborts), keep transactions short, and make sure predicates use indexes, since a sequential scan takes a relation-level SIREAD lock that conflicts with every write to the table.

MySQL InnoDB: Record, Gap and Next-Key Locks

InnoDB's default REPEATABLE READ uses MVCC snapshots for plain SELECT (consistent reads), but locking reads (SELECT ... FOR UPDATE, FOR SHARE) and writes (UPDATE, DELETE) read the latest committed version and lock it. To stop phantoms on those paths, InnoDB locks index ranges:

LockLocksPurpose
Record lockOne index recordProtect an existing row
Gap lockThe open interval between two index records (or before the first / after the last)Block inserts into the gap. Gap locks do not conflict with each other; they only block inserts
Next-key lockA record plus the gap before it: the half-open interval (prev, this]The default for range scans at RR; prevents phantoms
Insert intention lockA gap-level lock taken by INSERTConcurrent inserts into the same gap at different positions do not block each other

Worked example. An index on enrolled(score) contains values 10, 20, 30.

-- Session 1 (REPEATABLE READ)
BEGIN;
SELECT * FROM enrolled WHERE score BETWEEN 15 AND 25 FOR UPDATE;
-- Takes next-key locks on (10, 20] and (20, 30]: record 20, record 30, and both gaps.

-- Session 2
INSERT INTO enrolled (sid, cid, score) VALUES (9, 'CS340', 18);   -- blocks: gap (10, 20)
INSERT INTO enrolled (sid, cid, score) VALUES (9, 'CS340', 27);   -- blocks: gap (20, 30)
INSERT INTO enrolled (sid, cid, score) VALUES (9, 'CS340', 35);   -- succeeds: beyond 30

Locking (20, 30] even though only values up to 25 were requested is the price of locking ranges of the index rather than predicates. If the predicate has no usable index, InnoDB scans and locks the whole clustered index, effectively locking the table against inserts.

Points that trip people up:

  • Mixed reads in one transaction. At RR, a plain SELECT reads the snapshot, while an UPDATE in the same transaction acts on the latest committed data. A transaction can therefore update rows its own SELECT cannot see.
  • READ COMMITTED disables most gap locking (only foreign-key and duplicate-key checks use gaps). That reduces deadlocks and lock waits significantly, which is why many large MySQL deployments run at RC, accepting phantoms.
  • SERIALIZABLE in InnoDB converts plain SELECT into SELECT ... FOR SHARE (when autocommit is off), making it essentially strict 2PL with next-key locks: correct, with far more blocking and deadlocks than PostgreSQL's SSI.
  • Unique-key inserts deadlock. Several sessions inserting the same duplicate key each take a shared lock on the conflicting record and then wait to upgrade: a textbook upgrade deadlock.

For the full anomaly-by-anomaly comparison of isolation levels in both databases, see Isolation Levels.

War Story (illustrative)

An order service ran on MySQL at the default REPEATABLE READ. Each checkout did SELECT ... FOR UPDATE on the inventory table filtered by warehouse_id and sku, but the only index was on sku. Under load, deadlocks climbed from a handful a day to hundreds a minute. The cause: without a composite index, the locking read took next-key locks on every index entry for the SKU across all warehouses, plus the gaps between them, and concurrent checkouts for the same popular SKU in different warehouses now contended on overlapping ranges, acquired in different orders. Adding an index on (sku, warehouse_id) shrank each transaction's lock footprint to one record, and deadlocks dropped back to near zero. In InnoDB, your indexes define your locks.

Comparing the Approaches

Strict 2PLTimestamp orderingOCCMVCC + SISSI
SerializableYesYesYesNo (write skew)Yes
Readers block writersYesNo (but may abort)NoNoNo
DeadlocksYesNoNoWrite-write onlyWrite-write only
Conflict resolutionWaitAbortAbort at commitWait or abort on write-writeAbort at commit
OverheadLock managerPer-item timestamps, reads write metadataRead/write set trackingVersion storage and GCSI + rw-dependency tracking
Best workloadHigh contention, short transactionsRarely used aloneLow contentionRead-heavy OLTPRead-heavy, needs serializable
Used bySQL Server (default), DB2, InnoDB SERIALIZABLEFoundations of MVTOFoundationDB, in-memory research systemsPostgreSQL RR, Oracle, InnoDB consistent readsPostgreSQL SERIALIZABLE, CockroachDB (variant)

Common Misconceptions

MisconceptionReality
"Serializable means transactions run one at a time"It means the result equals some serial order; execution is still concurrent
"The equivalent serial order is the start order"It can be any order consistent with the conflicts (Worked Example 1 serialized as T3, T1, T2)
"2PL means two locks"It means two phases: grow, then shrink
"2PL prevents deadlocks"It causes them. Only conservative 2PL is deadlock-free
"MVCC means serializable"MVCC usually provides snapshot isolation, which allows write skew
"Row locks prevent phantoms"Phantoms are rows that do not exist yet; you need range or predicate locks
"A deadlock is a database bug"It is an expected outcome of locking; the fix is consistent lock ordering plus retries
"Optimistic locking means no locks at all"The write itself still takes a short row lock; "optimistic" refers to not holding locks across the read phase

Interview Questions

1. Is this schedule conflict serializable? R1(X) R2(X) W1(X) W2(X) No. R2(X) before W1(X) gives T2 → T1; W1(X) before W2(X) gives T1 → T2. A cycle. It is the lost update: both read the same X and the later write erases the earlier one.

2. Draw the precedence graph for R1(A) W2(A) R3(B) W1(B) R2(B) and give an equivalent serial order. On A: R1(A) before W2(A) gives T1 → T2. On B: R3(B) before W1(B) gives T3 → T1; W1(B) before R2(B) gives T1 → T2. Edges T3 → T1 → T2, acyclic, so it is conflict serializable with serial order T3, T1, T2.

3. What is the difference between conflict and view serializability? Conflict serializability requires every pair of conflicting operations to be ordered as in a serial schedule; testable in polynomial time via the precedence graph. View serializability only requires the same initial reads, reads-from relations and final writes; it is strictly larger (it admits schedules with blind writes) and testing it is NP-complete.

4. Why does basic 2PL guarantee serializability, and why do databases use strict 2PL instead? Under 2PL, an edge Ti → Tj in the precedence graph implies Ti's lock point precedes Tj's, so a cycle is impossible. But basic 2PL can release an X lock before commit, letting others read uncommitted data and causing cascading aborts or non-recoverable schedules. Strict 2PL holds X locks until commit, producing strict, recoverable schedules.

5. Explain wait-die and wound-wait. Both assign start timestamps. In wait-die, an older requester waits for a younger holder, and a younger requester dies. In wound-wait, an older requester wounds (aborts) a younger holder, and a younger requester waits. Waits only go one way by age, so no cycles form. Restarted transactions keep their original timestamp to avoid starvation.

6. What are intention locks for? They let a transaction lock a coarse node (a table) without checking every fine-grained lock beneath it. A transaction locking a row first puts IX on the table, so a later request for S or X on the table sees the conflict at the table node immediately.

7. What is the Thomas write rule? In timestamp ordering, if T wants to write X but a younger transaction has already written X (and no younger transaction has read it), T's write is obsolete in timestamp order and can be skipped instead of aborting T. It permits some view-serializable but not conflict-serializable schedules.

8. When is optimistic concurrency control better than locking? When conflicts are rare and transactions are short, so validation almost always succeeds and no time is spent waiting on locks. Under high contention on hot items, OCC wastes work through repeated aborts and locking does better.

9. Why is snapshot isolation not serializable? How does PostgreSQL make it serializable? SI only detects write-write conflicts, so two transactions that read overlapping data and write disjoint data (write skew) both commit, producing a state no serial order could. PostgreSQL's SSI tracks read-write antidependencies with SIREAD locks and aborts a transaction when two consecutive rw-antidependencies form among concurrent transactions.

10. How does InnoDB prevent phantoms at REPEATABLE READ? Plain reads use a consistent snapshot. Locking reads and writes take next-key locks (a record plus the gap before it) on the index ranges they scan, so concurrent inserts into those ranges block until commit.

11. Which schedule property guarantees that aborting a transaction never requires aborting another? Cascadelessness (avoiding cascading aborts): transactions read only committed data. Strictness is stronger and additionally makes undo by before-images correct.

Summary

ConceptOne-line version
ScheduleAn interleaving of transactions' operations, preserving each one's internal order
ConflictDifferent transactions, same item, at least one write
Conflict serializablePrecedence graph is acyclic; topological sort gives the serial order
View serializableSame reads-from and final writes; larger class, NP-complete to test
Recoverable / cascadeless / strictCommit after your sources / read only committed / touch only committed
2PLNo lock after the first unlock; guarantees conflict serializability
Strict / rigorous 2PLHold X / all locks until commit; strict schedules
Intention locksIS, IX, SIX on ancestors make multi-granularity locking cheap
DeadlocksWait-for graph cycles; detect and abort a victim, or prevent with wait-die / wound-wait
Timestamp orderingSerialize by start timestamp; abort late operations; Thomas rule skips obsolete writes
OCCRead, validate, write; abort on conflict at commit
MVCCMultiple versions, snapshot reads; SI allows write skew; SSI fixes it
PostgreSQLMVCC + row locks; SERIALIZABLE is SSI
InnoDBMVCC + record/gap/next-key locks; SERIALIZABLE is 2PL-like

Where to Go Next