Deadlock Detection with Wait-For Graphs

Two bank-transfer transactions hit a production database simultaneously.

• T1 moves ₹500 from alice to bob. Locks alice, then wants bob.
• T2 moves ₹300 from bob to alice. Locks bob, then wants alice.

Timing is unlucky. T1 gets its write lock on alice at 12:00:00.001, T2 gets bob at 12:00:00.002. T1 asks for bob — held by T2, blocks. T2 asks for alice — held by T1, blocks. Neither can release — both are in 2PL's growing phase, and 2PL forbids release-then-acquire. They are stuck forever, holding connections, row locks, and transaction IDs. Every new transaction that touches alice or bob queues behind them.

Here is the scenario as runnable Python against the lock manager from chapter 53:

# deadlock_demo.py — reproduce a classic two-transaction deadlock
import threading, time
from concurrency.lockmgr import LockManager

lm = LockManager()

def tx1():
    lm.acquire("T1", "alice", "W"); print("T1 got alice")
    time.sleep(0.05)                                 # let T2 grab bob
    print("T1 waits for bob...")
    lm.acquire("T1", "bob", "W")                     # blocks forever
    print("T1 got bob (never prints)")

def tx2():
    lm.acquire("T2", "bob", "W"); print("T2 got bob")
    time.sleep(0.05)                                 # let T1 grab alice
    print("T2 waits for alice...")
    lm.acquire("T2", "alice", "W")                   # blocks forever
    print("T2 got alice (never prints)")

t1 = threading.Thread(target=tx1); t2 = threading.Thread(target=tx2)
t1.start(); t2.start()
t1.join(timeout=2); t2.join(timeout=2)
print("both stuck?", t1.is_alive() and t2.is_alive())

Run it and the output is deterministic:

T1 got alice
T2 got bob
T1 waits for bob...
T2 waits for alice...
both stuck? True

The threads do not return. The process hangs. Without a deadlock detector this is how your 50-ms bank transfer turns into a permanent outage of two rows plus anything that queues behind them. Every real database ships code specifically to prevent that process from hanging forever. This chapter builds that code.

What a deadlock actually is

A set of transactions S is deadlocked when every transaction in S is blocked waiting on a lock held by some other transaction in S. Formally: for every T ∈ S there exists some T' ∈ S such that T is waiting on a lock held by T'. The definition is circular on purpose — the circularity is the deadlock.

Equivalently: build a directed graph with one node per live transaction and a directed edge T_i → T_j whenever T_i is blocked waiting on a lock held by T_j. Then S is deadlocked if and only if the subgraph restricted to S contains a directed cycle that covers every node in S. The cycle is the deadlock; the nodes on the cycle are the deadlocked transactions.

Why this reduces cleanly to cycle detection: the "waits-for" relation is transitive in its observable consequences (if T1 waits on T2 and T2 waits on T3, then T1's completion depends on T3's completion) but not in the graph itself — edges record immediate waits only. A cycle means some transaction is — via a chain of waits — waiting on itself. No progress is possible because unblocking any one transaction in the cycle requires its predecessor to finish, which requires its predecessor to finish, all the way around the loop back to the transaction you started with.

The two-transaction deadlock — T1 waits on T2, T2 waits on T1 — is by far the common case in production. OLTP workloads are dominated by short transactions touching two or three rows; the natural deadlock shape is a two-cycle. But longer cycles happen. Three-way cycles are documented in real workloads (three bank transfers forming a ring: A→B, B→C, C→A) and Postgres's detector explicitly handles cycles of arbitrary length. The algorithm does not care about length; any directed cycle is a deadlock, and the same DFS finds all of them.

One subtlety: a cycle in the wait-for graph is a necessary condition for deadlock, not just a sufficient one. Any deadlocked set of transactions produces a cycle, and any cycle represents a genuine deadlock — assuming the edges are accurate at the moment of inspection. "Accurate at the moment of inspection" is the source of most detector complexity; more on that shortly.

The wait-for graph

The data structure is almost embarrassingly simple. A hash map from transaction to the set of transactions it is waiting on. Build it incrementally — add an edge when a transaction blocks, remove the edges when a transaction unblocks or commits or aborts.

# concurrency/wfg.py — the wait-for graph
from collections import defaultdict

class WaitForGraph:
    """Directed graph: edge T_i -> T_j means T_i waits on a lock held by T_j."""

    def __init__(self):
        self.waits_for: dict[str, set[str]] = defaultdict(set)

    def add_edge(self, waiter: str, holder: str) -> None:
        if waiter != holder:                         # self-loops never happen
            self.waits_for[waiter].add(holder)

    def remove_transaction(self, tx: str) -> None:
        self.waits_for.pop(tx, None)                 # tx no longer waits
        for w in list(self.waits_for):
            self.waits_for[w].discard(tx)            # nobody waits on tx now
            if not self.waits_for[w]:
                self.waits_for.pop(w)

    def has_cycle(self) -> list[str] | None:
        WHITE, GREY, BLACK = 0, 1, 2
        colour = defaultdict(lambda: WHITE)
        parent: dict[str, str] = {}

        def dfs(u: str) -> list[str] | None:
            colour[u] = GREY
            for v in self.waits_for.get(u, ()):
                if colour[v] == GREY:                # back-edge -> cycle
                    cycle = [v]
                    x = u
                    while x != v:
                        cycle.append(x); x = parent[x]
                    return list(reversed(cycle + [v]))
                if colour[v] == WHITE:
                    parent[v] = u
                    if (c := dfs(v)) is not None:
                        return c
            colour[u] = BLACK
            return None

        for node in list(self.waits_for):
            if colour[node] == WHITE:
                if (cycle := dfs(node)) is not None:
                    return cycle
        return None

Forty lines, pure Python, no external dependencies. The add_edge method is called by the lock manager every time a transaction blocks; remove_transaction is called on commit, abort, or whenever a transaction's wait is resolved. The has_cycle method returns a list [T_a, T_b, ..., T_a] describing the cycle it found, or None if the graph is acyclic.

Why three colours and not two: a two-colour (visited / unvisited) DFS cannot distinguish "I have seen this node on the current path, so there is a cycle" from "I have seen this node on some earlier completed traversal, which is fine." Grey nodes are on the current recursion stack. Encountering a grey node through an edge means the edge closes a cycle. Encountering a black node means the edge points into a region already fully explored — not a cycle, just a shared descendant. Three colours is the minimum information needed.

The waits_for map is authoritative. Every other piece of deadlock bookkeeping — the list of blocked transactions, the lock manager's wait queues, per-connection state — is either a consequence of it or a redundant copy of part of it. When you want to know whether the system is deadlocked, you run has_cycle(). That is the entire API.

Cycle detection, precisely

The DFS above is standard, but worth walking through once. You start from some unvisited (white) node, mark it grey, and recursively follow every outgoing edge. When the recursion on a neighbour returns, you keep going; when all neighbours are done, you mark the current node black and return.

A back-edge — an edge from a grey node to an ancestor that is also grey — is the signature of a cycle. The ancestor is on the current path (it is grey), and the current node is a descendant trying to point back at it. Following parent pointers from the current node up to the target of the back-edge reconstructs the cycle.

Worked trace on the two-transaction deadlock:

waits_for = { T1: {T2}, T2: {T1} }

dfs(T1):
  colour[T1] = GREY
  edge T1 -> T2, T2 is WHITE
  parent[T2] = T1
  dfs(T2):
    colour[T2] = GREY
    edge T2 -> T1, T1 is GREY  <-- BACK EDGE, cycle found
    cycle = [T1, T2, T1]
    return [T1, T2, T1]

Complexity is O(V + E): every node is pushed and popped once, every edge is traversed once. In a real lock manager V is the number of live transactions — maybe a few hundred on a busy OLTP system, a few thousand in extreme cases. E is bounded by V because a transaction can be waiting on at most one lock at a time (it blocks on one, then unblocks, then possibly blocks on another). Total work per scan: hundreds of nodes, hundreds of edges, well under a millisecond.

An alternative is Kahn's algorithm (repeated removal of in-degree-zero nodes; whatever remains is in a cycle). Kahn runs in the same complexity and is easier to parallelise, but it does not naturally reconstruct the cycle itself — you only learn that there is a cycle, not which transactions form it. For a deadlock detector that then needs to pick a victim from the cycle, DFS with parent pointers is the cleaner fit.

Running the detector

When should the lock manager call has_cycle()? Three plausible schedules.

On every lock wait. Check immediately whenever a transaction blocks. Zero detection latency but a DFS per block — wasteful when contention is high.

Periodically. Every T milliseconds run the detector once; missed deadlocks stay stuck for up to T ms. Postgres uses deadlock_timeout = 1 second: when a transaction blocks, a timer starts; if still blocked after 1 s, the detector runs. This amortises detector cost across many lock waits, most of which resolve naturally.

On timeout. No periodic scan; instead every lock wait has a timeout (InnoDB's innodb_lock_wait_timeout, default 50 s). The waiter aborts regardless of whether a cycle exists. Simpler, but a 50-second hang looks catastrophic. Modern InnoDB runs a wait-for-graph detector alongside the timeout; the timeout is a fallback.

Why Postgres's 1-second default is the OLTP sweet spot: it is longer than the 99th-percentile legitimate lock wait and shorter than the "this page is broken" threshold. Genuine deadlocks are rare, so the scan rarely fires; when a wait is legitimate, it resolves before 1 s and the detector never runs; when it is a genuine deadlock, 1 s of hang plus abort+retry is well inside a typical HTTP request budget.

Picking the victim

Once you have a cycle, you pick one transaction to abort. Four criteria are in play.

1. Least work done. Count rows modified or log records emitted; abort the one with the smallest count. Wastes the least. The primary signal in most production engines.
2. Youngest transaction. Abort the most recently started. Younger transactions have done less work; also, aborting the oldest could starve it (still oldest on retry, deadlocks again). Postgres's default is a variant of this.
3. Lowest priority. SQL Server exposes SET DEADLOCK_PRIORITY LOW | NORMAL | HIGH; useful when analytics workloads should always yield to OLTP.
4. Random. Uniform from the cycle. Avoids priority inversions; no major production system uses it as the default.

Aborting the victim: mark aborted, release every lock it holds, wake waiters, notify the client. The driver almost always retries automatically — in Postgres the error is 40P01 deadlock detected, which psycopg and SQLAlchemy treat as retryable. The retry usually succeeds on the second try because the race that caused the cycle is rare. If it deadlocks again, a well-designed application retries with exponential backoff.

# concurrency/victim.py — pick the least-work victim from a cycle
def pick_victim(cycle: list[str], work_done: dict[str, int]) -> str:
    """cycle is a list of tx IDs, work_done maps tx ID -> rows modified."""
    return min(cycle, key=lambda tx: work_done.get(tx, 0))

One line of real logic. The transaction already tracks work_done for rollback, so there is no extra bookkeeping.

Prevention — wound-wait and wait-die

The alternative to detection is prevention: refuse to let a wait happen whenever it might cycle. Two classical schemes, both due to Rosenkrantz, Stearns, and Lewis (1978), use transaction timestamps — a total order assigned at start time — to decide which waits are allowed.

Wait-die. When T_i tries to acquire a lock held by T_j: if T_i is older (smaller timestamp), T_i waits; if T_i is younger, T_i dies — aborts and restarts with the same timestamp so it does not keep losing.

Wound-wait. When T_i tries to acquire a lock held by T_j: if T_i is older, T_i wounds T_j (forcibly aborts it) and takes the lock; if T_i is younger, T_i waits.

Both schemes are deadlock-free. In wait-die every wait edge runs older-to-younger, so cycles require a younger-to-older edge that is never allowed. Wound-wait is symmetric — edges run younger-to-older, and any older-to-younger request wounds rather than waits. Why both schemes abort younger transactions: the total timestamp order has to choose a consistent tiebreaker; picking "older survives" means the older transaction — which has already done more work — is not restarted. Wait-die aborts at the younger's wait time; wound-wait aborts at the older's request time. Wound-wait generally aborts fewer transactions because it only wounds when an older one actually needs the lock, but requires signalling the wounded transaction.

Neither is the default in modern relational databases. Detection wins because genuine deadlocks are rare — roughly one per thousand transactions on typical OLTP. Prevention aborts many transactions that would never have deadlocked, just to eliminate the cycle possibility. But prevention is the standard choice in distributed systems where maintaining a global wait-for graph is too expensive.

Timeouts as a fallback

Even with a proper detector, most databases also ship a coarse timeout that aborts any transaction waiting longer than a threshold — Postgres's statement_timeout, InnoDB's innodb_lock_wait_timeout, Oracle's ddl_lock_timeout. Why? Because detection only catches lock cycles. Transactions can wait for reasons the lock manager cannot see — RPCs to other services, synchronous triggers hitting HTTP endpoints, a stalled SSD flush, a network partition. None show up as edges in the wait-for graph, and all can hang a transaction indefinitely. A 30-second statement_timeout prevents the worst outage mode (connection pool fills with hung transactions, service unreachable) at the cost of occasionally killing a legitimate slow query. Detection and timeouts are complementary — ship both.

The role of SELECT ... FOR UPDATE

SQL provides an explicit way to take a write lock without modifying a row: SELECT ... FOR UPDATE. It is the cause of a disproportionate fraction of production deadlocks.

BEGIN;
SELECT balance FROM accounts WHERE id = 'alice' FOR UPDATE;
-- application computes: new_balance = balance + 100
UPDATE accounts SET balance = :new_balance WHERE id = 'alice';
COMMIT;

Why users write this: to prevent the read-modify-write race. Without the FOR UPDATE, two transactions can both read Alice's balance, both compute balance + 100, both update. One write clobbers the other — same lost update as chapter 52. FOR UPDATE takes a write lock on the rows as they are read, so the second transaction blocks at its own SELECT until the first commits.

The Python equivalent against the chapter-53 lock manager:

# select_for_update.py — explicit write-lock at read time
def credit(tx, account, amount):
    tx.acquire(account, "W")                         # FOR UPDATE behaviour
    balance = storage.read(account)                  # consistent read
    storage.write(account, balance + amount)         # write to same row
    tx.commit()

The problem: SELECT ... FOR UPDATE extends the write lock's lifetime backwards. An ordinary UPDATE takes the write lock only when the row is being modified, typically near commit. FOR UPDATE takes it at the read — possibly the first statement of the transaction. Earlier acquisition means longer hold, which means more opportunity for another transaction to request the same lock and form a cycle. Two bank-transfer transactions written with FOR UPDATE are exactly the deadlock that opened this chapter. Use FOR UPDATE only when the read-then-write pattern is genuinely required; where possible, fuse the operation into a single UPDATE accounts SET balance = balance + 100 WHERE id = 'alice', which is atomic at the row level with no explicit locking.

Lock ordering as a developer-side fix

A theorem that eliminates whole classes of deadlock: if every transaction acquires locks in the same global canonical order, the wait-for graph cannot have a cycle.

Why this is true: under a total order on resources (say alphabetical by key), if T_i is waiting for resource A, it has not yet acquired any resource greater than A. If T_j holds some resource B > A, it must already have finished acquiring A, so T_i cannot be holding A. Every edge in the wait-for graph points from a transaction waiting on a smaller resource to one holding a bigger one. Edges only ever go "up" the order. An acyclic directed graph has no cycles — no deadlocks.

The practical form: pick a canonical order (alphabetical by primary key) and always acquire locks in that order.

# concurrency/ordered_lock.py — canonical lock ordering
def transfer(tx, src: str, dst: str, amount: int) -> None:
    """Atomic transfer. Locks are acquired in alphabetical order
    so transfer(a, b) and transfer(b, a) cannot deadlock."""
    first, second = sorted([src, dst])               # canonical order
    tx.acquire(first, "W")
    tx.acquire(second, "W")
    src_bal = storage.read(src); dst_bal = storage.read(dst)
    storage.write(src, src_bal - amount)
    storage.write(dst, dst_bal + amount)
    tx.commit()

Now transfer("alice", "bob") and transfer("bob", "alice") both lock alice first and bob second. The earlier deadlock vanishes — no interleaving of these transactions can produce a cycle.

This is the standard advice for banking-style workloads where the access pattern is obvious. It scales poorly when transactions touch a set of rows determined at runtime by an index scan: the "canonical order" there is whatever the index returns, and concurrent inserts can shift it between transactions. For those workloads, detection is the pragmatic answer.

A production-realistic scenario

t=0:    T1 acquires write(A).  [A locked W by T1]
t=0.1:  T2 acquires write(B).  [B locked W by T2]
t=0.2:  T3 acquires write(C).  [C locked W by T3]
t=0.3:  T1 wants write(B). Blocks.  Edge T1 -> T2.
t=0.4:  T2 wants write(C). Blocks.  Edge T2 -> T3.
t=0.5:  T3 wants write(A). Blocks.  Edge T3 -> T1.

dfs(T1):  colour[T1] = GREY
  edge T1 -> T2, WHITE, parent[T2] = T1
  dfs(T2):  colour[T2] = GREY
    edge T2 -> T3, WHITE, parent[T3] = T2
    dfs(T3):  colour[T3] = GREY
      edge T3 -> T1, T1 is GREY  <-- cycle detected
      reconstruct: T3 -> T2 -> T1 (via parents), prepend T1, reverse
      return [T1, T2, T3, T1]

t=1.001: T3 aborted. Lock on C released. T2 unblocks.
t=1.002: T2 acquires write(C). Completes bob->carol transfer.
t=1.003: T2 commits. Locks on B, C released. T1 unblocks.
t=1.004: T1 acquires write(B). Completes alice->bob transfer.
t=1.005: T1 commits. Locks on A, B released.
t=1.1:   T3 retries automatically. Acquires write(C), then write(A). Succeeds.

Common confusions

• "If two transactions use the same lock order, they cannot deadlock." True pairwise, but three transactions can still deadlock transitively — T1 locks A then B, T2 locks B then C, T3 locks C then A. The fix has to be a global canonical order over all resources the workload touches, not a per-pair order.
• "Read locks cannot deadlock." False. Two transactions each holding a read lock and each attempting to upgrade to write is the classic upgrade deadlock: both block on the other's read lock. Postgres and InnoDB warn about this and sometimes require FOR UPDATE at read time to avoid it.
• "Optimistic concurrency control avoids deadlocks." It avoids them during execution but can livelock in the commit phase: A invalidates B's read set (B retries), B then invalidates A's read set (A retries), they ping-pong. Under high contention throughput collapses to near zero.
• "Deadlock detection is expensive." O(V + E) with V in the hundreds; per-scan cost is microseconds. Even at a 100 ms period that is ~0.01% CPU. The expensive part is rolling back the victim, which runs only when a cycle is actually found.
• "You can prevent deadlocks by waiting longer." No. A cycle is structural; longer timeouts just mean you stay stuck longer. Waiting resolves contention, not deadlocks.

Going deeper

The basic wait-for graph handles a single-node database. Production reality is messier.

Distributed deadlock detection

When transactions span multiple database nodes, the wait-for graph is distributed. Each node sees only its local waits; a cycle might wind through several nodes and no single node can see the whole graph. The classic algorithm is Chandy, Misra, and Haas (1983) Distributed Deadlock Detection: a blocked transaction periodically sends a probe message along each outgoing wait edge carrying the initiator's transaction ID; when another blocked transaction receives a probe with its own ID, it has detected a cycle back to itself and aborts. No global graph is ever materialised; at most one message per edge per round. Google Spanner sidesteps the problem with wound-wait over globally-ordered TrueTime timestamps — cycles cannot form, at the cost of extra aborts — because distributed detection would be prohibitively expensive.

Phantom deadlocks

The wait-for graph is a snapshot. By the time the detector reports a cycle, one of its transactions may have already aborted for an independent reason. This is a phantom deadlock — the reported cycle is no longer live. A well-designed detector re-verifies each edge before aborting a victim; Postgres holds a latch on the lock partitions while it verifies. False aborts are rare but embarrassing when they happen, so production systems pay the extra verification cost.

Lock-free data structures

Avoiding locks avoids deadlocks by construction. Lock-free data structures use atomic compare-and-swap operations — threads race, one wins, the other retries, no waits, no cycles. The costs are real: CAS is an order of magnitude more expensive than a regular write, memory reclamation requires hazard pointers or epoch-based schemes to handle the ABA problem, and fairness guarantees are weaker. Modern databases use lock-free techniques in specific hot paths (page cache, transaction ID allocator, skip-list MemTables) but not for transaction-level concurrency — the correctness cost is too high and a well-tuned lock manager with deadlock detection is fast enough for OLTP.

Where this leads next

You now have the last missing piece of the lock-based concurrency stack: the detector that keeps 2PL from hanging. With locks, phase discipline, granularity, and deadlock detection in place, you can build a serialisable database that actually scales on multi-core hardware. The next chapters leave the locking model behind and look at what it buys — and what it costs.

• Demonstrating anomalies (chapter 56) — code up the classic concurrency anomalies (dirty read, non-repeatable read, phantom, lost update, write skew) against your lock manager and see which ones 2PL rules out and which ones sneak through at weaker isolation levels.
• Isolation levels (chapter 57) — read committed, repeatable read, snapshot isolation, serialisable. What the ANSI SQL standard says, what databases actually implement, and the enormous gap between the two.
• MVCC (Build 8) — the protocol that lets readers never block writers by keeping multiple versions of each row. Where Postgres's SELECT finally stops fighting UPDATE.

Detection is the pragmatic answer to the deadlock problem. It is not elegant — you let the cycle happen and then clean up — but it is cheap, correct, and predictable. Every production database you will work with implements some version of what you wrote above: a wait-for graph, a periodic cycle detector, a victim selector, a client-side retry. Forty lines of Python; essentially unchanged since the 1970s; still the default answer in 2026.

References

1. Chandy, Misra, Haas, Distributed Deadlock Detection, ACM TOCS 1(2), 1983 — the classic algorithm for finding cycles in a wait-for graph spread across multiple machines, using probe messages instead of a materialised global graph. Still the template for distributed lock managers.
2. Rosenkrantz, Stearns, Lewis, System Level Concurrency Control for Distributed Database Systems, ACM TODS 3(2), 1978 — the paper that introduced wound-wait and wait-die. Short, readable, contains the proofs that both schemes are deadlock-free.
3. Bernstein, Hadzilacos, Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley 1987 — the textbook. Chapter 4 covers deadlock detection, prevention, and avoidance with full proofs. Free PDF from Microsoft Research.
4. PostgreSQL source, deadlock.c — the actual detector in a production relational database. About 1200 lines of C, heavily commented. Implements the wait-for graph, DFS-based detection with "soft" vs "hard" edges for multi-waiter queues, and victim selection.
5. MySQL Reference Manual, InnoDB Deadlock Detection — how InnoDB's detector runs on every lock wait (unlike Postgres's periodic approach), plus the option to disable it entirely and rely on innodb_lock_wait_timeout under extreme write contention.
6. Gray, Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann 1992 — chapter 7.11 on deadlocks is the industry's practical reference. Measurements of deadlock frequency in real workloads (roughly one per thousand transactions), analysis of detection vs prevention trade-offs, and the empirical argument for why production systems chose detection.