InnoDB索引部分代码阅读

​ 本次阅读的目的是要看下索引分裂的过程和MTR的关系。入口是innodb创建系统表空间的代码，位于innobase_start_or_create_for_mysql()。

1
2
3
4
5
if (create_new_db) {
	mtr_start(&mtr);
	bool ret = fsp_header_init(0, sum_of_new_sizes, &mtr);	//创建系统表空间！
	mtr_commit(&mtr);
}

​ 由上面的代码可以看到，整个系统表空间的header初始化过程都使用的一个MTR来贯穿，以保证原子性。

InnoDB中的行数据类型

数据类型描述：dtype_t

InnoDB中的数据类型是指InnoDB所支持的SQL数据类型在内部代码的实现。这部分的内容主要在data0type.*文件中。在InnoDB中所有的数据类型都以dtype_t表示，该结构体的声明如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct dtype_t{
	unsigned	prtype:32;	/*!< precise type; MySQL data
					type, charset code, flags to
					indicate nullability,
					signedness, whether this is a
					binary string, whether this is
					a true VARCHAR where MySQL
					uses 2 bytes to store the length */
	unsigned	mtype:8;	/*!< main data type */

	/* the remaining fields do not affect alphabetical ordering: */

	unsigned	len:16;		/*!< length; for MySQL data this
					is field->pack_length(),
					except that for a >= 5.0.3
					type true VARCHAR this is the
					maximum byte length of the
					string data (in addition to
					the string, MySQL uses 1 or 2
					bytes to store the string length) */
	unsigned	mbminmaxlen:5;	/*!< minimum and maximum length of a
					character, in bytes;
					DATA_MBMINMAXLEN(mbminlen,mbmaxlen);
					mbminlen=DATA_MBMINLEN(mbminmaxlen);
					mbmaxlen=DATA_MBMINLEN(mbminmaxlen) */
};

由上面的定义可以看到，在InnoDB的内部实现中，数据类型分为主类型（mtype）和精确类型（prtype）。主类型说明了一个数据类型的大类，例如该类型是数据类型还是字符串类型等，而精确类型则说明了例如是否为空，字符串的字符集等信息。在data0type.h中有对prtype各个字节含义的说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MySQL用户创建的表具有以下约定：

- 在精确类型的最低有效字节中，我们存储MySQL的数据类型码（不适用于系统列）。

- 在第二个最低有效字节中，我们标记DATA_NOT_NULL，DATA_UNSIGNED，DATA_BINARY_TYPE。

- 在精确类型的字符串类型的第三个最低有效字节中，我们存储MySQL‘charset-collation（字符集排序）’代码。在使用<4.0.14创建的DATA_BLOB列中，我们实际上并不知道它是BLOB还是TEXT列。由于<4.0.14中的BLOB或TEXT列的前缀没有索引，因此这没有问题。

请注意，版本<4.1.2或<5.0.1未将charset代码存储到精确类型，因为charset始终是MySQL安装的默认字符集。如果InnoDB的系统表SYS_COLUMNS中存储的字符集代码为0，则表示应使用此MySQL安装的默认字符集。

当将表定义从系统表加载到主存储器中的InnoDB数据字典高速缓存时，InnoDB版本> = 4.1.2和> = 5.0.1检查存储的字符集整理是否为0，如果是这种情况，则type是非二进制字符串，用此MySQL安装的默认charset-collation代码替换0。简而言之，在旧表中，磁盘上系统表中的charset-collation代码可以为0，但在内存数据结构（dtype_t）中，对于非二进制字符串类型，charset-collation代码始终为！= 0。

在新表中，在二进制字符串类型中，charset-collation代码是'binary charset'的MySQL代码，即！= 0。

对于二进制字符串类型和DATA_CHAR，DATA_VARCHAR以及那些二进制或具有charset-collation latin1_swedish_ci的DATA_BLOB，InnoDB在内部执行所有比较，而不依赖于MySQL比较函数。这是为了节省CPU时间。

InnoDB自己的内部系统表的列有不同的精确类型，对于它们，通常根本不使用精确类型。
列类型描述：dict_col_t

dict_col_t是对表中一列的元数据类型进行描述，包括：列的数据类型（dtype_t来定义），该列在表中的位置（第多少列，index），是否是参与索引排序的列，最大的索引前缀长度。dict_col_t的定义如下，可以清楚的看到每个成员的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/** Data structure for a column in a table */
struct dict_col_t{
	/*----------------------*/
	/** The following are copied from dtype_t,
	so that all bit-fields can be packed tightly. */
	/* @{ */
			...该部分和dtype_t的内容相同，该列的数据类型信息...
	/*----------------------*/
	/* End of definitions copied from dtype_t */
	/* @} */

	unsigned	ind:10;		/*!< table column position
					(starting from 0) */
	unsigned	ord_part:1;	/*!< nonzero if this column
					appears in the ordering fields
					of an index */
	unsigned	max_prefix:12;	/*!< maximum index prefix length on
					this column. Our current max limit is
					3072 for Barracuda table */
};
索引字段类型描述：dict_field_t

dict_field_t用来描述索引的一个字段信息，这里要说明的是，表的信息是由列(dict_col_t)信息组成的，而索引信息是通过字段(dict_field_t)信息组成的。dict_field_t的定义如下，可以看到每个字段都关联到一个数据列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** Data structure for a field in an index */
struct dict_field_t{
	dict_col_t*	col;		/*!< pointer to the table column */
	id_name_t	name;		/*!< name of the column */
	unsigned	prefix_len:12;	/*!< 参与索引排序的前缀长度
					0 or the length of the column
					prefix in bytes in a MySQL index of
					type, e.g., INDEX (textcol(25));
					must be smaller than
					DICT_MAX_FIELD_LEN_BY_FORMAT;
					NOTE that in the UTF-8 charset, MySQL
					sets this to (mbmaxlen * the prefix len)
					in UTF-8 chars */
	unsigned	fixed_len:10;	/*!< 固定字段的长度
					0 or the fixed length of the
					column if smaller than
					DICT_ANTELOPE_MAX_INDEX_COL_LEN */
};

B+树的查找

数据结构

page_cur_t

索引页游标结构

1
2
3
4
5
6
7
/** Index page cursor */
struct page_cur_t{
	const dict_index_t*	index;
	rec_t*		rec;	/*!< pointer to a record on page */
	ulint*		offsets;
	buf_block_t*	block;	/*!< pointer to the block containing rec */
};

####关键函数

row_ins_clust_index_entry

该函数用于聚簇索引的插入操作，会首先进行乐观插入，接着进行悲观插入。函数在[row 3280 @ row0ins.cc]。

函数的大致流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
row_ins_clust_index_entry(){

    //第一步：进行外键约束检查
    if (!index->table->foreign_set.empty()) {
		err = row_ins_check_foreign_constraints(
			index->table, index, entry, thr);
	}

	/* Try first optimistic descent to the B-tree */
	//尝试进行乐观更新，加BTR_MODIFY_LEAF锁
	if (!dict_table_is_intrinsic(index->table)) {
		log_free_check();
		flags = dict_table_is_temporary(index->table)
			? BTR_NO_LOCKING_FLAG
			: 0;
		... ...
		err = row_ins_clust_index_entry_low(
			flags, BTR_MODIFY_LEAF, index, n_uniq, entry,
			n_ext, thr, dup_chk_only);
	}

	/* 如果乐观更新没有成功，则开始进行悲观更新！加BTR_MODIFY_TREE锁*/
	/* Try then pessimistic descent to the B-tree */
	if (!dict_table_is_intrinsic(index->table)) {
		log_free_check();
		... ...
		err = row_ins_clust_index_entry_low(
			flags, BTR_MODIFY_TREE, index, n_uniq, entry,
			n_ext, thr, dup_chk_only);
	}

	DBUG_RETURN(err);
}
btr_attach_half_pages()

该函数是在索引页分裂时，向中间节点页上加一个node ptr记录，用来记录新加入的数据页。该函数导致递归分裂。递归过程如下所示：

1
2
3
4
5
row_ins_index_entry_low 
	-> btr_cur_pessimistic_insert  <------------------|
		-> btr_page_split_and_insert				|
			-> btr_attach_half_pages				|
				-> btr_insert_on_non_leaf_level ------
btr_page_split_and_insert()

该函数是进行B+树分裂的主体函数。

btr_cur_search_to_nth_level()

该函数是用来检索B+树，并在指定位置放置一个cursor。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
## 如果是要进行B树结构的调整，则是以下流程
1. 根据请求的latch mode设置branch节点的锁类型：
	如果是BTR_MODIFY_TREE，则对branch页加x-latch；
	如果是BTR_SEARCH_TREE或BTR_MODIFY_LEAF，则对branch页加s-latch；
	如果是只读模式（srv_read_only_mode=true）,则对branch页不加latch；
	
2. 根据请求的latch mode设置对index的加锁类型：
	如果是BTR_MODIFY_TREE，则对index加x-lock；
	如果是BTR_SEARCH_TREE或BTR_MODIFY_LEAF，则对index加s-lock；

3. 根据请求的latch mode设置对root页的加锁类型：
	BTR_SEARCH_* => S-LATCH
	BTR_MODIFY_* => X-LATCH

4. 设置对branch页的检索方式：采用PAGE_CUR_LE匹配方式

5.
MySQL5.0.15中对B+树的检索方式
WL#6326:InnoDB:fix index->lock contention

在InnoDB中，对于中间节点页latch的获取是受到index->lock保护的。

在WL#6326之前，index->lock以S和X两种模式来保护中间节点的latch，在这种情况下，检索B+树不会获取任何中间节点的lock。

在WL#6326之后，中间节点的受到block->lock的保护（s-latch或x-latch）。为了防止死锁，在获取中间节点的latch之前要先获得index->lock的latch。

（0）定义：B树的层数

（0.1）B树的叶子节点处于第0层；

（0.2）第L层节点的父亲节点在L+1层；

（0.3）index->lock处于（树高+1）层，也就是说，index->lock是root页的父亲。

在WL#6326中，index->lock有三种模式：

（1）当持有index->lock的S-latch的情况：

（1.1）页面latch必须以层数降序的方式来获取；（level n->level n-1->level … ->level 1）

（1.2）当要获取给定层上的一个节点页时，必须持有其父亲页的latch；

（1.3）如果已经持有一个中间节点页的latch，那么我们只能获取右兄弟页的latch；（防止死锁）

（1.4）中间节点页的latch释放必须遵循先释放孩子节点再释放父亲节点的顺序（这里主要是防止和index->lock SX-latch的情况发生死锁）：

（1.4.1）要释放一个L层中间节点页的latch，必须保证所有小于L层的页锁已经释放，或者

（1.4.2）所有中间节点页的latch必须一次释放，释放的期间不能请求获取其他任何latch。

（1.5）从1.1和1.2可以推出，第一个获取latch一定是root页的。

（2）当持有index->lock的SX-latch的情况：

规则1.2和1.3在此模式下可以放宽，并整合到规则2.2中，规则1.4可以移除。这意味着，我们可以不获取某些层上数据页的latch，可以以一个更为宽松的规则获取latch。

（2.1）[和1.1相同]：页面的latch必须以层数降序的方式来获取；（level n->level n-1->level … ->level 1）

（2.2）当要获取L层上中间节点页的latch时，必须先持有其左兄弟节点的latch（L层），或着持有其祖先页的latch（> L层）；

（2.3）[由2.1和2.2] 第一个获取的latch可以是任何中间节点页；

（3）当持有index->lock的X-latch的情况：

在获取索引的X-latch时，我们可以以任意方式获取中间节点的页的latch；

NOTE：WL#6326不会影响对叶子节点的加锁顺序：

读需要获取index->lock的S-latch，一旦到达叶子层，我们可以释放index->lock和中间节点页的latch。一旦到达叶子节点，我们可以放心地获取右兄弟节点的latch，释放老页的latch，进行从左往右的索引扫描。

对叶子节点修改（BTR_MODIFY_LEAF）要获取index->lock的S-latch；

如果发生页面分裂或合并（BTR_MODIFY_TREE）或进行页面分配，则要获取index->lock的X-latch。

几个例子

[1]

读写锁（read-write latch）

文档目标：InnoDB内建rw_lock的实现机制|使用方式。

读写锁是innodb用来保证资源的一致性的机制。看本部分代码的原因是在MA项目中日志应用和数据页临时拷贝都会应用到读写锁机制，在从机应用索引分裂的日志时，也会使用到。所以，搞清楚这部分代码可以在MA中使用innodb内建的读写锁。

读写锁结构：rw_lock_t

innodb中读写锁的实现是rw_lock_t，该结构体中包含了一个读写锁的状态变量、条件变量等内容，下面看一下这个结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

struct rw_lock_t
{
	/** 记录该RW锁状态. */
	volatile lint	lock_word;

	/** 当有等待该锁的线程时置为1 */
	volatile ulint	waiters;

	/** 是否为递归锁，如果为TRUE，则writer_thread是记录的写线程的id，否则
	writer_thread的值无意义！*/
	volatile bool	recursive;

	/** 当前SX的锁数量. */
	volatile ulint	sx_recursive;

	/** This is TRUE if the writer field is RW_LOCK_X_WAIT; this field
	is located far from the memory update hotspot fields which are at
	the start of this struct, thus we can peek this field without
	causing much memory bus traffic */
	bool		writer_is_wait_ex;

	/** recursive = TRUE时，该值为写线程的线程id（可能该线程已经持有该锁
	也可能正在等待） */
	volatile os_thread_id_t	writer_thread;

    /** 如果是buf block的锁，则此成员值为：1 */
	unsigned	is_block_lock:1;
    
	/** 线程等待队列信号量 */
	os_event_t	event;

	/** 写请求等待的信号量，一个线程必须先递减lock_word，再等待。*/
	os_event_t	wait_ex_event;

	/** Count of os_waits. May not be accurate */
	uint32_t	count_os_wait;

	/** 系统中所有的RW锁都保存在rw_lock_list全局变量中。用于诊断。 */
	UT_LIST_NODE_T(rw_lock_t) list;

	/** 保护此rw_lock_t的锁 */
	mutable ib_mutex_t mutex;

};

可以看到，innodb中的RW锁就是基于经典的读写锁实现。在此基础上，innodb的RW锁还加入了等待队列，和可重入特性。

等待队列

首先看一下innodb中等待队列的实现介绍，下面摘自其代码注释：

在innodb中，等待队列是通过wait array数组实现的，其中wait array的每个数组元素都有一个信号量。当一个线程等待一个锁时，可以在wait array中申请一个元素空间（cell），并让自己在该元素上的信号量上等待。

当使用等待队列时，必须要保证持有该锁的线程知道有其他线程在等待这个锁，这样在释放锁时可以通知这些等待的现车结束等待。

为什么要实现一个等待队列？主要是为了使锁效率更高。

在5.0.30版本及以后，由于现代操作系统可以很高效的处理大量的信号量，不再需要在每个等待队列的cell里包含一个信号量。相反，现在在每个锁内部都加入了一个信号量，等待线程可以在此信号量上等待。现在innodb中保留全局等待队列（wait array）的原因是为了诊断和避免无限等待。error_monitor thread 可以通过扫描全局 wait array来避免等待线程错过某些信号量。

从代码上，看是有两个等待队列：一个是在rw_lock_t->event上的队列，另一个是在sync_wait_array的等待队列。但是这两个队列是共享一个条件变量的（即系统都是通过rw_lock_t->event信号量来通知的），具体做法是sync_wait_array中的每个成员会保存一个指向本成员所绑定锁的rw_lock_t->event的指针。

之所以还保留sync_wait_array的原因是error_monitor线程可以通过扫描全局的等待队列，来判断是否有等待线程错过某些信号量。

####InnoDB内建读写锁的使用

下面的所有代码都已经过测试，可以在MySQL中正确运行。

头文件包含（#include）

使用InnoDB内建的读写锁时需要包含下列头文件：

1
2
3
4
#include "sync0sync.h";
#include "sync0types.h";
#include "sync0rw.h";
#include "sync0arr.h";
创建锁

创建并初始化一个锁可以用innodb中预先定义的宏。用于创建锁的宏有：

1
2
3
4
5
6
7
/**
说明：
1）K为PSI KEY，可以设置为PSI_NOT_INSTRUMENTED，则该锁不会被performance schema跟踪。
2）L是锁变量的地址，用于创建和初始化rw_lock_t。
3）level是用来Debug的，可以设置为SYNC_NO_ORDER_CHECK，则该锁不会被检查。
*/
#define rw_lock_create(K, L, level);

例：

如何定义并初始化一个读写锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//定义计数器类型 counter
struct counter{
    rw_lock_t lock;
    __int64 count;
};

static counter count;

//初始化count
void count_init() {
	count->count = 0;
    //初始化读写锁
	rw_lock_create(PFS_NOT_INSTRUMENTED, &count->lock, SYNC_NO_ORDER_CHECK);
}

#####使用锁

读写锁的加锁和解锁都可以使用innodb定义的宏来实现，这些宏有：

1
2
3
4
5
6
7
8
9
10
11
12
13
/** 加锁的操作
1）其中参数L的类型为：rw_lock_t*
*/
#define rw_lock_s_lock(L)
#define rw_lock_sx_lock(L)	
#define rw_lock_x_lock(L)
    
/** 解锁的操作
1）其中参数L的类型为：rw_lock_t*
*/
#define rw_lock_s_unlock(L)
#define rw_lock_x_unlock(L)
#define rw_lock_sx_unlock(L)

例：

使用读写锁控制的方式来读取上面定义count中的值，有两个写（writer）线程，两个读线程（read）。读线程会对count对象加s-lock来读取其中的count成员的值；写线程会相应的加x-lock，并执行count->count++;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//第一个写线程
/**
WRITE THREAD function
*/
extern "C"
os_thread_ret_t
DECLARE_THREAD(write_thread)(
void*	arg MY_ATTRIBUTE((unused))) {
	int i = 0;
	while (i < 500000)
	{
		rw_lock_x_lock(&count->lock);
		count->count++;
		i++;
		rw_lock_x_unlock(&count->lock);
	}
	OS_THREAD_DUMMY_RETURN;
}

//第二个写线程和第一个线程的代码相同。
extern "C"
os_thread_ret_t
DECLARE_THREAD(write_thread_2)(
    void*	arg MY_ATTRIBUTE((unused))){    
    /*......*/
}

//读线程
/**
READ THREAD function
*/
extern "C"
os_thread_ret_t
DECLARE_THREAD(read_thread)(
void*	arg MY_ATTRIBUTE((unused))) {
	while (true)
	{
		rw_lock_s_lock(&count->lock);
		std::cout << count->count << std::endl;
		rw_lock_s_unlock(&count->lock);
	}
	OS_THREAD_DUMMY_RETURN;

执行这四个线程后，count->count的值会正确的加到1000000，读写锁可以正常使用。

销毁读写锁

以上面的count对象为例，不能通过直接delete count来销毁读写锁，需要调用专门的宏函数来实现。因为读写锁中包含的信号量需要单独销毁，且由于所有的读写锁都会加入到全局的rw_lock_list中，销毁时需要把读写锁从这个链表中移除。

用户销毁读写锁的宏函数为：

1
2
3
4
/*销毁一个读写锁。
1)参数M为rw_lock_t*类型。
*/
# define rw_lock_free(M)

例：

以上面的代码为例，当要销毁count对象时，需要像下面这样：

1
2
3
4
5
/** 销毁count对象*/
void count_free(){
    rw_lock_free(&count->lock);
    delete count;
}

行锁及表锁部分代码阅读

行锁

行锁就是记录锁，与rw-latch不同，行锁是逻辑层的锁，是InnoDB用来实现2PL协议的组件，下面主要看一下其基本数据结构和维护过程。

行锁结构（lock_rec_t）

表示行锁结构的类型是lock_rec_t(row76@lock0priv.h)，其详细结构定义如下：

1
2
3
4
5
6
7
8
9
/** Record lock for a page */
struct lock_rec_t {
	ib_uint32_t	space;		/*!< space id */
	ib_uint32_t	page_no;	/*!< page number */
	ib_uint32_t	n_bits;		/*!< number of bits in the lock
					bitmap; NOTE: the lock bitmap is
					placed immediately after the
					lock struct */
};

总的来说一个行锁是由表空间号（space_id）、页面号（page_no）和一个位图（bitmap）组成，位图是用来标记该行锁对应页面中的哪个记录（record），是用heap_no表示的，heap_no可以认为是一个记录在页面内的物理偏移。

事务锁（lock_t）

事务锁是一个事务执行过程中需要管理的锁，有表锁和行锁两种，这两种锁都是保存在一个lock_t结构中。一个事务所有的lock_t对象都保存在了trx->lock中。lock_t结构如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** Lock struct; protected by lock_sys->mutex */
struct lock_t {
	trx_t*		trx;		/*!< transaction owning the
					lock */
	UT_LIST_NODE_T(lock_t)
			trx_locks;	/*!< list of the locks of the
					transaction */

	dict_index_t*	index;		/*!< index for a record lock */

	lock_t*		hash;		/*!< hash chain node for a record
					lock. The link node in a singly linked
					list, used during hashing. */

	union {
		lock_table_t	tab_lock;/*!< table lock */
		lock_rec_t	rec_lock;/*!< record lock */
	} un_member;			/*!< lock details */

	ib_uint32_t	type_mode;	/*!< lock type, mode, LOCK_GAP or
					LOCK_REC_NOT_GAP,
					LOCK_INSERT_INTENTION,
					wait flag, ORed */
};

用于创建记录锁的RecLock类

RecLock[row 607@lock0priv.h]类是用来创建记录锁的工具类。同时该类还有死锁检测和锁优先级的功能。下面主要看下它创建记录锁的逻辑。

InnoDB锁实现概述

下面的文字翻译自`row265@lock0priv.h`:

[1] 一个显式的（explicit）记录锁会锁定一个记录和该记录之前的gap。一个隐式的（implicit）记录锁（x-lock）不会影响gap，而只会锁定该记录。

[2] 如果一个事务更新或插入了一个条索引记录，则它拥有一个隐式的x-lock在所修改的记录上。对于二级索引来说，如果一个事务修改了聚簇索引的记录，并且对应二级索引所在数据页的PAGE_MAX_TRX_ID大于当前事务的ID（或者正在进行崩溃恢复），并且没有显式的non-gap锁请求在该二级索引上，那么该事务拥有该二级索引的隐式x-lock。

[3] 二级索引上锁定义的复杂性主要是因为它的实现方式：我们想通过查看一个聚簇索引记录的最新值（而不是历史版本）来判断在一个二级索引上是否有隐式的x-lock。可以向用户解释复杂的定义，以便在回答查询时访问路径中存在不确定性：我们可能会或可能不会访问聚簇索引记录，因此可能会或可能不会碰到x锁在那里。

[3] 值得一提的是，不同的事务可以同时对于某个gap拥有冲突的锁。这时因为GAP锁的语义仅仅是“禁止”：如果事务T1拥有某个gap的x-lock，那么另外的事务则不能在gap内插入或进行查询。但是T1拥有的gap-lock并不能让T1直接在gap内插入记录（意思是即使T1拥有该gap的锁，但是如果要在该gap内插入记录还是需要申请记录锁）。

[4] 一个显式的（explicit）锁可以加在一条用户记录或supremum记录上。加在supremum记录上的锁总被认为是gap锁，虽然锁上的gap位没有set。当我们要更新一条记录，并且记录的空间大小发生变化时，我们会将该记录锁临时地保存在该页上的infimum记录，infimum记录只有在这种情况下会被加锁。

[5] 另外，一个waiting record lock可以也是gap锁。一个waiting record lock请求只有在该lock队列中的其他冲突请求被满足后才能得到满足。

[6] 在4.0.5版本中，我们还加入了另一个显式锁类型：LOCK_REC_NOT_GAP，它只锁定单条记录，不包括记录之前的记录。加入该中锁类型的原因是要模拟Oracle-like的读提交（RC）隔离级别。

[7] RULE 1：如果有一个隐式的x-lock在一个记录上，并且在该记录锁的等待队列中有non-gap锁请求，那么持有该隐式x-lock的事务也相当于持有一个显式的non-gap x-lock。因此，只要锁被释放了，我们可以仅仅根据请求队列中的显式锁请求来授予锁。

[8] RULE 3：不同的事务不能同时对同一条记录加冲突的non-gap锁，但是他们可以拥有冲突的gap-lock。

[9] RULE 4：如果有一个waiting lock request在一个队列中，没有其他锁请求可以被插入到等待队列头部。在记录删除或页面分裂时，数据库本身可以为一个事务创建一个新的gap类型的锁，如果没有RULE4，那么waits-for graph可能会出现环，而数据库本身不会处理这种死锁，因为死锁检测仅在一个事务请求一个锁时才进行（而不是数据库本身为事务创建一个锁对象时）。

[10] 如果下一条记录（next record）上的其他事务没有明确的锁定请求，则允许插入该gap。 无论这些锁定请求是被授予还是等待，是否设置了gap bit都没有关系，除非是由另一个事务设置的等待进行插入的gap类型请求被忽略。 另一方面，另一个事务的隐式x锁定不会阻止插入，当使用Oracle样式的序列号生成器作为主键并且许多事务同时执行插入时，这允许更多的并发性。

[11] 一个事务只有在获得记录的x-lock或者没有其他事务请求该记录的non-gap锁的情况下才能对一个记录进行修改。

[12] 如果一个事务拥有一个记录的non-gap explicit锁或是隐式锁，亦或是其他事务没有对该记录加锁，这时该事务才能通过cursor读取该记录。

[13] 总的来说，一个隐式锁（implicit lock）可以被看做授予在某条记录上的x-lock；一个显式的锁（explicit lock）但是没有设置gap bit则可以被看做对记录和gap共同上锁；而设置gap bit的锁则只能用来对gap 加锁。不同的事务不能同时拥有某条记录上相冲突的锁，但可以同时拥有某个gap上相冲突的锁。授予关于某个记录的锁表明可以修改该记录，而gap类型的锁则表示禁止操作。

[14] NOTE：找出某个事务是否在辅助索引记录上具有隐式x锁定可能很麻烦。 我们可能必须查看相应聚簇索引记录的先前版本，以查明删除标记的辅助索引记录是否被活动事务标记为删除，而不是由已提交的事务标记。

[15] FACT A：如果一个事务插入了一行，则可以在任何时候删除该记录，并且一定不会发生锁等待。

[16] FACT B：如果一个事务用cursor读了一些记录（结果集），则他可以再次读这些记录，并且读的结果集和原来的相同如果该事务没有修改其中的记录。所以，不会发生幻读。如果结果集中，字母序最大的记录被移除了，则会发送锁等待，否则的话则不会。

[17] PROOF：当一个read cursor前进时，它会对每条读到的用户记录加s-lock，并对每个supremum加gap类型的s-lock。该cursor必须等待直到获取了上面的锁。所以，其他事务没办法获取该结果集中任何一条记录的x-lock，更无法修改记录。因为cursor推进时还会对每条记录上gap锁，所以其他事务也无法插入该cursor扫描过的记录。页面的分裂或合并，或者老版本的记录被purge，并不会影响此结果。因为当一条用户记录或supremum记录被移除时，下个记录会继承该记录的锁，并设置为gap类型。另外，如果一个supremum记录被插入，则它会继承它的后继记录（successor）的锁。当cursor再次被定位到结果集的头部时，cursor所能访问的记录要么是上次记录访问的，要么是新插入的supremum记录。cursor可以不用等待访问所有的记录，当cursor到达最大的记录时，他会通知结果集已经遍历完成。如果最大的记录已经被移除，则会发生等待，因为next record仅继承了gap类型的锁。

[18] 如果一个索引记录要被修改或新插入，则我们必须检查在该条记录上是否有锁在该条记录上，和下一条记录上是否有（gap lock）。当一个cursor开始读取记录时，我们会为每个读取的记录加一个s-lock，除了cursor在的初始记录。这是因为根据我们index tree索引传统，cursor会被放置在第一个可能匹配的记录之前的位置。这里有可优化的地方：如果一个记录是由在唯一键上的等值条件索引得到的，那么我们没必要对该记录加gap lock锁，而仅仅加记录锁就可以了。在当前版本下，next-key锁会对记录加x-lock锁，并同时阻止在该记录之前的插入操作。

[19] 每个页面上有两条特殊的记录：infimum和supremum记录。一个read cursor可以对supremum记录加锁，supremum记录不能被修改，但是对supremum加锁可以防止在页尾插入记录。

[20] next-key lock可以阻止幻读的产生，防止幻读可以实现可串行化。

[21] 如果我们想插入一条新的记录，那么需要检查什么？只需要检查同一个页面上的next record即可，因为supremum记录也是可以带有锁信息的。s-lock可以阻止插入，那么如果是一个x-lock呢？比如说一个insert…select语句会对选择的记录加s-lock，这时插入会被阻止。如果我们的事务拥有next record的x-lock但是有一个waiting s-lock请求在next record会发生什么？如果该s-lock是由一个read cursor请求的，且该read cursor是按照递增的方向访问索引的，那么我们不能立即插入。因为如果我们提交了更改，则read cursor可以看到新插入的记录。我们应当移动read cursor到next record之前的位置，这样它可以读取到新插入的记录。当然，这种方式实现起来很麻烦。当我们处于上述情况时，我们仅仅在next record上为我们的事务申请第二个x-lock，这时死锁检测机制会注意到我们的事务和read cursor的事务已经发生死锁。这似乎是一个OK的解决方案。

[22] 我们可以设一个约定：被授予的显式记录锁（explicit lock）阻止记录修改的同时会锁记录前面的gap。一个waiting explicit lock请求会锁定gap。隐式的记录x锁（implicit x-lock）派生于聚簇索引中的事务id，它只锁记录不锁gap。

[23] 我们应该如何存储update locks？如果一个search查询是通过unique key进行的，则我们可以仅仅修改记录的trx id。不然的话，我们要在记录上加一个x-lock。如果更新更改了聚簇索引记录的排序字段，则插入的新记录在锁定表中不需要记录锁定，则trx id就足够了。 二级索引记录也是如此。 搜索删除类似于更新。

[24] PROBLEM：如果有waiting lock request怎么办？如果一个事务正在等待更新一条记录，而这条记录被另外一个未提交的事务修改，那么正在修改这条记录的事务如何发送“结束等待”信号给等待的事务？如果我们约定一个事务在某一时刻只能等待一个锁，那我们如何保护这个锁如果lock wait ends？

[25] PROBLEM：对一个二级索引来说，如果仅仅是修改，而不是做插入，那么还有必要检查二级索引记录的trx id字段吗？一个二级索引被修改其实只是指set和reset该二级索引记录的delete flag。一个二级索引记录包含了能唯一确定聚簇索引的字段（用来做“回表”）。一个二级索引只有在其聚簇索引发生被修改时才能被修改。在我们要修改二级索引之前，需要检查对应聚簇索引上的trx id字段。所以，当要delete mark或unmark一个二级索引时，我们不关心该二级索引的trx id字段，只需要看锁表中是否有对应的（聚簇索引记录）锁即可。在对一个二级索引做SELECT时，trx id至关重要，我们必须要检查对应的聚簇索引。

[26]PROBLEM：当页面发生分裂或合并、亦或是一个记录被删除或被更新时如何更新记录的锁信息？如果记录的长度发生变化，我们会用delete and insert的方式进行更新操作。在这种情况下，我们如何重新获得记录的锁，或在这条记录上等待锁？一个记录锁是使用bitmap来记录对应的记录在页面内的heap no，当我们要移除一条记录时，可能仍会保留lock bits。如果页面重新组织了，我们可以新建一张表，用来记录记录新、老heap no的对应关系，并相应地变换锁中bitmap的信息。接着，我们把更新的记录的结束为止加入到表中。如果更新不需要重组页面，我们可以简单的移除lock的bits，并更新为记录当前的heap no。（如果我们用完了当前lock的bitmap位，我们可能需要重新分配一个lock。）

[27] 一个更为复杂的情况时当要重新插入更新的记录时，需要分裂数据页（而不是页面重组），这时索引树的结构会发生变换。这就引出了下面的问题。

[28] PROBLEM：如果一个supremum记录在页面合并的时候被移除，或者一个记录被purge掉了，那么waiting lock requests如何处理？如果页面向右分裂，我们可以简单的将lock request加到新的supremum记录上。如果一个记录被移除，我们可以将waiting lock request放置到该记录的下一条记录上。在这种情况下，下一条记录上可能已有其他锁请求存在，所以新的死锁检测必须判断是否可以进行加锁。

[29] PROBLEM：如果一个记录被插入了，它应该从它的下一条记录获取什么锁？在页面分裂时，一个supremum总会被插入，而且总可以插入成功，但是插入一条用户记录需要其upper neighbor上没有其他事务持有的任何锁或锁请求。解决方案：我们可以将upper neighbor的锁拷贝过来作为gap类型的锁，这样waiting locks会被转换称为在插入记录上已授予的gap类型。

[30] 对于行来所，InnoDB只会获取S或X类型的锁，对于表来说，InnoDB通常获取IS或IX，只有在需要锁表的情况下才会获取S或X锁。自增锁（AI）在语句级别的binlog中是需要的。

物理的LATCH和逻辑的锁如何配合保证事务的隔离性？

LATCH，即闩，大部分情况下是用来保证数据页访问的正确性。而锁（行锁、表锁）则是用来保证访问一条记录的正确性，是用来防止幻读等异常现象。这两者配合保证了事务执行的正确性。这里的问题是LATCH和锁如何交互的？首先，LATCH对一个事务（trx）来说应该是透明的，因为LATCH仅是为了保证页面的物理访问的正确性。但是一个事务是能感知到锁的存在的，而锁要依赖于页面中记录的位置信息。下面我们通过跟踪一条记录的插入过程，看下LATCH和记录锁如何交互。

btr_cur_optimistic_insert()函数是将一条记录以乐观方式插入到数据页上：

1
2
3
4
5
6
//btr_cur_optimistic_insert的调用逻辑如下：
	btr_cur_open() //打开一个指向“待插入”位置的cursor，对数据页加latch
          ↓↓
btr_cur_optimistic_insert() //执行乐观插入
          ↓↓
       释放LATCH

btr_cur_optimistic_insert()函数的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*************************************************************//**
Tries to perform an insert to a page in an index tree, next to cursor.
It is assumed that mtr holds an x-latch on the page. The operation does
not succeed if there is too little space on the page. If there is just
one record on the page, the insert will always succeed; this is to
prevent trying to split a page with just one record.
@(Database)return DB_SUCCESS, DB_WAIT_LOCK, DB_FAIL, or error number */
dberr_t
btr_cur_optimistic_insert(
/*======================*/
{

	//获取要进行插入的数据页
	block = btr_cur_get_block(cursor);
	page = buf_block_get_frame(block);
	index = cursor->index;
	//获取cursor，该cursor已被放置到要插入记录的前一条记录的位置
	page_cursor = btr_cur_get_page_cur(cursor);

	/* 下面开始尝试插入 */
	{
		const rec_t*	page_cursor_rec = page_cur_get_rec(page_cursor);

		if (dict_table_is_intrinsic(index->table)) {

			index->rec_cache.rec_size = rec_size;
			//如果是临时表，则直接插入
			*rec = page_cur_tuple_direct_insert(
				page_cursor, entry, index, n_ext, mtr);
		} else {
			/* 如果不是临时表，则要检查锁信息，可能还要写UNDO信息 */
			err = btr_cur_ins_lock_and_undo(flags, cursor, entry,
							thr, mtr, &inherit);

			if (err != DB_SUCCESS) {
				goto fail_err;
			}
			/* 在数据页上写入记录 */
			*rec = page_cur_tuple_insert(
				page_cursor, entry, index, offsets, heap,
				n_ext, mtr);
		}
		/* 根据游标在页面内的位置判断是否发生了页面重组 */
		reorg = page_cursor_rec != page_cur_get_rec(page_cursor);
	}

	if (*rec) {
	} else if (page_size.is_compressed()) {
		/* Reset the IBUF_BITMAP_FREE bits, because
		page_cur_tuple_insert() will have attempted page
		reorganize before failing. */
		if (leaf
		    && !dict_index_is_clust(index)
		    && !dict_table_is_temporary(index->table)) {
			ibuf_reset_free_bits(block);
		}

		goto fail;
	} else {

		/* For intrinsic table we take a consistent path
		to re-organize using pessimistic path. */
		if (dict_table_is_intrinsic(index->table)) {
			goto fail;
		}

		ut_ad(!reorg);

		/* 如果页面放不下记录，则尝试重组页面 */
		if (!btr_page_reorganize(page_cursor, index, mtr)) {
			ut_ad(0);
			goto fail;
		}

		ut_ad(page_get_max_insert_size(page, 1) == max_size);

		reorg = TRUE;

		*rec = page_cur_tuple_insert(page_cursor, entry, index,
					     offsets, heap, n_ext, mtr);
	}

	return(DB_SUCCESS);
}

未完待续！

参考资料

[1] https://dev.mysql.com/worklog/task/?id=6363WL#6363 : InnoDB: implement SX-lock for rw_lock