# DDIA Ch. 8: two transactions deadlock — Postgres shoots one, doesn't hang ## Concept Two transactions each lock the same two rows in the *opposite* order: A takes row 1 then reaches for row 2; B takes row 2 then reaches for row 1. Each now holds a lock the other needs, so each waits on the other — a cycle. The naive prediction is that they wait **forever** (or until someone kills a session). They don't. Under two-phase locking Postgres holds each row's write-lock until commit, so the wait is real; but after `deadlock_timeout` (default **~1 s**) Postgres's deadlock detector notices the cycle in its wait-for graph and **aborts one victim** with SQLSTATE `40P01` `deadlock detected`. The survivor's blocked statement immediately proceeds and it commits. You will type this into two real `psql` sessions, watch one session block, then watch the database pick a victim, print the exact `40P01` error (with its DETAIL about the two-process lock cycle), and let the other transaction win. The victim must retry at the app level. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 8 — *Transactions*, §"Implementation of two-phase locking": > Deadlocks can occur [...] The database automatically detects deadlocks between > transactions and aborts one of them so that the others can make progress. The > aborted transaction needs to be retried by the application. The book names the mechanism (automatic detection + abort one) and the app's obligation (retry). Here you *trigger* the deadlock on demand and read the real error the database returns. ## Prerequisites The surprise is about a cycle two lock-orders create, and how the database breaks it. These help; each line notes where it shows up. 1. **Two-phase locking (2PL)** — a transaction acquires locks as it touches rows and holds every one until it commits or aborts (no early release). Because the write-lock on a row is held to commit, the second session genuinely cannot proceed. It shows up in Step 2 as Session A *hanging* on B's row. 2. **Lock ordering** — the order in which a transaction acquires its locks. Two transactions taking the same locks in *opposite* orders is the entire setup; taking them in a *consistent* order is the entire fix (Step 4). 3. **Wait-for graph / deadlock detection** — model each waiting transaction as a node with an edge to the transaction it waits on; a **cycle** in that graph *is* a deadlock. Postgres periodically checks for a cycle and, finding one, aborts a victim to break it. It shows up as the `40P01` DETAIL naming both processes waiting on each other. 4. **`deadlock_timeout`** — the check isn't continuous; a transaction that blocks waits this long (default `1s`) before Postgres runs the cycle-detection pass. So detection costs ~1 s of latency, paid only by transactions that actually block. It shows up as the ~1 s pause before the victim is shot. ### Where to learn the prerequisites - **2PL, deadlocks, detection (#1, #3):** DDIA §"Two-phase locking (2PL)" and §"Implementation of two-phase locking"; Postgres manual §"Explicit Locking → Deadlocks". - **`deadlock_timeout` (#4):** the PostgreSQL manual entry for `deadlock_timeout` (Server Configuration → Lock Management). - **Lock ordering as the fix (#2):** DDIA §"Deadlocks" and the standard application rule "acquire locks in a consistent global order." If only one is new, make it #3 — a deadlock *is* a cycle in the wait-for graph, and everything else is how the database finds and breaks it. ## Environment The *detection* is deterministic (a victim is always chosen and the survivor always commits); the *victim's identity* is not. - PostgreSQL 16.14 (Debian, aarch64) in Docker on macOS 26.5.2 (Darwin 25.5.0), arm64 - Two real `psql` sessions against one server; the capture harness `code/deadlock_detection.py` drives the same two transactions from two threads, via psycopg[binary] on Python 3.12 (uv) - `deadlock_timeout` is the default `1s` - Which transaction becomes the victim can vary run to run — the DETECTION is deterministic, the victim identity is not. The transcripts below caught **Session B** as the victim; you may catch A. ## Mental model A deadlock is a **cycle in the wait-for graph**. Each transaction is a node; draw an arrow from a transaction to the one it is *waiting on* to release a lock. When A → B (A waits on B's row) and B → A (B waits on A's row), the arrows form a loop, and no one in the loop can ever advance on its own — each is waiting for the other to move first. Postgres does not spin forever. Any transaction that blocks on a lock sets a timer; if it's still blocked after `deadlock_timeout` (1 s), the backend runs a **deadlock-detection pass** that walks the wait-for graph looking for a cycle. If it finds one, it picks a **victim**, aborts it (freeing its locks), and the remaining transactions proceed. The check is periodic and lazy — paid only when something is actually stuck — which is why detection costs ~1 s of latency but zero overhead on transactions that never block. The capture harness `code/deadlock_detection.py` runs exactly this from two threads so the transcript is real; the Steps below have you type it by hand, which is the point. ## Setup ``` # a Postgres 16 server (this exercise's is already running as ddia-ch08-pg): docker run -d --name ddia-ch08-pg \ -e POSTGRES_HOST_AUTH_METHOD=trust -e POSTGRES_DB=study \ -p 5432:5432 postgres:16 # your own database, seeded with two rows at v=0: docker exec ddia-ch08-pg psql -U postgres -c "CREATE DATABASE ex_ch08_deadlock;" docker exec ddia-ch08-pg psql -U postgres -d ex_ch08_deadlock -c \ "CREATE TABLE rows (id int PRIMARY KEY, v int); INSERT INTO rows VALUES (1,0),(2,0);" # open TWO psql sessions in two terminals -- Session A and Session B: docker exec -it ddia-ch08-pg psql -U postgres -d ex_ch08_deadlock # Session A docker exec -it ddia-ch08-pg psql -U postgres -d ex_ch08_deadlock # Session B ``` `code/deadlock_detection.py` is the capture harness — it drives the same two transactions from two threads and prints the verbatim `40P01`. Run the Steps by hand first, then check against it. Do **not** read ahead — make each prediction first. ## Steps ### Step 1 — each session locks its own row **Predict.** In Session A, `BEGIN` and update row 1. In Session B, `BEGIN` and update row 2. They touch *different* rows. Does either block, or do both return immediately? ``` -- Session A: BEGIN; UPDATE rows SET v=v+1 WHERE id=1; -- Session B: BEGIN; UPDATE rows SET v=v+1 WHERE id=2; ``` **Observe.** ``` -- Session A -- Session B BEGIN BEGIN UPDATE 1 UPDATE 1 ``` Both return `UPDATE 1` instantly. A holds the write-lock on row 1, B holds the write-lock on row 2 — no conflict yet, because 2PL only blocks you when you want a lock *someone else already holds*. ### Step 2 — Session A reaches across to row 2 (held by B) **Predict.** Still inside its transaction, Session A now updates row 2 — the row B is holding. What does A's `psql` do: return `UPDATE 1`, error, or something else? ``` -- Session A: UPDATE rows SET v=v+1 WHERE id=2; ``` **Observe.** ``` -- Session A (no output -- the prompt hangs; A is blocked, waiting on B's lock on row 2) ``` A **blocks**. Under 2PL, B holds row 2's write-lock until it commits, so A's `UPDATE` can only wait. Nothing is wrong yet — this is an ordinary lock wait, and if B committed now, A would immediately proceed. Leave A hanging and go to B. ### Step 3 — Session B completes the cycle (the surprise) **Predict.** Session B, still open, now updates row 1 — the row A is holding. Now A waits for B *and* B waits for A. Do both sessions hang forever until someone kills them? ``` -- Session B: UPDATE rows SET v=v+1 WHERE id=1; ``` **Observe.** ``` -- Session B (after ~1 s) ERROR: deadlock detected DETAIL: Process 474 waits for ShareLock on transaction 4566; blocked by process 473. Process 473 waits for ShareLock on transaction 7738; blocked by process 474. HINT: See server log for query details. CONTEXT: while updating tuple (0,1) in relation "rows" ``` ``` -- Session A (its hung UPDATE returns the instant B is aborted) UPDATE 1 ``` **Not forever — ~1 second.** The moment B asked for row 1, the wait-for graph gained its second edge and closed the cycle. After `deadlock_timeout` (1 s) Postgres ran its detection pass, saw the cycle — the DETAIL spells it out: process 474 waits on 473, process 473 waits on 474 — and aborted **B** as the victim. The instant B's locks were released, A's blocked `UPDATE` completed. Now commit the survivor: ``` -- Session A: COMMIT; -- COMMIT -- Session B (already aborted; its transaction block is dead): COMMIT; -- ROLLBACK (nothing to commit; B was rolled back) -- confirm the final state: SELECT id, v FROM rows ORDER BY id; ``` ``` id | v ----+--- 1 | 1 2 | 1 (2 rows) ``` Both rows show `v=1` — **entirely from A**, the survivor (its two `+1`s). Every change B made was rolled back with it. In a real app, B would now catch `40P01` and *retry* its transaction. ### Step 4 — the fix: acquire locks in a consistent order **Predict.** Re-run the whole thing, but have **both** sessions lock row 1 *before* row 2 (a consistent global order). Session A: update 1, then 2. Session B: update 1, then 2. Can a deadlock still form? ``` -- reset: UPDATE rows SET v=0; (either session, its own txn) -- Session A: -- Session B: BEGIN; BEGIN; UPDATE rows SET v=v+1 WHERE id=1; UPDATE rows SET v=v+1 WHERE id=1; -- wants row 1 UPDATE rows SET v=v+1 WHERE id=2; COMMIT; UPDATE rows SET v=v+1 WHERE id=2; COMMIT; ``` **Observe.** ``` -- Session A -- Session B BEGIN BEGIN UPDATE 1 UPDATE 1 <- blocks until A commits, then returns UPDATE 1 UPDATE 1 COMMIT COMMIT ``` ``` id | v ----+--- 1 | 2 2 | 2 (2 rows) ``` **No deadlock — B just waits, then wins.** Because both sessions grab row 1 first, B blocks on row 1 at the *start* and can't get ahead of A to grab row 2. There is never a moment where A holds something B has and B holds something A has, so the wait-for graph stays acyclic — a plain queue, not a loop. Both transactions commit; each row ends at `v=2`. ## What you should see - Step 1: both first `UPDATE`s return `UPDATE 1` — no conflict on distinct rows. - Step 2: Session A's cross-update **blocks** (2PL holds B's lock to commit). - Step 3: after **~1 s**, one session gets `ERROR: deadlock detected` (SQLSTATE `40P01`) with a DETAIL naming the two processes in the cycle; the other's blocked statement completes and it commits. Final rows come entirely from the survivor: `(1,1),(2,1)`. Which session is the victim varies. - Step 4: with a consistent lock order, **no** deadlock — the second session waits then proceeds; both commit, rows `(1,2),(2,2)`. ## Why Postgres uses locks to enforce serializability of conflicting writes: a transaction that updates a row takes that row's write-lock and, under two-phase locking, holds it until commit. That "hold until commit" is what makes the guarantee sound — no other transaction can slip in and change the row underneath you — but it is also exactly what lets a cycle form. When A holds row 1 and wants row 2 while B holds row 2 and wants row 1, each is waiting for a lock the other won't release until *it* finishes, and neither can finish. Draw it as a wait-for graph — a node per transaction, an edge to whatever it's blocked on — and the two edges close a loop. A loop in that graph is the definition of a deadlock: a set of transactions each waiting on the next, all the way around. A database has two options: prevent cycles, or detect and break them. Postgres detects. Rather than pay to keep the wait-for graph acyclic on every lock acquisition, it lets waits happen and, whenever a transaction has been blocked for `deadlock_timeout` (default 1 s), runs a pass that walks the graph from the blocked transaction looking for a cycle back to itself. Finding one, it must sacrifice a member to break it — there is no way to satisfy everyone in a cycle — so it picks a **victim**, aborts it (`40P01`), and releases its locks. That single abort collapses the cycle: the survivor's edge now points at a transaction that no longer holds the lock, so it proceeds. This is why the failure is ~1 s, not infinite, and why it surfaces as an *error the loser must handle*, not a hang. The victim is chosen by the backend and isn't stable across runs; your job as the application is simply to catch `40P01` and retry. **The boundary — a consistent global lock order makes the cycle impossible.** Detection cleans up after a deadlock; *ordering* prevents it. If every transaction that needs several locks always acquires them in the same global order (here: always row 1 before row 2), then a transaction can only ever wait on one holding a *lower*-ordered lock — waits point strictly "up" the order, and a strictly monotonic chain can't loop back on itself. No cycle can form, so the detector never fires and no one is ever a victim (Step 4). This is the standard fix — sort your lock acquisitions by a stable key (primary key, resource id) before taking them. It has limits: it only helps for locks you can see and order up front, so deadlocks from lock *escalation*, foreign-key or index locks, or locks taken deep inside library code can still surprise you — which is why real systems keep the retry loop *and* order their locks. ### Go deeper 1. **Watch the timer.** In one session `SET deadlock_timeout = '5s';` before you `BEGIN`, then re-run Steps 1–3. Predict how long the victim now takes to be shot (it's the *waiting* transaction's timeout that governs the pass), and confirm detection latency is a tunable, not a constant. 2. **Three-way cycle.** Add a row 3 and a third session so A→B→C→A. Predict whether Postgres still detects it (it walks the whole graph, so yes) and which of the three it chooses — then read the DETAIL to see all three edges named. 3. **Order it away, then break the order.** Do Step 4's consistent order, confirm no deadlock, then have just *one* session violate the order (lock 2 before 1) and watch the cycle come back — proof that the guarantee is the *shared* convention, and one non-conforming caller is enough to reintroduce deadlocks. ```