Database Deadlock: Causes, Detection, and Prevention

Transaction A                    Transaction B
─────────────────────────────────────────────────────────
LOCK A                           LOCK B
    │                                  │
    │                                  │
    ▼                                  ▼
WAIT FOR B ←──── DEADLOCK ────→ WAIT FOR A

Four necessary conditions:
1. Mutual exclusion (locks cannot be shared)
2. Hold and wait (hold locks while waiting for others)
3. No preemption (locks cannot be forcibly taken)
4. Circular wait (cycle of waiting transactions)

Transaction A                    Transaction B
─────────────────────────────────────────────────────────
BEGIN;                           BEGIN;
    UPDATE accounts SET balance = balance - 100 WHERE id = 1;
                                     UPDATE accounts SET balance = balance - 50 WHERE id = 2;
    -- Lock on account 1 held         -- Lock on account 2 held

    UPDATE accounts SET balance = balance + 100 WHERE id = 2;
    -- Waiting for lock on account 2
                                     UPDATE accounts SET balance = balance + 50 WHERE id = 1;
                                     -- Waiting for lock on account 1

DEADLOCK! Neither transaction can proceed.
Database detects deadlock and aborts one transaction (victim).

Transaction A ──waits for──→ Transaction B
      ↑                              │
      │                              │
      └──────────waits for───────────┘

Cycle detected → Deadlock!

Detection methods:
- Periodic polling: Check for cycles at regular intervals
- Timeout-based: Assume deadlock if transaction waits too long
- Edge-chasing: Propagate probes to detect cycles

PostgreSQL:
- Automatically detects deadlocks using wait-for graph
- Aborts one transaction with error: "deadlock detected"
- Returns error code: 40P01

MySQL (InnoDB):
- Automatically detects deadlocks
- Aborts the transaction that has done the least work
- Returns error: "Deadlock found when trying to get lock"

SQL Server:
- Automatically detects deadlocks
- Aborts the transaction with lower cost
- Returns error: 1205

Oracle:
- Automatically detects deadlocks
- Aborts the transaction that detected the deadlock
- Returns ORA-00060

-- Transaction A
UPDATE products SET price = price * 1.1 WHERE category = 'electronics';
UPDATE inventory SET quantity = quantity - 10 WHERE product_id IN (SELECT id FROM products WHERE category = 'electronics');

-- Transaction B (running concurrently)
UPDATE inventory SET quantity = quantity + 100 WHERE product_id = 123;
UPDATE products SET price = price * 0.9 WHERE id = 123;

-- Transaction A: Updates via index
UPDATE users SET status = 'active' WHERE status = 'pending';

-- Transaction B: Updates via primary key
UPDATE users SET last_login = NOW() WHERE id = 123;

-- Deadlock occurs because locks are acquired in different orders on the index and table

-- Transaction A
INSERT INTO orders (customer_id, total) VALUES (1, 100);
-- Locks parent table (customers) for referential integrity check

-- Transaction B
DELETE FROM customers WHERE id = 1;
-- Locks customers table, waiting for orders foreign key check

-- Deadlock: A holds lock on customers? B holds lock on customers? (depends on order)

-- Bad: Different access orders
-- Transaction A: Table1 → Table2
-- Transaction B: Table2 → Table1

-- Good: Same access order
-- Transaction A: Table1 → Table2
-- Transaction B: Table1 → Table2

-- Bad: Long transaction with user interaction
BEGIN;
    SELECT * FROM accounts WHERE id = 1;  -- Lock held during user think time
    -- User thinks for 10 seconds...
    UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

-- Good: Short transaction
SELECT * FROM accounts WHERE id = 1;  -- No lock
-- User thinks
BEGIN;
    UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

-- Serializable has highest deadlock risk
-- Read Committed has lower deadlock risk
-- Read Uncommitted has no read locks (but risks dirty reads)

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;

-- Ensure your database uses row-level locking
-- In MySQL: Use InnoDB (not MyISAM)
-- In PostgreSQL: Default is row-level
-- Avoid operations that escalate to table locks:
--   - ALTER TABLE
--   - LOCK TABLE
--   - Large DELETE without WHERE

-- PostgreSQL: NOWAIT (fail if lock not available)
BEGIN;
    SELECT * FROM jobs WHERE status = 'pending' FOR UPDATE NOWAIT;
    -- If lock cannot be acquired, error is thrown immediately
COMMIT;

-- PostgreSQL: SKIP LOCKED (skip locked rows, continue with others)
BEGIN;
    SELECT * FROM jobs WHERE status = 'pending' FOR UPDATE SKIP LOCKED;
    -- Returns only rows that are not locked by other transactions
COMMIT;

import time
from psycopg2 import errors

def execute_with_retry(func, max_retries=3):
    for attempt in range(max_retries):
        try:
            return func()
        except errors.DeadlockDetected as e:
            if attempt == max_retries - 1:
                raise
            time.sleep(0.1 * (2 ** attempt))  # Exponential backoff
            continue

@execute_with_retry
def transfer_money():
    with connection.begin():
        connection.execute("UPDATE accounts SET balance = balance - 100 WHERE id = 1")
        connection.execute("UPDATE accounts SET balance = balance + 100 WHERE id = 2")

async function executeWithRetry(fn, maxRetries = 3) {
    for (let i = 0; i < maxRetries; i++) {
        try {
            return await fn();
        } catch (err) {
            if (err.code !== 'ER_LOCK_DEADLOCK' || i === maxRetries - 1) {
                throw err;
            }
            await new Promise(resolve => setTimeout(resolve, 100 * Math.pow(2, i)));
        }
    }
}

await executeWithRetry(async () => {
    await connection.beginTransaction();
    await connection.execute('UPDATE accounts SET balance = balance - 100 WHERE id = 1');
    await connection.execute('UPDATE accounts SET balance = balance + 100 WHERE id = 2');
    await connection.commit();
});

-- Check deadlock logs
SHOW log_min_messages;  -- Should be 'warning' or lower

-- Query deadlock statistics
SELECT * FROM pg_stat_database WHERE datname = 'your_database';

-- Track deadlock frequency
SELECT datname, deadlocks FROM pg_stat_database;

-- Show the last deadlock
SHOW ENGINE INNODB STATUS\G
-- Look for "LATEST DETECTED DEADLOCK" section

-- Enable deadlock logging
SET GLOBAL innodb_print_all_deadlocks = ON;

-- Check deadlock metrics
SHOW STATUS LIKE 'Innodb_deadlocks';

-- Capture deadlock graphs using extended events
CREATE EVENT SESSION deadlock_monitor ON SERVER
ADD EVENT sqlserver.xml_deadlock_report
ADD TARGET package0.ring_buffer;

-- Query deadlock frequency
SELECT * FROM sys.dm_tran_locks
WHERE request_status = 'WAIT';

-- Without index: UPDATE locks entire table
-- With index: UPDATE locks only matching rows

CREATE INDEX idx_orders_status ON orders(status);

-- This UPDATE now locks only rows with status = 'pending'
UPDATE orders SET status = 'processed' WHERE status = 'pending' LIMIT 100;