Deadlock

When should a database detect deadlocks and when prevent them, and why is a timeout never right?

What it is

If transactions block, and acquire locks in arbitrary order, they can form a cycle in the waits-for graph (an arrow T₁ → T₂ means "T₁ waits for a lock held by T₂"). A cycle means nobody can ever proceed. In general you cannot avoid this without either knowing every transaction's full lock set in advance (so you can impose a global acquisition order) or breaking one of the Coffman conditions by force. (The four Coffman conditions for deadlock are: mutual exclusion, hold-and-wait, no preemption, and circular wait.)

Detection

Detection builds the waits-for graph and aborts a victim when it finds a cycle. A run costs O(V + E) (linear in the number of transactions and waits).

InnoDB checks eagerly, on every new wait edge.
Postgres checks lazily, only when a wait lasts longer than deadlock_timeout (default 1 second). A genuine deadlock costs you a second of held locks, but a busy system without deadlocks pays nothing for detection.

The eager approach has a failure mode. Under very high concurrency, the detector's own cost grows superlinearly with the size of the waits-for graph. InnoDB added the ability to turn detection off entirely and fall back on lock-wait timeouts, precisely because the cure had started to scale worse than the disease.

Prevention by timestamp

Prevention makes cycles impossible by construction. Give each transaction a timestamp when it starts and allow waiting in only one direction of timestamp order. All edges are then monotone in a total order, and a monotone graph has no cycles. Two versions exist:

Wait-die (non-preemptive): an older transaction that wants a lock held by a younger one waits. A younger one that wants a lock held by an older one dies (aborts) immediately.
Wound-wait (preemptive): an older transaction that wants a lock held by a younger one wounds it (forces it to abort). A younger requester waits.

A detail people forget: a restarted transaction keeps its original timestamp. That is what rules out starvation: a transaction only grows older, and a sufficiently old transaction is never the victim. Without this rule both schemes starve some transactions.

Wound-wait aborts less work in expectation. The transaction that has done the most work (the oldest) is never the one killed, and short, young transactions can wait out a lock that may free in microseconds instead of dying at once. Spanner (Google's globally distributed database) uses wound-wait.

Why distributed systems prevent instead of detect

Detection requires a global waits-for graph, which requires a consistent snapshot of the whole distributed system, which is expensive and out of date by the time you have it. Prevention needs only a local timestamp comparison, with no communication at all.

Timeout, the degenerate prevention scheme

A timeout (abort if you waited more than T) is the simplest scheme, and it fails for a specific reason: it cannot tell a deadlock from a slow transaction. The right timeout depends on the tail of the lock-wait distribution, and that distribution is heavy-tailed, so no correct value exists. Too short and you abort live work; too long and you sit in a deadlock. It is the variance, not the mean, that defeats you.

Detection needs a global view; prevention needs only a total order; distance decides which you can afford.

Beyond the database: pools, slots and permits

The same cycle forms between services, where the resources are not locks but pools, slots and permits, and no component has a global view that could detect it. Example: service A holds a connection slot in pool P and calls B, while B holds a slot in the same pool and calls A. Nobody sees the cycle. The universal fallback is a timeout, and a timeout cannot tell deadlock from slowness: the failure-detector problem again.

So prevention wins here too. Global lock ordering (everyone takes resources in the same agreed order) removes circular wait. It is the prevention that scales, because it needs no runtime machinery. It needs only agreement, which is why it is an organizational constraint as much as a technical one.

A code sketch: avoid the deadlock by ordering

Same two transfers, two lock orders

Tomas's wallet bug has the simplest fix of all: impose a global order on lock acquisition yourself.

-- Lock both wallets in a fixed order (by id), whoever is the sender.
BEGIN;
SELECT balance FROM wallets
 WHERE owner IN ('anna', 'ben')
 ORDER BY owner            -- always the same order for every transaction
 FOR UPDATE;
UPDATE wallets SET balance = balance - 30 WHERE owner = 'anna';
UPDATE wallets SET balance = balance + 30 WHERE owner = 'ben';
COMMIT;

(FOR UPDATE asks the database to take exclusive row locks on the selected rows. Because both transfers now lock anna first and ben second, a cycle cannot form.)

Case, resolvedConstructed case · Tomas at Kestrel Tickets

A deadlock between two friends paying each other

Wallet transfers between two friends deadlocked a few times an hour, a report's count(*) read 41 then 43 inside one transaction, and dropping an 'unused' index made the same transaction lock the whole seats table. Where it started: Locking →

The wallet deadlock. Tomas sorts the two wallet ids before locking, so every transfer locks in the same global order. A cycle is now impossible. Lena also keeps the deadlock detector on, because deadlocks across other code paths can still occur, and sets an application retry for the rare victim.

The changing count and the dropped index. Lena explains that locks protect rows that exist, and the new seats were a physical insert the lock manager could not see: a phantom. Next-key locks protect the gaps of an index range, but only if the optimizer uses an index that covers the predicate. The dropped index meant the optimizer scanned the whole table, and the only safe lock for that is a table lock. The team restores the index and adds a rule to the review checklist: "When you drop or add an index, re-test the concurrency of every transaction that uses it."