Contention-Aware Lock Scheduling 和 （b）LDSF 算法

基本模型

论文里是一个高度形式化¹的模型，容易看得头大，然后图形表示里箭头指向的含义也很奇怪……²，其实主体就是一个 trival 的事务的等待关系图，我把这模型稍微改了下应该会比较好理解。

等待关系图

节点

对象

指可以被事务锁定的资源，用圆圈表示。

事务

就是通常理解的事务，用圆角矩形表示。

边

持锁

事务指向对象的实线箭头指事务锁定了这个对象。

等锁

事务指向对象的虚线箭头指事务等待锁定这个对象。

共享锁和排他锁

在对应的边上写 X 或者 S。

目标

目标就是找到一个算法，让所有事务的总运行时间的期望值最短。

由于共享锁的存在，这样的算法是 NP 难的（具体见原论文的参考文献）。

因此这篇论文提出了一个近似算法。

LDSF 算法

基本思想就是让（现在） block 了更多其他事务的事务先拿到锁。

例如下面的等待关系图：

digraph {
    O1[label="O1", shape="circle"];
    t1 -> O1[label="X",style="dashed"];
    t2 -> O1[label="X",style="dashed"];
    subgraph cluster_t1 {
        label = "t1";
        t1[label="t1", shape="Mrecord"];

        O2[label="O2", shape="circle"];
        O3[label="O3", shape="circle"];
        O4[label="O4", shape="circle"];
        t1 -> O2;
        t1 -> O3;
        t1 -> O4;

        t3[label="t3", shape="Mrecord"];
        t4[label="t4", shape="Mrecord"];
        t5[label="t5", shape="Mrecord"];
        t6[label="t6", shape="Mrecord"];
    
        t3 -> O2[label="",style="dashed"];
        t4 -> O2[label="",style="dashed"];
        t4 -> O3[label="",style="dashed"];
        t5 -> O4[label="",style="dashed"];
        t6 -> O4[label="",style="dashed"];
    }

    subgraph cluster_t2 {
        label = "t2";
        t2[label="t2", shape="Mrecord"];
        O5[label="O5", shape="circle"];
        O6[label="O6", shape="circle"];
        t2 -> O5;
        t2 -> O6;

        t7[label="t7", shape="Mrecord"];
        t8[label="t8", shape="Mrecord"];
        t9[label="t9", shape="Mrecord"];

        t7 -> O5[label="",style="dashed"];
        t8 -> O6[label="",style="dashed"];
        t9 -> O6[label="",style="dashed"];

        O7[label="O7", shape="circle"];
        O8[label="O8", shape="circle"];
        O9[label="O9", shape="circle"];

        t7 -> O7[label="",style="dashed"];
        t7 -> O8[label="",style="dashed"];
        t8 -> O9[label="",style="dashed"];
        t9 -> O9[label="",style="dashed"];
    }
}

上一个锁定 O1 的事务已经完成，现在希望锁定 O1 的事务有 t1 和 t2。

观察等待关系图可以发现, t1 已经 block 了 t3-t6 共 4 个事务，而 t2 只 block 了 3 个事务，因此我们的算法会让 t1 先持有这个锁。

我们定义某个事务的“依赖集合”为其所有的直接或间接阻塞的事务（包含其本身）。

优先级的计算

要加排他锁的事务

LDSF 算法中，要加排他锁的事务的优先级是其依赖集合的大小。

要加共享锁的事务

由于共享锁是“共享”的，出于方便考虑 LDSF 算法会一次性让所有要加共享锁的事务拿到锁。因此，要加共享锁的事务整体的优先级就是所有要加共享锁的事务的依赖集合的并集的大小。

LDSF 会让优先级最高（大）的事务（或者事务集合，如果是共享锁的话）成功加上锁。

改进：bLDSF 算法

LDSF 算法一次性让所有要加共享锁的事务拿到锁，如果有其中某个事务长期持有某个资源上的共享锁，而其他事务在等着锁定这个资源，系统整体的效率会变得很烂。

例如：

digraph {
    O[label="O", shape="circle"];
    t1 -> O[label="S",style="dashed"];
    t2 -> O[label="S",style="dashed"];
    t3 -> O[label="S",style="dashed"];
    t4 -> O[label="X",style="dashed"];
    subgraph cluster_t1 {
        label = "t1, size=6";
        t1[label="t1", shape="Mrecord"];
    }
    subgraph cluster_t2 {
        label = "t2, size=1";
        t2[label="t2", shape="Mrecord"];
    }
    subgraph cluster_t3 {
        label = "t3, size=1";
        t3[label="t3", shape="Mrecord"];
    }
    subgraph cluster_t4 {
        label = "t4, size=5";
        t4[label="t4", shape="Mrecord"];
    }
}

按照 LDSF 算法，此时应该让 t1、t2 和 t3 获取到共享锁，但此时较优的方案是先给 t1 共享锁，然后给 t4 排他锁，最后同时给 t2 和 t3 共享锁。

为了解决此类问题，文章提出了 bLDSF 算法。

delay 因子

可以看出，一组共享锁加锁成功后，这个资源下一次可用的时间取决于获得到锁的事务集合中其中最慢的事务的剩余运行时间。

我们将这个时间的期望值称为 R_max(m)，其中 m 为集合大小，而每个事务本身的剩余运行时间期望值称为 R。

我们定义 delay 因子为 f(m) = R_max(m)/R，显然随着获得到锁的事务集合的增大，f(m) 也会随之增大。

在不同的负载下，R_max 的计算方法 和对应的 f 的值也会不同，但文章表明，实践中只需使用递增的亚线性函数即可达到比较好的效果。

优先级计算的改进

对于排他锁，优先级计算方式不变。

对于共享锁，在 bLDSF 算法中，备选的加锁集合是所有是 所有要加共享锁的事务组成的集合 的所有非空子集。

对于这些子集，其优先级计算方法为：这个子集的所有元素的依赖集合的并集的大小 / 这个集合的 delay 因子。

工程实现中的改进

估算依赖集合的大小

实践上无论是直接搜索整个等待关系图还是在构建等待关系图时维护，计算依赖集合的大小都是比较消耗资源的（因为实际上依赖图是 DAG），文章中针对这个问题提出的改进是别管什么 DAG 了，就按树来算（即 依赖集合的大小 = 所有被直接 block 的事务的依赖集合的大小之和 + 1）。

bLDSF 中遍历所有非空子集

实践中为了节约资源，可以直接遍历任意一组长度递增的非空子集，而不是遍历所有非空子集。

比如 {t1, t2, t3} 我们只考虑 {t1}, {t1, t2}, {t1, t2, t3} 就行了。

防止饥饿

文章中的意思应该是隔一段时间放置一个 barrier，barrier 之后到达的事务一定要在 barrier 之前的事务都完成之后才能获得锁。

私货：TiKV里能用到哪些？

TiKV 里全都是排他锁，因此 LDSF 就很够了。

不过现在这个等锁之后隔段时间就全部返回到 TiDB 再重试的行为³和 LDSF 好像不是特别兼容……