GaussDB(DWS) 内核死锁检测的实现

GaussDB(DWS)允许事务以任意顺序来申请锁,所以就有可能出现死锁。我们采用了标准的死锁检测算法，同时考虑到实现的锁模型也有额外的权衡，其基本思想是：

• 乐观等待：如果事务线程不能马上获得请求锁，则马上进入睡眠，同时设置了定时器。
• 延迟检测：如果在事务线程拿到表锁之前定时器到点，那么执行死锁检测。

如果确实发生了死锁，那么回滚事务、释放锁资源，解决这个死锁问题。否则，事务线程会重新进入睡眠并等待直至可以拿到表锁。 通过这种方法，避免过早地执行死锁检测处理开销。

锁请求遵循以下原则:

1. 如果请求锁矩阵无冲突，或者事务线程已持有较大类型的锁的请求，那么锁请求立即成功。
2. 否则事务线程会加入到锁等待队列。一般情况下,锁请求会加入到队尾。特殊情况如下：如果事务线程已在对象上持有锁，但与其他等候者的锁请求存在冲突，事务线程就会插入到队列中第一个等候者的前面。相对于在死锁检测时方才做调整的代价来讲， 检查执行的成本 要低一些。

锁释放时,ProcLockWakeup会扫描锁对象的等待队列，唤醒满足如下两个条件的等候者。

(a) 等候者的锁请求与现存锁不存在冲突。

(b) 等候者的锁请求与它前面未唤醒的等候者都不存在冲突。 规则(b)保证了存在冲突的锁请求必须按照先来先得的顺序满足。这里，ProcLockWakeup并不会调整锁等候者的次序。

GaussDB(DWS)内核采用了有向无环图的方法来执行死锁检测。在此图中，事务线程为图中的节点，锁的请求和进程的等待则是图中的边。如果A事务线程等待B,那么会有存在一条从A指向B的边。当且仅当图中出现循环时,则判定为存在死锁问题。从等待的边进行检索，检测是否会回到出发点来判断是否出现循环，有3种可能结果:

1. 所有出发的路径都终止于一个正在运行的事务线程(该事务线程没有等待的边)。
2. 最后回到开始点，说明检测到了死锁。处于起点的事务线程将回滚，释放所有的持有的锁资源。
3. 某些路径回到某些节点而不是开始点. 这意味着死锁发生了,但执行检测的事务线程并不是开始点。

我们秉承“由相关事务线程来解决死锁”这一原则来解决死锁问题，所以，第1种和第3种情况的执行结果为无死锁，只有等2种情况会判定为死锁并解决死锁问题。

有几个情况我们还要考虑一下:

1. 事务线程可等待的其他事务线程数目可能大于1。
2. 在等待队列中，如果事务线程A在事务线程B之后，并且它们的请求锁还存在冲突，我们定义A在等待B。 因为ProcLockWakeup在B之前不会唤醒A，这会在图中产生额外的依赖关系，我们称之为软依赖的边；相对的，因为锁持有而形成的依赖关系为硬依赖的边。

对于软依赖的边，重新排列等待队列的顺序，而不是通过回滚事务来解决死锁问题。重排会调整相关事务线程的优先顺序；如果能够重排而解决循环现象，就没有必要执行更大代价的回滚事务。软死锁问题的检测和解决是一块硬骨头，主要由FindLockCycle实现。在返回有死锁现象时,它还构建了一个包含涉及所有软依赖边的链表。

• 如果结果链表为空,那么只存在硬死锁,重排不会成功。
• 如果链表不是空的，则递归地对链表中的边进行重新排序，再检查看是否可以消除循环问题。

由此可见，开始执行死锁检测的事务线程是随机的，那么在等同执行时间的前提下，因死锁问题而导致的回滚事务也是随机的了。考虑到长事务或重事务回滚后再次执行的代价过大，我们对vacuum full等重事务的超时进行了必要的延长，以便消减其因死锁而导致回滚的概率。

轻量级死锁的检测主要是借鉴了表锁的死锁检测原理，但是也存在一些差异。

第一个主要的区别在于不存在软死锁的问题。由于轻量级锁只有共享读和排它写这两种模式，所以并不存在复杂的兼容/冲突矩阵。也正是基于这一点，基本不存在一个事务线程等待多个其他事务线程的问题，即1个事务线程只会等待另1个事务线程。 基于这个事实，内核不需要考虑软死锁的问题。

第二个主要的区别在于执行死锁检测的线程不再是事务线程，而是单独的监控线程。轻量级锁属于内核内部资源，而表锁则是可对外可查询、可设置的锁资源。轻量级锁如果发生死锁，主要的原因是开发者使用不当造成的，而不是业务执行引起的。所以，轻量级死锁问题的发生并不常见，不需要放在事务线程中执行。 由一个单独的监控线程，周期性地监测即可。监测的周期时长以分钟为单位。

考虑到性能，轻量级锁的检测分为两个阶段执行。

在第一个阶段，监控线程快速地比较了线程的计算状态和轻量级锁的请求对象是否相同。这一个阶段不加任何锁，并且都是简单的整数比较，性能非常高，并且99%的情况在第一阶段执行中上。

如果第一阶段判定很大概率上存在死锁的问题，那么进入第二阶段，与表锁的死锁检测算法一样，直接检测是否有环境出现。 如果有， 则存在死锁问题；否则的话，可能是一个长时间的执行事务阻塞了锁的请求。

死锁问题的解决是通过选择一个事务线程、发送信号令其强行退出来解决的。 事务线程受害者的选择考虑了事务的执行时长、执行线程的重要程度等多个因素，尽量选择回滚和执行代价小的事务线程。

无论是表锁，还是轻量级锁，都使用了有向无环图的遍历算法来检测死锁问题。在标准检测算法的基础上，GaussDB(DWS)内核考虑了锁模式的不同和应用场景的出现概率，采用了不用的优化方式，定向地选择事务线程来解决死锁问题，以减少事务回滚和再执行的代价。

 参考文章：

http://blog.itpub.net/6906/viewspace-2656469/   The Deadlock Detection Algorithm