跳到主要内容

死锁检测与恢复

被动检测死锁的手段及规模故障下的恢复策略

核心要点：

  • 避免是主动设计，恢复是被动兜底
  • 恢复省缓冲但牺牲吞吐
  • 检测主流靠超时
  • 恢复分回滚式与前进式
  • 规模放大故障频率，进而放大死锁面

前置阅读：

避免和恢复，工程上怎么选？​

避免（avoidance）是在设计期保证不死锁，恢复（recovery）是允许死锁发生、检测到再打破——两者是互补的两条路线。

维度避免恢复
时机设计期（路由 / VC / 拓扑保证无环）运行期（检测 + 解除）
缓冲开销高（需额外 VC / headroom）低（不预留破环资源）
吞吐高较低（解除有代价）
连接限制有（路由受约束）无（不限制通信对）
典型场景片上网络（NoC）、生产无损网络并行计算机网络、缓冲受限场景

避免是 02-06 各章的主线（CDG 无环、VC 破环、SM 算无死锁表等）。恢复的价值在于省缓冲、不限制连接，代价是降低吞吐——适合死锁罕见、缓冲昂贵的场景。万卡 AI 集群通常以避免为主、恢复为兜底（如 PFC watchdog，见 04-pfc死锁）。

怎么检测网络死锁？​

主流检测靠超时——一个报文 / 缓冲卡住超过阈值就判定为疑似死锁。

  • 超时检测：允许通道依赖图存在环，报文卡住超时即触发解除（释放缓冲 / 通道）。实现简单，但阈值难调：太短误判正常拥塞，太长恢复慢。
  • 数据面探测：在交换机数据面主动探测循环缓冲依赖。PFC 死锁的专项方案 ITSY、Roundabout 属此类（见 04-pfc死锁），优点是探测快、就地解除，难点是误判率与硬件开销。

超时是工程上最普遍的检测信号——NCCL watchdog（见 07-集合通信死锁）、PFC watchdog（见 04-pfc死锁）本质都是超时检测。

检测到死锁怎么恢复？​

恢复分回滚式（regressive）与前进式（progressive）两类[1]：

  • 回滚式（abort-and-retry）：丢弃环上的报文 / flit，释放其占用的缓冲，源节点等随机间隔后重传。代表 AFBAR 等（软件、超时驱动）。优点实现简单，代价是丢包 + 重传延迟[2]。
  • 前进式：不丢报文，而是把死锁报文导入一条无死锁逃生通道继续前进。代表 DISHA（硬件，用路由器内共享的中央 deadlock buffer 提供逃生通道）。优点不丢包，代价是需要额外硬件资源。

回滚式与 03-流控与无损可丢 的「可丢网络」同源——都是用丢弃打破「不可抢占」条件；前进式则更接近 02-死锁理论基础 的逃生通道思想。

故障重路由为什么会制造死锁，怎么应对？​

链路 / 节点故障触发重路由，新路径可能引入此前无环拓扑里没有的通道环——这是 PFC 死锁的主要诱因（见 04-pfc死锁），也是恢复机制要应对的动态场景。

应对的关键是快速、无死锁地重算路由表：

  • Up/Down 等无死锁二次路径**：故障后切到预定的无死锁备份路由
  • Dmodc：面向 Parallel Generalized Fat-Tree 的快速确定性路由——用基于模运算的闭式公式计算转发表，配合快速预处理，能在不到一秒内对数万节点的拓扑完整重路由，让集中式 fabric 管理在故障后快速给出高质量、无死锁的路由表，且不影响运行中的应用[3]

核心矛盾：重路由既要快（故障常态化下不能慢）、又要保证新路由表无死锁——Dmodc 这类算法就是在解这个矛盾。

规模如何放大死锁面？​

规模通过放大故障频率间接放大死锁面：万卡集群的链路 / 节点故障是常态而非例外，而 PFC 死锁恰恰由故障态重路由触发（见 04-pfc死锁）。

因果链：

  • 节点越多 → 单位时间故障次数越多 → 重路由越频繁 → 形成 CBD 的机会越多 → 死锁概率上升
  • 同时规模越大，单次死锁波及的流量越广（pause storm 传播范围大），恢复代价越高

这解释了为什么死锁在小集群里是理论问题、在万卡集群里是工程必须解决的问题，也是业界转向 Ultra Ethernet 去无损路线（见 03-流控与无损可丢）的规模动因——从源头消除死锁面，比在巨大规模上维持「检测 + 恢复」成本更低、更可控。

Takeaway​

问题结论
避免 vs 恢复避免在设计期保证无环（缓冲贵）；恢复运行期解除（省缓冲、降吞吐）
检测主流靠超时（watchdog）；数据面探测用于 PFC 专项
恢复方式回滚式（丢包重传，STAFR/AFBAR）/ 前进式（逃生通道，DISHA）
故障重路由故障引入新通道环 → CBD；靠 Up/Down 备份路由 + Dmodc 快速无死锁重路由应对
规模影响规模放大故障频率 → 死锁概率与波及面上升

@tbl-deadlock-recovery-takeaway 死锁检测与恢复速查

开放问题​

  • 补一张「避免 / 检测 / 恢复」三层时序与代价对比图（drawio）
  • 调研 ITSY / Roundabout 数据面检测的探测准确率与误判率
  • 量化万卡集群故障率与 PFC 死锁触发频率的实测关系

参考资料​

  1. Comparison of Deadlock Recovery and Avoidance Mechanisms to Approach Message Dependent Deadlocks in On-chip Networks, IEEE. https://ieeexplore.ieee.org/document/5507567/
  2. DBR: A Simple, Fast and Efficient Dynamic Network Reconfiguration Mechanism Based on Deadlock Recovery Scheme, arXiv:1211.5747. https://arxiv.org/pdf/1211.5747
  3. Gliksberg, Capra, Louvet, García, Sohier, High-Quality Fault Resiliency in Fat Trees (Dmodc), arXiv:2211.13101. https://arxiv.org/abs/2211.13101

延伸阅读​