OB的LCL算法学习笔记_Dennis_GAO

http://blog.sina.com.cn/u/1182000643

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

OB的LCL算法学习笔记

(2023-04-30 01:09:20)

标签：

oceanbase

分类：工作学习

OB的LCL算法是边追逐算法：依据事务依赖关系向下游节点发送消息，死锁产生的环将通过这些消息被推断出来。

参考https://zhuanlan.zhihu.com/p/624847601 算法过程理解如下：

事务的全局等待关系是一个有向图，每个节点是一个处于等待状态的事务，每个边是一个等待关系。SCC是强连通分量，即一个死锁环。

对于每个事务节点存储如下信息：

1. 对于每个事务启动的时候会分配一个PrID和PrAP，为顶点私有的长亮编号和优先级。这个分配过程是递增的，一个事务分配后PrID和PrAP是固定的。

2. 每个事务节点存储PuID和PrAP，用于存储它目前发现的可能是阻塞它的最晚启动的事务的PrID和PrAP。PuID和PrAP是变量，随着算法的推演会被改变。

3. 每个事务节点存储一个LCLV，用于存储它目前可能阻塞的最大锁等待链长度。

算法的执行过程分为3个阶段：繁殖阶段、扩散阶段和检测阶段：

1. 繁殖阶段

繁殖阶段在A(≠B)→B上的推演定义为：A.(PuAP, PuID)=A.(PrAP, PrID)， B.(PuAP, PuID)=B.(PrAP, PrID)，B.LCLV=max(B.LCLV, A.LCLV+1)。

我理解的解释为：

可以并发从有向图的多个不同节点出发，在算法设定的时间上限或轮次里，确保至少有向图的每个边都推演过至少1次，而次数与顺序没有要求。

A节点等待B节点，那么B节点的LCLV会调整为max(B.LCLV, A.LCLV+1)。

预期通过繁殖阶段，至少一个SCC上的部分节点将有最大的LCLV。

2. 扩散阶段

扩散阶段在A(≠B)→B上的推演定义为：B.LCLV=max(B.LCLV,A.LCLV)，如果 B.LCLV==A.LCLV，那么 B.(PuAP, PuID)=max(B.(PuAP, PuID), A.(PuAP, PuID))。

我理解的解释为：

可以并发从有向图的多个不同节点出发，在算法设定的时间上限或轮次里，确保至少有向图的每个边都推演过至少1次，而次数与顺序没有要求。

A节点等待B节点，那么B节点的LCLV会调整为max(B.LCLV, A.LCLV)，同时如果调整后B的LCLV与A的LCLV相同，说明原本A的LCLV>=B的LCLV，这种情况下将B的(PuAP, PuID)调整为max(B.(PuAP, PuID), A.(PuAP, PuID))。

注意这个过程中LCLV不会再增加了，而(PuAP, PuID)将会调整为SCC节点中PrAP和PrID最大的节点，即死锁环上最晚的启动的事务节点。

3. 检测阶段

检测阶段在 A(≠B)→B 上的推演：如果 B.LCLV==A.LCLV 且 B.(PuAP, PuID)==A.(PuAP, PuID) 且 B.(PuAP, PuID)==B.(PrAP, PrID)，则 B 将检测检测到死锁并主动释放资源。繁殖阶段的时间复杂度为 O(N)，其中 N 是 WFG 中有向边的数量。图5 展示了系统中检测到死锁的情况。

我理解的解释为：

经过扩散阶段后，如果A节点等待B节点，而B.LCLV==A.LCLV，那么他们肯定在一个SCC死锁环上；如果B.(PuAP, PuID)==B.(PuAP, PuID)，说明这个B节点是这个死锁环上最晚启动的事务节点，优先被杀死。

其他思考和疑问：

1. 一个算法3阶段周期只会破除一个SCC死锁环，因为如果有其他的SCC环，那么他们的(PuAP, PuID)已经是全局最晚的节点了，需要在下一轮3阶段算法中破除了。

2. 实际运行中的一个数据系统的锁等待图应该是一个动态的有向图，每个节点只是向下游其他节点发送信息，那由谁来进行算法阶段的切换与轮次周期的切换？

转载请注明转自高孝鑫的博客！

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：金融核心常见并行验证切换策略

后一篇：保险养老金业务粗析

新浪BLOG意见反馈留言板　欢迎批评指正