知识卡片
Greenplum的全局死锁检测:把本地等待图汇总成全局图
单机数据库检测死锁只需要看一张等待图(WFG,顶点是进程、边表示 “谁在等谁释放锁”),一旦这张图里出现环路就说明死锁发生了。 Greenplum作为分布式数据库,每个工作实例(segment)本地确实也 在维护一份自己的WFG,但死锁完全可能横跨多个工作实例——某个 事务在实例A上等着一把锁,而持有那把锁的事务本身又在实例B上 等着别的锁——单看任何一个实例的本地图都发现不了这种跨实例的 环。Greenplum的全局死锁检测(GDD)算法解决的正是这个问题:先 在每个工作实例上收集本地WFG,再把这些局部信息汇总构建出一张 全局WFG,图中每个顶点代表一个事务、记录它的出度和入度。GDD 定义了两种边:实边表示”必须等待对方事务结束才能消失”的硬依赖, 加点边表示”对方事务即使还没结束、也可能提前释放锁”的软依赖。 算法本身是一种贪心迭代:反复做三件事——删除全局出度为0的顶点 (这类事务不再等任何人,不可能是死锁的一部分)、删除全局入度 为0的顶点(没人在等它,同样不可能卡在环里)、以及在每个工作 实例的本地图里删除本地出度为0的顶点对应的加点边——不断循环 执行直到没有顶点可删为止;如果循环结束后图里还剩下边,剩下的 就是真正的死锁环,需要被打破。这套设计的关键在于它没有假设 “能一次性拿到全局完整状态再做判断”,而是通过局部信息的持续 交换和迭代式剪枝,逐步收敛到全局结论——这正是很多分布式系统 问题(不只是死锁检测)处理”本地视角拼出全局真相”时的通用套路。
结构图:
flowchart TD
A[各工作实例收集本地WFG] --> B[汇总构建全局WFG<br/>顶点=事务 记录出度/入度]
B --> C{迭代剪枝}
C -->|全局出度为0| D[删除顶点+相关边<br/>不再等任何人]
C -->|全局入度为0| E[删除顶点+相关边<br/>没人在等它]
C -->|本地出度为0| F[删除对应加点边<br/>软依赖已消失]
D --> C
E --> C
F --> C
C -->|无顶点可删| G{图中是否还有剩余边}
G -->|有| H[确认为死锁环<br/>需要打破]
G -->|无| I[无死锁]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入浅出Greenplum分布式数据库:原理、架构和代码分析》
第3章"并发控制"3.9节"死锁管理"(源文件:
_epub-src/EPUB/xhtml/chapter8.xhtml)
- 结论依据:原文明确"Greenplum是一个分布式数据库,在每个单
节点上借用了PostgreSQL的死锁检测和管理策略,同时发展出一套
自己的全局范围死锁检测(GDD)算法。Greenplum的GDD算法需要在
每个工作实例上收集本地WFG,还要构建全局WFG……GDD算法的实现
主要分为以下几步:遍历全局WFG,如果顶点的全局出度为0,删除
顶点和相关的边;遍历全局WFG,如果顶点的全局入度为0,删除
顶点和相关的边……循环执行这3个步骤,直到没有可以删除的顶点
时停止。如果有遗留的边,则表示发生了死锁",直接给出GDD算法
的完整迭代逻辑。
- 原始内容:GDD算法的实现主要分为以下几步:遍历全局WFG,如果
顶点的全局出度为0,删除顶点和相关的边……循环执行这3个步骤,
直到没有可以删除的顶点时停止。如果有遗留的边,则表示发生了
死锁,措施就是破除闭环。