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.

   sql

   Open in EditorCopy

   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;

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

   python

   Open in EditorCopy

   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

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.