当前位置：首页 > news >正文

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

news 来源：原创 2024/9/30 5:35:30

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

一、等待与图

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，被调整的虚边数不能超过该值。