Notestransactions🌱 seedling

Deadlock

Also: Deadlocks · Waits-For Graph · Deadlock Detection · Wound-Wait · Wait-Die · Lock Ordering

Two or more transactions each hold a lock the other needs, so all of them wait forever. Databases find the cycle in a waits-for graph (or prevent it with timestamp priorities) and abort a victim, which the application must retry.

Why it exists

Any system where transactions acquire locks incrementally and hold them, like Two-Phase Locking or SELECT … FOR UPDATE, can form a cycle: T1 holds A and wants B, T2 holds B and wants A.

How it works

  • Detection: the lock manager tracks who waits for whom and searches for cycles. Postgres checks after deadlock_timeout (1 s by default) and aborts a victim with SQLSTATE 40P01; InnoDB checks as soon as a transaction would wait (MySQL error 1213).
  • Timeouts: with innodb_deadlock_detect off (sometimes done under extreme concurrency, where detection itself is costly), InnoDB relies on innodb_lock_wait_timeout, 50 s by default.
  • Prevention by priority: each transaction gets a timestamp. Wait-die: a younger requester aborts itself instead of waiting. Wound-wait: an older requester aborts the younger holder. Either way waits only run one direction, so no cycle forms.
  • Prevention by ordering: acquire locks in a global order (e.g. ascending primary key).

Trade-offs

Approach Cost
detection CPU for graph search; victims lose their work
timeouts slow to resolve; can abort transactions that weren't deadlocked
wait-die / wound-wait aborts some transactions that would never have deadlocked
lock ordering discipline across every code path

In practice

  • Spanner uses wound-wait for read-write transactions, so it never needs global deadlock detection.
  • A frequent real-world source: two code paths updating the same pair of rows in opposite orders, or gap-lock conflicts between concurrent inserts in InnoDB.

Pitfalls

  • Treating a deadlock error as fatal instead of retrying the whole transaction.
  • Long transactions widen the window in which cycles form.

Recall

These cards are also in your review deck, scheduled with spaced repetition.