Skip to content

Deadlocks

1. What is it? (2-3 lines)

A Deadlock is a circular dependency condition in concurrent database transactions where two or more transactions are blocked indefinitely, each holding a lock that the other transaction requires to proceed.

2. Why does it exist?

Deadlocks occur naturally when concurrent transactions acquire exclusive locks on multiple shared resources in different orders. Because relational databases enforce strict lock wait queues to guarantee transaction isolation, circular dependencies create permanent blocking loops that cannot resolve without engine intervention.

3. Where is it used?

  • Relational Storage Engines: PostgreSQL, MySQL (InnoDB), Oracle, SQL Server lock managers.
  • Distributed Lock Managers: ZooKeeper, etcd, Redis Redlock (distributed deadlocks).

4. How does it work? (simple flow)

  1. Classic Deadlock Scenario:
  2. Transaction A acquires Exclusive Lock on Row 1.
  3. Transaction B acquires Exclusive Lock on Row 2.
  4. Transaction A attempts to acquire Exclusive Lock on Row 2 \(\rightarrow\) BLOCKED (waits for Transaction B).
  5. Transaction B attempts to acquire Exclusive Lock on Row 1 \(\rightarrow\) BLOCKED (waits for Transaction A).
  6. Circular Dependency: Transaction A \(\rightarrow\) waits for B \(\rightarrow\) waits for A.
  7. Deadlock Detection (Wait-For Graph): Database background thread runs a Wait-For Graph algorithm. Nodes = Transactions; Edges = Lock Wait dependencies.
  8. Cycle Detection: If a cycle is detected (\(T_A \to T_B \to T_A\)), the database chooses a "victim" transaction (usually the one with fewer updates).
  9. Victim Abort: Engine aborts the victim transaction with DeadlockDetectedException (40P01), rolls back its changes, and releases its locks, unblocking the remaining transaction.

5. Advantages

  • Automatic engine detection prevents permanent server thread hangs and resource leaks.
  • Preserves transactional isolation and data consistency by rolling back conflicting transactions cleanly.

6. Limitations

  • Aborted victim transactions require application-level retry handling logic.
  • Frequent deadlocks degrade database throughput due to CPU overhead from constant detection and rollbacks.

7. Common interview questions (10)

  1. What are the 4 Coffman conditions required for a Deadlock to occur?
  2. How does a database engine detect deadlocks using Wait-For Graphs?
  3. How does Lock Ordering (consistent access order) eliminate deadlocks at application design time?
  4. How do lock timeouts (lock_timeout / innodb_lock_wait_timeout) serve as an alternative to active deadlock detection?
  5. How does MySQL InnoDB select which transaction to abort as the "deadlock victim"?
  6. How do Gap Locks and Next-Key Locks in InnoDB increase deadlock frequency?
  7. What is the difference between a Deadlock and Livelock or Lock Starvation?
  8. How should application microservices handle DeadlockDetectedException retries safely?
  9. How can Indexing reduce or eliminate deadlocks in high-concurrency UPDATE queries?
  10. What is a Distributed Deadlock and why is it far harder to detect than a single-node database deadlock?

8. Common misconceptions

  • Misconception: Deadlocks are bugs in the database engine. Fact: Deadlocks are normal concurrency events resulting from application transactions locking resources in inconsistent orders.
  • Misconception: Increasing lock timeouts solves deadlocks. Fact: Increasing timeouts simply delays error detection, keeping threads blocked longer and reducing system throughput.

10. 30-second cheat sheet

  • Definition: Circular wait condition (\(T_A \to T_B \to T_A\)). Neither transaction can proceed.
  • Engine Resolution: Wait-For Graph Cycle Detection \(\implies\) Select Victim \(\implies\) Abort & Rollback.
  • Primary Prevention: Consistent Lock Ordering across all application queries (e.g., always lock Row 1 before Row 2).
  • Application Rule: Always wrap database calls in a retry loop with Exponential Backoff and Jitter on deadlock errors.