System Design Concurrency
Deadlock Detection and Avoidance
Two checkout workers lock inventory then wallet; two refund workers lock wallet then inventory. Under load they meet in the middle and freeze. That freeze is a : a cycle in the , not “the database is slow.”
Services inherit the same four as operating systems, then add RPC-spanning cycles, , and database detectors that abort a . This note is how you prevent, avoid, detect, and recover—without pretending locks are free.
Handle a cycle
One global acquire order.
Refuse grants that are unsafe.
Find cycles in the wait-for graph.
Abort a retryable victim.
What actually happens
Thread 1 holds mutex A and wants B. Thread 2 holds B and wants A. Both sit in BLOCKED until a watchdog, a lock manager, or an operator kills one. CPU looks idle. Latency is infinite for those requests. Health checks may still pass if they do not take the same locks.
Databases do this on row/gap locks. Distributed systems do it across lock services, saga steps, and nested RPCs that each take a lock “just for a moment.” is the same cycle with worse observability.
Detection finds the cycle after it exists. Avoidance refuses the grant that would make the state unsafe. Prevention designs the protocol so a cycle cannot form. Recovery aborts someone. Production systems mix them: order locks, time out acquisitions, and let InnoDB/Postgres break leftover cycles.
Four conditions, four design levers
| Condition | Meaning | How services break it |
|---|---|---|
| Mutual exclusion | Resource not shareable | Prefer immutable data, MVCC reads, or lock-free structures where safe |
| Hold and wait | Hold one, wait for another | Acquire all locks atomically, or never nest; tryLock and drop all on fail |
| No preemption | Cannot steal a held lock | Lease + fencing; DB abort of the victim; cancel the owner |
| Circular wait | Cycle in the wait-for graph | by resource id |
Opposite lock order
Read the diagram definition
sequenceDiagram
autonumber
participant T1 as Txn / thread 1
participant A as Lock A
participant B as Lock B
participant T2 as Txn / thread 2
T1->>A: acquire A
T2->>B: acquire B
T1->>B: wait for B
T2->>A: wait for A
Note over T1,T2: Cycle: T1 waits T2, T2 waits T1
Note over A,B: Neither can releasePrevention (circular wait):
lock(min(accountA, accountB))
lock(max(accountA, accountB))
transfer()
unlock in reverse
Wrong “fix”:
if (!tryLock(B, 50ms)) keep holding A and retry B
→ you still hold A while probing; others deadlock on A
Right timeout path:
if (!tryLock(B, 50ms)) { unlock(A); backoff; retry both from scratch }Detect, then recover
Read the diagram definition
flowchart TD
Waits[Lock waits / blocked queries] --> WFG[Build wait-for graph]
WFG --> Cycle{Cycle?}
Cycle -->|No| Idle[Keep serving]
Cycle -->|Yes| Pick[Select victim]
Pick --> Abort[Abort victim, release locks]
Abort --> Retry[Client retries with backoff]
Retry --> Waits
Cycle -->|Repeated| Alert[Page: lock order bug, not load]InnoDB looks at waiting lock structs; Postgres uses a lock DAG. Both pick a victim (often the cheaper transaction) and return an error the client must retry. If your app retries blindly without jitter, you get .
Application-level detectors (JVM deadlock MXBean, jcmd Thread.print) catch mutex cycles, not pool-join hangs and not SQL cycles inside the database. Use the right dump for the layer you suspect.
Cycle detection sketch (single lock manager):
WFG: directed graph of waiters → holders
deadlock ⇔ cycle
Algorithm: DFS / Tarjan SCC on the wait-for graph
Cost: cheap if waiters are few; run on a timer or on each wait
Victim cost examples:
- work_done (undo volume)
- lock_count
- deadline remaining (abort the one already late)
- tenant priority (protect paying SLO)
After abort:
release locks in a defined order
surface a retryable error (SQLSTATE 40001 / serialization failure)
increment deadlock_count; page if rate stays highAvoidance vs prevention
The is the textbook avoidance method: processes declare maximum claims; a request is granted only if there exists an order in which every process could still finish. It needs trusted max claims and a single allocator. That is a poor fit for a fleet of stateless API pods, and a decent mental model for a partitioner that will not hand out the last connection slots if it would strand everyone.
Prevention is what you actually ship: lock ranking, hierarchical locking (lock table then page then row in one direction), single-resource critical sections, optimistic CAS instead of nested mutexes, and not holding a lock across an RPC.
Prefer prevent
- Documented lock rank / resource id order
- No lock held over network I/O
- One lock per request when possible
- Optimistic version checks for rare conflicts
Keep detect+recover
- SQL engines will still deadlock under RR/gap locks
- Third-party code ignores your rank
- as a backstop
- Metrics on deadlock rate, not only latency
Distributed cycles and probes
Read the diagram definition
sequenceDiagram
autonumber
participant A as Service A
participant LA as Lock mgr A
participant B as Service B
participant LB as Lock mgr B
A->>LA: holds X, waits on Y
Note over A,B: Y is owned by B
A->>B: edge-chasing probe
B->>LB: holds Y, waits on X
LB-->>B: local wait is on A
B-->>A: probe returns to A
Note over A,B: Probe home = cycle across servicesEdge chasing (Chandy–Misra–Haas style): a blocked process sends a probe along wait edges. If the probe returns to the initiator, a cycle exists. Phantom deadlocks happen when a wait ends while the probe is in flight. Timeouts plus idempotent retry are usually cheaper than a perfect global WFG for request-path systems; lock services still need fencing so a timed-out holder cannot write.
Practical SD policy for cross-service locks:
1. Do not nest distributed locks. One resource, one lease.
2. Never hold lock L while calling a service that might lock L' then wait on you.
3. Prefer: lock, touch storage, unlock, then RPC.
4. If a saga needs multiple resources, use an orchestrator + compensations,
not a chain of mutexes.
5. Deadlines on RPCs bound how long a wait can last even if detection is imperfect.
Phantom deadlock:
Probe says cycle, but B already released Y
Aborting A is wasteful but safe if A is retryable
Unsafe if abort is not idempotentPool deadlock: no mutex cycle
A does not show “Found one Java-level deadlock.” Every worker is waiting on a Future whose task is still queued. Common-pool join, servlet threads calling into the same bounded executor, and “run this on the pool I am already on” are the usual plots.
Pattern:
pool size = N
N workers each do: result = pool.submit(leaf).get()
leaves never start → hang
Fixes:
- do leaf work on this thread when the pool is saturated (managedBlocker)
- separate pools: callers vs CPU vs blocking I/O
- do not join tasks that must run on the same executor
- cap inbound concurrency below pool size if you must join
Dump clue:
threads in WAITING on Future / queue, no monitor cycle
runnable queue has the work that would unblock themWhere this shows up in designs
Database row locks
Money movement / inventory
Job schedulers and shard locks
Cache compute functions
Worked example: payments + inventory
Checkout locks SKU row then user wallet. Refunds lock wallet then SKU. After a sale event both paths run. Deadlock rate climbs; p99 is “fine” because deadlocked requests never finish and the load balancer already returned 504.
Invariant:
any code path that needs (sku_id, user_id) locks
lock(row(min(sku,user))) then lock(row(max(sku,user)))
Detection (DB):
deadlock_count / sec on the primary
SHOW ENGINE INNODB STATUS / pg_locks + pg_stat_activity
victim is retryable POST /checkout with idempotency key
Avoid the mutex entirely:
append-only ledger + outbox
inventory reservation with a single row + version column
refunds apply compensating entries, no reverse lock order
Timeout backstop:
lock_timeout = 200ms
on timeout: abort txn, jitter 20–80ms, retry ≤ 3
if still failing: 503, do not hold partial locksTrade-offs
| Choice | Gain | Cost |
|---|---|---|
| Global lock order | Cycles cannot form on those locks | Discipline; all call sites must obey |
| Detect + abort | Works with messy third-party locking | Wasted work; retry storms; needs idempotency |
| Banker-style avoidance | Never enter an unsafe state | Needs max claims; centralized; conservative denials |
| tryLock timeouts | Bounds wait; sheds instead of freeze | Livelock if retry is naive; must drop all holds |
| No nested locks | Simple liveness | May need extra round-trips or coarser locks |
| Coarse one big lock | No cycles | Throughput collapse; convoy |
Choosing and explaining deadlock detection and avoidance
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
Deadlock is a wait-for cycle under the four Coffman conditions, not merely a slow lock.
Prevention (lock order, no nested locks) is the design default; databases still detect and abort leftover cycles.
Recovery only works if the victim is idempotent. Pool deadlocks and distributed cycles need different dumps than mutex cycles.
When it belongs
Multi-row transactions, money movement, or shard-pair jobs.
Nested locks, cache loaders, or thread-pool joins.
Cross-service lock plus RPC that might lock in reverse.
How it fails
Opposite lock order under real concurrency.
Timeout retry that keeps holding the first lock.
Phantom vs missed distributed cycles.
Executor join deadlock with no mutex cycle in the dump.
Livelock from synchronized deadlock retries.
Trade-offs to weigh
Fine-grained locks (throughput) versus cycle risk.
Abort-and-retry waste versus conservative avoidance denials.
Coarse locking simplicity versus convoy latency.
Common misunderstandings
Calling any hang a deadlock (could be missing notify, GC pause, or pool join).
Retrying deadlocks without jitter or idempotency keys.
Treating Redlock/TTL expiry as a deadlock detector.
Holding a mutex or row lock across an outbound RPC.
Wrap-up
Design so cycles cannot form, keep a detector for the layers you do not control, and make every abort retryable. Measure deadlock rate as its own SLO signal—timeouts hide it.
Exercises
- Rank the locks. List every resource checkout and refund touch. Write one total order and a tryLock failure path that drops all holds.
- Read a dump. Sketch what a mutex cycle looks like versus a pool deadlock versus a SQL deadlock victim error at the API.
- Cross-service. Service A locks order, calls B; B locks inventory, calls A to confirm. Draw the WFG and name two protocol changes that remove the cycle.
Primary sources
Key takeaway
Deadlock is a cycle. Order locks, do not hold them over RPCs, detect what you cannot prevent, and abort only work that can replay. Timeouts without dropping holds, and retries without jitter, are how a liveness bug becomes an outage.