DEV Community

Cover image for Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

#dbms #sql #database #systemdesign

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

In relational database systems running under Two-Phase Locking (2PL), deadlock is an inevitable side effect of concurrent lock acquisition.

Traditionally, databases employ Deadlock Detection: the engine builds a Wait-For Graph in memory, runs cycle-detection algorithms (e.g., Tarjan's or DFS), and selects a victim to abort when a cycle forms.

However, in ultra-high-throughput systems, constantly searching for cycles introduces significant locking overhead.

Instead, database engines can employ Timestamp-Based Deadlock Prevention: Wait-Die and Wound-Wait.

1. The Timestamp Precedence Rule

Every transaction T_i is assigned a monotonically increasing timestamp TS(T_i) when it begins.

  • If TS(T_i) < TS(T_j), T_i is older (senior).
  • If TS(T_i) > TS(T_j), T_i is younger (junior).

A deadlock requires a cyclic dependency chain:

T₁ → T₂ → ... → T_n → T₁
Enter fullscreen mode Exit fullscreen mode

By enforcing strict directional rules based on age, cyclic dependencies become mathematically impossible.

2. The Wait-Die Scheme (Non-Preemptive)

Suppose transaction T_i requests a lock currently held by T_j:

  • If T_i is older than T_j (extTS(T_i) < extTS(T_j)):
    • T_i is allowed to WAIT until T_j releases the lock.
  • If T_i is younger than T_j (extTS(T_i) > extTS(T_j)):
    • T_i DIES (aborts, rolls back its mutations, and restarts).

Intuition:

Only older transactions may wait for younger transactions. A younger transaction can never wait for an older one, making cycles impossible.

3. The Wound-Wait Scheme (Preemptive)

Suppose transaction T_i requests a lock currently held by T_j:

  • If T_i is older than T_j (extTS(T_i) < extTS(T_j)):
    • T_i WOUNDS T_j. The engine immediately preempts and aborts T_j, granting the lock to T_i.
  • If T_i is younger than T_j (extTS(T_i) > extTS(T_j)):
    • T_i is allowed to WAIT for T_j.

4. Preventing Starvation

In both schemes, when an aborted transaction restarts, it retains its original timestamp.

As time progresses, an aborted transaction becomes progressively older relative to newly arriving transactions. Eventually, it becomes the oldest transaction in the system, guaranteeing it will never be aborted again.

Explore full database concurrency control architectures at Binary Dose.

Top comments (0)