Transaction deadlock storm

The idea

A deadlock is a standoff. Transaction T1 holds a lock on row A and now wants row B. Meanwhile T2 holds B and wants A. Each is blocked waiting for a lock the other refuses to release. They will wait forever.

The database draws a wait-for graph: an edge from every blocked transaction to whoever holds the lock it wants. When that graph contains a cycle, a deadlock exists. The engine can't satisfy everyone, so it picks a victim, rolls it back, and lets the survivor proceed. A "storm" is many such cycles forming at once under heavy contention.

How it works

The lock manager tracks who holds each lock and who is queued for it. On every grant request — or on a periodic timer — it walks the wait-for graph. A cycle means deadlock; the engine rolls back the cheapest victim, often the youngest transaction or the one holding the fewest locks, and returns a deadlock error the client should retry.

# Wait-for graph deadlock detection (cycle search)
def has_deadlock(waits_for):
    # waits_for[t] = set of transactions t is blocked behind
    WHITE, GREY, BLACK = 0, 1, 2
    color = {t: WHITE for t in waits_for}

    def dfs(t):
        color[t] = GREY
        for u in waits_for.get(t, ()):
            if color[u] == GREY:        # back-edge => cycle
                return True
            if color[u] == WHITE and dfs(u):
                return True
        color[t] = BLACK
        return False

    return any(color[t] == WHITE and dfs(t) for t in waits_for)

Cost & trade-offs

Watch out for

• Inconsistent lock ordering. The root cause is two paths grabbing the same rows in opposite order. Always acquire locks in a fixed global order, such as ascending primary key.
• Assuming retries are free. The victim's whole transaction is undone. Without idempotent, bounded retries you can amplify the storm.
• Long transactions. Holding locks across user think-time or network calls widens the window for cycles. Keep transactions short.
• Escalation surprises. Row locks escalating to page or table locks suddenly conflict with transactions that never touched your rows.
• Silent victims. If the app swallows the deadlock error instead of retrying, the user sees a mysterious failure.

Worked example

Two transfers run at once. T1 does debit(A); credit(B); T2 does debit(B); credit(A). T1 locks A, T2 locks B. Now T1 waits for B and T2 waits for A — a 2-cycle. The detector picks T2 as victim, rolls it back, and T1 completes. The fix: have both transfers lock accounts in account-id order, so both grab A first and one simply queues behind the other — no cycle.

Check yourself