DBMS Deadlock — Lock Order Bugs That Freeze Payment Systems

Every production database will eventually deadlock. It's not a sign that something is broken — it's a mathematical certainty when multiple transactions compete for overlapping resources. What separates a system that handles deadlocks gracefully from one that freezes under load is understanding the four conditions that create them, the algorithms that detect them, and the prevention strategies that trade throughput for safety. Netflix, Amazon, and every major bank have war stories about deadlocks that brought services down at peak traffic. This isn't academic — it's survival knowledge for anyone building data-intensive systems.

The root problem is that databases need locks to guarantee isolation — one of the four ACID properties. But the moment you have locks, you have the possibility of circular waiting. Two transactions each hold a resource and each wants a resource the other holds. Without intervention, they'll wait forever. The database has to pick a strategy: never let it happen (prevention), detect it after the fact and break the cycle (detection + recovery), or let the caller handle timeouts (avoidance via timeouts). Each strategy has real performance costs.

By the end of this article you'll be able to draw a resource allocation graph and spot a deadlock cycle in it, explain exactly how PostgreSQL's deadlock detector works and when it fires, write transaction code that minimises deadlock probability, and answer the trick interview questions about why deadlock prevention can be worse for throughput than detection. You'll also understand the four Coffman conditions and why you only need to break one of them to eliminate deadlocks entirely.

What is Deadlock in DBMS? The Four Coffman Conditions

A deadlock requires exactly four conditions to hold simultaneously. That's not a simplification — it's a theorem from Coffman et al. (1971). Break any one, and the deadlock disappears. Here's each condition with a database example.

1. Mutual Exclusion: Resources (rows, tables, pages) can be held by only one transaction at a time. If you could share every resource, no problem. But writes need exclusive access.
2. Hold and Wait: A transaction holds at least one lock while waiting for another. This is the default behavior — acquire lock A, then request lock B without releasing A.
3. No Preemption: The database can't forcibly take a lock from a transaction. Only the transaction itself releases its locks (usually at commit or rollback).
4. Circular Wait: There's a cycle in the lock-wait graph. Transaction T1 waits for a lock held by T2, T2 waits for T3, ..., Tn waits for T1.

The practical insight: prevention strategies target one condition. For example, using a lock ordering protocol (e.g., always lock accounts by ascending ID) prevents circular wait without changing anything else. That's the most common production fix.

-- Simulate hold-and-wait with circular wait
-- Transaction A
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- holds lock on row 1
-- now wait for row 2
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

-- Transaction B (run concurrently)
BEGIN;
UPDATE accounts SET balance = balance - 200 WHERE id = 2;  -- holds lock on row 2
-- now wait for row 1
UPDATE accounts SET balance = balance + 200 WHERE id = 1;
COMMIT;

-- If both run simultaneously, deadlock occurs.
-- PostgreSQL detects it after deadlock_timeout (default 1s) and aborts one transaction.

Deadlock Detection Algorithms: Wait-For Graph and Wound-Wait

Detection is the most common real-world strategy. Instead of preventing deadlocks (which costs throughput), allow them to happen, but catch them quickly and break them. There are two main detection approaches:

Wait-For Graph (WFG): The database maintains a directed graph where nodes are transactions, and an edge Ti → Tj means Ti is waiting for a lock held by Tj. Periodically, or when a lock wait exceeds a threshold, the system checks for cycles. If a cycle exists, choose a victim transaction and abort it (preferably the one that will cause the least work to rollback).

Example: PostgreSQL uses a background deadlock detector that runs every deadlock_timeout (default 1 second). It builds a wait-for graph from the lock manager's state and searches for cycles using a depth-first search. If found, it aborts the youngest transaction in the cycle. The error message tells you exactly which transaction was killed and why.

MySQL/InnoDB uses a different approach: it detects deadlocks immediately upon lock acquisition that would cause a cycle. It automatically chooses a transaction to roll back (the one that holds fewer locks or has done less work). You can see the last deadlock with SHOW ENGINE INNODB STATUS.

Wound-Wait and Wait-Die: These are both prevention and detection hybrids using transaction age (timestamp). Older transactions get priority. In Wound-Wait, if an older transaction requests a lock held by a younger one, it 'wounds' the younger (aborts it). In Wait-Die, older transactions wait, younger ones die (abort). These can cause more aborts than simple WFG detection.

-- PostgreSQL: Check current wait-for graph (requires pg_stat_activity and pg_locks)
SELECT
    blocked.pid AS blocked_pid,
    blocked.query AS blocked_query,
    blocking.pid AS blocking_pid,
    blocking.query AS blocking_query
FROM pg_locks blocked
JOIN pg_locks blocking ON blocked.locktype = blocking.locktype
    AND blocked.database = blocking.database
    AND blocked.relation = blocking.relation
    AND blocked.objid = blocking.objid
WHERE NOT blocked.granted
AND blocking.granted;

-- This shows pairs (blocked, blocking). If you find a cycle, you have a deadlock.

Deadlock Prevention Strategies: Breaking the Coffman Conditions

Prevention eliminates deadlocks by design — but it costs throughput. Here are the four strategies, each targeting one Coffman condition:

1. Prevent Mutual Exclusion: That's impossible for write operations. You can use optimistic concurrency control (like MVCC snapshot isolation) where writers don't block readers and write conflicts are detected on commit. But writes still need exclusive locks on the data being modified — you can't two people update the same row simultaneously without conflict.

2. Prevent Hold-and-Wait: Require a transaction to acquire all locks it will ever need upfront (predeclaration). In a database, this is often done by starting the transaction, locking all required rows in a single statement (e.g., SELECT ... FOR UPDATE for all needed rows in a consistent order). If any lock is unavailable, the transaction fails immediately instead of waiting. This reduces deadlock risk but increases lock contention and reduces concurrency.

3. Prevent No Preemption: Allow the database to preempt (forcibly abort) a transaction when deadlock is detected — that's detection, not prevention. True 'prevention' of no preemption would require a mechanism for the DB to take locks away, which isn't standard.

4. Prevent Circular Wait: Enforce a global ordering of resources. For example, always lock rows in ascending primary key order. If every transaction follows the same order, cycles cannot form. This is the most practical prevention technique and widely used in production.

Trade-off: Prevention via predeclaration (hold-and-wait) reduces concurrency dramatically. Prevention via lock ordering (circular wait) is cheap but requires discipline across the entire codebase. Most teams go with detection + recovery because prevention is complex to enforce.

// TheCodeForge — Lock ordering to prevent deadlock
package io.thecodeforge.db;

import java.sql.*;

public class LockOrderingExample {
    // Always lock accounts in ascending ID order
    public static void transferFunds(Connection conn, int fromId, int toId, double amount) throws SQLException {
        int lowId = Math.min(fromId, toId);
        int highId = Math.max(fromId, toId);

        conn.setAutoCommit(false);
        try {
            // Lock low ID first, then high ID
            lockAccount(conn, lowId);
            lockAccount(conn, highId);

            // Perform transfer
            updateBalance(conn, fromId, -amount);
            updateBalance(conn, toId, amount);

            conn.commit();
        } catch (SQLException e) {
            conn.rollback();
            throw e;
        } finally {
            conn.setAutoCommit(true);
        }
    }

    private static void lockAccount(Connection conn, int accountId) throws SQLException {
        String sql = "SELECT balance FROM accounts WHERE id = ? FOR UPDATE";
        try (PreparedStatement ps = conn.prepareStatement(sql)) {
            ps.setInt(1, accountId);
            ps.executeQuery();
        }
    }

    private static void updateBalance(Connection conn, int accountId, double delta) throws SQLException {
        String sql = "UPDATE accounts SET balance = balance + ? WHERE id = ?";
        try (PreparedStatement ps = conn.prepareStatement(sql)) {
            ps.setDouble(1, delta);
            ps.setInt(2, accountId);
            ps.executeUpdate();
        }
    }
}

Deadlock Recovery: Choosing the Victim and Rolling Back

When a deadlock is detected, the database must break the cycle by aborting one or more transactions (the 'victim'). The victim is chosen based on a cost metric:

• Transaction age: Younger transactions are cheaper to abort (less work done).
• Number of locks held: Fewer locks means less rollback work.
• Work done (e.g., rows modified): Rollback of a large transaction costs more I/O and CPU.

PostgreSQL's victim selection: it picks the transaction that will cause the least amount of redo (i.e., the one that has made the fewest changes). In practice, it's the youngest transaction in the cycle — not by timestamp, but by the transaction's virtual transaction ID (VXID).

MySQL's victim selection: InnoDB chooses the transaction that has performed the least work (based on undo log size). If equal, it picks one with fewer locks.

Once a victim is chosen, the database rolls back that transaction entirely. All its locks are released, allowing the other waiting transaction(s) to proceed. The application receives an error (e.g., '40001' serialization failure in PostgreSQL). The application must retry.

# TheCodeForge — Deadlock retry with exponential backoff
import time
import random
from sqlalchemy import create_engine, exc

def execute_transaction(conn_func):
    max_retries = 5
    for attempt in range(max_retries):
        try:
            return conn_func()
        except exc.OperationalError as e:
            if 'deadlock detected' in str(e) and attempt < max_retries - 1:
                sleep_time = 0.1 * (2 ** attempt) + random.uniform(0, 0.1)
                time.sleep(sleep_time)
            else:
                raise
    raise RuntimeError("Transaction failed after retries")

# Usage
engine = create_engine('postgresql://user:pass@localhost/db')
with engine.begin() as conn:
    result = execute_transaction(lambda: conn.execute("UPDATE accounts SET balance = balance - 100 WHERE id = 1"))

MVCC and Optimistic Concurrency Control: Avoiding Locks Altogether

Multi-Version Concurrency Control (MVCC) doesn't eliminate locks, but it changes the game. In MVCC, readers don't block writers and writers don't block readers — each transaction sees a snapshot of the database (a version). Conflicts only arise on write-write collisions. Deadlocks still happen, but they're less frequent because read operations don't acquire locks.

In PostgreSQL's MVCC (snapshot isolation), a write-transaction that updates a row locks that row. If another write-transaction tries to update the same row, it waits. If there's a cycle, deadlock occurs. So MVCC reduces the chance of deadlock by eliminating reads from the lock picture, but write-write contention remains.

Optimistic Concurrency Control (OCC): No locks at all during the transaction. All operations are applied locally to a private copy. At commit time, the database checks if a conflict occurred (e.g., via a version number or timestamp). If yes, the transaction is aborted and retried. OCC completely eliminates deadlocks because there are no locks! But the cost is high abort rate under contention.

In practice, most relational databases use MVCC (which is a form of pessimistic concurrency control for writes). In-memory databases and some NoSQL systems use OCC. The trade-off is clear: OCC has zero deadlock risk but can waste work on aborts under heavy contention. MVCC has lower abort rates but risk of deadlock.

-- OCC style version check in SQL (if your DB supports it)
-- Assume table accounts has a column 'version' integer
BEGIN;
SELECT balance, version INTO v_bal, v_ver FROM accounts WHERE id = 1;
-- Perform local calculation
UPDATE accounts SET balance = v_bal - 100, version = v_ver + 1 WHERE id = 1 AND version = v_ver;
-- If ROW_COUNT = 0, conflict – rollback and retry
COMMIT;

Deadlock Avoidance vs. Prevention: Why the Banker’s Algorithm Never Got Hired

Most teams confuse prevention with avoidance. Prevention breaks Coffman conditions upfront. Avoidance is smarter—it checks if granting a lock keeps the system in a safe state where all transactions can eventually complete. The textbook example is the Banker’s Algorithm: resources are like cash in a vault, and each transaction declares its max need upfront. The system only approves a request if it can still satisfy all remaining demands after the grant. In practice, real databases rarely implement this. Why? Because transactions don’t know their final resource requirements in advance, and the CPU cost of running the safety check on every lock request kills throughput. SQL Server’s deadlock avoidance is simpler: it uses the wait-die and wound-wait timestamp schemes. In wait-die, older transactions wait; younger ones die and retry. In wound-wait, older transactions force younger ones to abort. Both guarantee no deadlocks without needing a full safety check. The lesson: perfect avoidance is academic. Timestamp-based schemes are the pragmatic middle ground.

-- io.thecodeforge
-- Demonstration: Wait-Die vs Wound-Wait behavior
-- Assume transaction T1 (older, TS=10) holds lock on TableA
-- Transaction T2 (younger, TS=20) requests conflicting lock

-- Wait-Die:
-- T2 (younger) dies immediately, releases any held locks, retries later
-- T1 (older) continues waiting

-- Wound-Wait:
-- T1 (older) wounds T2: forces T2 to abort and release TableA
-- T1 acquires lock immediately

-- Simulated transaction using timestamp ordering
BEGIN TRANSACTION;
DECLARE @my_timestamp BIGINT = 20; -- younger transaction
IF EXISTS (SELECT 1 FROM sys.dm_tran_locks WHERE resource_database_id = DB_ID() AND request_owner_type = 'TRANSACTION' AND request_session_id <> @@SPID)
BEGIN
    -- Wound-Wait logic: if younger, abort
    IF @my_timestamp < (SELECT MIN(transaction_begin_time) FROM sys.dm_tran_current_transaction)
        ROLLBACK;
    ELSE
        WAITFOR DELAY '00:00:01'; -- simulate waiting
END;
COMMIT;

Real-World Deadlock Hunting: Trace Flags, Extended Events, and the Profiler Graph

When a deadlock hits production at 3 AM, you don’t guess. You need forensic evidence. SQL Server gives you three weapons. First, Trace Flag 1222 formats deadlock info into the SQL Server Error Log in XML. Enable it with DBCC TRACEON(1222, -1). The log shows you the victim transaction, the resources involved (like RID, KEY, or PAGE locks), and the exact SQL statements. Second, Extended Events capture deadlock graphs with zero overhead. Create a session on xml_deadlock_report and the database_xml_deadlock_report events. You get structured XML you can query. Third, the Profiler Deadlock Graph event produces a visual graph of circles (transactions) and squares (resources) with arrows showing wait chains. In practice, I start with Extended Events because it doesn’t require a server restart and runs 24/7. Parse the XML to find patterns: transactions accessing the same tables in opposite order, or queries with missing indexes causing table scans. Once you see the graph, the fix is usually obvious: reorder access, add an index, or switch to read committed snapshot isolation.

-- io.thecodeforge
-- Step 1: Enable Trace Flag 1222 for deadlock info in error log
DBCC TRACEON(1222, -1);
GO
-- Step 2: Query the error log for deadlock reports (SQL Server 2012+)
EXEC xp_readerrorlog 0, 1, N'deadlock', N'', N'2025-01-01', N'2025-12-31', 'asc';
GO

-- Step 3: Create an Extended Events session (lightweight, always-on)
CREATE EVENT SESSION [DeadlockMonitor] ON SERVER 
ADD EVENT sqlserver.xml_deadlock_report (
    ACTION (sqlserver.sql_text, sqlserver.session_id, sqlserver.client_hostname)),
ADD EVENT sqlserver.database_xml_deadlock_report (
    ACTION (sqlserver.sql_text))
ADD TARGET package0.event_file (SET filename = N'C:\DeadlockLogs\DeadlockMonitor.xel')
WITH (MAX_MEMORY=4096 KB, EVENT_RETENTION_MODE=ALLOW_SINGLE_EVENT_LOSS, 
       MAX_DISPATCH_LATENCY=30 SECONDS);
ALTER EVENT SESSION [DeadlockMonitor] ON SERVER STATE = START;
GO

Handling Deadlocks in Code: TRY...CATCH and Retry Logic That Won’t Burn CPU

You cannot eliminate deadlocks entirely. You handle them. The universal pattern is to catch error 1205 (deadlock victim) in SQL Server and retry. But naive retry kills performance. Here’s the correct approach: wrap each transaction in a TRY...CATCH block. On deadlock, wait a random amount of time (exponential backoff) to avoid same-cycle collisions, then retry up to 3 times. If it fails after that, log it and escalate. The worst retry strategy is immediate retry—you just hit the same deadlock instantly. The best strategy adds jitter: WAITFOR DELAY '00:00:00.' + CAST(FLOOR(RAND() * 500) AS VARCHAR). Also, keep transactions short. Long transactions are deadlock magnets. If you are using Entity Framework, set SqlCommand.CommandTimeout low and catch SqlException with number 1205. In Java with JDBC, catch SQLException with error code 1205. And never, ever put user input prompts inside a transaction. That’s the classic production deadlock: the user goes to lunch while holding locks.

// io.thecodeforge
using System;
using System.Data.SqlClient;
using System.Threading;

public class DeadlockHandler
{
    public static void ExecuteWithRetry(string connectionString, string commandText)
    {
        int maxRetries = 3;
        int retryCount = 0;
        int baseDelayMs = 100;
        Random rng = new Random();

        while (retryCount < maxRetries)
        {
            try
            {
                using (var conn = new SqlConnection(connectionString))
                {
                    conn.Open();
                    using (var cmd = new SqlCommand(commandText, conn))
                    {
                        cmd.CommandTimeout = 30; // short timeout
                        cmd.ExecuteNonQuery();
                    }
                }
                return; // success, exit loop
            }
            catch (SqlException ex) when (ex.Number == 1205) // deadlock victim
            {
                retryCount++;
                if (retryCount >= maxRetries)
                {
                    // Log and escalate
                    throw new InvalidOperationException("Deadlock persisted after retries", ex);
                }
                // Exponential backoff with random jitter
                int delayMs = (int)Math.Pow(2, retryCount) * baseDelayMs + rng.Next(0, 200);
                Thread.Sleep(delayMs);
            }
        }
    }
}

Deadlock Detection in PostgreSQL: deadlock_timeout and pg_locks

PostgreSQL uses a deadlock detection mechanism that relies on a timeout and a wait-for graph. The parameter deadlock_timeout (default 1 second) controls how long a process waits before checking for deadlocks. When a process waits for a lock longer than this timeout, PostgreSQL builds a wait-for graph and checks for cycles. If a deadlock is detected, one transaction is chosen as the victim and rolled back, releasing its locks. The pg_locks system view provides real-time lock information, showing which locks are held and which are awaited. For example, you can query pg_locks to identify blocking sessions. Practical use: set deadlock_timeout to a lower value (e.g., 200ms) in high-contention systems to detect deadlocks faster, but be aware of the overhead of frequent graph checks. Use pg_stat_activity and pg_locks together to pinpoint problematic queries. Example: a payment system where two transactions update accounts in opposite order can deadlock; monitoring pg_locks reveals the cycle.

-- Check current locks and waits
SELECT pid, locktype, relation::regclass, mode, granted
FROM pg_locks
WHERE NOT granted;

-- Identify blocking sessions
SELECT blocked.pid AS blocked_pid,
       blocked.query AS blocked_query,
       blocking.pid AS blocking_pid,
       blocking.query AS blocking_query
FROM pg_stat_activity blocked
JOIN pg_locks blocked_locks ON blocked.pid = blocked_locks.pid
JOIN pg_locks blocking_locks ON blocked_locks.locktype = blocking_locks.locktype
  AND blocked_locks.database = blocking_locks.database
  AND blocked_locks.relation = blocking_locks.relation
  AND blocked_locks.mode = blocking_locks.mode
JOIN pg_stat_activity blocking ON blocking.pid = blocking_locks.pid
WHERE NOT blocked_locks.granted
  AND blocking_locks.granted;

Application-Level Deadlock Prevention Patterns

Application-level patterns can prevent deadlocks without relying solely on database mechanisms. Key patterns include: (1) Fixed lock ordering – always acquire locks in a consistent global order (e.g., by table name or primary key). For example, in a payment system, always lock account A then B, never B then A. (2) Lock timeout with retry – use NOWAIT or lock_timeout in PostgreSQL to fail fast if a lock cannot be acquired, then retry with exponential backoff. (3) Single-threaded worker per resource – use a queue to serialize access to a resource (e.g., a dedicated worker for each account). (4) Optimistic concurrency – use version numbers or timestamps to detect conflicts and retry the transaction. Example: in a banking app, use SELECT ... FOR UPDATE NOWAIT and catch the lock failure, then retry after a random delay. These patterns reduce deadlock probability but require careful design. For distributed systems, consider using a distributed lock manager like Redis Redlock.

import psycopg2
from psycopg2 import OperationalError
import time
import random

def transfer_funds(from_acct, to_acct, amount):
    # Fixed lock order: always lock smaller account ID first
    if from_acct > to_acct:
        from_acct, to_acct = to_acct, from_acct
        amount = -amount
    conn = psycopg2.connect("dbname=payments")
    try:
        with conn:
            with conn.cursor() as cur:
                # Use NOWAIT to fail fast if lock not available
                cur.execute("SELECT balance FROM accounts WHERE id = %s FOR UPDATE NOWAIT", (from_acct,))
                cur.execute("SELECT balance FROM accounts WHERE id = %s FOR UPDATE NOWAIT", (to_acct,))
                cur.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s", (amount, from_acct))
                cur.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", (amount, to_acct))
    except OperationalError as e:
        if 'could not obtain lock' in str(e):
            time.sleep(random.uniform(0.1, 0.5))
            return transfer_funds(from_acct, to_acct, amount)  # retry
        else:
            raise

Distributed Database Deadlocks and Wait-Die/Wound-Wait

In distributed databases, deadlocks span multiple nodes and are harder to detect. Two classic schemes are Wait-Die and Wound-Wait, which are deadlock prevention protocols that assign timestamps to transactions. In Wait-Die: if an older transaction (smaller timestamp) waits for a younger one, it dies (rolls back) and restarts with the same timestamp; if younger waits for older, it waits. In Wound-Wait: if an older transaction requests a lock held by a younger one, it wounds (forces rollback) the younger; if younger requests from older, it waits. These schemes prevent deadlocks without detection overhead. For example, in a sharded payment system, each transaction gets a timestamp from a global clock. Wait-Die is pessimistic (older transactions die often), while Wound-Wait is more aggressive (younger transactions are killed). Practical implementation: use a distributed timestamp oracle (e.g., Google Spanner's TrueTime) or logical clocks. Many modern distributed databases (e.g., CockroachDB) use variants of these protocols. Trade-offs: Wait-Die reduces wasted work from killed young transactions, but older transactions may starve; Wound-Wait favors older transactions but can cause more rollbacks.

import time

class DistributedTransaction:
    def __init__(self, timestamp):
        self.timestamp = timestamp
        self.locks = set()

    def request_lock(self, lock, other_txn):
        # Wait-Die: older waits for younger? No: older dies if waiting for younger
        if self.timestamp < other_txn.timestamp:  # older
            # Die: rollback and restart
            self.rollback()
            return False
        else:  # younger
            # Wait
            lock.wait(self)
            return True

    def rollback(self):
        # release locks, restart with same timestamp
        pass

# Wound-Wait: older wounds younger
class WoundWaitTransaction:
    def request_lock(self, lock, other_txn):
        if self.timestamp < other_txn.timestamp:  # older
            lock.wound(other_txn)  # force rollback of younger
            lock.acquire(self)
            return True
        else:  # younger
            lock.wait(self)
            return True