A deadlock is a cycle of waiting: transaction A holds a lock B needs, while B holds a lock A needs, so neither can ever proceed. Interviewers probe it because it is the point where locking (see Concurrency Control and Locks) stops being a theory topic and becomes a production error code, and because the right answer is never "the database will handle it": the database resolves it by killing one of your transactions, so your code must be ready for that.
For a Backend engineer, deadlocks show up as intermittent, load-dependent failures in payment, inventory and queue-worker code, the sort that never reproduce on a laptop. Knowing why they occur, how each engine detects them, and how to make them rare and harmless is a standard senior-level question. Snapshot readers do not take part in these cycles (see MVCC Internals); deadlocks come from writers and locking reads.
-- Table accounts(id PRIMARY KEY, balance). Rows 1 and 2 exist.
-- Both sessions transfer money between the same two accounts, in opposite directions.
-- Works the same shape in PostgreSQL and InnoDB.
-- Session A: 1 -> 2 -- Session B: 2 -> 1
BEGIN; BEGIN;
UPDATE accounts SET balance = balance - 10
WHERE id = 1; -- locks row 1
UPDATE accounts SET balance = balance - 10
WHERE id = 2; -- locks row 2
UPDATE accounts SET balance = balance + 10
WHERE id = 2; -- WAITS for B
UPDATE accounts SET balance = balance + 10
WHERE id = 1; -- WAITS for A => cycle
Wait-for graph: A ------waits for------> B
^ |
+-------waits for--------+
-- The database detects the cycle and aborts ONE session (the victim):
-- PostgreSQL: ERROR: deadlock detected (SQLSTATE 40P01)
-- InnoDB: ERROR 1213 (40001): Deadlock found when trying to get lock;
-- try restarting transaction
-- SQL Server: Msg 1205: Transaction was deadlocked ... chosen as the deadlock victim
-- The survivor's blocked UPDATE then proceeds and it can commit.A deadlock needs four things at once (the Coffman conditions): exclusive access to the resource, a transaction holding one lock while waiting for another (hold and wait), no way to forcibly take a lock away (no preemption), and a circular chain of waiters. Databases cannot drop the first three, because they are what make transactions correct. So they either break the fourth, by making everyone acquire locks in one order, or they let the cycle form and break it afterwards by preemption in the only way available: rolling a transaction back.
Notice that each statement here is perfectly reasonable. No single query is wrong; the bug lives in the interleaving, which is why deadlocks are timing-dependent and rise with concurrency. Run the two transfers one after the other and nothing happens.
Lock manager keeps: who holds what, who waits for what.
Wait-for graph: node = transaction, edge T1 -> T2 means "T1 waits for a lock T2 holds"
Deadlock <=> the graph has a cycle.
T1 -> T2 -> T3 -> T1 cycle: pick a victim, roll it back,
its locks are released, the others continue
How the engines schedule the check (generally, check your version):
PostgreSQL waits deadlock_timeout (default 1s) before running the check, because
most lock waits end on their own and the check is not free.
The session that runs the check and finds the cycle is aborted.
InnoDB checks the wait-for graph as soon as a lock wait starts (innodb_deadlock_detect
= ON by default). Victim = the transaction that has changed the fewest rows
(cheapest to roll back). Can be turned off; then only innodb_lock_wait_timeout
(default 50s) ends the waiting, and it rolls back just the statement by default.
SQL Server a lock-monitor thread searches for cycles periodically (about every 5s,
faster once deadlocks are being found). Victim = lowest DEADLOCK_PRIORITY,
then the transaction cheapest to roll back.The detection cost is real: searching a graph for cycles takes CPU, and on a very hot row with thousands of waiters InnoDB's per-wait check has been a bottleneck, which is why turning it off and relying on a short lock-wait timeout is a known (and risky) tuning option for some workloads. PostgreSQL's one-second delay is the opposite trade: pay a delay of about a second on true deadlocks to avoid running the check for every ordinary short wait.
Resolution is always the same in spirit: choose a victim, roll back its entire transaction, release its locks. In PostgreSQL the transaction is left in an aborted state and the application must issue ROLLBACK (or roll back to a savepoint). The victim is not "wrong"; it was simply the cheapest way to break the cycle, and your code should simply run it again. Distributed databases cannot always afford a global graph, so some prevent cycles up front with timestamp rules (wait-die, wound-wait; Spanner uses wound-wait) or lean on timeouts.
1. Lock upgrade (both take a weak lock, both want the strong one)
Session A Session B
BEGIN; BEGIN;
SELECT * FROM stock WHERE id=7 FOR SHARE;
SELECT * FROM stock WHERE id=7 FOR SHARE;
UPDATE stock SET qty=qty-1 WHERE id=7; -- wants exclusive, waits for B's shared lock
UPDATE stock SET qty=qty-1 WHERE id=7; -- waits for A => deadlock
Fix: take FOR UPDATE at the start, or just run the atomic UPDATE.
2. InnoDB gap locks (REPEATABLE READ; ids 1 and 10 exist, 5 does not)
Session A Session B
BEGIN; BEGIN;
SELECT * FROM t WHERE id=5 FOR UPDATE; -- no row, takes a gap lock on (1,10)
SELECT * FROM t WHERE id=5 FOR UPDATE; -- gap locks do not conflict: succeeds
INSERT INTO t (id) VALUES (5); -- needs insert-intention lock, blocked by B's gap lock
INSERT INTO t (id) VALUES (5); -- blocked by A's gap lock => deadlock
Fix: skip the check-then-insert; INSERT and handle the duplicate-key error,
or use INSERT ... ON DUPLICATE KEY UPDATE; READ COMMITTED also avoids most gap locks.
3. Different lock order through different access paths (InnoDB)
One statement finds rows via a secondary index, another via the primary key.
Both touch the same row, but lock the secondary and clustered entries in opposite order.
4. Batch updates in unspecified order
UPDATE orders SET ... WHERE id IN (5, 2, 9) locks rows in the ORDER THE PLAN VISITS them,
not the order you typed. Two workers with different plans (or different data layouts)
can lock the same rows in opposite order.These are the cases that surprise people: nothing in the code "looks" like a cycle. The common thread is that the locks you take are decided by the execution plan and the isolation level, not just by the SQL text. That is why an EXPLAIN change, a missing index (which makes a statement scan and lock far more rows) or a switch from Read Committed to Repeatable Read can suddenly create deadlocks in code that ran fine for years.
-- BEFORE: lock order depends on who calls first
UPDATE accounts SET balance = balance - :amt WHERE id = :from_id;
UPDATE accounts SET balance = balance + :amt WHERE id = :to_id;
-- AFTER (PostgreSQL / MySQL): take all row locks first, in a fixed order, then write
BEGIN;
SELECT id FROM accounts WHERE id IN (:from_id, :to_id) ORDER BY id FOR UPDATE;
UPDATE accounts SET balance = balance - :amt WHERE id = :from_id;
UPDATE accounts SET balance = balance + :amt WHERE id = :to_id;
COMMIT;
-- Both A->B and B->A transfers now lock the lower id first, so the second one
-- simply waits instead of forming a cycle.# Retry wrapper (real, run with python3; the exception stands in for 40P01 / 1213 / 1205)
import random, time
class DeadlockDetected(Exception):
pass
def run_with_retry(txn, max_attempts=4, base=0.01):
for attempt in range(1, max_attempts + 1):
try:
return txn(attempt) # the WHOLE transaction is re-run
except DeadlockDetected:
if attempt == max_attempts:
raise
sleep = random.uniform(0, base * 2 ** attempt) # exponential backoff with full jitter
print(f"attempt {attempt}: deadlock victim, retrying")
time.sleep(sleep)
def transfer(attempt):
if attempt < 3: # simulate being chosen as victim twice
raise DeadlockDetected()
return "committed on attempt %d" % attempt
print(run_with_retry(transfer))
# Actual output:
# attempt 1: deadlock victim, retrying
# attempt 2: deadlock victim, retrying
# committed on attempt 3Ordering is prevention: it removes the circular-wait condition, so the deadlock cannot form at all. Retrying is recovery: it accepts that some deadlocks will still happen (different code paths, foreign-key checks, gap locks) and makes them harmless. You need both, because ordering only helps for the locks you control. The retry must re-run the entire transaction from its first statement, because the victim's work was rolled back, and any side effects outside the database (emails, payment calls) must be idempotent or kept outside the transaction.
The remaining habits all shrink the window in which a cycle can form: keep transactions short, never wait on a user or an HTTP call while holding locks, touch as few rows as possible, put indexes on the columns your WHERE clauses use so statements lock only the rows they need, prefer one atomic statement to a read-then-write, and use NOWAIT or SKIP LOCKED for queue-style workers so they move on instead of waiting.
Lock wait timeout T1 waits for T2, T2 is just slow (or idle in transaction). NO cycle.
Ends when the timeout fires (InnoDB 50s default; PG needs lock_timeout set).
Deadlock cycle. Detected and broken by the database, usually within a second or so.
Starvation a transaction keeps losing the race for a lock; no cycle, no error.
Livelock transactions keep aborting and retrying each other without progress
(bad retry code without jitter can cause this).
Where to look:
PostgreSQL server log has the DETAIL lines: both processes, both statements, lock types.
Turn on log_lock_waits; inspect pg_locks and pg_stat_activity for live waits.
Counter: pg_stat_database.deadlocks.
InnoDB SHOW ENGINE INNODB STATUS -> "LATEST DETECTED DEADLOCK" (last one only);
innodb_print_all_deadlocks logs every one to the error log.
SQL Server deadlock graph via Extended Events (system_health session captures them).Telling a deadlock from a plain long wait matters, because the fixes differ. A deadlock is fixed by ordering and shorter transactions; a long wait is usually a stuck or idle-in-transaction session holding a lock, fixed by finding and fixing that session. Both leave the same symptom of "requests are hanging", so look at the error code first: a deadlock produces an explicit error within seconds, a timeout produces a slower, different one.
40P01, InnoDB error 1213, SQL Server 1205.deadlock_timeout (default 1s) first; InnoDB checks immediately by default; SQL Server checks periodically.SELECT ... ORDER BY id FOR UPDATE first).deadlock_timeout (PostgreSQL) or on its next periodic pass (SQL Server), and finds the cycle.# Runnable with python3: deadlock detection is just cycle finding in a wait-for graph.
def find_cycle(waits_for):
def dfs(node, path, seen):
if node in path:
return path[path.index(node):] + [node]
if node in seen:
return None
seen.add(node)
for nxt in waits_for.get(node, []):
cyc = dfs(nxt, path + [node], seen)
if cyc:
return cyc
return None
seen = set()
for start in waits_for:
cyc = dfs(start, [], seen)
if cyc:
return cyc
return None
def build_graph(holds, wants): # holds: txn -> rows locked, wants: txn -> row it waits for
owner = {row: t for t, rows in holds.items() for row in rows}
g = {}
for t, row in wants.items():
if row in owner and owner[row] != t:
g.setdefault(t, []).append(owner[row])
return g
g = build_graph({"T1": {1}, "T2": {2}}, {"T1": 2, "T2": 1})
print("opposite order graph:", g, "-> cycle:", find_cycle(g))
g = build_graph({"T1": {1}, "T2": set()}, {"T1": 2, "T2": 1})
print("consistent order graph:", g, "-> cycle:", find_cycle(g))
g = build_graph({"T1": {1}, "T2": {2}, "T3": {3}}, {"T1": 2, "T2": 3, "T3": 1})
print("three-way graph:", g, "-> cycle:", find_cycle(g))
# Actual output:
# opposite order graph: {'T1': ['T2'], 'T2': ['T1']} -> cycle: ['T1', 'T2', 'T1']
# consistent order graph: {'T2': ['T1']} -> cycle: None
# three-way graph: {'T1': ['T2'], 'T2': ['T3'], 'T3': ['T1']} -> cycle: ['T1', 'T2', 'T3', 'T1']
-- PostgreSQL (two psql sessions; not runnable here, so no output is invented)
-- CREATE TABLE accounts (id INT PRIMARY KEY, balance INT);
-- INSERT INTO accounts VALUES (1, 100), (2, 100);
-- Session A: BEGIN; UPDATE accounts SET balance = balance - 10 WHERE id = 1;
-- Session B: BEGIN; UPDATE accounts SET balance = balance - 10 WHERE id = 2;
-- Session A: UPDATE accounts SET balance = balance + 10 WHERE id = 2; -- blocks
-- Session B: UPDATE accounts SET balance = balance + 10 WHERE id = 1; -- blocks, then after about
-- deadlock_timeout (1s) one session fails with "ERROR: deadlock detected"
-- The other session's blocked UPDATE completes; ROLLBACK the failed one and COMMIT the other.
-- While they are stuck, from a third session:
-- SELECT pid, wait_event_type, wait_event, state, left(query, 50) FROM pg_stat_activity WHERE wait_event_type = 'Lock';
-- Repeat, but make both sessions lock id 1 first, then id 2: the second one waits and no deadlock occurs.
Q: What is a deadlock?
A: Two or more transactions each hold a lock the next one needs, forming a cycle, so none can ever proceed. It requires exclusive locks that are held while waiting for more, and it is resolved only by aborting a transaction because locks cannot be taken away politely. The trade-off is that locking gives you correctness at the price of occasional forced aborts, so callers must be written to retry.
Q: Give a real database deadlock example.
A: Two concurrent transfers between accounts 1 and 2 in opposite directions: A updates row 1 then row 2, B updates row 2 then row 1. Each locks its first row, then waits for the other's, and the database aborts one with an error (40P01 in PostgreSQL, 1213 in InnoDB). A less obvious one in InnoDB is two sessions running SELECT ... FOR UPDATE on a missing key, both taking compatible gap locks, then both trying to insert into that gap.
Q: How does the database detect a deadlock?
A: It maintains a wait-for graph with transactions as nodes and "waits for" as edges, and a cycle in it means deadlock. InnoDB checks when a lock wait begins and generally rolls back the transaction that changed the fewest rows; PostgreSQL waits deadlock_timeout (1s by default) before checking, to avoid paying for waits that resolve themselves; SQL Server checks periodically and honours DEADLOCK_PRIORITY. The victim's whole transaction is rolled back and the client receives an error.
Q: How can application code reduce deadlocks?
A: Acquire locks in a consistent order everywhere (for example, sort ids and lock with SELECT ... ORDER BY id FOR UPDATE first), keep transactions short with no external calls inside, index the filtered columns so fewer rows are locked, and avoid read-then-write lock upgrades. Then add a bounded retry with jittered backoff that re-runs the whole transaction, because ordering cannot remove every cycle. The cost of ordering is that you must know all the rows up front, which is awkward for complex workflows.
Follow-up: Can a deadlock happen on a single table with a single-row update?
A: Yes, though it is less common. In InnoDB two statements can reach the same row through different indexes and lock the secondary and clustered index entries in opposite order, and foreign-key checks can take extra locks on parent rows. The lesson is that lock order is determined by the plan and constraints, not only by the order you wrote the statements.
Follow-up: Why doesn't the database just prevent deadlocks instead of detecting them?
A: Prevention would require either knowing every lock a transaction will need in advance (impractical for interactive or data-dependent transactions) or using timestamp rules such as wait-die and wound-wait that abort transactions that were not actually deadlocked. Detection lets transactions run at full speed and only pays when a real cycle appears. Some distributed systems do choose wound-wait because global cycle detection is expensive.
Follow-up: You see a spike of deadlocks after a deploy. How do you investigate?
A: Read the deadlock report (PostgreSQL log DETAIL lines, InnoDB LATEST DETECTED DEADLOCK or innodb_print_all_deadlocks, SQL Server deadlock graph) to see the two statements and the lock each held and wanted. Then check what changed: a new code path locking rows in a different order, a dropped index turning targeted locks into scans, an isolation-level change adding gap locks, or a larger batch size. Fix the ordering or the index, and confirm the retry path is working while you do.
Deadlocks are a design-time concern wherever many workers update overlapping sets of rows: order and payment systems, inventory reservation, ledger transfers, and job queues. The design responses are structural. Define one canonical lock order for shared resources (for example, always lock accounts by ascending id, or lock the parent order before its line items) and document it as a rule of the codebase. Make every write path retry-safe, with idempotency keys so that a re-run after a deadlock victim rollback cannot double-charge, and keep external calls outside the transaction. For queue-like tables, use SELECT ... FOR UPDATE SKIP LOCKED so workers skip rows another worker holds rather than queueing behind them, which removes both waiting and most deadlock exposure. When a single row is a hot spot (a global counter, a popular product), no ordering discipline helps, so the answer is to split the row (sharded counters), batch updates, or move to an append-only design and aggregate later. Finally, monitor the deadlock counter and the retry rate as service metrics, since a rising trend often signals a new code path or a lost index before users notice.
The decision is whether to prevent cycles by discipline, recover from them by retry, or both. Consistent lock ordering is cheap at runtime and removes the deadlocks you can predict, but it constrains code structure, needs every team to follow it, and cannot cover locks taken implicitly (foreign keys, gap locks, index lookups). Retry-on-victim covers the rest but requires transactions that are safe to re-run, adds latency under contention, and can turn into a retry storm if backoff and jitter are missing. Lowering the isolation level (for example InnoDB Read Committed) removes gap-lock deadlocks but gives up repeatable reads, and taking all locks up front with SELECT ... FOR UPDATE shrinks deadlocks but holds locks longer, which raises waiting. Turning off deadlock detection in InnoDB for hot-row workloads trades CPU for long timeouts and is the wrong choice when transactions are long or when you cannot tolerate 50-second stalls. Deadlocks that occur at a rate of a few per million transactions with a working retry are normal and acceptable; a steady climb, or a business flow with no retry, is the design problem to fix.