Day 404: Deadlock Detection, Timeout, and Avoidance

The core idea: Once strict locking uses waiting to preserve correctness, the engine also needs a policy for impossible waits, because a cycle in the wait graph will never resolve on its own.

Today's "Aha!" Moment

In 03.md, Harbor Point accepted the main bargain of strict 2PL: if two traders want to update the same issuer_exposure['MUNI-77'] row, one of them must wait. That solved the over-allocation anomaly, but it introduced a new operational fact. Waiting is only safe when there is still some future commit or rollback that can release the resource. If every blocked transaction is waiting for another blocked transaction, the lock manager has preserved correctness and lost progress.

That is exactly what happens during the desk's market-open rush. One transaction amends reservation QR-1842, so it locks the reservation row first and then reaches for the issuer summary row to recompute headroom. At the same time, a risk-control transaction tightens the MUNI-77 limit, so it locks the issuer summary row first and then tries to mark QR-1842 for review. Each transaction is behaving sensibly in isolation. Together they form a circle: each one needs the other to move first.

Deadlock handling is the subsystem that turns that frozen circle back into forward progress. Detection proves a cycle exists and chooses a victim. Timeout gives up after a wait budget is exceeded, even if the engine cannot prove why the wait is long. Avoidance changes the waiting rules or lock acquisition pattern so the cycle never becomes possible. These are not interchangeable operational details. They shape how much work is wasted, how quickly the application gets a retryable error, and how often tail latency turns into a customer-visible incident.

This also prepares the transition to 05.md. MVCC reduces many read-write waits by letting readers follow version visibility rules instead of entering the lock queue, but writer-writer conflicts and metadata locks still need a deadlock policy. Deadlocks are not an edge case bolted onto locking. They are the cost of using waiting as a correctness tool.

Why This Matters

Harbor Point's approval API has a tight SLO at market open, but its real requirement is stronger than latency: the desk cannot oversubscribe an issuer and it cannot leave traders staring at requests that never finish. Deadlock handling sits directly on that boundary between correctness and operability. When it works well, one transaction is rolled back quickly, the application retries cleanly, and the exposure invariant remains intact. When it works poorly, threads pile up, timeouts fire far from the real blocker, and operators see a "slow database" incident that is actually a lock-cycle problem.

The distinction matters because long waits and deadlocks are not the same failure. A long wait may be healthy backpressure behind one hot lock holder. A deadlock is a proof that no amount of patience will help. If the team responds to every wait by increasing timeout values, they simply stretch user-facing latency while preserving the cycle. If they disable detection to save CPU, they may reduce lock-manager overhead while turning a fast retryable abort into a multi-second outage pattern. Production engineering here is mostly about precision: knowing which waits are productive, which are impossible, and which design changes remove the cycle entirely.

Learning Objectives

By the end of this session, you will be able to:

1. Explain how a deadlock emerges from ordinary lock waits - Turn a Harbor Point contention incident into a wait-for graph and identify the cycle.
2. Compare detection, timeout, and victim-selection strategies - Reason about how engines decide that a wait is impossible and which transaction to abort.
3. Choose practical avoidance techniques for production workloads - Use lock ordering, shorter critical sections, and age-based policies to reduce deadlocks without abandoning correctness.

Core Concepts Explained

Concept 1: A deadlock is a cycle in the wait-for graph, not just a slow queue

The Harbor Point scenario becomes a deadlock the moment both transactions hold one lock and wait on the other. Transaction T1 is editing reservation QR-1842, so it already owns an exclusive lock on that reservation row. Transaction T2 is tightening the issuer limit, so it already owns an exclusive lock on issuer_exposure['MUNI-77']. Each transaction then asks for the other resource:

T1: X-lock quote_reservations[QR-1842] granted
T2: X-lock issuer_exposure['MUNI-77'] granted
T1: X-lock issuer_exposure['MUNI-77'] requested -> waits for T2
T2: X-lock quote_reservations[QR-1842] requested -> waits for T1

The lock manager can rewrite that situation as a wait-for graph:

T1 --> T2
^       |
|       v
T2 <-- T1

Each edge means "this transaction cannot proceed until that one releases a conflicting lock." As soon as the graph contains a cycle, no local wakeup rule can fix it. Neither transaction can reach commit, so neither transaction can release what the other needs. That is the important distinction from ordinary contention. In a healthy queue, at least one path to commit still exists. In a deadlock, every path loops back into the wait graph.

Strict 2PL makes this possible because it holds locks until the end of the transaction. That strictness is still the right choice for Harbor Point; it protects the exposure invariant and simplifies recovery. But it also means that a transaction does not gradually free resources as it moves through business logic. If lock acquisition order is inconsistent, the engine will eventually see a cycle created by otherwise valid transactions. Lock upgrades can create the same pattern: two transactions may both start with shared locks and then deadlock when each tries to upgrade to exclusive.

The trade-off is subtle. Fine-grained locking lets Harbor Point process unrelated issuers concurrently and keeps the hot path narrower than a table lock would. At the same time, more lockable objects and more access paths increase the number of possible wait edges. Concurrency improves, but the state space where cycles can form also grows.

Concept 2: Detection and timeout both recover progress, but they answer different questions

A detector works from lock-manager state, not from elapsed time alone. When a transaction blocks, the engine already knows which lock request could not be granted and which transactions currently hold conflicting locks. That is enough to add edges to a wait-for graph and ask whether the newly blocked transaction closes a cycle. Some engines run this check immediately on each blocking event; others run it periodically to reduce overhead. Either way, a detector is doing proof, not guesswork.

For Harbor Point, a simplified detector path looks like this:

1. T1 waits on a lock held by T2 -> add edge T1 -> T2
2. T2 later waits on a lock held by T1 -> add edge T2 -> T1
3. Cycle found -> choose victim
4. Abort victim, release its locks, wake surviving transaction

Victim selection is where engineering policy enters. Many systems prefer the younger transaction, the one with the fewest updates, or the one with the lowest estimated rollback cost. That choice matters operationally. Aborting a short, fresh transaction usually wastes less work and releases resources faster. Aborting a large transaction with many dirty pages may free a critical lock, but it also creates more undo work and can amplify retry pressure upstream. A good deadlock report therefore includes both the cycle and the chosen victim so operators can see whether the heuristics match the workload.

Timeout is different. A timeout policy says, in effect, "this wait lasted longer than we are willing to tolerate, so abort someone even if we cannot prove a cycle." That is useful as a safety boundary, especially when the engine cannot observe the full dependency graph, as in some distributed locking or multi-node transaction paths. It is also cheaper than running cycle detection aggressively on every wait. But timeout is blunt. A transaction can legitimately wait behind one long-running holder without any deadlock at all. If Harbor Point sets lock wait timeout too low, it will abort healthy work during market spikes. If it sets the timeout too high, true deadlocks will linger and inflate p99 latency before anyone is released.

The practical lesson is to treat detector and timeout as complementary, not equivalent. Detection is the right tool when one lock manager can see the cycle. Timeout is the outer guardrail that limits damage when visibility is incomplete or blocking is simply too long to accept. Using timeout as the only deadlock strategy inside a single-node lock manager is usually a sign that the team is paying user-visible latency to avoid implementing or tuning the more precise mechanism.

Concept 3: Avoidance removes cycles by constraining how waits are allowed to form

The cheapest avoidance technique is usually design discipline. Harbor Point can remove the deadlock above by making every workflow acquire the issuer summary row before touching individual reservation rows. If both the trader amendment path and the risk-tightening path lock issuer_exposure['MUNI-77'] first, then one of them will queue immediately and the cycle cannot form. A total order on lock acquisition does not eliminate waiting, but it turns circular waits into straight lines.

That principle extends beyond application code. Lock upgrades are dangerous because they introduce "I already hold a weaker lock and now want a stronger one" edges late in the transaction. If Harbor Point knows a path will definitely update a reservation, it is often safer to request the stronger mode up front instead of taking a shared lock and upgrading later. Shorter critical sections help for the same reason: the less application work done while holding the first hot lock, the fewer opportunities there are for another transaction to interleave and create the opposite half of a cycle.

Database engines also implement algorithmic avoidance policies. In wait-die, an older transaction is allowed to wait for a younger one, but a younger transaction that wants a lock held by an older one is aborted immediately. In wound-wait, the older transaction preempts the younger holder instead of waiting. Both schemes use transaction age to impose a monotonic direction on waits, which prevents cycles from forming. The cost is more aborts, especially for younger transactions during bursts of contention. To avoid starvation, restarted transactions usually keep their original timestamp so they do not remain "young forever."

There is an even stronger form, sometimes called conservative 2PL, where a transaction must acquire all the locks it will need before doing any work. That prevents deadlocks because the transaction never waits mid-flight after partially claiming resources. In practice, Harbor Point cannot use this broadly: the exact set of reservation rows may only become known after reading current state. Conservative schemes are strongest when the access set is predictable and small; otherwise they trade away too much concurrency and flexibility.

This is where the bridge to 05.md matters. MVCC removes many read-side waits by letting readers consult visibility metadata rather than queue behind writers. That shrinks the space where deadlocks can arise, but it does not erase it. Writers can still deadlock on hot rows, indexes, and metadata. Avoidance is therefore not a relic of lock-only systems. It remains part of the production toolbox even in versioned engines.

Troubleshooting

Issue: Harbor Point sees lock timeout errors, but deadlock logs are empty.

Why it happens / is confusing: A timeout only proves the wait exceeded a budget. The blocker may be one long transaction on a hot issuer rather than a cycle, or the lock manager may not be running a detector for that path.

Clarification / Fix: Inspect blocked and blocking sessions first. If there is one root blocker, shorten its critical section or move non-essential work out of the transaction. If there is a genuine cycle that the engine cannot see directly, use timeout as the fallback and tighten application retry handling.

Issue: The same business action deadlocks only intermittently.

Why it happens / is confusing: Deadlocks depend on interleaving. Two code paths can be correct in isolation and still deadlock only when timing causes them to acquire the same resources in opposite orders.

Clarification / Fix: Compare the exact lock acquisition order across the conflicting statements. Standardize the order, avoid late lock upgrades, and make hot paths lock the shared summary row first.

Issue: Deadlock detection resolves the cycle quickly, but the service still melts down under load.

Why it happens / is confusing: Breaking the cycle is only half the story. If every aborted transaction retries immediately, the application can recreate contention faster than the database can drain it.

Clarification / Fix: Make deadlock retries idempotent, add bounded backoff with jitter, and cap the number of immediate retries on the same hot issuer.

Issue: Deadlock reports mention index or metadata locks that the application never requested explicitly.

Why it happens / is confusing: SQL statements often touch more than the obvious row. Index maintenance, foreign-key checks, and metadata access can add lock edges that are invisible at the ORM level.

Clarification / Fix: Read the engine's deadlock report as a physical execution trace, not only as a logical statement list. The missing edge often appears in the index path or constraint check, and that is where the ordering fix must be applied.

Advanced Connections

Connection 1: Deadlock handling ↔ operating-system resource allocation

The same graph logic appears in operating systems when processes wait for multiple resources. Database lock managers simply make the graph more dynamic and more granular: row, page, index-key, and metadata locks are all resource nodes that can create wait edges. The key idea carries over cleanly: prevention constrains allowed waits, detection finds cycles after they form, and recovery chooses who to evict.

Connection 2: Deadlock handling ↔ MVCC visibility rules

Deadlock handling explains why many engines invested so heavily in MVCC. If readers can decide visibility from tuple-version metadata, they avoid joining the wait graph for many common cases. That does not eliminate writer deadlocks, but it changes where the system spends coordination cost. 05.md picks up exactly there by showing how snapshots replace some blocking decisions with version-selection rules.

Resources

Optional Deepening Resources

• [DOC] PostgreSQL Documentation: Deadlocks
  • Focus: Review how PostgreSQL detects deadlocks, what the error reports look like, and why the server aborts one transaction to preserve progress.
• [DOC] MySQL 8.0 Reference Manual: Deadlocks in InnoDB
  • Focus: Study InnoDB's detector, lock wait timeout behavior, and concrete guidance on reducing deadlocks in row-level locking workloads.
• [DOC] SQL Server Deadlocks Guide
  • Focus: Compare wait-for graphs, victim choice, and monitoring tooling in another major lock-based engine.

Key Insights

1. A deadlock is a structural impossibility, not a long wait with bad luck - Once the wait-for graph contains a cycle, no amount of patience will let every transaction finish.
2. Detection and timeout solve different problems - Detection proves a cycle and aborts precisely, while timeout enforces an upper bound on waiting when proof is missing or too expensive.
3. The best avoidance technique is usually predictable lock behavior - Stable lock ordering, fewer upgrades, and shorter critical sections remove many deadlocks before detector heuristics ever matter.