Tachikoma blog

Email | Weibo | Github

整理一下最近读的MDL源码

Fri, Apr 4, 2014

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

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的许可或请求, 会同时挂在两处:

  1. 挂在所属MDL_Context中, 通过MDL_ticket.next_in_context/prev_in_context组织链表
  2. 挂在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是冗余的信息, 至于原因源代码中有解释, 此处不冗余说明…

如何释放锁

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

  1. 将ticket从MDL_lock的数据结构上卸下来
  2. 调度选择新的锁占有者
  3. 将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, 此处忽略细节

comments powered by Disqus