Deadlocks and Recovery

Two Trains, One Track

Picture two trains on a single-track rail network. Train A is sitting at Station X, waiting for the line between X and Y to clear. Train B is sitting at Station Y, waiting for the line between Y and X to clear.

Neither train will ever move. Both are waiting for the other. There is no resolution — unless someone outside the system intervenes and moves one of the trains backward.

That is a deadlock. And it happens in databases dozens of times per day in any busy system.

What Is a Database Deadlock?

A deadlock occurs when two or more transactions are each waiting for a lock held by another transaction in the group. No transaction can proceed — they are all frozen, waiting indefinitely.

Transaction A holds: Lock on Row 1
Transaction A wants: Lock on Row 2

Transaction B holds: Lock on Row 2
Transaction B wants: Lock on Row 1

→ Circular wait. Neither can proceed.

The Four Coffman Conditions

A deadlock can only occur when all four conditions hold simultaneously. These were identified by Edward Coffman in 1971:

Break any one of these conditions and deadlock becomes impossible.

Detection: The Wait-For Graph

Databases detect deadlocks by building a Wait-For Graph (WFG):

• Each transaction is a node
• A directed edge from A → B means "Transaction A is waiting for a lock held by Transaction B"
• A cycle in the graph = a deadlock

Wait-For Graph — No Deadlock:        Wait-For Graph — Deadlock Detected:

  Txn A ──→ Txn B ──→ Txn C            Txn A ──→ Txn B
                                               ↑         │
  (no cycle = no deadlock)                     └──── Txn C ←─┘

                                        (cycle A→B→C→A = deadlock!)

The database's deadlock detector runs periodically (e.g., every 1 second in PostgreSQL) or on every lock wait. When a cycle is found, it selects one transaction as the victim and rolls it back.

Real Deadlock Error Messages

PostgreSQL:

ERROR:  deadlock detected
DETAIL:  Process 12483 waits for ShareLock on transaction 7890;
         blocked by process 12491.
         Process 12491 waits for ShareLock on transaction 7889;
         blocked by process 12483.
HINT:   See server log for query details.

MySQL:

ERROR 1213 (40001): Deadlock found when trying to get lock;
try restarting transaction

Your application must catch these errors and retry the transaction.

Prevention: Break a Coffman Condition

Strategy 1: Lock Ordering (Breaks Circular Wait)

Always acquire locks in the same global order. If every transaction locks Row 1 before Row 2 before Row 3, a circular wait can never form.

-- WRONG: Transaction A locks orders then customers
--        Transaction B locks customers then orders
-- → Deadlock possible

-- CORRECT: Both transactions always lock in the same order
-- 1. Lock customers table first
-- 2. Then lock orders table

Strategy 2: Lock Everything Upfront (Breaks Hold and Wait)

Acquire all needed locks at the start of the transaction. If any lock is unavailable, release all held locks and retry.

-- Acquire all locks in one shot
SELECT * FROM accounts WHERE id IN (1, 2) FOR UPDATE;
-- Now update safely — no incremental lock acquisition
UPDATE accounts SET balance = balance - 500 WHERE id = 1;
UPDATE accounts SET balance = balance + 500 WHERE id = 2;
COMMIT;

Strategy 3: Timeouts (Break No Preemption)

Set a lock wait timeout. If a transaction waits too long, it is automatically aborted.

-- PostgreSQL: abort if waiting more than 3 seconds
SET lock_timeout = '3s';

-- MySQL: wait at most 5 seconds for a lock
SET innodb_lock_wait_timeout = 5;

Avoidance: The Banker's Algorithm (Brief Overview)

The Banker's Algorithm (Dijkstra, 1965) is a resource-allocation strategy that only grants a resource if doing so leaves the system in a "safe state" — a state from which all transactions can eventually complete.

It works by simulating resource allocation ahead of time:

If granting this lock would leave the system unable to
satisfy all remaining transactions → DENY the lock (wait)

If granting the lock still leaves a safe path to completion → GRANT it

This is used in operating systems and some specialized database environments. Most general-purpose databases prefer detection + recovery because avoidance is too expensive to compute at high transaction rates.

Recovery: Victim Selection

When a deadlock is detected, the database must choose a victim transaction to roll back. Selection criteria typically include:

1. Transaction age — kill the youngest transaction (least work lost)
2. Number of locks held — kill the transaction holding fewest locks
3. Number of rows modified — kill the transaction with fewest changes
4. Explicit priority — some systems allow user-defined priority

-- PostgreSQL: you can view lock conflicts in pg_locks
SELECT pid, wait_event_type, wait_event, query
FROM pg_stat_activity
WHERE wait_event IS NOT NULL;

Application-Level Best Practices

These habits dramatically reduce deadlock frequency in production systems:

1. Keep transactions short. The longer a transaction runs, the more time it holds locks and the more chances for a conflict.

2. Access tables in a consistent order. If one part of your app always updates orders before order_items, every part of your app should do the same.

3. Avoid user interaction inside transactions. Never wait for a user to click a button while holding a database lock.

4. Use SELECT ... FOR UPDATE deliberately. This escalates a read lock to a write lock immediately — useful when you know you will update the row.

   BEGIN;
   SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;
   -- Now this row is exclusively locked — no other transaction can modify it
   UPDATE accounts SET balance = balance - 100 WHERE id = 1;
   COMMIT;
   

   Copy

5. Implement retry logic. Deadlocks are a normal part of database operation. Your application must catch deadlock errors and retry.

   import time
   
   def transfer_funds(conn, from_id, to_id, amount, retries=3):
       for attempt in range(retries):
           try:
               with conn.transaction():
                   conn.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s", (amount, from_id))
                   conn.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", (amount, to_id))
               return  # success
           except DeadlockError:
               if attempt == retries - 1:
                   raise
               time.sleep(0.1 * (attempt + 1))  # exponential backoff
   

   Copy

Key Takeaways

• A deadlock is a circular wait where each transaction holds a lock the next transaction needs.
• Four Coffman conditions must all be true for a deadlock to occur — eliminate any one to prevent it.
• Databases use a Wait-For Graph to detect cycles and identify deadlocks automatically.
• The database resolves deadlocks by selecting a victim transaction and rolling it back.
• Prevention strategies: consistent lock ordering, upfront locking, and lock timeouts.
• Application best practice: always implement retry logic for deadlock errors — they are expected, not exceptional.

A deadlock is not a bug in your database. It is a sign that two transactions are competing over the same resources. The right response is always retry with intelligent backoff.