知识卡片

结构图卡

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[无死锁]
这张卡片看不懂?

已有反馈 · 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个步骤, 直到没有可以删除的顶点时停止。如果有遗留的边,则表示发生了 死锁,措施就是破除闭环。