数据库系统中的死锁检测与消除问题在经典集中式数据库中相对成熟，但在分布式环境中仍处于起步阶段。分布式环境下每个节点只有局部视图，构建/维护全局 WFG 成本高、还会拉高尾延迟。

早期的 M&M (Mitchell-Merritt) 算法默认“每个事务每次仅等待一个资源”，但现实中一个事务可能并发等待多个资源，导致其适用性受限；CMH（Chandy-Misra-Haas）算法虽然去中心化，但可能触发“多受害者”回滚。

为解决这些问题，OceanBase 团队在分布式死锁检测上推出了 LCL+：一套“无需全局视图、消息轻量、单受害者解锁”的分布式算法。它针对“混合死锁”（本地+分布式）做了加速优化。

目前，该工作已发表于 ACM Transactions on Computer Systems（ACM TOCS，2025），并已在 OceanBase 生产系统中实现，多维度评测显示显著改进吞吐、尾延迟与可扩展性。

本文提出并在 OceanBase 落地了 LCL+：一种基于“锁链长度”单向传播的纯分布式死锁检测与消除方法，依靠仅向直接下游交换的轻量消息并叠加 Stage-0 预繁殖即时识别本地/混合死锁，严格实现“每个环只终止一个受害者”，在无全局等待图的前提下显著提升吞吐、降低尾延迟、增强可扩展性，解决了分布式场景死锁检测难、通信与回滚成本高以及多受害者误杀的工程痛点。

论文链接：

https://dl.acm.org/doi/10.1145/3768621

在分布式数据库里做死锁检测，单机时代的成熟方法并不好直接套用：各节点只能看到局部等待关系，全局一致识别很难；经典 M&M 算法假设“每个事务一次只等一个资源”， 难以适应现实里的多出度并发场景；CMH（Chandy-Misra-Haas）算法可能造成一次“多受害者”回滚，工程上代价高、吞吐低。

图1：LCL+算法推导

1.核心理念：Lock Chain Length（锁链长度）

为应对这些问题，LCL+ 以“锁链长度”这一可传播的局部度量为抓手，把分布式死锁检测这类“全局难题”拆解为“局部轻交互”。

如图 1 所示，给每个等待节点维护一个会“沿依赖链单向传播”的整数（LCLV）。在有环时，环内 LCLV 会不断增大；无环路径则会收敛到上界。基于这个性质，算法能在纯分布式环境下仅靠“向下游邻居发消息”完成检测与选定“受害者”。

LCL 算法有以下三个核心阶段：

• Stage 1：Proliferation（“繁殖”）：沿依赖边单向传播并递增LCLV，使无环路径收敛、环内数值持续上升，从数值上区分环与非环，为后续扩散做铺垫。

图2 第1阶段：LCL 繁殖阶段

• Stage 2：Spread（“扩散”）：同步环内的最大 LCLV，并基于预设“终止优先级”（例如时间戳/事务优先级）选出唯一受害者（single victim），再把该受害者的 ID 扩散给环内所有节点。

图3 第2阶段：LCL扩散阶段

• Stage 3：Detection（“确认”）：满足“三等式”条件时，即在同一环内且该节点即为受害者，随后仅终止一个事务即可打破死锁。

图4 第3阶段：LCL 确认阶段

而LCL+ 在核心流程前引入前置机制：

图5 第 0 阶段：LCL+ 预繁殖，加速混合死锁检测

• Stage 0：Pre-proliferation（预繁殖）：如图5所示是 LCL+ 的新增机制。为了弥补“周期化”可能带来的检测等待，使本地小环立刻识别，并加速跨机大环检测。对本地等待链采用深度优先遍历（DFS）进行快速传播与回访日志检查，即时识别本地环并选出单一受害者；对跨机部分则把消息投入 LCL缓冲，等待周期化流程协同推进，从而显著加速“混合死锁”（本地+分布式）的整体检测。

在 6 台 OceanBase 服务器集群中对比结果显示，在相同硬件与负载下，LCL+ 相比常用的 Timeout 基线，把系统吞吐量提升了 150%～540%（不同负载分布下），采用 LCL+与Timeout 的组合时，峰值提升最高可达 820%（相对单用Timeout）；同时 LCL+ 在 99%/99.9% 尾延迟上显著优于仅用超时（Timeout）与传统分布式检测方案（例如 CMH 算法），避免多受害者回滚带来的额外开销。

该算法用可单向传播的“局部指标”（LCLV）替代“昂贵的全局收敛”，把“全局难题”拆成“局部轻交互”。通过引入 Stage 0 预繁殖机制，在无需全局等待图、仅与直接下游交换极少量消息的前提下，实现吞吐显著提升与尾延迟下降、严格单受害者解锁，让 SLA 更稳、回滚与网络开销更低、资源利用率更高且易于在现有系统中灰度落地扩展。

想了解更多行业资讯

扫码关注👇

了解更多考试相关

扫码添加上智启元官方客服微信👇