Drill 71 — The Deadlock at Midnight

Theme: Concurrency & Race Conditions · Format: 20-min drill · Difficulty: core

The story

A custody bank runs two batch jobs against the same accounts ledger every night. The reconciliation job sweeps yesterday's trades and adjusts balances so the books tie out; the settlement job moves cash for trades that cleared. Both jobs, at some point, touch the same pair of accounts inside one transaction — a house account and a client account — because a single settlement both debits one and credits the other.

Each job was written by a different team, a year apart, and each looks correct in isolation. The reconciliation job, walking its worklist, happens to lock the accounts in the order it reads them: A then B. The settlement job, walking a different worklist, locks them in its natural order: B then A. Nobody noticed, because for eleven months the two jobs barely overlapped — recon finished by 11:40pm, settlement started at midnight, and on a quiet night a transaction held its locks for a few milliseconds.

Then comes month-end. Volume triples, both jobs run long, and now they are running at the same time over the same hot accounts. Each transaction holds its first lock for hundreds of milliseconds while it does other work. The settlement job grabs B and reaches for A. The reconciliation job is already holding A and reaching for B. Neither will let go. The database's deadlock detector notices the cycle, picks a victim, and kills it with a deadlock detected error. The job's framework does what frameworks do — it retries the failed transaction. In the same lock order. Into the same collision. It re-deadlocks. On-call's phone lights up at 12:07am with a batch job failing page, and the runbook says nothing about locks.

⏸ Stop here and ask the room: each job is correct on its own and the retry logic is textbook — so why does the system wedge itself solid the moment they overlap?

Run it — facilitator script

Timing for a 20-minute session: 2 min story · 10 min staged questions · 3 min reveal · 5 min transfer.

What has to be true for a deadlock to happen at all — name the conditions.

Listen for: a circular wait in the wait-for graph — job 1 holds A and wants B while job 2 holds B and wants A. That needs mutual exclusion, hold-and-wait, no preemption, and a cycle. Break any one of those and deadlock is impossible; the cheapest to break is the cycle, by making every transaction acquire locks in one global order.
Weak signal: "the database is slow" or "add more connections" — treating a structural cycle as a capacity problem.

The retry made it worse, not better. Why?

Listen for: the retry replays the identical lock sequence into the identical contention, so it re-deadlocks immediately and burns CPU — a tight retry loop with no backoff. Retry is the right instinct (deadlock is a transient, the victim rolls back cleanly) but only with exponential backoff and jitter so the two jobs de-synchronize instead of colliding in lockstep.
Weak signal: "turn off retries" — now the batch just fails and the books don't tie out; the retry isn't the bug, the tight, un-jittered retry into a fixed lock order is.

Where does the fix belong — in the two jobs, or somewhere they can't both forget it?

Listen for: a single canonical lock order enforced for anything that touches multiple accounts — e.g. always lock rows in ascending account_id. Ideally it lives in a shared data-access helper so a new third job can't reintroduce the opposite order. Plus shorter transactions so locks are held for milliseconds, not hundreds.
Weak signal: "we'll be careful to lock in the same order" as a code-review convention with nothing enforcing it — the exact discipline that already failed here twice.

The reveal

There was no data corruption and no bug in either job's logic — the ledger math was perfect. The wedge was purely lock-ordering: two transactions acquiring the same two rows in opposite orders under enough concurrency to overlap. The fix was three lines of policy, not a rewrite. Every transaction that touches more than one account now locks rows in ascending account_id — a global lock order — so a cycle can no longer form. The retry got exponential backoff with jitter, so even a rare lock wait resolves instead of spinning. And the transactions were shortened to hold locks only across the actual read-modify-write, not the surrounding bookkeeping. Deadlocks at month-end went from dozens an hour to essentially zero, and the midnight page stopped.

Why this happens — the mechanics

A deadlock is a cycle in the wait-for graph: transaction T1 waits on a lock held by T2, and T2 waits on a lock held by T1. Databases don't prevent this — they detect it (the engine periodically walks the wait-for graph looking for a cycle) and resolve it by choosing a victim, rolling it back, and returning a deadlock error. That is correct, safe behavior: the loser's work is undone atomically, no data is damaged. The catch is that detection is a runtime backstop, not prevention — the database will happily let you build a system that deadlocks constantly, and it just keeps killing victims.

The reason two individually-correct jobs collide is that lock order is an emergent, cross-transaction property that neither author can see from inside their own code. Recon locks A-then-B because that's the order its query returned rows; settlement locks B-then-A for the same innocent reason. In isolation, order is invisible. It only becomes a cycle when both run concurrently over the same rows — which is exactly why it slept for eleven months and detonated at month-end, when overlap and transaction duration both spiked. Longer transactions widen the window during which the first lock is held, turning a theoretical cycle into a near-certain one. And a tight retry loop that replays the same order simply feeds the detector fresh victims. This is the dining-philosophers problem wearing a ledger costume: the textbook fix is to impose a total order on resource acquisition so a cycle is structurally impossible.

Diagrams

Problem — how the failure unfolds:

sequenceDiagram
    autonumber
    participant R as Recon job
    participant DB as Accounts DB
    participant S as Settle job
    R->>DB: LOCK account A
    S->>DB: LOCK account B
    R->>DB: want LOCK B<br/>(waits on Settle)
    S->>DB: want LOCK A<br/>(waits on Recon)
    Note over R,S: circular wait -<br/>each holds one, wants other
    DB--xR: deadlock victim<br/>killed, txn rolled back
    R->>DB: retry same order<br/>re-deadlocks instantly
    Note over R,DB: tight retry loop -<br/>pages on-call at midnight

Solution — where the guardrails go:

flowchart TD
    A["Any txn touching<br/>2+ accounts"] --> B["Lock rows in ascending<br/>account_id (global order)"]
    B --> C["Short txn: read,<br/>modify, write, commit"]
    C --> D["On deadlock: retry with<br/>backoff + jitter, cap 5"]
    D --> E["READ COMMITTED +<br/>explicit row locks"]
    E --> H["No cycle possible<br/>by construction"]
    G1["Deadlock-rate SLI<br/>> 5 per hour"] -.-> AL["Page + flag a<br/>lock-order regression"]
    D -.-> G1

What good looks like

A single canonical lock order, enforced in a shared helper: any transaction touching multiple accounts acquires rows in ascending account_id. A cycle in the wait-for graph is then structurally impossible — this is prevention, not detection.
Short transactions / minimal lock scope: hold locks only across the read-modify-write, target a p99 lock-hold time under 50ms, and never hold a row lock across a network call or an external API. Long locks turn a rare cycle into a frequent one.
Deadlock-aware retry with backoff and jitter: catch the deadlock error, retry with exponential backoff (base ~50ms, full jitter) capped at 5 attempts; alert if any single logical operation exhausts its retries. Never a tight loop that replays the same order.
The right isolation level: use READ COMMITTED with explicit row locks (SELECT … FOR UPDATE) rather than SERIALIZABLE everywhere — serializable trades deadlocks for serialization failures and can raise abort rates on hot rows. Match the level to the invariant, not the default.
A deadlock-rate SLI: emit deadlocks_detected per hour; baseline is ~0, warn at 5/hour, page at 20/hour — a rising count is an early signal that a new job introduced the opposite lock order.
A concurrency game-day / contract test in CI: run recon and settlement against the same hot accounts in parallel and assert zero deadlocks survive retries — catches a reintroduced lock-order inversion before it reaches production.

The lesson

A deadlock isn't a database failing — it's your code asking for the same locks in two different orders. Impose one global order on how every transaction acquires its locks, keep transactions short, and retry transients with jitter; then a cycle can't form in the first place.

Named concepts: lock ordering, deadlock detection, transaction design, isolation levels.

Real-world echoes

The dining-philosophers problem. The canonical concurrency exercise is exactly this: philosophers each grab the fork on their left, then wait forever for the fork on their right, and the table deadlocks. The textbook resolution — impose a global order on fork acquisition so at least one philosopher takes the higher-numbered fork first — is precisely the "lock rows in ascending id" fix, and it's why lock-ordering is a named discipline rather than a clever trick.

Transfer

Where in your stack do two code paths lock the same two resources — rows, files, mutexes, distributed locks — without anyone guaranteeing they take them in the same order? "Our jobs don't overlap much" is the eleven-months answer, not a guarantee.

Make it a ticket: pick the two highest-traffic jobs that write shared rows, define a canonical lock order (ascending primary key), route their writes through one shared helper that enforces it, add a deadlock-rate SLI (warn 5/hour, page 20/hour), and add a parallel-collision test to CI.

Drill 69 — The Double-Charge Race — same theme; a check-then-act race where, as here, the guarantee has to live below the application logic.
Drill 21 — The Thundering Herd, theme 4 — load is the trigger that turns a latent flaw into an outage; overlap and volume are what woke this one.
Drill 20 — The Agent That Wouldn't Stop, theme 3 — an un-backed-off retry loop amplifying its own failure, the same shape as the re-deadlocking batch.
Pattern #140 — Consistent Lock Ordering (the reusable fix: impose a total order on resource acquisition).