整理一下最近读的MDL源码

以下都是个人理解, 如有疏漏请斧正另, 因为理解不深, 将忽略锁级别以及锁共享的细节

MDL

MDL (Metadata lock), 除了正常的Condition var提供的功能外, 还额外提供了 1. 不同的锁级别. 在不冲突的情况下, 允许共享资源 2. 死锁检查和处理 3. 记录等待状态, 是死锁检查的基础

模型

MDL_lock 表示Mysqld中的一个资源(库/表/…) 存储在全局结构 mdl_locks (MDL_map)中, mdl_locks内有m_partitions (锁的分区), 用来分散查找lock时的竞争

MDL_context 为MDL上下文接口, 表示一个资源竞争者, THD实现了这个接口, 即一个Mysqld的线程可以是MDL_lock的资源竞争者

MDL_ticket 表示MDL_lock的许可或请求, 会同时挂在两处:

挂在所属MDL_Context中, 通过MDL_ticket.next_in_context/prev_in_context组织链表
挂在MDL_lock的队列中, 通过MDL_ticket.next_in_lock/prev_in_lock组织链表. MDL_lock的队列分为两种, 一个MDL_ticket可能会挂在其中之一
- 挂在MDL_lock的等待队列(MDL_lock.m_waiting)中, 表示MDL_ticket的owner (MDL_context)正在等待该资源(MDL_lock)
- 挂在MDL_lock的已许可队列(MDL_lock.m_granted)中, 表示MDL_ticket的owner (MDL_context)已经获得该资源(MDL_lock)

总结一下, MDL_context和MDL_ticket的关系是一对多, 一个竞争者可以同时申请/获得多个资源的许可; MDL_ticket和MDL_lock的关系是多对一, 可以同时有多个资源许可在竞争一个资源, 或者多个资源许可可以有条件地共享一个资源

如何获得锁

简单分析MDL_context::acquire_lock方法, 其主要流程是

bool MDL_context::acquire_lock(MDL_request *mdl_request, ulong lock_wait_timeout) {
    ...

    try_acquire_lock_impl(...) 
    //尝试不等待立刻获得资源, 如果成功直接返回
    //以下是等待资源的处理
    ...
    lock->m_waiting.add_ticket(ticket) 
    //将一个资源申请`ticket`挂入资源`lock`的等待队列`m_waiting`
    if (lock->needs_notification(ticket)) {
        //如果等待资源时需要通知状态, 则不断轮询并通知
        //将忽略此处的细节
        ...
    } else {
        //等待资源
        //结果可能是获得资源, 或者超时, 或者异常 (比如被死锁检测机制判定死亡)
        //`timed_wait`中的实现是等待COND(条件变量)`m_wait.m_COND_wait_status`
        wait_status= m_wait.timed_wait(...);
    }
    //收尾处理
    m_tickets[mdl_request->duration].push_front(ticket)
    //将资源申请`ticket`挂入`MDL_Context.m_tickets`
    ...
}

记录等待状态

之前提到了记录等待状态, 在MDL_context::acquire_lock方法中可以看到如下代码 (上一节未列出)

bool MDL_context::acquire_lock(MDL_request *mdl_request, ulong lock_wait_timeout) {
    m_wait.reset_status();
    ...
    will_wait_for(ticket); //其中设置了`m_waiting_for`
    if (lock->needs_notification(ticket)) {
        ...
        //等待资源
        wait_status= m_wait.timed_wait(m_owner, &abs_timeout, TRUE,
                                  mdl_request->key.get_wait_state_name());
    } else {
        //等待资源
        wait_status= m_wait.timed_wait(m_owner, &abs_timeout, TRUE,
                                  mdl_request->key.get_wait_state_name());
    }
    done_waiting_for(); //其中清空了`m_waiting_for`
    ...
}

可以看到MDL_context.m_wait是用来等待资源的工具类, 其中进行等待处理, 并记录等待资源的状态/结果.

还有一个MDL_context.m_waiting_for也在记录MDL_context正在进行的资源申请(MDL_ticket), 其正在等待某个资源. 实际上m_waiting_for是冗余的信息, 至于原因源代码中有解释, 此处不冗余说明…

如何释放锁

释放锁, 需要完成下面几个动作:

将ticket从MDL_lock的数据结构上卸下来
调度选择新的锁占有者
将ticket从MDL_context的数据结构上卸下并回收

入口为MDL_context::release_lock

void MDL_context::release_lock(enum_mdl_duration duration, MDL_ticket *ticket) 
{
    ...
    lock->remove_ticket(&MDL_lock::m_granted, ticket) {
        //将`ticket`从`MDL_lock`的数据结构上卸下来
        (this->*list).remove_ticket(ticket);
        ...
        //调度选择新的锁占有者
        reschedule_waiters();
    }()

    //将`ticket`从`MDL_context`的数据结构上卸下并回收
    m_tickets[duration].remove(ticket);
    MDL_ticket::destroy(ticket);
    ...
}

下面说明调度的细节

释放锁时的调度

调度函数的入口是MDL_lock::reschedule_waiters

最简单的调度就是从MDL_lock.m_waiting队列中取出头元素, 直接将资源调度给头元素即可

Mysqld在此基础上添加了一个退让条件: 如果资源连续被高优先级(比如SNW/SNRW/X锁类型)的ticket获得, 那么退让一步, 允许资源间隔被调度给低优先级的ticket防止其饿死.

用MDL_lock::reschedule_waiters的代码说就是, 如果MDL_lock被连续分配给hog_lock_types_bitmap()中定义的高优先级类型的ticket,连续的次数m_hog_lock_count超过max_write_lock_count, 那么开启退让条件, 批准第一个非高优先级的ticket获得资源

死锁检测

死锁检测的入口是MDL_context::find_deadlock, 本身原理很简单, 但源码写的很复杂= =. 先说明原理, 再对应源码

设当前MDL_context为图的一个节点A, 从节点A出发, 找到A的正在等待的资源L(A.m_waiting_for.m_lock)中的m_granted里的每一个MDL_ticket对应的MDL_context B, 表示A正在等待B释放资源L. 在图中A -> B 添加一条有向边

死锁检查的工作就是遍历这张有向图, 检查其是否存在环路

以MDL_context::find_deadlock入口, 展开一些调用来说明代码

(MDL_context::find_deadlock)
while(1) {
    visit_subgraph(visitor) {
        m_waiting_for->accept_visitor(visitor) {
            m_lock->visit_subgraph(this, visitor) {
                ...
            }()
        }()
    }()
    break if no deadlock
    set deadlock victim
    break if deadlock victim is current context
}

可以看到find_deadlock以MDL_context.m_waiting_for.m_lock为起始点, 不断遍历其有向图, 选出victim. 直到 * 没有发现死锁 * 或自己被选为victim

其使用一个visitor (MDL_wait_for_graph_visitor) 贯穿遍历过程, 其记录了遍历的过程

再来看MDL_lock::visit_subgraph, 此函数是以一个MDL_lock为起点, 来遍历依赖图

MDL_lock::visit_subgraph(MDL_ticket *waiting_ticket, MDL_wait_for_graph_visitor *gvisitor) {

    //此处是因为MDL_context.m_waiting_for是冗余信息, 但无法保证更新同步, 带来的额外操作. 忽略此处细节
    if (src_ctx->m_wait.get_status() != MDL_wait::EMPTY) {...}

    //visitor用来记录遍历层次
    //当遍历层次大于MAX_SEARCH_DEPTH(32), 也认为发现死锁
    if (gvisitor->enter_node(src_ctx)) {...}

    //由于现在是以一个资源(`MDL_lock`)为视角, 之后的检查为了效率, 遍历会从两个方向同时进行, 即检查节点的出度方向(`MDL_lock.m_granted`)和节点的入度方向(`MDL_lock.m_waiting`). 


    //为了效率, 死锁检测会先检测距离为1的临近节点, 而先不深度遍历图

    while ((ticket= granted_it++))
    {
      if (ticket->get_ctx() != src_ctx &&
          ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
          gvisitor->inspect_edge(ticket->get_ctx()))
      {
        goto end_leave_node;
      }
    }

    while ((ticket= waiting_it++))
    {
      /* Filter out edges that point to the same node. */
      if (ticket->get_ctx() != src_ctx &&
          ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
          gvisitor->inspect_edge(ticket->get_ctx()))
      {
        goto end_leave_node;
      }
    }

    //此处开始, 深度遍历图

    granted_it.rewind();
    while ((ticket= granted_it++))
    {
      if (ticket->get_ctx() != src_ctx &&
          ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
          ticket->get_ctx()->visit_subgraph(gvisitor))
      {
        goto end_leave_node;
      }
    }

    waiting_it.rewind();
    while ((ticket= waiting_it++))
    {
      if (ticket->get_ctx() != src_ctx &&
          ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
          ticket->get_ctx()->visit_subgraph(gvisitor))
      {
        goto end_leave_node;
      }
    }
    ...

    //visitor退栈
    gvisitor->leave_node(src_ctx);
    ...
}

发现死锁后, 会调用Deadlock_detection_visitor::opt_change_victim_to, 其中进行MDL_context权重比较, 来选取一个作为victim, 此处忽略细节

Tac say

只想做个程序演奏家