How Deadlocks Happen (and Lock Ordering)

Scenario

Example app: a peer-to-peer wallet. Friends split bills constantly, so transfers A → B and B → A often happen at the same time. Each transfer debits one wallet and credits the other in one transaction.

What you see in production

About 1 in 2,000 transfers fails with:

ERROR:  deadlock detected
DETAIL:  Process 81723 waits for ShareLock on transaction 9912; blocked by process 81731.
         Process 81731 waits for ShareLock on transaction 9911; blocked by process 81723.

(MySQL: ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction.)

The naive code

def transfer(from_id, to_id, amount):
    with Session(engine) as s, s.begin():
        s.execute(update(Wallet).where(Wallet.id == from_id)
                  .values(balance=Wallet.balance - amount))      # locks from_id
        s.execute(update(Wallet).where(Wallet.id == to_id)
                  .values(balance=Wallet.balance + amount))      # then to_id

@Transactional
public void transfer(long fromId, long toId, BigDecimal amount) {
    wallets.debit(fromId, amount);    // UPDATE … WHERE id = fromId  (row lock)
    wallets.credit(toId, amount);     // UPDATE … WHERE id = toId    (row lock)
}

DB::transaction(function () use ($from, $to, $amount) {
    Wallet::whereKey($from)->decrement('balance', $amount);
    Wallet::whereKey($to)->increment('balance', $amount);
});

Reproduce it

A lock manager with a wait-for graph: when the graph has a cycle, the database picks a victim and aborts it:

holders = {}                 # row -> transaction
waits_for = {}               # transaction -> transaction it waits on

def lock(tx, row):
    owner = holders.get(row)
    if owner in (None, tx):
        holders[row] = tx
        print(f"{tx}: locked {row}")
        return
    waits_for[tx] = owner
    print(f"{tx}: waits for {row} (held by {owner})")
    # deadlock detection: follow the wait-for chain
    seen, cur = [tx, owner], owner
    while cur in waits_for:
        cur = waits_for[cur]
        seen.append(cur)
        if cur == tx:
            print("deadlock detected: " + " -> ".join(seen) + f"; aborting {tx}")
            for r, t in list(holders.items()):
                if t == tx: del holders[r]
            del waits_for[tx]
            return

# T1: transfer A -> B, T2: transfer B -> A, interleaved
lock("T1", "wallet A"); lock("T2", "wallet B")
lock("T1", "wallet B"); lock("T2", "wallet A")
print("rows still locked:", holders)

T1: locked wallet A
T2: locked wallet B
T1: waits for wallet B (held by T2)
T2: waits for wallet A (held by T1)
deadlock detected: T2 -> T1 -> T2; aborting T2
rows still locked: {'wallet A': 'T1'}

Root cause

A deadlock is a cycle of waits: T1 holds A and waits for B, while T2 holds B and waits for A. Neither can proceed, so the database detects the cycle (Postgres checks after deadlock_timeout, 1 s by default; InnoDB detects immediately) and rolls one transaction back. Deadlocks need two ingredients: transactions that lock several rows, and that lock them in different orders.

The fix

Always lock rows in a consistent global order — for example ascending primary key — and retry the rare deadlock that remains:

def transfer(from_id, to_id, amount):
    with Session(engine) as s, s.begin():
        # lock both rows in id order, whatever the transfer direction
        s.execute(select(Wallet.id).where(Wallet.id.in_([from_id, to_id]))
                  .order_by(Wallet.id).with_for_update())
        s.execute(update(Wallet).where(Wallet.id == from_id).values(balance=Wallet.balance - amount))
        s.execute(update(Wallet).where(Wallet.id == to_id).values(balance=Wallet.balance + amount))

@Transactional
public void transfer(long fromId, long toId, BigDecimal amount) {
    wallets.lockInOrder(Math.min(fromId, toId), Math.max(fromId, toId));   // SELECT … ORDER BY id FOR UPDATE
    wallets.debit(fromId, amount);
    wallets.credit(toId, amount);
}

-- one UPDATE touching both rows; Postgres still locks rows in scan order, so ORDER BY in a locking subquery
UPDATE wallets w
SET balance = w.balance + CASE WHEN w.id = $1 THEN -$3 ELSE $3 END
FROM (SELECT id FROM wallets WHERE id IN ($1, $2) ORDER BY id FOR UPDATE) locked
WHERE w.id = locked.id;

DB::transaction(function () use ($from, $to, $amount) {
    Wallet::whereIn('id', [$from, $to])->orderBy('id')->lockForUpdate()->get();   // ordered locks
    Wallet::whereKey($from)->decrement('balance', $amount);
    Wallet::whereKey($to)->increment('balance', $amount);
}, attempts: 3);                                                                 // retry deadlocks

The same simulation with ordered locking — the second transfer waits instead of deadlocking:

holders = {}

def lock(tx, row):
    owner = holders.get(row)
    if owner in (None, tx):
        holders[row] = tx
        return f"{tx}: locked {row}"
    return f"{tx}: waits for {row} (held by {owner}) — no cycle, just a queue"

def ordered(*rows): return sorted(rows)

for row in ordered("wallet B", "wallet A")[:1]:
    print(lock("T1", row))                      # T1 (A->B) locks A first
for row in ordered("wallet A", "wallet B")[:1]:
    print(lock("T2", row))                      # T2 (B->A) ALSO wants A first -> waits
print(lock("T1", "wallet B"))                   # T1 continues, commits
holders.clear()
print("T1 committed; T2 now locks wallet A and wallet B and completes")

T1: locked wallet A
T2: waits for wallet A (held by T1) — no cycle, just a queue
T1: locked wallet B
T1 committed; T2 now locks wallet A and wallet B and completes

Trade-offs

• Lock ordering prevents deadlocks between code paths you control; foreign-key checks, triggers and ORMs flushing changes in their own order can still lock in surprising orders.
• Some deadlocks will always remain in a busy system — a retry (with jitter, a few attempts) is part of the fix, not an alternative to it.
• Fewer, smaller transactions and single-statement updates reduce deadlock windows.

Detect it in production

• Postgres: SELECT deadlocks FROM pg_stat_database WHERE datname = current_database(); — graph it.
• MySQL: enable innodb_print_all_deadlocks so every deadlock goes to the error log, not just the latest.
• Track deadlock retries per endpoint; read the full report (next lesson) for the top offenders.

Key points

• A deadlock is a cycle in the wait-for graph; the database aborts one victim.
• Transactions that lock several rows in different orders deadlock.
• Lock in a consistent order (e.g. ascending id), keep transactions short, and retry deadlock errors.