MDL_map_partition中对锁的过渡

Sat, Apr 5, 2014

• mysql
• MDL
• lock

在MDL源码中有一段MDL_map_partition中对锁的过渡有点意思, 拿出来分析一下

场景

MDL_map_partition是容纳MDL_lock的一个容器, MDL_lock可以简单的理解为一种锁.

那么场景问题是现在我要从锁容器C中查找一个锁L并加锁L, 怎样做到多线程安全

场景中C上有保护C的锁A (容器锁), L上的锁为B (成员锁) (此处做了简化, 实际上MDL_lock并不是一个锁, 而是类似于条件变量, 而锁B是保护L的锁. 此处将L简化为一把锁)

分析1

最简单的方法, 就是A加锁, B加锁, A解锁. 这种方法肯定不会有错, 但是并发性上会出现问题. 比如以下场景

1. 线程T1持有B
2. 线程T2正在容器中查找B.
3. 线程T3在同一个容器中查找另外一个MDL_lock

T2先将A加锁, 加锁B时, 由于T1持有B, T2被阻塞; T3在同一个容器中查找另一个不相关的成员, 先要加锁A, A被T2持有, T3被阻塞

因此, 这种做法的并发性很差

分析2

提高并发性的关键是将A锁过渡到B锁, 比如这样: A加锁, 查找B, A解锁, B加锁.

这种方法解决了并发性, 但显而易见形成了一个无锁区 (从A解锁到B加锁这个区域). 如果在无锁区另一个线程将B销毁或移出容器, 那么后面的B加锁操作就会悲剧

分析3

面对无锁区的问题, 可以试着加version(版本变量)来解决, 规则如下:

• 任何将成员移入/移出容器的情况, 都需要获得容器锁A和成员锁B, 并在元素version上加1
• 对成员的销毁, 需要先将成员移出容器

这样, 查找成员的流程变为:

1. 线程T1, 对A加锁, 找到B, 记录B的version, 记为v1. 对A解锁
2. 线程T2, B销毁或移出容器, 需要获得A和B锁, 对version加1, 记为v2
3. 线程T1, 等到T2释放B锁后, 可获得B锁, 发现v1 != v2, 意味着成员可能在容器中已经被移出或销毁, 则需要重试整个过程

加入version后, 对于销毁成员的场景, 并发性并没有改变 (因为仍然需要同时获得两把锁), 但对于查找成员的场景, 并发性和分析2一样

不幸的是, 这个场景仍然存在问题, 很容易看到其中一个逻辑问题, T1在T2销毁B锁后, 还获得了B锁. 也就是T2不能即刻销毁B锁, 否则所有等待B锁的线程都会悲剧. 那B锁何时能被安全销毁

分析4

要解决分析3的问题, 可以在B上添加引用计数, 细节如下:

• 在成员未被移出容器时, 持有A锁可以对成员引用计数usage_count进行加1, 即在容器中查找成员时, 容器负责对成员的usage_count加1
• 持有B锁可以对自己的解引用计数release_count进行加1, 即使用者在使用完B后, 对B进行解引用
• 如果usage_count == release_count, 则B可以被安全销毁

可以看到usage_count和release_count在分别在不同锁的保护下, 代入分析3的场景, 发现可以解决分析3的问题

还有一些需要说明的边界情况

• 在成员已经被移出容器后, 成员引用计数usage_count不再受A锁保护, 而是受B锁保护. 相当于容器已经不再管理成员的引用计数
• 如何判断”成员已经被移出容器”, 可以在成员上添加状态量is_removed_from_container, 读取此状态需要A锁或B锁, 修改此状态需要A锁和B锁.

Mysql的实现

Mysql的实现和之前的分析大致相同, 给出映射表

分析里的概念	Mysql的变量
版本变量version	MDL_lock.m_version
成员引用计数usage_count	MDL_lock.m_ref_usage
成员解引用计数release_count	MDL_lock.m_ref_release
状态量is_removed_from_container	MDL_lock.m_is_destroyed

实现锁拆分的函数为MDL_map_partition::move_from_hash_to_lock_mutex, 一看就懂