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

By | 2013 年 9 月 12 日

死锁检测一般采用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. 欢迎补充…

2 thoughts on “InnoDB 锁系统及死锁检测实现分析

发表评论

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