Part 3 of 5 · 1 min read
Deadlock detection via a wait-for graph
A wait-for graph with a cycle reveals exactly which transactions are deadlocked.
Think of mapping an arrow from each stuck driver to whichever other driver is blocking them. The arrows form a closed loop, proving none of them can ever move without outside help.
In plain words: a wait-for graph has one node per transaction, with an edge from transaction A to transaction B whenever A is waiting for a lock currently held by B. The database periodically checks this graph for cycles. A cycle in the wait-for graph is both necessary and sufficient proof that a deadlock exists among the transactions on that cycle, since it shows each one is, directly or indirectly, waiting on itself through the others.
A worked example. The deadlock from the earlier example produces a wait-for graph with an edge from A to B, since A waits on B's lock on Y, and an edge from B to A, since B waits on A's lock on X, forming a two-node cycle.
The key lines. No new SQL; the wait-for graph and its cycle check are maintained internally by the database's lock manager.
Wait-for graph
A wait-for graph has one node per transaction and an edge from A to B whenever A is waiting for a lock B currently holds; a cycle in this graph proves a deadlock exists among the transactions on it.
Example: arrows drawn from each stuck driver to whoever blocks them, forming a closed loop, mirrors a cycle in a wait-for graph.