Deadlock Detection & Prevention

The Circular Wait Problem 🌀

Deadlock occurs when two or more transactions wait for each other indefinitely, creating a circular dependency that prevents any of them from proceeding.

Classic Deadlock Example

T1: LOCK_X(Account_A)
T2: LOCK_X(Account_B)
T1: LOCK_X(Account_B)  ← Waits for T2 to release B
T2: LOCK_X(Account_A)  ← Waits for T1 to release A

Result: Both transactions are stuck forever! 💀

Deadlock Detection: Wait-for Graphs 📊

The Graph Approach

A wait-for graph is a directed graph where:

• Nodes represent transactions

• Edges represent waiting relationships (Ti → Tj means Ti waits for Tj)

Deadlock Detection Algorithm

def detect_deadlock(wait_for_graph):
    """
    Use DFS to detect cycles IN wait-for graph
    Returns: List of transactions IN deadlock (if any)
    """

    def dfs(node, visited, rec_stack, path):
        visited.add(node)
        rec_stack.add(node)
        path.append(node)

        for neighbor IN wait_for_graph[node]:
            if neighbor IN rec_stack:
                # Found cycle - extract deadlock
                cycle_start = path.index(neighbor)
                return path[cycle_start:]

            if neighbor NOT IN visited:
                result = dfs(neighbor, visited, rec_stack, path)
                if result:
                    return result

        rec_stack.remove(node)
        path.pop()
        return None

    for TRANSACTION IN wait_for_graph:
        if TRANSACTION NOT IN visited:
            cycle = dfs(TRANSACTION, SET(), SET(), [])
            if cycle:
                return cycle

    return None  # No deadlock

Deadlock Prevention Strategies 🛡️

1. Lock Ordering (Conservative Approach)

2. Timeout-Based Prevention

3. Timestamp-Based Protocols

Deadlock Resolution: Victim Selection 🎯

When a deadlock is detected, one transaction must be aborted to break the cycle.

Victim Selection Criteria

Victim Selection Algorithm

def select_victim(deadlock_cycle):
    """
    SELECT best victim FROM deadlock cycle
    Returns: TRANSACTION to abort
    """
    best_victim = None
    min_cost = float('inf')

    for TRANSACTION IN deadlock_cycle:
        # Calculate composite cost score
        cost = (
            TRANSACTION.work_done * 0.4 +           # 40% weight
            TRANSACTION.locks_held * 0.3 +          # 30% weight  
            TRANSACTION.abort_count * (-0.2) +      # 20% weight (negative = priority)
            TRANSACTION.age * (-0.1)                # 10% weight (negative = priority)
        )

        if cost < min_cost:
            min_cost = cost
            best_victim = TRANSACTION

    return best_victim

Real-World Deadlock Handling 🏭

PostgreSQL Approach

-- Configure deadlock detection
SET deadlock_timeout = '1s';  -- Check for deadlocks after 1 second

-- PostgreSQL automatically:
-- 1. Detects deadlocks using wait-for graphs
-- 2. Selects victim (usually newest transaction)
-- 3. Aborts victim with ERROR: deadlock detected

MySQL InnoDB Strategy

-- InnoDB deadlock detection is automatic
-- Configuration options:
SET GLOBAL innodb_deadlock_detect = ON;    -- Enable detection
SET GLOBAL innodb_lock_wait_timeout = 50;  -- Max wait time

-- InnoDB automatically:
-- 1. Detects deadlocks immediately 
-- 2. Selects victim with least cost (estimated by undo work)
-- 3. Returns ERROR 1213: Deadlock found when trying to get lock

Performance Implications ⚡

Best Practices 🎯

Key Takeaways 🧠

What's Next? 🔜

Now you understand how to handle deadlocks. Continue learning:

1. Lock Examples - See deadlocks and resolution in action

2. Two-Phase Locking - Review how 2PL creates deadlock potential

3. Lock Foundations - Back to the basics