专栏首页MongoDB中文社区浅析MongoDB中的意向锁

浅析MongoDB中的意向锁

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冲突,需要对GrantList进行遍历进行冲突检测,这样做是不高效的。

引用计数数组

为了解决这个问题,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的性质判断是否成环。

作者:孔德雨

  • MongoDB中文社区深圳分会主席
  • 现就职于腾讯互娱 技术运营部

本文分享自微信公众号 - Mongoing中文社区(mongoing-mongoing)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • 日访问百万级微信小程序优化技巧总结

    之前负责的锡慧在线小程序是一款公益性质在线教育类小程序,因疫情影响导致流量暴增,日访问过百万

    薛定喵君
    小程序微信缓存RedisCanvas
  • Spiral: 一个性能卓越的PHP/Golang混合开发框架

    春节期间,了解到一个“全新”的 WEB 开发框架:Spiral, 最开始引起我的兴趣是从同事那里听说了 RoadRunner. 然后去了解 RoadRunner 的时候看到了 Spiral. 之所以把“全新”用双引号引起来,是因为这个框架其实从 2013 年起就在它的开发团队以及一些企业客户中应用了,经历了各种实际应用场景的考验,Spiral 的功能及其丰富,性能与当前主流的 PHP 框架相比也相当出众。但这个框架源自俄国,在国内不算知名,他们团队开始重视和梳理开源,也应该是才开始的事情。

    小李刀刀
    PHPGoSymfony
  • kubernetes系列教程(二十)prometheus提供完备监控系统

    上一个章节中kubernetes系列教程(十九)使用metric-server让HPA弹性伸缩愉快运行介绍了在kubernetes中的监控架构,通过安装和使用metric-server提供kubernetes中的核心监控指标:提供node节点和pod容器CPU和内存的监控能力,核心监控指标提供的监控维度和指标相对有限,需要更好的扩展监控能力,需要使用自定义监控来实现,本文介绍prometheus提供更更加丰富的自定义监控能力。

    HappyLau谈云计算
    Kubernetes容器微服务云监控
  • 如何将设计思维应用到精益初创公司的软件开发

    我们所说的设计思维,是指由 IDEO 公司的 Tim Brown 提出,并且正在改变全世界组织的设计思维,简称 DT。(译者注:IDDO,当代最具影响力的设计公司之一)

    Aceyclee
    Serverless无服务器云函数
  • InnoDB 事务加锁分析

    一般大家对数据库事务的了解可能停留在事务的ACID特性以及事务4种不同的隔离级别层面上,而对于事务 4 种不同隔离级别如何实现了解相对较少。

    2020labs小助手
    MySQLSQL数据库MVCMVCC
  • FutureTask 核心源码解析

    研究源码,一般我们都从整体以及实例先入手,再研究细节,不至于一开始就“深陷其中而"当局者迷".

    JavaEdge
    HTTPJava
  • 200行代码落地人脸识别开锁应用

    2019年国庆,帮朋友实现了一个人脸识别进行开锁的功能,用在他的真人实景游戏业务中。几个月来运行稳定,体验良好,借着这个春节宅家的时间,整理一下这个应用的实现过程。

    高树磊
    人脸识别图像处理
  • 滑动验证码攻防对抗

        在业务安全领域,滑动验证码已经是国内继,传统字符型验证码之后的标配。众所周知,打码平台和机器学习这两种绕过验证码的方式,已经是攻击者很主流的思路,不再阐述。冷渗透介绍的是一个冷门的绕过思路和防御方案。这些积累,均来自于实战之中,希望有用。

    周俊辉
    HTTP网络安全安全网站
  • 程序员进阶必读,万字总结Mysql优化精华篇

    price decimal(8,2)有2位小数的定点数,定点数支持很大的数(甚至是超过int,bigint存储范围的数)

    程序员内点事
    全文检索缓存SQL数据库Python
  • 运维转型 | 运维人不再只是“救火英雄”

    各行各业都开启了数字化转型的进程,运维团队在这种时代的浪潮中又该何去何从?我在帮助一些企业落地了运维技术平台之后,开始反思这个问题,并将所思所想整理成本篇文章。

    嘉为科技
    企业运维自动化云计算

扫码关注云+社区

领取腾讯云代金券