01

意向锁，解决的问题

成熟的数据库设计中，需要一个模块对资源的并发控制进行管理。意向锁就是实现资源并发控制管理的经典方式。在讨论它的概念与设计前，我们先举几个MongoDB的经典场景。

1. mongoDB 默认是行级并发，我们希望多行并发读写互不影响，但是我们又希望对在dropCollection时，不能有任何对表的读写在操作，这个“不希望”也是双向的，即在对表并发读写时，我们也不希望dropCollection在操作。

2. 在执行dbStats命令时，希望和dropDB/insert命令互斥，但是又不影响对表的并发读。

3. 由于写每个db的每张表，都须要往oplog中写记录，因此oplog是全局的，我们希望在truncate oplog这个全局操作在进行时，任何db对oplog的写操作都被阻塞。

第一个例子中，我们似乎用传统的rwlock就可以解决，在对表进行并发读写前，加rlock，在对表进行dropCollection前，加wlock。 暂不论rwlock的r状态和并发写的行为不一致，至少这样是行得通的。 可是遇到了第二个例子，我们发现rwlock的rw两个状态无法表达我们的锁需求了，到了第三个例子，只要能隐约觉得，这个锁，还得有层级结构。

而意向锁协议，是一种对树形（层级）资源进行并发控制的协议。它由"操作约定"和"冲突矩阵"两部分组成，且看下文。

02

MongoDB中的意向锁的定义

MongoDb使用了简化版的意向锁协议，抛却了SIX状态，保留了 IS/IX/S/X四种锁状态。其冲突矩阵为：

其使用方式为：

1. 对一个节点加IX/X锁时，必须先（递归）获取其父节点的IX锁。

2. 对一个节点加IS/S锁时，必须先（递归）获取其父节点的IS锁。

举个例子：MongoDB中的资源层级结构如下：

在对Collection2中的记录进行读操作时，需要先获得其IS锁。因此先递归获得其父节点Global的IS锁。

此时，如果执行对Db2的drop操作，则需要获得Db2的X锁，由于Db2 目前处于IS锁状态，且IS锁与X锁互斥，因此锁无法立即获得。

此时，如果执行对collection2的记录的写操作，则需要获得Global的IX锁，Db2的IX锁，Collection2的IX锁，从根节点一路下来，IX与IS状态互不冲突，因此加锁成功。如下图：

通过上述的例子，我们可以发现，意向锁的设计较为简洁，仅仅通过一个矩阵（冲突矩阵），两条原则（递归加锁）就可以满足数据库系统中对资源的并发控制的需求。

03

Mongo中意向锁的实现

虽然意向锁的设计非常简洁，但是理论和工程实践上，我们至少还要考虑如下几点：

1. 一个高并发读写的db中，IS/IX锁源源不断的加上来，且相互不冲突，在这种条件下，如何避免X锁的饿死。

2. 如何避免死锁。

带着这两个问题，我们分析mongoDB 意向锁的实现。 整体结构 mongoDB中的意向锁实现主要在 lockmanager.cpp/lockstate.cpp两部分。一个简化的意向锁的原语可以用如下两条语句来表达。

比如，我们想要给DB加上X锁，就可以执行 (newLockObject).lock("mydb", MODE_X)。

其整体结构如下图所示：

BucketArray

上图中，意向锁划分为128个元素的BucketsArray, BucketsArray可以无锁访问，一个lock(ResourceId, LockMode)操作，首先通过Hash(ResourceId)%128 找到对于的bucket，这一步无锁操作非常重要，充分利用了不同ResourceId的无关性，使得意向锁模块具备水平扩展性。

Bucket

每个Bucket是ResourceId->LockHead的哈希表。该哈希表被Bucket对象中的mutex保护。

LockHead

LockHead是对应于某个ResourceId的锁对象。LockHead维护着所有对该ResourceId的锁请求。LockHead由ConflictList和GrantList组成。ConflictList是该锁的等待队列， GrantList是持有锁的对象链表。

思考与尝试

上面我们分析了MongoDB中意向锁的结构图，假设我们现在对db1加了大量的IS锁，现在我们要对db1加IX锁，为了检查IX锁是否和GrantList冲突，需要对买二手QQGrantList进行遍历进行冲突检测，这样做是不高效的。

引用计数数组

为了解决这个问题，MongoDB为GrantList和ConflictList增加了引用计数数组。在将一个对象增加到GrantList中时，顺带对grantedCounts[mode] 累加，如果grantedCounts[mode]是从0到1的变化， 则将grantedModes对应的bitMask设置为1。 从GrantList中删除对象时，是一个逆向的对称操作。这样，在判断某个模式是否与GrantList中已有对象冲突时，可以通过对grantedModes和待加节点的mode进行比较，将时间复杂度从O(n)降到O(1)。

避免饿死

一个锁请求，如果和GrantList无冲突，就将其添加到GrantList中，并加锁成功，否则就加到ConflictList中，并等待grantedModes变更时，从ConflictList中选择一批与grantedModes兼容的加锁请求进入GrantList。 这是很显然的调度策略。不过这个调度策略无法避免一个问题，如果ConflictList中有X锁在等待，而GrantedList中的IS/IX锁源源不断的进来，那么X锁就一直得不到调度。

为了解决这个问题，MongoDB中为加锁操作增加了compatibleFirst参数。

该参数的作用机制如下代码诠

1. 如果锁请求与该锁目前的grantModes冲突，则进入等待，这一点毫无疑问。

2. 207行可以看到如果请求与grantModes不冲突，也未必能加锁成功，还要检验锁资源上的compatibleFirstCount, 该变量可以解释为：锁资源的GrantList中compatibleFirst=true的属性的锁请求的元素的个数。如果GrantList中无compatibleFirst的锁请求，且conflictList非空（有等待的锁请求），则将请求加入到conflictList中。

3. 如果获锁成功，则将锁请求加入到GrantList中，并累加锁资源的compatibleFirstCount计数器。

上述第二点，实则提供了等待优先级的概念。如果所有锁请求的compatibleFirst都为false，则上述算法则可以简述成如下更直接，更容易理解的防饿死控制：

1. 和grantedModes冲突，则进入等待。这一点毫无疑问。

2. 和grantedMode不冲突，但和conflictModes冲突，依然进入等待，这一点防止了饿死。

而mongoDB引入的compatibleFirst属性，可以理解为对该简化版模型的一个优化，引入了等待优先级，而且将优先级的设置暴露给了意向锁的使用者。在mongoDB中，只有Global的S/X锁设置了compatibleFirst=true，其解释如下：

04

死锁检测

MongoDB意向锁的死锁检测基于广度优先遍历(BFS)算法。某个锁请求是否会产生死锁，等价于 “从有向图中的一点出发，是否可以找到一个环”。如何使用BFS算法找有向图的环，不在本文的讨论范围内。在将死锁检测规约为成环问题的过程中，如何构图是关键，如何描述"点"，点与点的依赖关系(边)是什么？读者不妨先自行思考一下。

死锁检测的构图

MongoDB中，一个锁依赖图 G=（V, E）， Vi = (Request, Resource, Mode)， 即图中的一个点的含义为对某个资源的某种模式的锁请求，一个点Vi对另一个点Vj有依赖 当且仅当 Vj 持有 Vi.Resource的锁，且锁模式与Vi.Mode冲突，且Vj 本身也在等待其他资源。概念有点绕，举个例子。

上图中，有三个Lock，分别为Lock1， Lock2， Lock3，Lock1当前持有Res1，在等待Res2, Lock2当前持有Res2，在等待Res3，Lock3 当前持有Res3，在等待Res1。很明显死锁了，但是如何将其转化为有向图，使得计算机能帮我们检测死锁呢。

我们从Lock1 Acquire Res2来看， 由于Res2被Lock2持有，所以Lock1 Acquire Res2 依赖 Lock2 Release Res2。 而Lock2 Release Res2 依赖 Lock2 Acquire Res3， Lock2 Acquire Res3 依赖 Lock3 Release Res3。 如下图所示：

图中Release动作的依赖并不是必须的，可以简化成：

在工程实践中，可以通过GrantList判断某个资源是否被某个锁持有。核心代码如下：

1. 代码框架上，使用_queue进行BFS的迭代。

2. 979行迭代ResourceId对于的Lock的GrantList，如果某个GrantList中的元素也有依赖的Resource，则将其入队。

3. 970行检查node是否为初始入队元素。根据BFS的性质判断是否成环。