postgresql源码学习（十五）—— 行锁③-死锁检测

本篇主要学习下死锁检测的原理，不研究具体算法和代码，有兴趣请参考原书。

一、 等待与图

1. 等待与有向图

       事务T1在等待事务T2，可以用一个有向图表示。如果每个等待是一条“边”，那么死锁检测其实就是一个找“环”的过程。

2. 实边与虚边

• 实边（Hard Edge）：等待队列中的事务等待持锁事务。假设事务A持有表的共享锁或排它锁，当事务B申请表的排他锁时，就要进入等待。pg称这种等待的边为“实边”。
• 虚边（Soft Edge）：均发生在等待队列中的事务。假设事务A持有表的共享锁，事务B申请表的排他锁被阻塞，事务C又想申请该表共享锁。此时事务C需要等待事务B，于是BC都在等待队列中，pg称这种等待的边为“虚边”。

3. 死锁

       假设等待图中有环，且环全部由实边构成，那么此时只能中断某个事务来打破这个环，这就是死锁。若环还有虚边，说明有事务尚未真正持有锁，此时还可以通过调整事务顺序来避免死锁。

二、 死锁检测定时器

每个会话启动时都会注册一个死锁检测定时器，用于提示进行死锁检测。

以下在postinit.c文件InitPostgres函数

    /*
     * Also set up timeout handlers needed for backend operation.  We need these in every case except bootstrap.
     */
    if (!bootstrap)
    {
        RegisterTimeout(DEADLOCK_TIMEOUT, CheckDeadLockAlert);
        RegisterTimeout(STATEMENT_TIMEOUT, StatementTimeoutHandler);
        RegisterTimeout(LOCK_TIMEOUT, LockTimeoutHandler);
        RegisterTimeout(IDLE_IN_TRANSACTION_SESSION_TIMEOUT,
                        IdleInTransactionSessionTimeoutHandler);
        RegisterTimeout(IDLE_SESSION_TIMEOUT, IdleSessionTimeoutHandler);
        RegisterTimeout(CLIENT_CONNECTION_CHECK_TIMEOUT, ClientCheckTimeoutHandler);
    }

其中CheckDeadLockAlert作为定时任务，会定时设定一个死锁检测标志got_deadlock_timeout。

当事务处于等待状态时，ProcSleep函数（proc.c文件）会根据此标志决定是否进行死锁检测。

/* check for deadlocks first, as that's probably log-worthy */
            if (got_deadlock_timeout)
            {
                CheckDeadLock();
                got_deadlock_timeout = false;
            }

CheckDeadLock是死锁检测入口函数。

检测过程是互斥的，也就是说在检测开始时，主锁表就需要被保护起来，避免被修改（因为要检查锁持有和等待队列）。如果事务只通过本地锁表或fast path就持有锁，则它不在死锁检测范围内。

三、 主要结构体

等待图由PGPROC（会话或进程）和EDGE（边）两个结构体构成。

deadlock.c文件

typedef struct
{
    PGPROC     *waiter;         /* 等待者 */
    PGPROC     *blocker;        /* 阻塞者 */
    LOCK       *lock;           /* 等待的锁 */
    int         pred;           /* 拓扑排序使用的额外变量 */
    int         link;           /*拓扑排序使用的额外变量 */
} EDGE;

       如果环中包含虚边，可以尝试通过调整等待队列来消除环。新的等待队列保存在waitOrders数组中，每个数组元素但是一个等待队列，由WAIT_ORDER结构体保存该队列。

/* One potential reordering of a lock's wait queue */
typedef struct
{
    LOCK       *lock;           /* 调整的是哪个锁上的等待队列 */
    PGPROC    **procs;          /* 在该锁上新的等待队列 */
    int         nProcs;          /* procs数组长度 */
} WAIT_ORDER;

       在环的查找过程中，可以被调整的虚边记录在possibleConstraints数组中。每次向前推进都会从possibleConstraints找到一个虚边进行探索，被探索的边保存在curConstraints数组中。

       这两个数组长度要足够大，例如curConstraints数组长度是MaxBackends，被调整的虚边数不能超过该值。

四、 主要函数及作用

1. CheckDeadLock函数

死锁检测入口函数

2. DeadLockCheckRecurse函数

不断被递归调用，检测死锁

• 如果遇到实边构成的环，则停止探测并报出死锁错误
• 如果遇到虚边构成的环，则尝试在curConstraints数组中推进探测的Configuration

3. TestConfiguration函数

• 根据当前Configuration（即curConstraints）产生新的等待队列
• 使用新等待队列检测是否存在环。
•        如果遇到实边构成的环，则停止探测并报出死锁错误
•        如果遇到虚边构成的环，则将当前虚边保存到possibleConstraints数组中

4. FindLockCycle系列函数

       FindLockCycle函数实现找环操作。具体而言，它不停调用FindLockCycleRecurse函数分别查找实边和虚边构成的环。

       FindLockCycleRecurse函数会再调用FindLockCycleRecurseMember函数，该函数还是两个功能：

• 如果遇到实边构成的环，则停止探测并报出死锁错误
• 如果遇到虚边构成的环，则将当前虚边保存到possibleConstraints数组中

       在查找环的过程中，它会优先从waitOrders数组中选择等待队列，如果没有，才会使用锁本身的等待队列。

参考

《PostgreSQL技术内幕：事务处理深度探索》第2章