原来是“图”！

死锁检测技术实现：等待图与定时遍历方案

死锁是数据库和并发系统中常见的问题，多个事务互相持有对方所需的资源，导致系统陷入停滞。通过构建等待图并配合定时检测机制，可以高效识别死锁并触发事务回滚，保障系统可用性。

等待图（Wait-for Graph）建模

等待图是一种有向图，用于表示事务间的资源依赖关系。图中节点代表事务，边表示事务A正在等待事务B释放资源。当图中存在环时，说明死锁发生。

class WaitForGraph { private Map<Long, Set<Long>> adjacencyList = new HashMap<>(); // 添加事务节点 public void addTransaction(Long transactionId) { adjacencyList.putIfAbsent(transactionId, new HashSet<>()); } // 添加等待边：fromTxId → toTxId public void addEdge(Long fromTxId, Long toTxId) { adjacencyList.get(fromTxId).add(toTxId); } // 移除事务节点及关联边 public void removeTransaction(Long transactionId) { adjacencyList.remove(transactionId); adjacencyList.values().forEach(edges -> edges.remove(transactionId)); } }

死锁检测算法实现

基于深度优先搜索（DFS）的环检测算法可高效发现等待图中的死锁环。以下代码实现了递归DFS检测：

class DeadlockDetector { private Set<Long> visited; private Set<Long> recursionStack; private WaitForGraph graph; public boolean hasCycle(WaitForGraph graph) { this.graph = graph; visited = new HashSet<>(); recursionStack = new HashSet<>(); for (Long txId : graph.getTransactions()) { if (detectCycle(txId)) { return true; } } return false; } private boolean detectCycle(Long currentTx) { if (recursionStack.contains(currentTx)) return true; if (visited.contains(currentTx)) return false; visited.add(currentTx); recursionStack.add(currentTx); for (Long neighbor : graph.getEdges(currentTx)) { if (detectCycle(neighbor)) { return true; } } recursionStack.remove(currentTx); return false; } }

定时检测与事务回滚

通过定时任务周期性检测死锁，发现死锁后选择牺牲者事务进行回滚。牺牲者选择策略通常基于事务优先级、已执行时间或修改数据量。

class DeadlockMonitor { private ScheduledExecutorService scheduler; private WaitForGraph graph; private long detectionInterval = 5000; // 5秒检测一次 public void startMonitoring() { scheduler = Executors.newSingleThreadScheduledExecutor(); scheduler.scheduleAtFixedRate(this::checkDeadlocks, detectionInterval, detectionInterval, TimeUnit.MILLISECONDS); } private void checkDeadlocks() { DeadlockDetector detector = new DeadlockDetector(); if (detector.hasCycle(graph)) { Long victimTxId = selectVictim(); // 实现牺牲者选择策略 abortTransaction(victimTxId); } } private void abortTransaction(Long txId) { // 回滚事务并释放资源 graph.removeTransaction(txId); System.out.println("Aborted transaction: " + txId); } }

优化与实践建议

1. 增量检测：在大型系统中，每次全图检测成本高。可跟踪新增的边进行局部检测。
2. 牺牲者策略：根据业务特点定制选择策略，如回滚修改最少数据的事务。
3. 避免过度回滚：添加事务超时机制，与死锁检测互补。

// 示例：基于时间戳的牺牲者选择 private Long selectVictim() { return graph.getTransactions().stream() .min(Comparator.comparingLong(txId -> getStartTime(txId))) .orElseThrow(); }

通过等待图建模与定期检测，系统能主动识别死锁并恢复，显著提升稳定性。实际部署时需根据负载调整检测频率，平衡性能与实时性。