Deadlock Detection: The Waits-For Graph

Transfer A moves money from account 1 to account 2; transfer B moves money from 2 to 1. Each updates its source first. A takes the exclusive lock on row 1; B takes the exclusive lock on row 2. A now requests row 2 and is queued behind B; B requests row 1 and is queued behind A. Both are asleep on their semaphores. Both hold a lock the other needs, and neither will release anything until it commits, which it cannot do until it gets the lock. The lock manager has done nothing wrong.

Read the lock table's wait queues as edges. Every waiting request contributes an edge from the waiter to each transaction whose granted lock conflicts with it (and, in engines that queue strictly, to the waiters ahead of it that conflict too). Nodes are transactions, not resources: the resource is what labels the edge. The result is the waits-for graph — a Directed Graph that the lock manager maintains implicitly and that the detector materialises when it needs to.

A deadlock is exactly a cycle in this graph. If there is no cycle, every chain of waiting ends at a transaction that is running and will eventually commit or abort, releasing the chain. A cycle means every member is waiting on another member; no external event will resolve it. Longer cycles happen in practice — A waits for B waits for C waits for A — and are just as fatal, which is why counting on "I only ever lock two rows" is not a defence.

Cycle detection in a directed graph is a depth-first search that colours nodes: white (unvisited), grey (on the current path), black (finished). Following an edge into a grey node is a back edge, and a back edge closes a cycle. That is the whole algorithm from Cycle Detection, and the waits-for graph is small enough — tens of nodes, one edge per blocked request — that a search from the transaction that just blocked costs microseconds. The search starts from the new waiter because any cycle that did not exist a moment ago must pass through the edge just added.

The engineering questions are around the search rather than inside it. The graph must be read consistently, which means holding the lock-table latches (all sixteen partitions, in PostgreSQL) while walking; that is why the search should be rare or fast. The edges must reflect the queue policy: PostgreSQL treats a waiter as blocked by the holders *and* by conflicting waiters ahead of it in the queue, since it will not be granted before them either. And the result must be acted on before the latches are dropped, or the graph can change underneath.

Once a cycle is found, one member must be aborted; its abort releases its locks, which grants the next waiter, which unwinds the cycle. Which member? The searcher — the transaction that just blocked and found the cycle — is the simplest choice and the one PostgreSQL makes: it errors out its own request with deadlock detected and reports the cycle in the error detail. It is fair in the sense that the transaction that completed the cycle pays for it, and it needs no global comparison. The cheapest to redo is InnoDB's choice: it compares the transactions on the cycle by the number of rows they have modified and locks they hold and aborts the one with the smallest weight, so that the most work survives. The youngest is what timestamp-ordered schemes pick, which guarantees the oldest transaction eventually commits and no transaction is starved by being repeatedly chosen.

Whatever the rule, the victim's session receives an error and its transaction is rolled back. The application must retry — the whole transaction, from BEGIN — because the schedule that failed has been discarded. A deadlock error treated as a fatal bug rather than a retryable condition is the most common mishandling.

PostgreSQL combines the two. A blocked process first simply sleeps. If it is still waiting after deadlock_timeout — one second by default — it wakes, takes all lock-table partition latches, builds the waits-for graph and runs the search. No cycle: it goes back to sleep and never searches again for this wait (it may log the wait if log_lock_waits is on, which is the cheapest way to find lock contention in production). Cycle: it first tries to break it by reordering wait queues without aborting anyone, and only if that fails aborts itself with SQLSTATE 40P01.

The delay is a bet that most waits are short and healthy, so the search — which stalls the whole lock manager — should not run on every block. Lowering deadlock_timeout finds deadlocks faster at the cost of more searches on a contended system; raising it is done on systems where lock waits of several seconds are normal. lock_timeout is a different, unrelated knob: it aborts *any* wait after the interval, deadlock or not, and is the tool for migrations that must not queue behind long transactions.

InnoDB searches immediately: every lock wait triggers a depth-first walk of the waits-for graph before the requester sleeps (innodb_deadlock_detect = ON), so a deadlock is reported at the instant it forms. On systems with very many concurrent waiters the walk itself becomes the bottleneck, and the documented remedy is to disable detection and rely on innodb_lock_wait_timeout (50 seconds by default) — the naive solution, chosen deliberately because at that scale the search is worse. The victim is the transaction with the least undo, and SHOW ENGINE INNODB STATUS prints the last detected deadlock in full: both transactions, both statements, the locks held and waited for.

Detection limits the damage of a deadlock; it does not reduce how many happen. Prevention does, and it is almost entirely the application's responsibility. Lock ordering: if every transaction acquires its locks in a single global order — ascending account id, say — a cycle cannot form, because a cycle would require some transaction to wait for a lock that sorts *before* one it already holds. SELECT … WHERE id IN (1, 2) ORDER BY id FOR UPDATE before the two UPDATEs is the whole fix for the transfer example, and the practical lesson Locks and Deadlocks shows the code. Short transactions shrink the window in which a cycle can close. Taking the coarse lock first — one row that represents the whole operation — serialises intentionally at the cost of concurrency.

Protocol-level prevention exists too. Wait-die and wound-wait compare transaction start times: a transaction is only ever allowed to wait for an older (wait-die) or a younger (wound-wait) one, so waits are all one direction and cannot cycle; the disallowed direction aborts instead. Neither is used by PostgreSQL or InnoDB for row locks — the abort rate is too high for their workloads — but both appear in distributed transaction managers where assembling a global waits-for graph would need a round of messages per wait.