InnoDB 锁系统及死锁检测实现分析

死锁检测一般采用Wait-For-Graph算法，这个不是非常复杂或者新奇的内容，cs课程中一般都会交代，本文从代码层面解析InnoDB锁系统及死锁检测实现，一方面给自己阅读代码做做笔记，另一方面希望也能够为一些有疑惑的朋友提供帮助

几个问题

1. InnoDB中锁在是怎样表示和维护的
2. 死锁检测发生在什么时候
3. InnoDB中的Wait-For-Graph是如何实现的
4. InnoDB通常在哪些情况下可能发生死锁

InnoDB中的锁实现

InnoDB支持行锁，所有事务加的行锁通过一个全局的hash表lock_sys维护：

/* The lock system */
UNIV_INTERN lock_sys_t*	lock_sys	= NULL;
typedef struct lock_sys_struct	lock_sys_t;
 
/** The lock system struct */
struct lock_sys_struct{
	hash_table_t*	rec_hash;	/*!< hash table of the record locks */
	ulint		rec_num;
};

在进一步介绍行锁实现之前，先介绍一下InnoDB中事务与锁相关的数据结构

struct trx_struct{
        ...
	lock_t*		wait_lock;	/*!< if trx execution state is
					TRX_QUE_LOCK_WAIT, this points to
					the lock request, otherwise this is
					NULL */
	UT_LIST_BASE_NODE_T(lock_t)
			trx_locks;	/*!< locks reserved by the transaction */
        ...
}

每个事务都会维护执行过程中加的所有锁（trx_locks，双向链表），以及发生锁等待时等待的锁（wait_lock）
lock_sys中保存的对象为lock_t，它可以描述一个行锁或者表锁，如果是行锁，会被lock_sys维护，若是表锁，会被对应的dict_table_t维护

typedef struct lock_struct	lock_t;
/** Lock struct */
struct lock_struct {
	trx_t*		trx;		/*!< transaction owning the
					lock */
	UT_LIST_NODE_T(lock_t)
			trx_locks;	/*!< list of the locks of the
					transaction */
	ulint		type_mode;	/*!< lock type, mode, LOCK_GAP or
					LOCK_REC_NOT_GAP,
					LOCK_INSERT_INTENTION,
					wait flag, ORed */
	hash_node_t	hash;		/*!< hash chain node for a record
					lock */
	dict_index_t*	index;		/*!< index for a record lock */
	union {
		lock_table_t	tab_lock;/*!< table lock */
		lock_rec_t	rec_lock;/*!< record lock */
	} un_member;			/*!< lock details */
};

不论行锁还是表锁，都记录了所属的事务，锁创建后会通过trx_locks（next和prev指针）添加到所属事务已获得锁链表中（trx_struct.trx_locks），如果创建的锁为行锁，会使用（space_no, page_no）经过hash函数计算后添加到lock_sys中（lock_rec_create），InnoDB hash算法解决冲突的方式是拉链法，因此有一个hash_node_t hash（next指针）指向同一个桶中的下一个元素，同一个桶中添加元素是加在拉链尾部（位于同一个桶中相同row，先加入的锁不需要等待后加入的锁）；如果创建的锁为表锁，将其加入到对应dict_table_t的表锁链表尾部（lock_table_create）

行锁与表锁

InnoDB中一个事务中的行锁是按照page和锁类型组织，相同的锁类型，锁一行和锁这行所在page中所有行的存储代价是一样的，lock_rec_struct中的成员nbits后面有一个bitmap，bitmap占用的存储空间为：(1 + (nbits-1)/8)bytes，即：lock_rec_struct占用的实际存储空间为：sizeof(lock_rec_struct) + 1 + (nbits-1)/8，bitmap中的每一位标识对应的行是否加锁

/** Record lock for a page */
typedef struct lock_rec_struct		lock_rec_t;
/** Record lock for a page */
struct lock_rec_struct {
	ulint	space;			/*!< space id */
	ulint	page_no;		/*!< page number */
	ulint	n_bits;			/*!< number of bits in the lock
					bitmap; NOTE: the lock bitmap is
					placed immediately after the
					lock struct */
};

lock_table_t表锁，保存了对应的table和table上表锁链接locks（prev和next指针）

/** A table lock */
typedef struct lock_table_struct	lock_table_t;
/** A table lock */
struct lock_table_struct {
	dict_table_t*	table;		/*!< database table in dictionary
					cache */
	UT_LIST_NODE_T(lock_t)
			locks;		/*!< list of locks on the same
					table */
};

说明：lock_t表示一个锁，表锁或者行锁，其中的trx_locks成员会被链接到trx_struct中的已加锁链表trx_struct.trx_locks中，而lock_table_t中的locks成员是需要链接到对应table后面，作用不同但容易混淆；在本人看来，lock_t中的hash和index成员放到lock_rec_t结构体中更加合适，可能是基于lock_t是行锁的可能性更大的前提考虑的

背景知识介绍的差不多了，问题1回答完毕，进入第二个问题

死锁检测发生在什么时候

死锁检测发生在加锁请求无法立即满足需要进入所等待时，lock_deadlock_occurs被两个函数锁调用：
lock_rec_enqueue_waiting
lock_table_enqueue_waiting

Wait-For-Graph在InnoDB中的实现

InnoDB在实现Wait-For-Graph时基于性能方面的考虑，定义了两个变量：

LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK(默认200)：深度优先遍历的层数超过此值，即认为发生死锁，回滚当前事务
LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK(默认1000000)：lock_deadlock_recursive递归调用的次数超过此值，即认为发生死锁，回滚当前事务

lock_deadlock_recursive函数定义

static ulint lock_deadlock_recursive(
/*====================*/
	trx_t*	start,		/*!< in: recursion starting point */
	trx_t*	trx,		/*!< in: a transaction waiting for a lock */
	lock_t*	wait_lock,	/*!< in: lock that is waiting to be granted */
	ulint*	cost,		/*!< in/out: number of calculation steps thus
				far: if this exceeds LOCK_MAX_N_STEPS_...
				we return LOCK_EXCEED_MAX_DEPTH */
	ulint	depth)		/*!< in: recursion depth: if this exceeds
				LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK, we
				return LOCK_EXCEED_MAX_DEPTH */

lock_deadlock_recursive是一个递归函数，start是Wait-For-Graph的起点，trx是当前遍历节点，wait_lock是trx需要等待的锁，*cost在每次进入lock_deadlock_recursive会增加1，depth在递归调用lock_deadlock_recursive进入Wait-For-Graph下一个节点时增加1

lock_deadlock_recursive执行逻辑

    // trx-sys中所有事务trx->deadlock_mark在lock_deadlock_occurs中被置为0
    if (trx->deadlock_mark == 1) {
        /* We have already exhaustively searched the subtree starting from this trx */
        return(0);
    }
 
    // cost 增加1
    *cost = *cost + 1;
 
    // 等待的锁为行锁，找到lock_sys中相同行上的第一个锁
    if (lock_get_type_low(wait_lock) == LOCK_REC) {
 
        space = wait_lock->un_member.rec_lock.space;
        page_no = wait_lock->un_member.rec_lock.page_no;
        lock = lock_rec_get_first_on_page_addr(space, page_no);
 
        /* Position the iterator on the first matching record lock. */
        while (lock != NULL
               && lock != wait_lock
               && !lock_rec_get_nth_bit(lock, heap_no)) {
 
            lock = lock_rec_get_next_on_page(lock);
        }
        // 找到自身，不需要继续找lock_sys中相同行上的下一个锁
        if (lock == wait_lock) {
            lock = NULL;
        }
    } else {  // 等待的锁为表锁
        lock = wait_lock;
    }
 
    /* Look at the locks ahead of wait_lock in the lock queue */
    for (;;) {
        // lock为表锁，定位到table对应表锁链表中lock前一个表锁
        /* Get previous table lock. */
        if (heap_no == ULINT_UNDEFINED) {
            lock = UT_LIST_GET_PREV(un_member.tab_lock.locks, lock);
        }
        // 没有找到前一个表锁，即lock为最后一个表锁请求，不会造成死锁，返回FALSE
	// 或者，lock_sys中找到相同行上第一个锁lock == wait_lock，不会造成死锁，返回FALSE
	// 死锁检测时，不需要关心是否与之后加的锁有冲突，Wait-For-Graph节点之间是单向关系
        if (lock == NULL) {
            /* We can mark this subtree as searched */
            trx->deadlock_mark = 1;
            return(FALSE);
        }
        // Wait-For-Graph中找到了一条边，需要检查是否死锁
        if (lock_has_to_wait(wait_lock, lock)) {
            // 判断是否调用层次太深，或者调用次数过多
            ibool    too_far
                = depth > LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK
                || *cost > LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK;
 
            lock_trx = lock->trx;
            // Wait-For-Graph中找到了回路，出现死锁！
            if (lock_trx == start) {
                // 判断事务权重，若start权重较小，返回LOCK_VICTIM_IS_START，start将被回滚
                if (trx_weight_ge(wait_lock->trx, start)) {
                        return(LOCK_VICTIM_IS_START);
                }
                // wait_lock->trx权重较小，需要回滚，返回LOCK_VICTIM_IS_OTHER
                lock_deadlock_found = TRUE;
                wait_lock->trx->was_chosen_as_deadlock_victim = TRUE;
                lock_cancel_waiting_and_release(wait_lock);
 
                return(LOCK_VICTIM_IS_OTHER);
            }
            // 调用层次太深，或者调用次数过多，返回LOCK_EXCEED_MAX_DEPTH
            if (too_far) {
                return(LOCK_EXCEED_MAX_DEPTH);
            }
            // 目前还没有出现死锁，继续在Wait-For-Graph寻找可能的边
            if (lock_trx->que_state == TRX_QUE_LOCK_WAIT) {
 
                ret = lock_deadlock_recursive(start, lock_trx, lock_trx->wait_lock, cost, depth + 1);
		// 只有当检测出死锁或者发现调用层次(次数)过深(过多)才返回，否则为Wait-For-Graph选择下一个节点
                if (ret != 0) {
                    return(ret);
                }
            }
        }
	// wait_lock与lock没有冲突，继续找lock_sys中相同行上的下一个锁
        /* Get the next record lock to check. */
        if (heap_no != ULINT_UNDEFINED) {
            do {
                lock = lock_rec_get_next_on_page(lock);
            } while (lock != NULL && lock != wait_lock && !lock_rec_get_nth_bit(lock, heap_no));
            // 找到自身，不需要继续找lock_sys中相同行上的下一个锁
            if (lock == wait_lock) {
                lock = NULL;
            }
        }
    }/* end of the 'for (;;)'-loop */

lock_deadlock_recursive返回值的处理

1. LOCK_VICTIM_IS_OTHER，发生死锁，需要回滚其它事务，但可能多个事务与当前事务发生死锁，因此需要再次调用lock_deadlock_recursive
2. LOCK_EXCEED_MAX_DEPTH，调用层次(次数)过深(过多)，回滚当前事务
3. LOCK_VICTIM_IS_START，发生死锁，需要回滚当前事务

InnoDB通常在哪些情况下可能发生死锁

回顾一下cs课本上关于发生死锁的几个条件：
1. 资源互斥；2. 请求保持；3. 不剥夺；4. 循环等待

对于DB而言，导致死锁意味着发生了循环等待，在InnoDB中由于行锁的引入，比较容易发生死锁，下面总结一些发生死锁的情况（不全）：
1. 同一索引上，两个session相反的顺序加锁多行记录
2. Primary key和Secondary index，通过primary key找到记录，更新Secondary index字段与通过Secondary index更新记录
3. UPDATE/DELETE通过不同的二级索引更新多条记录，可能造成在Primary key上不同的加锁顺序，可以参考之前一篇博客
4. 欢迎补充…

《InnoDB 锁系统及死锁检测实现分析》上有2条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注