Distributed Deadlock Detection Mechanics
In distributed database systems, deadlock detection typically triggers when a transaction exceeds a predefined lock_wait_timeout. Rather than running a continuous global scan, the system initiates a Wait-for-Graph (WFG) analysis only after a transaction has been blocked for a specific duration. This prevents the system from wasting CPU and network resources on short-lived contention that would naturally resolve without intervention.
Managing WFG Performance Bottlenecks
To prevent the WFG from becoming a performance bottleneck during high-contention bursts, distributed systems generally employ three primary strategies:
- Hierarchical Partitioning: The system first checks for local deadlocks within a single node. Only if a dependency chain extends to a remote node is the dependency propagated to a global or regional detector, reducing the volume of inter-node traffic.
- Probe-Based Detection: Instead of maintaining a mirrored global graph, the system may use a probe-based approach (such as the Chandy-Misra-Haas algorithm). A probe is sent along the dependency chain; if the probe returns to the initiator, a cycle is confirmed. This avoids the O(N²) complexity of a centralized global graph.
- Priority Preemption: Mechanisms like Wound-Wait act as a first line of defense. By preemptively aborting younger transactions that conflict with older ones, the system kills potential cycles before they ever require a WFG traversal.
Assumptions and Trade-offs
The efficiency of these mechanisms assumes that most transactions are short-lived and that contention is localized. In scenarios with "deep" dependency chains (where Transaction A waits for B, which waits for C, and so on across multiple nodes), the latency of detection increases linearly with the chain length.
A significant risk in distributed WFG analysis is the phantom deadlock. This occurs when a dependency is reported to the detector, but by the time the detector identifies a cycle, one of the transactions has already released its lock or timed out. This results in an unnecessary transaction abort.
Verification and Diagnostics
To verify the impact of deadlock detection on your specific workload, monitor the ratio of deadlock_detected events versus lock_timeout events. If the system is aborting transactions via timeouts before the WFG can identify the cycle, the detection interval may be too conservative.
Diagnostic Detail Needed: To provide a more precise recommendation on threshold tuning, please provide the average lock_wait_timeout setting and the average number of tablets involved per distributed transaction.
yugabytedb