1. 前言#
数据库系统的并发控制与其多个模块相关联，其用于实现无冲突、保持一致性的多事务并发操作。并发控制模块需要保证事务并发执行的效果与要求的串行执行模式的效果完全相同，以达到隔离性的要求，不合理的并发控制可能导致更新丢失、不可重复读、脏读、幻读等问题。
目前常用的并发控制协议可被粗略并不完整的分为悲观和乐观两大类：此处乐观协议指狭义乐观并发控制，如指基于完成有效性验证的并发控制，主要为前向 OCC 和后向 OCC 两类；而悲观协议又分为基于锁和非锁两大类，基于锁的协议有 2-Phase Locking、Altruistic Locking、Read/Write Tree Locking 等，非锁类协议有基于基于事务串行化图的协议等。此外，还可以进一步可以结合多版本并发控制（MVCC），以提高数据库的（读）性能。
2. InnoDB 事务锁#
2.1 两阶段锁（2PL Locking）#
这里介绍最常用的为 2PL 协议，这也是 MySQL 使用的机制。2PL 将事务的执行阶段分为三个不同的部分：
- 1）第一阶段，事务开始执行时，事务开始获取需要的锁的权限，但不释放锁；
- 2）第二部分是事务获取所有锁的过程；
- 3）当事务释放它的第一个锁时，第三阶段开始，此阶段事务不能要求任何新锁，只释放获取的锁。
从上可以看出 2PL 分为 Growing phase 和 Shrinking phase 两个阶段。根据锁定细节还可演化为 Conservative-2PL、Strict-2PL、Rigorous-2PL 等。2PL 协议提供了可序列化性，但不能保证不发生死锁，因此需要进行死锁预防或死锁检测。MySQL 采用的是死锁检测加超时恢复的机制，死锁检测一般通过 waits-for 图结构实现：图中点代表事务，有向边代表事务在等待另一个事务放锁，当 waits-for 图出现环时说明有死锁出现。此时需要进行死锁恢复，最常见的解决办法就是选择整个环中一个事务进行回滚，以打破整个等待图中的环，此时需要考虑如何选择回滚以避免饥饿并最小化代价。
2.2 InnoDB 中的 Lock#
目前 InnoDB 层主要有 LOCK_TABLE 和 LOCK_REC 两大类，后者提供更细粒度的锁操作。行锁以 scope 划分细节类型，有 LOCK_ORDINARY（next-key，记录及其前间隙的组合锁），LOCK_GAP（记录值的前间隙锁），LOCK_REC_NOT_GAP（单记录锁），LOCK_INSERT_INTENTION（为插入行为的gap锁）等。其次，行锁的锁定模式为 LOCK_IS、LOCK_IX、LOCK_S、LOCK_X、LOCK_AUTO_INC 等。
InnoDB 的所有事务锁对象挂在全局对象 lock_sys_t 上，同时每个事务对象trx_t 上也维持了其拥有的事务锁，每个表对象 dict_table_t 上维持了其上的表级锁。8.0.21 版本还对 record hash 做 mutex 分片拆减少瓶颈。在一个系统中，每个表和每一行都可以被视作一种资源，并且事务在请求资源访问权限时会指定一个模式（mode），以表明它打算如何使用该资源。例如，LOCK_X 模式意味着事务需要排他性访问，而 LOCK_S 模式意味着事务可以与其他使用 LOCK_S 模式的事务共享资源，锁可以是等待状态（WAITING）或已授予状态（GRANTED）。锁系统使用页面编号（page_no，即包含记录的页面的标识符）和在页面内部分配记录数组中的位置（heap_no）来标识行记录。这在 b-tree 合并、分裂或可变长度记录的重新分配时变得很重要，这些操作都需要通知锁系统以反映变化。
锁系统中的锁包含了元素：
1）请求锁的事务（requesting transaction）；
2）资源目标标识（特定的行或表定位）；
3）锁类型与模式（如 LOCK_X、LOCK_S 等）；
4）锁状态（WAITING 或 GRANTED）。
锁的生命周期通常如下：
1）事务请求锁，如果没有与现有锁冲突则立即授予（GRANTED），否则进入等待状态（WAITING）；
2）若锁处于 WAITING 状态，则线程（主动）休眠；
3）WAITING 锁要么在没有冲突的情况下变为 GRANTED，要么在回滚的情况下被取消，同时唤醒原先等待的事务线程；
4）事务结束（提交或回滚）时释放其所有锁。
行锁冲突关系通过函数 rec_lock_check_conflict 确定。
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
|
static inline Conflict rec_lock_check_conflict(const trx_t *trx,
ulint type_mode, const lock_t *lock2,
bool lock_is_on_supremum, Trx_locks_cache &trx_locks_cache) {
/* 锁模式的兼容矩阵
IS IX S X AI
IS + + + - +
IX + + - - +
S + - + - -
X - - - - -
AI + + - - -
Note that for rows, InnoDB only acquires S or X locks.
For tables, InnoDB normally acquires IS or IX locks,
S or X table locks are only acquired for LOCK TABLES.
Auto-increment (AI) locks are needed because of
statement-level MySQL binlog.
*/
/* 锁模式兼容 */
if (trx == lock2->trx ||
lock_mode_compatible(static_cast<lock_mode>(LOCK_MODE_MASK & type_mode),
lock_get_mode(lock2))) {
return Conflict::NO_CONFLICT;
}
/* 这里需要注意一点，新来的锁是需要和对应锁链上所有相同资源目标的锁做兼容比较，
包括原先为 waiting 状态的锁，这样做防止了 X 锁饥饿的问题 */
const bool is_hp = trx_is_high_priority(trx);
/* 高优先级是事务可以忽略原先的 waiting 状态的低优先级事务*/
if (is_hp && lock2->is_waiting() && !trx_is_high_priority(lock2->trx)) {
return Conflict::NO_CONFLICT;
}
/* 要加的锁是 非insert_intention的 上界 或 gap 锁，可以兼容任何锁 */
if ((lock_is_on_supremum || (type_mode & LOCK_GAP)) &&
!(type_mode & LOCK_INSERT_INTENTION)) {
return Conflict::NO_CONFLICT;
}
/* 要加 非insert_intention的锁，可以兼容 gap 锁 */
if (!(type_mode & LOCK_INSERT_INTENTION) && lock_rec_get_gap(lock2)) {
return Conflict::NO_CONFLICT;
}
/* 要加的锁是 gap 锁，可以和 rec_not_gap 兼容 */
if ((type_mode & LOCK_GAP) && lock_rec_get_rec_not_gap(lock2)) {
return Conflict::NO_CONFLICT;
}
/* 锁链上待比较的锁是 insert_intention 的，可以兼容其他锁 */
if (lock_rec_get_insert_intention(lock2)) {
return Conflict::NO_CONFLICT;
}
/* insert_intention 锁最大的问题是后续插入后会把 lock 区间分裂，
并由单个 lock 产生两个 lock，这样就有可能导致事务 waiting 状态的
gap 或 next-key lock 变成两个 waiting 状态的 lock，违背事务最
多一个 waiting lock 的原则 */
if (!(type_mode & LOCK_INSERT_INTENTION) && lock2->is_waiting() &&
lock2->mode() == LOCK_X && (type_mode & LOCK_MODE_MASK) == LOCK_X) {
/* 如果 waiting 状态的锁是被当前 trx 自己已经 granted 的锁给阻塞，则不需要等这个 waiting 状态的锁 */
if (trx_locks_cache.has_granted_blocker(trx, lock2)) {
return Conflict::CAN_BYPASS;
}
}
return Conflict::HAS_TO_WAIT;
}
|
2.2 加锁逻辑（案例）#
以 sysbench 表结构为例，介绍写入时的加锁逻辑。
1
2
3
4
5
6
7
8
|
CREATE TABLE `sbtest1` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`k` int(11) NOT NULL DEFAULT '0',
`c` char(120) NOT NULL DEFAULT '',
`pad` char(60) NOT NULL DEFAULT '',
PRIMARY KEY (`id`),
KEY `k_1` (`k`)
) ENGINE=InnoDB;
|
这里先额外说明一下 innodb 在加行锁时一定 cursor 已经定位了（为了确定资源目标标识，即 page_id 和 heap_no），并且获得了 page 页面锁以防止修改。
首先讨论 insert 场景，insert 流程先主键（row_ins_clust_index_entry）再二级索引（row_ins_sec_index_entry），在每个索引上执行的操作步骤类似：
- 定位 cursor 至目标位置（这里还可以获得定位匹配情况）；
- a）如果是唯一索引（包括主键），并且定位时发现和目标索引上存在 record 和将要插入的记录物理 match，则要走到 record 判重逻辑中（row_ins_duplicate_error_in_clust / row_ins_scan_sec_index_for_duplicate），其中会先对应去加目标行的行锁（lock_clust_rec_read_check_and_lock / lock_sec_rec_read_check_and_lock 两个函数的执行逻辑基本一致），这里可能产生锁等待，再判断重复性是否满足要求；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
dberr_t lock_clust_rec_read_check_and_lock(
const lock_duration_t duration, const buf_block_t *block, const rec_t *rec,
dict_index_t *index, const ulint *offsets, const select_mode sel_mode,
const lock_mode mode, const ulint gap_mode, que_thr_t *thr) {
if (srv_read_only_mode || index->table->is_temporary())
return (DB_SUCCESS);
dberr_t err;
ulint heap_no = page_rec_get_heap_no(rec);
// 隐式锁判断：通过 "主键record上面的系统列" 和 "活跃事务数组" 判断对应记录是否存在隐式锁，如有则为其加上显示锁
// 判断二级索引无法过滤时，需要回表
if (heap_no != PAGE_HEAP_NO_SUPREMUM) {
lock_rec_convert_impl_to_expl(block, rec, index, offsets);
}
{
locksys::Shard_latch_guard guard{UT_LOCATION_HERE, block->get_page_id()};
if (duration == lock_duration_t::AT_LEAST_STATEMENT) {
lock_protect_locks_till_statement_end(thr);
}
// 加行锁，不可为隐式锁
err = lock_rec_lock(false, sel_mode, mode | gap_mode, block, heap_no, index, thr);
}
return (err);
}
|
b）如果是非唯一索引，或者未发现已存在匹配 record，则在 insert 阶段可以跳过重复性检查（进而这里也不再需要走加锁逻辑）；
3. 进行真正的插入操作（btr_cur_optimistic_update / btr_cur_pessimistic_update 这两个接口为通过修改插入； btr_cur_optimistic_insert / btr_cur_pessimistic_insert 这两个接口为直接插入），其中会对应进行行锁操作 （lock_clust_rec_modify_check_and_lock / lock_sec_rec_modify_check_and_lock 通过修改插入； lock_rec_insert_check_and_lock 直接插入）：
修改插入（update）：
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
|
dberr_t lock_clust_rec_modify_check_and_lock(
ulint flags, /*!< in: if BTR_NO_LOCKING_FLAG
bit is set, does nothing */
const buf_block_t *block, /*!< in: buffer block of rec */
const rec_t *rec, /*!< in: record which should be
modified */
dict_index_t *index, /*!< in: clustered index */
const ulint *offsets, /*!< in: rec_get_offsets(rec, index) */
que_thr_t *thr) /*!< in: query thread */
{
if (flags & BTR_NO_LOCKING_FLAG) return (DB_SUCCESS);
dberr_t err;
ulint heap_no = rec_offs_comp(offsets) ? rec_get_heap_no_new(rec)
: rec_get_heap_no_old(rec);
// 隐式锁判断：通过 "主键record上面的系统列" 和 "活跃事务数组" 判断对应记录是否存在隐式锁，如有则为其加上显示锁；
// 判断二级索引无法过滤时，需要回表
lock_rec_convert_impl_to_expl(block, rec, index, offsets);
{
locksys::Shard_latch_guard guard{UT_LOCATION_HERE, block->get_page_id()};
// 加行锁，可为隐式锁，即无冲突时不真正加行锁
err = lock_rec_lock(true, SELECT_ORDINARY, LOCK_X | LOCK_REC_NOT_GAP, block,
heap_no, index, thr);
}
if (err == DB_SUCCESS_LOCKED_REC)
err = DB_SUCCESS;
return (err);
}
|
直接插入（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
|
dberr_t lock_rec_insert_check_and_lock(
ulint flags, /*!< in: if BTR_NO_LOCKING_FLAG bit is
set, does nothing */
const rec_t *rec, /*!< in: record after which to insert */
buf_block_t *block, /*!< in/out: buffer block of rec */
dict_index_t *index, /*!< in: index */
que_thr_t *thr, /*!< in: query thread */
mtr_t *mtr, /*!< in/out: mini-transaction */
bool *inherit) /*!< out: set to true if the new
inserted record maybe should inherit
LOCK_GAP locks from successor record */
{
if (flags & BTR_NO_LOCKING_FLAG) return (DB_SUCCESS);
dberr_t err = DB_SUCCESS;
lock_t *lock;
auto inherit_in = *inherit;
trx_t *trx = thr_get_trx(thr);
const rec_t *next_rec = page_rec_get_next_const(rec);
ulint heap_no = page_rec_get_heap_no(next_rec);
{
locksys::Shard_latch_guard guard{UT_LOCATION_HERE, block->get_page_id()};
if (lock_rec_get_first(lock_sys->rec_hash, block, heap_no) == nullptr) {
// 锁链上无锁，直接加隐式锁
*inherit = false;
} else {
*inherit = true;
const ulint type_mode = LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION;
// 判断锁链上是否存在冲突模式的锁：如果存在其他后继记录的除 insert 目的外的 gap 锁
const auto conflicting = lock_rec_other_has_conflicting(type_mode, block, heap_no, trx);
if (conflicting.wait_for != nullptr) {
RecLock rec_lock(thr, index, block, heap_no, type_mode);
trx_mutex_enter(trx);
// 存在冲突，加行锁
err = rec_lock.add_to_waitq(conflicting.wait_for);
trx_mutex_exit(trx);
}
}
}
switch (err) {
case DB_SUCCESS_LOCKED_REC: err = DB_SUCCESS;
case DB_SUCCESS:
if (!inherit_in || index->is_clustered()) break;
/* 二级索引更新 page 上的 max trx id 标志 */
page_update_max_trx_id(block, buf_block_get_page_zip(block), trx->id, mtr);
default:
break;
}
return (err);
}
|
更多隐式锁相关内容可以参考这篇 mysql 月报文章。
update 流程会先通过读接口来寻找原先需要被更新的行记录（index_read -> row_search_mvcc），在读阶段就会对目标行进行加锁（lock_clust/sec_rec_read_check_and_lock），这里的加锁接口和 insert 判重阶段一致，具体加锁模式还和隔离级别有关。 update 第二个阶段会真正去修改数据，也有直接 update 模式和 delete_mark + insert 模式，到 btr_cur_ 层的接口一致，因此加锁函数接口也一致。
2.3 锁的释放#
大多数情况下事务持有的所有锁（trx_t::lock.trx_locks）都是在事务提交时释放(trx_release_impl_and_expl_locks->lock_trx_release_locks，在 trx_commit_in_memory 阶段的开始)。有两个例外：
a）AUTO-INC 锁（由参数 innodb_autoinc_lock_mode 控制）在SQL结束时直接释放（innobase_commit –> lock_unlock_table_autoinc）；
b）在 RC 隔离级别下执行 DML 语句时，从引擎层返回到 Server 层的记录，如果不满足 where 条件，则会立刻 unlock 掉（ha_innobase::unlock_row）。
对于行锁，从 lock sys hash 中删除后还需要判断是否有正在等待的会话可以被唤醒（lock_rec_dequeue_from_page）。这里采用的是 CATS 策略将所有处于 LOCK_WAIT 状态的锁对象按trx优先权、调度权重 trx->lock.schedule_weight 排序，然后依次处理。对于每个等待状态的锁对象，如果其不再等待任何已有 granted 的锁对象（包括这次循环前面 grant 的），则清理等待事务的相关锁等待状态并唤醒线程已经挂起的等待事务；反之，则更新等待关系、继续等待。
2.4 死锁检测及CATS策略#
官方在 Bug#29882690: UNDETECTED DEADLOCK WITH GAP AND INSERT INTENTION LOCKS IS POSSIBLE 中修复部分原先无法探测的死锁，还将锁阻塞信息（wait-for图）从 lock 转移到 trx 中，并且将死锁检测从前台事务线程转移到后台监控线程。这样减轻了前台事务线程的取锁冲突时的检测代价；但是死锁会先进入事务系统，后续检测出后回滚，也就意味着死锁事务会占用一段时间的线程、内存资源、导致锁链、事务数组等的膨胀后（对应线程先进入、然后 suspend 进入睡眠等待后）才会被回滚，若是死锁概率较高的高冲突场景这可能会导致整体事务系统的性能下降。死锁处理的逻辑在 lock_wait_timeout_thread 线程中（lock_wait_update_schedule_and_check_for_deadlocks），顾名思义这个函数更新了事务权重比检查了是否存在死锁。新版死锁检测逻辑的理论基础可以参考这篇 mysql 月报文章，下面主要介绍代码逻辑。
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
|
/** Takes a snapshot of transactions in waiting currently in slots, updates
their schedule weights, searches for deadlocks among them and resolves them. */
static void lock_wait_update_schedule_and_check_for_deadlocks() {
ut::vector<waiting_trx_info_t> infos;
ut::vector<int> outgoing;
ut::vector<trx_schedule_weight_t> new_weights;
/*
（以下持有 lock_sys->wait_mutex）
将 lock_sys 中所有 waiting 状态的 trx 及阻塞它的 blocking_trx 加入到 infos，构建 wait trx 的 snapshot；
*/
auto table_reservations = lock_wait_snapshot_waiting_threads(infos);
/*
构建 waiting for graph，实质上就是寻找某个 trx 的 blocking_trx 是否存在在 info 中，
blocking_trx 也存在的话通过 outgoing 数组关联位置起来，这样就将所有依赖的 trx 串联起来，
(即将这个 trx 在 info 中的 index 位置作为 outgoing index，
将 blocking_trx 在 info 中的 index 位置作为 outgoing 中这个 index 对应位置的元素）
*/
lock_wait_build_wait_for_graph(infos, outgoing);
/*
初始化事务权重值，正常等待事务初始为1，超时事务会初始为较大值；
通过关联树图算出 new_weights（依赖子树元素数目）：
将所有无入度的节点入栈，再遍历栈元素根据其出度确定父节点并将这个子节点的权重增加到父节点上，并减少其父节点入度计数；
如果对应父节点还存在有出度，当其所有入度处理完成后（入度计数为0，其所有入度已经转化为权重值），作为无入度节点入栈同上处理；
直到栈中无任何元素（不存在还有出度的元素）
NOTE：如果有环存在，其上一定不存在无入度的节点，因此不会在上述步骤处理，因此入度计数不为0
将除死锁环外的所有等待状态的事务权重更新（持有 lock_sys->wait_mutex）
*/
lock_wait_compute_and_publish_weights_except_cycles(infos, table_reservations,
outgoing, new_weights);
if (innobase_deadlock_detect) {
/*
用 DFS 方式确定的一个死锁环，如果存在的话就选择目标并回滚事务（lock_cancel_waiting_and_release）
*/
lock_wait_find_and_handle_deadlocks(infos, outgoing, new_weights);
}
}
|
CATS 策略基于后台生产的事务权重，在事务放锁选择最合适等待事务去唤醒，提升整体事务效率。
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
|
static void lock_rec_grant_by_heap_no(lock_t *in_lock, ulint heap_no) {
const auto hash_table = in_lock->hash_table();
using LockDescriptorEx = std::pair<trx_schedule_weight_t, lock_t *>;
Scoped_heap heap((sizeof(lock_t *) * 3 + sizeof(LockDescriptorEx)) * 32, UT_LOCATION_HERE);
RecID rec_id{in_lock, heap_no};
Locks<lock_t *> low_priority_light{heap.get()};
Locks<lock_t *> waiting{heap.get()};
Locks<lock_t *> granted{heap.get()};
Locks<LockDescriptorEx> low_priority_heavier{heap.get()};
const auto in_trx = in_lock->trx;
/* 对于锁链上每个 lock 划分到 granted、waiting、low_priority_light、low_priority_heavier 中：
granted: 已经获取到的锁，如果等待锁被授权，也会从 waiting 转移到 granted；
low_priority_light：低权重的 waiting 状态锁；
low_priority_heavier：高权重的 waiting 状态锁；
waiting：处于 waiting 状态的锁，最终 low_priority_light 和 low_priority_heavier 会合并入此数组；
*/
Lock_iter::for_each(rec_id,
[&](lock_t *lock) {
if (!lock->is_waiting()) {
granted.push_back(lock);
return (true);
}
const auto trx = lock->trx;
if (trx->error_state == DB_DEADLOCK || trx->lock.was_chosen_as_deadlock_victim) {
return (true);
}
const auto blocking_trx = trx->lock.blocking_trx.load(std::memory_order_relaxed);
if (blocking_trx != in_trx) { return (true); }
if (trx_is_high_priority(trx)) {
waiting.push_back(lock);
return (true);
}
/* 这个等待的事务还有等待它的事务，认为是高权重 */
const auto schedule_weight = trx->lock.schedule_weight.load(std::memory_order_relaxed);
if (schedule_weight <= 1) {
low_priority_light.push_back(lock);
} else {
low_priority_heavier.push_back(LockDescriptorEx{schedule_weight, lock});
}
return (true);
},
hash_table);
if (waiting.empty() && low_priority_light.empty() && low_priority_heavier.empty()) {
return;
}
/* 按权重进行排序，高权重优先 grant */
std::stable_sort(low_priority_heavier.begin(), low_priority_heavier.end(),
[](const LockDescriptorEx &a, const LockDescriptorEx &b) {
return (a.first > b.first);});
for (const auto &descriptor : low_priority_heavier) {waiting.push_back(descriptor.second);}
waiting.insert(waiting.end(), low_priority_light.begin(), low_priority_light.end());
const auto new_granted_index = granted.size();
granted.reserve(granted.size() + waiting.size());
for (lock_t *wait_lock : waiting) {
/* 已授权锁是否会阻塞当前锁 */
const lock_t *blocking_lock = lock_rec_has_to_wait_for_granted(wait_lock, granted, new_granted_index);
if (blocking_lock == nullptr) {
lock_grant(wait_lock);
lock_rec_move_granted_to_front(wait_lock, rec_id);
granted.push_back(wait_lock);
} else {
/* 等待的锁等待原因可能改变，更新 wait_for 图 */
lock_update_wait_for_edge(wait_lock, blocking_lock);
}
}
}
|
- 版权声明：如需转载或引用，请附加本文链接并注明来源。