Wait-for graph with a closed cycle, the four Coffman conditions, and the three deadlock strategies

Databases & Storage

Two Transactions Each Holding What the Other Needs

A deadlock is not a bug in one query. It is a cycle in a graph — and once you see it that way, every fix makes sense, because each strategy attacks a different condition that the cycle requires.

Core Concept

Draw one node per transaction, and draw an arrow from A to B when A is waiting for a lock that B holds. That is the wait-for graph. A deadlock is exactly a cycle in it: T1 holds what T2 wants, T2 holds what T1 wants, and neither can move. The cycle can only exist when four conditions hold at the same time — the Coffman conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Every strategy on the card removes one of them or reacts to the result.

Key Components

Wait-For Graph

One node per transaction, an arrow A→B when A waits on a lock B holds. A closed cycle = a deadlock, and nothing else qualifies.

Coffman Conditions

Mutual exclusion, hold-and-wait, no preemption, circular wait. All four must coexist — kill any one and the cycle cannot form.

Detection & Victim

The engine periodically checks the graph for cycles, picks a victim by a cost heuristic, and aborts it. Postgres reports SQLSTATE 40P01 (deadlock_detected).

Prevention & Recovery

Take locks in one global order (cheapest at runtime, costs discipline), or roll back and retry with backoff + jitter so retries don't rebuild the same cycle.

How It Works

The setup. Transaction A holds row X and asks for row Y. Transaction B holds row Y and asks for row X. Both are holding something while waiting for something else — hold-and-wait, live.

The graph closes. The wait-for graph gains two arrows: A→B and B→A. That is a cycle. With mutual exclusion, no preemption, and no third way out, all four Coffman conditions are now true at once.

The engine reacts. Detection waits a beat (Postgres: deadlock_timeout, default 1 second — that is the wait before checking for a cycle, so raising it slows reporting, it does not prevent anything), finds the cycle, and aborts the victim.

The app must retry. Roll back, release, and retry — but with backoff plus jitter. If both transactions retry at the same instant, they simply rebuild the identical cycle. The application is expected to survive a transaction it did nothing wrong in.

Real-World Applications

Bank transfers between two accountsThe canonical 40P01: two transfers swap balances on the same pair of accounts in opposite order. Fix: always lock account #1 before #2, by id.

Order + inventory updatesService A locks the order row then the inventory row; service B does the reverse. Global lock ordering (orders before inventory, always) makes the cycle impossible.

Reading the engine's own reportMySQL InnoDB detects immediately and names both victim statements in SHOW ENGINE INNODB STATUS — read it, confirm it names the two statements you suspect.

Building one on demandTwo sessions, each updating two rows in the opposite order. If you can't reproduce a deadlock on demand, you can't honestly claim to have prevented one.

Three Traps (Falsification)

Before you trust the fix

A timeout is not detection. If you only ever see "lock wait timeout exceeded", you cannot tell a genuine cycle from a slow transaction legitimately holding a lock — and the fix for each is opposite (reorder locks vs. make the slow thing faster).
"Stuck" is rarely a deadlock. A system that feels frozen is far more often suffering lock contention or a long-running transaction — neither is a cycle, so deadlock advice will not help.
A livelock survives every deadlock strategy. Transactions abort and retry forever without deadlocking or progressing — no cycle is ever detected, the graph looks healthy, and throughput is zero.

Checkpoint — answer before you move on

1.What structure in the wait-for graph is a deadlock exactly, and which of the four Coffman conditions does acquiring locks in a global order remove?

Think: closed loop / cycle … and the condition that says "each is waiting on the next one in a ring."

2.Postgres reports deadlocks as SQLSTATE 40P01. What does deadlock_timeout (default 1s) actually control — and why does raising it make real deadlocks take longer to report instead of preventing them?

Think: it is the wait before the engine even checks for a cycle, not a prevention knob.

3.Why must a retry after a deadlock abort use backoff plus jitter? What goes wrong if both aborted transactions retry at the same instant?

Think: synchronized retries rebuild the exact same cycle — a retry storm.