Deadlock Diagnosis Workflow
Diagnose a deadlock by capturing the lock wait graph at the moment of deadlock, identifying the cycle, and breaking it by ordering lock acquisition.
Objective
Identify the set of transactions and locks that form a deadlock cycle, and fix the code so the cycle cannot recur by imposing a lock acquisition order.
Environment
- A system with lock-based concurrency
- A way to dump the lock wait graph on deadlock
- Reproducing traffic that triggers the deadlock
Steps
1. Capture the wait graph
On a deadlock detection, dump the lock wait graph: which transaction holds which lock and waits for which.
Expected state: A graph with a cycle that is the deadlock.
2. Identify the cycle
Find the cycle in the wait graph; the transactions in the cycle are the deadlocked set, and the locks are the contested resources.
Expected state: A cycle of transactions and locks that explains the deadlock.
3. Impose lock order
Pick a total order on the locks and ensure all transactions acquire them in that order, so a cycle cannot form.
Expected state: The cycle is broken because no two transactions acquire locks in conflicting orders.
4. Verify no recurrence
Run the reproducing traffic and assert no deadlock occurs over a sustained period.
Expected state: The deadlock does not recur under the same traffic.
Decision points
Lock order by what?
- By lock id
- By resource name
By resource name, so the order is stable and readable across code changes.
Enforce order how?
- Runtime check that asserts order
- Code review only
Runtime check in test, code review in production, because a runtime check in production adds overhead.
Expected outcome
The deadlock cycle is identified and broken by a lock acquisition order, and the reproducing traffic no longer deadlocks.
Verification
Run the reproducing traffic for 10000 iterations and confirm no deadlock is detected, and the lock order is enforced by a runtime check or a code review.
Cleanup
Keep the lock order and the wait-graph dump tool; remove the reproducing traffic artifacts.
Capture the wait graph
A deadlock is a cycle in the lock wait graph: transaction A holds lock 1 and waits for lock 2, while transaction B holds lock 2 and waits for lock 1. The graph at the moment of deadlock has the cycle, and dumping it is the first step.
dump-wait-graph > graph.dot
cycle-detect graph.dotIdentify the cycle
The cycle in the wait graph is the deadlock. The transactions in the cycle are the deadlocked set, and the locks are the contested resources. The cycle explains who holds what and waits for what, which is the diagnosis.
Impose a lock order
A cycle forms because two transactions acquire locks in different orders. Impose a total order on the locks and ensure all transactions acquire them in that order, so a cycle cannot form: if every transaction acquires lock 1 before lock 2, no transaction can hold lock 2 and wait for lock 1.
// Always acquire locks in ascending id order
const locks = [l1, l2].sort(byId);
for (const l of locks) await l.acquire();Verification
The reproducing traffic runs for 10000 iterations with no deadlock. The lock order is enforced by a runtime assertion in test and a code review in production, so a future change that violates the order is caught before it ships.