Database deadlocks: an interactive wait-for graph and the lock-ordering fix

A deadlock happens when transactions wait for each other in a circle: T1 holds row A and wants row B, while T2 holds B and wants A. Neither can move, and waiting longer does not help. Databases detect the cycle in a wait-for graph and abort one transaction, which the application must retry. The reliable cure is to make cycles impossible by always taking locks in the same order.

The playground runs money transfers that each lock two account rows, taking turns. Step through what happens, watch the wait-for graph, and turn on locking in id order.

How a deadlock forms, and how it is found

Transferring from A to B locks A then B; transferring from B to A locks B then A. Run together, each takes its first row, then waits for the other’s. Every database keeps track of who waits for whom, and a cycle in that graph is a deadlock. PostgreSQL checks for one after a transaction has waited deadlock_timeout, one second by default, and aborts it with “deadlock detected”; InnoDB checks immediately and rolls back the transaction that has changed the fewest rows. The cycle can be longer than two: three transfers A to B, B to C and C to A deadlock the same way.

Deadlocks become common under load. In the playground’s random batches, eight concurrent transfers over five accounts deadlock about 25 times in every 100 transfers. Locking in id order brings that to zero.

Preventing them

• Lock in a consistent order. Sort the rows by id and lock them in that order, ideally in one statement with ORDER BY id FOR UPDATE. Whoever gets the first lock can always get the rest, so waits never form a circle.
• Keep transactions short and do no network calls or user interaction while holding locks.
• Retry on deadlock errors. Even careful code meets them, through foreign keys, indexes or triggers that take locks implicitly. Retry the whole transaction, and make it idempotent if it has effects outside the database.
• Avoid locks altogether where you can: a single UPDATE ... SET balance = balance - 10, or optimistic concurrency with a version check, holds nothing between statements.

Distributed locks across services can deadlock too, and there is no single database to see the whole graph. Systems there rely on lock ordering, timeouts and leases that expire rather than on detection.

A transfer that cannot deadlock with itself

from psycopg import errors

def transfer(conn, src, dst, amount, tries=3):
    for attempt in range(tries):
        try:
            with conn.transaction():
                # lock both rows up front, always in id order
                conn.execute(
                    "SELECT id FROM accounts WHERE id IN (%s, %s) ORDER BY id FOR UPDATE",
                    (src, dst))
                conn.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s", (amount, src))
                conn.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", (amount, dst))
            return
        except errors.DeadlockDetected:          # SQLSTATE 40P01: rerun the whole transaction
            continue
    raise RuntimeError("transfer kept deadlocking")

In a system design interview

Bring it up when two rows change in one transaction: “A transfer locks both accounts with SELECT FOR UPDATE ordered by account id, so concurrent transfers in opposite directions queue instead of deadlocking. Lock timeouts are short, and deadlock or serialization errors are retried with the same idempotency key, so a retry never moves money twice.” Expect the follow-ups: hot accounts that serialize every transfer, and what changes when the two accounts live on different shards.

Read the guide to transactions and isolation or distributed locks and leases, see isolation levels, or watch a strong candidate design a payment system.

Questions people ask