【腾讯云CDB】源码分析·MySQL5.7中MDL实现分析-腾讯云开发者社区-腾讯云

【腾讯云CDB】源码分析·MySQL5.7中MDL实现分析

原创

腾讯云数据库 TencentDB

修改于 2019-04-08 20:56:30

2.5K1

修改于 2019-04-08 20:56:30

1. 简介

Metadata Lock，顾名思义，是对元数据的保护。MDL是在5.5中引入的，之前版本对于元数据也有保护，但实现为语句级别的，当语句结束后元数据相关的锁就会被释放掉。这种实现会导致两个主要的问题：

无法实现RR隔离级别，比如以下场景：

tx1: BEGIN;
tx1: SELECT * FROM tbl; -- 获取元数据锁，返回(c1,c2)，释放元数据锁
tx2: ALTER TABLE tbl DROP COLUMN c2; -- 获取元数据锁，成功，释放元数据锁
tx1: SELECT * FROM tbl; -- 返回(c1)，不可重复读
tx1: END;

备库重放经常出错然后停止，比如以下场景：

tx1: BEGIN;
tx1: INSERT INTO tbl(c1, c2) VALUES(v1, v2);
tx2: ALTER TABLE tbl DROP COLUMN c2; -- commit并写入binlog 1
tx1: END; -- commit，写入binlog 2，备库先重放binlog 1，重放binlog 2时出错

于是5.5版本引入了MDL，实现为事务级别，事务中获取的MDL锁在事务提交或回滚时释放，并在后续版本中针对最初实现做了很多优化，包括：

MDL lock hash函数的修改
把保存MDL lock的hash表分区提升并发性能
Lock-free MDL hash table (5.7)
对常用锁模式的Lock-free加锁 (5.7)

本文将介绍5.7中的实现。搜索关注“腾讯云数据库”官方微信立得10元腾讯云无门槛代金券，体验移动端一键管理数据库，学习更多数据库技术实战教程。

2. MDL使用

内核开发过程中有时候需要使用MDL子系统，关于MDL使用有几个重要的概念：

MDL_key, 用来标识要加锁的目标对象，是一个三元组，namespace:db_name:object_name；db_name和object_name很好理解，namespace是一个枚举，表示目标对象的分类，根据namespace判定后续的db_name和object_name的含义以及是否有效。目标对象分为两大类，范围锁(scoped lock)和目标锁(object lock)，常见的范围锁类型包括GLOBAL, SCHEMA, TABLESPACE和COMMIT，常见的目标锁类型主要为TABLE。MDL_key在代码中的定义为：

struct MDL_key
{
  enum enum_mdl_namespace
 ｛
        GLOBAL = 0,         // global范围锁
        TABLESPACE,         // 表空间范围锁
        SCHEMA,             // 数据库范围锁
        TABLE,              // 表目标锁
        ...
        COMMIT,             // commit范围锁
  ｝;
  char m_ptr[];
}

三元组以字符串的方式连续存储在m_ptr中。目标锁理解为当要访问某些具体对象时需要对该目标加元数据锁，范围锁理解为当要进入某些范围内并且会在该范围内造成数据库改动时，需要加范围锁，其中GLOBAL范围锁几乎所有的会造成改动的语句都需要获取，COMMIT锁是在做事务提交之前获取，通过GLOBAL和COMMIT范围锁可以控制SQL语句的进入以及提交(FTWRL实现方式)。搜索关注“腾讯云数据库”官方微信立得10元腾讯云无门槛代金券，体验移动端一键管理数据库，学习更多数据库技术实战教程。

enum_mdl_type，加锁的模式，主要包括：

MDL_INTENTION_EXCLUSIVE           IX         // 只用于范围锁
MDL_SHARED                        S          // 只能读元数据，不能读写表数据，如检查表是否存在时用这个锁
MDL_SHARED_HIGH_PRIO              SH         // 只能读元数据，不能读写表数据，用于填充INFORMATION_SCHEMA，或者SHOW CREATE TABLE时，和S模式区别在于若其他线程持有S锁，且等待队列中有X锁时，可以直接获取锁(S锁需要等待X模式先被授予, SH可以优先于等待队列中的X)
MDL_SHARED_READ                   SR         // 可以读表数据，SELECT语句使用
MDL_SHARED_WRITE                  SW         // 可以写表数据，DML语句和SELECT FOR UPDATE使用
...
MDL_SHARED_UPGRADABLE             SU         // 可升级锁，类似SR，可以读表数据，但可以升级为SNW或者X锁，ALTER TABLE用
...
MDL_SHARED_NO_WRITE               SNW        // 其它线程能读元数据和表数据，但不能写表数据，持锁线程可以读写表数据，可以升级成X锁，ALTER TABLE用
MDL_SHARED_NO_READ_WRITE          SNRW       // 其它线程能读元数据，但不能读写表数据，持锁者可以读写表数据，可以升级成X锁，LOCK TABLES WRITE用
MDL_EXCLUSIVE                     X          // 排它锁，可以写元数据，禁止其它线程读元数据，CREATE/DROP/RENAME/ALTER TABLE用

值得注意的两点：

这里的模式指的是对元数据的锁模式，如果要读写表数据，需要先获取相应的SR模式MDL锁，然后获取相应的table lock才能安全访问数据，比如TL_READ；
IX模式只能用于范围锁，范围锁上能获取的模式只包括IX，S和X；

这几种模式中，SU比较特别，其他的模式都很容易理解。SU特别之处在于它的语义类似SR，但SR和SR之间是兼容的，而SU和SU之间是冲突的。SU的存在是为了解决一类死锁问题。对于某些DDL语句的实现(如ALTER TABLE)，为了不长时间阻塞其他数据库操作，需要先对表获取一个低级别MDL锁以读取数据，然后做一些很耗时的操作，最后关键步骤(如rename)将之前的低级别MDL锁升级为X锁以修改元数据。如果没有SU锁模式的存在，最合适的低级别MDL锁模式即为SR，那么就会存在如下场景：

tx1: acquire SR lock mode
tx2: acquire SR lock mode
tx1: acquire X lock mode

将上述场景中的SR替换为SU就能避免死锁，tx2在获取SU时就会阻塞，因为和tx1持有的SU冲突；5.7中的ALTER TABLE ... ALGORITHM = COPY就是这么实现的，先在打开表时获取SR锁，然后升级为SNW并读取表数据（其他线程不能写入表数据了），构建临时表，在最后rename表阶段升级为X模式。

另一个涉及锁升级的DDL语句是CREATE TABLE，首先获取S模式的MDL锁，用于检查表是否存在，然后升级为X模式并真正建表；它是直接从S升级到X，所以会存在上述的死锁问题，解决方法是代码中加了一个重试逻辑；

各种表模式的核心含义在于它们相互之间的兼容与互斥关系，这种关系可以划分到两类里，范围锁模式的互斥关系和目标锁模式的互斥关系，每一类下又包括两种互斥关系，一种是与已经被授予的锁模式的互斥关系，另一种是与等待队列中锁模式的互斥关系，获取锁时需要先判断是否和已经授予的锁模式冲突，如果不冲突再判断和等待队列中的请求是否冲突，都不冲突才能获取锁。第二个冲突检测的目的是给各种锁模式赋予了优先级，后来的锁只有优先级高于等待队列中的锁才能进行抢占。搜索关注“腾讯云数据库”官方微信立得10元腾讯云无门槛代金券，体验移动端一键管理数据库，学习更多数据库技术实战教程。

冲突矩阵从语义中已经可以推演出来了，具体为：

范围锁互斥矩阵：

           | Type of active   |
 Request |   scoped lock    |
  type   | IS(*)  IX   S  X |
  ---------+------------------+
  IS       |  +      +   +  + |
  IX       |  +      +   -  - |
  S        |  +      -   +  - |
  X        |  +      -   -  - |

  (*) IS和所有范围锁模式兼容，所以并没有相应的实现

           |    Pending      |
 Request |  scoped lock    |
  type   | IS(*)  IX  S  X |
  ---------+-----------------+
  IS       |  +      +  +  + |
  IX       |  +      +  -  - |
  S        |  +      +  +  - |
  X        |  +      +  +  + |

目标锁互斥矩阵：

 Request  |         Granted requests for lock           |
  type    | S  SH  SR  SW  SWLP  SU  SRO  SNW  SNRW  X  |
  ----------+---------------------------------------------+
  S         | +   +   +   +    +    +   +    +    +    -  |
  SH        | +   +   +   +    +    +   +    +    +    -  |
  SR        | +   +   +   +    +    +   +    +    -    -  |
  SW        | +   +   +   +    +    +   -    -    -    -  |
  SWLP      | +   +   +   +    +    +   -    -    -    -  |
  SU        | +   +   +   +    +    -   +    -    -    -  |
  SRO       | +   +   +   -    -    +   +    +    -    -  |
  SNW       | +   +   +   -    -    -   +    -    -    -  |
  SNRW      | +   +   -   -    -    -   -    -    -    -  |
  X         | -   -   -   -    -    -   -    -    -    -  |


 Request  |         Pending requests for lock          |
  type    | S  SH  SR  SW  SWLP  SU  SRO  SNW  SNRW  X |
  ----------+--------------------------------------------+
  S         | +   +   +   +    +    +   +    +     +   - |
  SH        | +   +   +   +    +    +   +    +     +   + |
  SR        | +   +   +   +    +    +   +    +     -   - |
  SW        | +   +   +   +    +    +   +    -     -   - |
  SWLP      | +   +   +   +    +    +   -    -     -   - |
  SU        | +   +   +   +    +    +   +    +     +   - |
  SRO       | +   +   +   -    +    +   +    +     -   - |
  SNW       | +   +   +   +    +    +   +    +     +   - |
  SNRW      | +   +   +   +    +    +   +    +     +   - |
  X         | +   +   +   +    +    +   +    +     +   + |

enum_mdl_duration，锁获得后持续的时间范围

enum enum_mdl_duration
{
  MDL_STATEMENT         // 语句结束释放
  MDL_TRANSACTION       // 事务结束释放
  MDL_EXPLICIT          // 需显式释放
}

MDL_request，一次锁请求的封装，包括上述提到的锁的各种属性，通过填充type, duration和key字段再调用锁获取接口

class MDL_request
{
  enum enum_mdl_type type;
  enum enum_mdl_duration duration;
  MDL_ticket *ticket; // 返回的锁获取结果
  MDL_key key;
}

3. MDL实现

3.1 实现锁的基本要素

在介绍MDL锁实现之前，有一些关于锁的背景先介绍一下。在各种不同的锁的实现中，个人认为有两个非常关键的基本要素：

基本的原子操作锁的目的是为了保护一块临界区，该临界区会被并发访问到，要么是进程并发访问，要么是线程并发访问。锁最本质的核心是一个布尔变量，为0或者1，为0时表示临界区现在没有被访问，为1时表示临界区正在被访问。各种锁的实现都是在这个0/1版本基础上的扩展。当一个并发要访问临界区时，先检查锁变量，若为0则将锁变量置为1，否则暂时不能访问临界区，这个过程就是获取锁。但有个关键问题是，锁变量本身是被并发访问的，它自身就是一块临界区，所以必须保证0/1这块临界区是被保护读写的才能保证锁逻辑的正确。一般的实现方式是用一个机器支持的原子数据类型存储这个0/1变量，并通过TAS或CAS这类原语来原子地读取并改写该变量，大部分机器会提供原子读写指令来实现TAS或CAS原语，比如xchg和cmpxchg，对于不提供这类指令的机器，可以使用汇编语法中的LOCK前缀，通过锁住CPU和内存之间总线的方式实现原语的逻辑。搜索关注“腾讯云数据库”官方微信立得10元腾讯云无门槛代金券，体验移动端一键管理数据库，学习更多数据库技术实战教程。
等待队列，睡眠和唤醒通过原子操作可以实现最简单的自旋锁，在代码逻辑中，除非是持锁时间非常短的场景，大多数场景下，为了更好利用CPU，当锁获取失败时不会选择循环重试，而是将自己挂起到一个等待队列上并让出CPU，等持锁的进程或者线程释放锁的时候会检查等待队列，并从上面摘取一个进程/线程，授予该锁，并唤醒它。等待队列一般通过自旋锁保护。这个过程的关键是等待队列的维护，以及进程/线程的睡眠和唤醒。
PostgreSQL通过上述的原子操作实现了spin lock，并用spin lock来保护一个自己维护的等待队列，进而实现了轻量级锁LWLock，进程的睡眠和唤醒用的是Posix semaphore或者System V semaphore，Posix semaphore是通过系统调用futex()实现的，System V semaphore是通过系统调用semop()实现的，都是利用内核提供的接口实现调度；
MySQL对于上述两个基本要素的实现都是依赖于libpthread提供的接口，包括pthread_mutex_t, pthread_cond_t, pthread_rwlock_t等，通过查看glibc中nptl模块的代码可以看到，libpthread也是通过上述的汇编调用实现基本原子操作，并将等待队列，线程睡眠和唤醒都交给内核实现，通过系统调用futex()的方式。主要的调用栈为：

__pthread_mutex_lock --> LLL_MUTEX_LOCK(macro) --> lll_lock(mutex->__data.__lock) --> assembly checking contension |__ __lll_lock_wait --> lll_futex_wait(macro) --> lll_futex_timed_wait(macro) --> syscall futex

__pthread_cond_wait --> lll_lock(cond->__data.__lock)
                    |__ __pthread_mutex_unlock_usercnt(mutex)
                    |__ cond->__data.__futex++ // integer
                    |__ cond->__data.__mutex = mutex // save the mutex for re-acquiring later
                    |__ futex_val = cond->__data.__futex
                    |__ lll_unlock(cond->__data.__lock)
                    |__ lll_futex_wait(&cond->__data.__futex, futex_val)(macro) --> ll_futex_timed_wait --> syscall futex

除此之外，MySQL在MDL中还自己维护了一个等待队列，具体在MDL_lock::m_waiting中 3.2 MDL具体实现

代码中的重要数据结构和类定义包括：

class MDL_ticket: public MDL_wait_for_subgraph // 一次锁请求的结果，可能是获取成功，可能是获取不成功需要等待
{
    enum enum_mdl_type m_type; // 锁模式
    enum enum_mdl_duration m_duration; // 持续时间

    MDL_context *m_ctx; // 对应的线程
    MDL_lock *m_lock; // 对应的锁
}

class MDL_wait // 等待行为的抽象，实现等待逻辑
{
    enum enum_wait_status m_wait_status; // 等待状态
    mysql_mutex_t m_LOCK_wait_status; // 保护m_wait_status的mutex
    mysql_cond_t m_COND_wait_status; // 当m_wait_status发生变化时线程唤醒用的pthread_cond_t，睡眠唤醒逻辑的封装

    timed_wait() // pthread_cond_t的经典用法，实现睡眠等待
    {
        mysql_mutex_lock();
        while(!m_wait_status)
        {
            mysql_cond_timedwait();
        }
        mysql_mutex_unlock();
    }
}

class MDL_context // 代表每个请求锁的线程
{
    /*
     * ... 线程对于MDL锁子系统的各种接口函数声明
     */
    MDL_wait m_wait; // 用于实现等待行为
    Ticket_list m_tickets; // 线程获得的所有锁
    MDL_wait_for_subgraph *m_waiting_for; // 正在等待的锁，同一时间只会有一个
}

class MDL_map // 全局变量，用于存储所有的锁
{
    LF_HASH m_locks; // Lock-free hash table，存储除COMMIT和GLOBAL外所有锁
    MDL_lock *m_global_lock; // GLOBAL范围锁，全局只一个
    MDL_LOCK *m_commit_lock; // COMMIT范围锁，全局只一个
}

class MDL_lock // 标识每个锁，和unique MDL_key一对一, 不管duration和锁模式
{
    MDL_key key;
    mysql_prlock_t m_rwlock; // 保护内部成员的rwlock, prefer reader, self-implemented using pthread_mutex_t, and pthread_cond_t; 

    Ticket_list m_granted; // 已经授予的请求
    Ticket_list m_waiting; // 等待这个锁的请求

    // fast path releated
    volatile fast_path_state_t m_fast_path_state; // flag和counter的组合, for atomic operations, use fast_path_state_cas()/add()/reset() wrappers

    struct MDL_lock_strategy
    {
        bitmap_t m_granted_incompatible; // 互斥矩阵
        bitmap_t m_waiting_incompatible; // 互斥矩阵
        fast_path_state_t m_unobtrusive_lock_increment[MDL_TYPE_END]; // longlong, base_increment, 0 means obtrusive mode
    }
    static const MDL_lock_strategy m_scoped_lock_strategy; // static, members hard-coded, IMPORTANT
    static const MDL_lock_strategy m_object_lock_strategy; // static, members hard-coded, IMPORTANT
}

MDL子系统的初始化调用栈为：

#0 MDL_map::init
#1 mdl_init
#2 init_server_components
#3 mysqld_main
#4 main

锁获取的流程为：

首先调用try_acquire_lock_impl尝试获取锁，如果获取成功则返回；如果不能获取，则将代表这次锁获取的MDL_ticket加入到对应MDL_lock的等待队列中，然后调用deadlock detector的接口find_deadlock()检查是否存在死锁，如果不存在则调用MDL_wait的成员函数睡眠，等待别的线程唤醒；唤醒后检查是否被授予了锁（有可能是等待超时或者被其他线程检测出死锁并标记为victim，或者收到了kill），并做相关的清理工作。
在try_acquire_lock_impl中，首先通过find_ticket()判断目标锁是否之前已经被获取过，如果是，直接返回，否则构造一个MDL_ticket用于保存获取结果；
然后从全局的lock-free哈希表中查找或插入对应的MDL_lock对象，并判断要获取的锁模式是否可以走fast path的代码路径，这里将锁模式划分为两类：
obstrusive mode: 重量级锁，不能走lock-free代码路径
nonobtrusive mode: 轻量级锁，可以走lock-free代码路径，只包括IX, S, SH, SR和SW，被DML使用，互相之间不冲突

代码中用一个原子数据类型变量m_fast_path_state的各个比特位段记录各种nonobtrusive锁的授予计数，以及当前锁上是否授予过obtrusive mode锁，由于obtrusive mode锁之间不冲突，如果之前被授予的锁模式全部为nonobtrusive mode，则可以直接原子地将相应模式的授予计数加一即可成功获取锁，在这个代码路径中，整个锁获取过程只原子地操作m_fast_path_state, 是lock free的，即为fast path优化；

对于不能走fast path的情况，会首先获取MDL_lock中的读写锁，记录相关的状态，然后调用can_grant_lock()分别检查MDL_lock中的授予队列和等待队列的冲突矩阵，判断是否可以获取锁；如果不能，将当前ticket保存在out_ticket中，并保持MDL_request.ticket为空；注意获取失败情况下从try_acquire_lock_impl()中返回时是持有MDL_lock中的读写锁的。
整个过程中不管加锁成功失败都会记录很多的状态信息，比如上述数据结构和类中的MDL_lock.m_granted, MDL_lock.m_waiting, MDL_context.m_waiting_for, MDL_context.m_tickets，MDL_ticket.m_ctx, MDL_ticket.m_lock, 三者之间通过这些成员变量形成关联。记录这些信息的目的是为死锁检测提供线索，后面章节会具体介绍死锁检测机制。
调用栈为：

acquire_lock --> try_acquire_lock_impl --> find_ticket // check if we have already hold this lock, MDL_contex::m_tickets, similar to PG locallock
             |                         |__ clone_ticket // if duration is not same
             |                         |__ fix_pins // get LF_PINS for lock-free hash access
             |                         |__ MDL_ticket::create // m_lock is null now
             |                         |__ get_unobtrusive_lock_increment
             |                         |__ retry label
             |                         |__ mdl_locks.find_or_insert(m_pins, key, &pinned) // pinned must be true for non-singleton locks, i.e, "locked"
             |                         |__ fast path branch --> old_state = lock->m_fast_path_state // save instant one
             |                         |                    |__ do{old_state flag checks} while(!lock->fast_path_state_cas(&old_state, old_state + unobtrusive_lock_increment)) // cas would update old_state if not equal, after get out from this loop, lock is granted
             |                         |                    |__ cleanups: lf_hash_search_unpin, save lock in ticket->m_lock, append the ticket to MDL_context::m_tickets, set mdl_request->ticket
             |                         |__ slow path branch --> mysql_prlock_wrlock(&lock->m_rwlock) // protecting list and counters
             |                                              |__ lf_hash_search_unpin // m_rwlock can protect the lock object now
             |                                              |__ do{} while(!lock->fast_path_state_cas()) // to mark HAS_SLOW_PATH and optional HAS_OBTRUSIVE
             |                                              |__ ticket->m_lock = lock
             |                                              |__ if lock->can_grant_lock --> lock->m_granted.add_ticket(ticket) // can_grant_lock checks granted, fast-path granted, and waiting bitmaps
             |                                              |                           |__ mysql_prlock_unlock
             |                                              |                           |__ append the ticket to MDL_context::m_tickets
             |                                              |                           |__ set mdl_request->ticket = ticket
             |                                              |__ else *out_ticket = ticket // not successful, HOLDING the m_rwlock
             |__ check mdl_request->ticket and return if granted
             |__ lock->m_waiting.add_ticket(ticket) // add itself to waiting list
             |__ m_wait.reset_status() // under protection of m_rwlock
             |__ mysql_prlock_unlock
             |__ MDL_context::m_waiting_for = ticket // inform deadlock detector, will_wait_for()
             |__ find_deadlock
             |__ m_wait.timed_wait() // two classes, one(with high prio) would notify other threads to release locks, then wait; the other would just wait
             |__ MDL_context::m_waiting_for = NULL // done_waiting_for()
             |__ check wait_status and clean up

释放锁的逻辑相较于获取简单：

首先判断锁获取时是否通过fast path，如果是则原子地将m_fast_path_state中相应比特位的授予计数减一，并调用reschedule_waiters()唤醒一个线程（将锁授予该线程）；
如果是slow path，则获取MDL_lock中的rwlock，将自己从授予链表m_granted上移除，并更新m_fast_path_state中的相应标记位，然后调用reschedule_waiters()唤醒一个线程（将锁授予该线程）；
reschedule_waiters()进入时是一定持有MDL_lock的rwlock的，该函数遍历MDL_lock.m_waiting链表，对每个元素调用can_grant_lock()检查互斥矩阵判定是否可以授予该锁，如果可以则将该线程的m_wait_status修改并调用pthread_cond_signal()唤醒线程（将锁授予该线程），并帮助该线程更新MDL_lock中的状态信息；
调用栈为：

release_lock --> if ticket->m_is_fast_path --> get_unobtrusive_lock_increment
             |                             |__ old_state = lock->m_m_fast_path_state
             |                             |__ do{mysql_prlock_wrlock();reschedule_waiters();mysql_prlock_unlock()} while(!lock->fast_path_state_cas())
             |__ slow path --> lock->remove_ticket --> mysql_prlock_wrlock()
             |                                     |__ remove_ticket
             |                                     |__ update flags, fast_path_state_cas()
             |                                     |__ reschedule_waiters()
             |                                     |__ mysql_prlock_unlock()
             |__ MDL_context::m_tickets.remove()
             |__ MDL_ticket::destroy()

reschedule_waiters(rwlock held) --> iterate m_waiting --> can_grant_lock --> yes --> m_wait.set_status(GRANTED) --> mysql_mutex_lock()
                                                                                 |                              |__ m_wait_status = status_arg
                                                                                 |                              |__ mysql_cond_signal()
                                                                                 |                              |__ mysql_mutex_unlock()
                                                                                 |__ cleanups, m_waiting.remove_ticket, m_granted.add_ticket

其他的一些MDL接口都是基于这两个基本操作实现的，比如MDL_context::upgrade_shared_lock()是调用MDL_context::acquire_lock()获取新的ticket，并移除老的ticket；MDL_context::release_locks_stored_before()是循环调用MDL_context::release_lock()，实现锁获取的回滚。

4. 死锁检测

上面章节中提到了锁获取过程中，线程在进入睡眠状态前会调用find_deadlock()检测是否存在死锁。死锁产生的根本原因是线程在持有锁的同时去等待另一个锁，所以就会存在线程之间的依赖关系，如果依赖关系中出现了环，则产生了死锁。

上面章节还提到，MDL_context, MDL_ticket和MDL_lock中存了很多状态信息，这些状态信息是死锁检测的依据。死锁检测过程具体为：

每一个MDL_context只能等待在一个锁上，记录在MDL_context.m_waiting_for(MDL_ticket类型)中；该MDL_ticket记录了所等待的MDL_lock，记录在MDL_ticket.m_lock中；而MDL_lock中记录了该锁授予的线程和等待在该锁上的线程，分别在m_granted和m_waiting中；
所以我们可以推算出当前MDL_context（线程）所依赖的那些MDL_context，将这个依赖关系形成一个有向图，并从图中一点出发遍历这个图，如果遍历过程中再次遇到了当前MDL_context，则表示图中有环，即存在死锁;
在这个环里，可以找出"权重"最低的MDL_context(权重通过MDL_ticket::get_deadlock_weight()获得)，将它选为victim，即让他放弃正在获取的和已经持有的锁，至少移出依赖图中的一个节点；
循环这个选择victim并移出的过程，直到依赖图中不存在环；
在遍历依赖图时，会首先检查距离为1的所有直接相邻MDL_context，如果没有环则用深度优先搜索的方式递归地检查相邻MDL_context，并用一个Deadlock_detection_visitor类做context类记录整个遍历过程的中间变量，以及起始MDL_context；整个遍历过程可以看作是DFS加一个步长为1的BFS优化；
值得注意的是，每个MDL_lock上不止授予链表中的元素需要检测是否存在依赖边，等待链表中的元素也需要，因为MySQL通过等待互斥矩阵实现了锁授予的优先级；这点和PostgreSQL不一样，PostgreSQL只有一个互斥矩阵(存储在静态结构LockConflicts中)，优先级是通过FIFO的方式体现的；相应的，MySQL也不存在PostgreSQL因为FIFO带来的soft edge和hard edge的概念，进而不存在死锁检测中通过调整等待队列中元素顺序去除soft edge来试图消除死锁的实现；
死锁检测不止检查MDL带来的等待关系，还检查其他如TABLE_SHARE带来的等待，都被抽象在MDL_wait_for_subgraph父类中；

调用栈为：

MDL_context::find_deadlock --> while(1) --> Deadlock_detection_visitor // each round would spot one victim, remove one node from graph
                                        |__ MDL_context::visit_subgraph --> MDL_ticket::accept_visitor --> MDL_lock::visit_subgraph --> mysql_prlock_rdlock(&m_rwlock)
                                        |                                                                                           |__ enter_node // depth++, if overflow, terimate and say deadlock found
                                        |                                                                                           |__ BFS direct neibors, including granted and waiting, inspect_edge() --> check if it is starting MDL_context
                                        |                                                                                           |__ DFS neibors, including granted and waiting, recursive MDL_context::visit_subgraph
                                        |                                                                                           |__ leave_node // depth--
                                        |                                                                                           |__ mysql_prlock_unlock
                                        |__ set victim m_waiting_status VICTIM

5. Lock-free Hash Table

上面章节也提到了，所有的锁对象(除了COMMIT和GLOBAL)都存放在一个全局的hash表中(LF_HASH)，这个hash表是实现为lock-free的。在5.7之前的版本中，hash表被实现为带分区的形式，但访问需要加锁。LF_HASH的实现是很经典的lock-free数据结构实现方式：用Copy-on-Write的方式，每次需要修改共享对象时都重新构造一个新的对象，然后原子地将指向对象的全局指针替换掉。这种方式有个问题是旧对象内存什么时候释放，如果在指针替换后立即释放，之前线程可能会在内存free掉之后还会通过之前存在local的指针访问该对象，那么就可能会出现segment fault。搜索关注“腾讯云数据库”官方微信立得10元腾讯云无门槛代金券，体验移动端一键管理数据库，学习更多数据库技术实战教程。

解决这个问题的方法有很多：

一个类别是用引用计数，但引用计数的问题是访问全局指针和通过全局指针访问对象中的引用计数不能是原子的，那么就会存在如下race condition：

thd1: save object pointer to register(old one)

还是没能避免segment fault；进一步解决这个问题的方式是用一个独立的读写锁保护引用计数，或者引入一个中间层结构体，给每个结构体加一个版本号，将引用计数和版本号一起存放在一个原子数据类型中，并通过原子读写指令在写之前判断版本和读时是否一致，通过这种方式将保护引用计数的读写锁去掉。后者的关键在于中间层结构体需要在并发周期内一直可访问，所以中间层结构体需要专门的分配器。
另一个类别的方法被称作harzard pointer，也是LF_HASH所采用的方式。不同于引用计数，每个线程在访问全局指针(这个共享的全局指针即为harzard pointer)前，先将该指针存放在一个全局变量中(每个线程有一个全局变量)，访问结束后将该变量置为NULL，当发生全局指针替换时，遍历所有的线程，看被覆盖版本的指针是否还在被其他线程访问，如果没有任何线程访问，则free该指针指向的内存。工程实现上，为了提升性能，会批量释放内存，判断一批指针是否可被free。
在MySQL中，定义了LF_PINS来记录线程所访问的指针，用LF_PINBOX来管理所有的pin，当替换一个全局指针时，将其添加到名为purgatory的链表中，当purgatory中指针超过一定数量时批量遍历LF_PINBOX中每个线程的记录，决定是否释放指针指向的内存。内存管理抽象为LF_ALLOCATOR类，是一个内存池，当要分配新的对象时，从LF_ALLOCATOR中获取，如果LF_ALLOCATOR的free stack不为空，则从stack上返回一个对象的内存，否则从LF_DYNARRAY中获取新的对象内存。当没有任何线程访问某个对象时，会将内存归还到LF_ALLOCATOR的free stack上。在此之上，实现了LF_HASH，每个元素的最新版本指针被保存在LF_DYNARRAY中(在MDL子系统中每个元素为指向MDL_lock对象的指针)，所有元素内存，包括旧的但还在被某些线程引用的版本，都由LF_ALLOCATOR管理。每个元素有最多4个pin，pin[0]和pin[1]一般用作临时用途，pin[2]是一般意义上的harzard pointer中的本地版本。每次通过lf_hash_search()读取一个hash表中的元素时，将该元素指针保存在pin[2]中，访问结束，通过调用lf_hash_search_unpin()将pin[2]置为NULL；简单来说，LF_HASH的实现，一是通过每个元素指针的原子赋值操作保证并发下的正确性，二是通过LF_PINBOX来安全回收内存。值得一提的是，harzard pointer实现中在保存全局指针到本地时有一个经典的double check逻辑：

void *g_hp_local_array[MAX_THREAD_ID]; // global

void *ref = NULL;

while(1)
{
  ref = g_ptr; // save global pointer locally             //1
  g_hp_local_array[thread_id] = ref;                      //2

  if (ref == g_ptr) // not overriden, safe now on         //3
        break;
}
// the double check is very important, if thd1 executes line 1, then is scheduled before line 2, then thd 2
// find no reference for the old g_ptr in g_hp_local_array, so frees the object, then thd1 gets back to line 2

这个逻辑在MySQL中也是存在的，可以在my_lfind()函数中看到