事务的锁调度

2018-10-11

简单介绍一下 VLDB 的一篇 paper： Contention-Aware Lock Scheduling for Transactional Databases

问题

多个事务访问到相同资源的时候，会涉及到加锁，怎么样进行调度，会使得各个事务的延迟尽量短，系统整体的吞吐更高，以及保证调度的公平性？

这个问题是比较难搞的。

• 首先这是一个 在线问题 。在事务结束之前，一个锁将会被持有多久，无法事先预知。
• 其次 依赖关系特别复杂 。一个事务可能持有许多的锁，以及多个事务间可能都依赖同一个锁。
• 接着是 访问模式的不确定 。不同的事务有不同的访问模式，有些对象可能是比较 popular 的，被许多事务依赖，不同对象之间并不等价。
• 锁的模式也有多种类别。比如写锁是排它的，而读锁是可共享的。

常规的系统大多采用的是 FIFO 的调度方式，也即是哪个事务请求先到达就先执行，并对相应的资源加锁。paper 里面指出，FIFO 的策略效果其实是很差的，而它提出的 contention aware 调度策略则相当牛逼。另外，MySQL innodb 引擎在 8.0.3 版本以后，默认采用的也是这篇 paper 里面的方法。

想法

contention-aware 调度的意思是，根据事务整体的锁竞争会对系统造成的影响，将事务分配优先级。调度是根据优先级进行的，而不是按 FIFO 方式。

那么第一个点就是如何确定锁竞争的激烈程度，下面是一些直观的想法。

最多锁持有优先(MLF)

一个事务，它持有的锁越多，则越有可能 block 住其它的事务。所以最多锁持有可以作为一种评判标准。

持有锁越多的事务，越优先调度。我们将这种方式称为“最多锁持有优先”。

这里的问题在于，对象之间并不是等价的。有些对象很 popular，持有它的锁会 block 住其它事务，而另一些对象其实并不 block 其它事务。依赖的节点多，并不意味着导致锁竞争。大部分上的节点都不会发生冲突。只有冲突节点上，才造成锁竞争。

最多 block 锁持有优先(MBLF)

事务依赖的锁，只有当这个锁还同时被其它事务依赖时，才导致锁竞争。所以上面的算法可以优化一下，不使用依赖的节点数量，而使用依赖的锁数量。

这里的问题在于，没有考虑进去锁的因素，将所有锁都看作相同的。假设有两个锁，其中一个 block 住了一个事务，而另一个锁 block 住了 10 个事务，在这个评判标准里面，两个锁还是被等同处理的。

依赖子图深度优先(DDF)

锁 block 住的事务多了，这个锁重要性也就提升了。为了抓住锁之间的重要性不同这个因素，我们可以考虑 “事务依赖的锁，锁 block 住的事务” 这一层关系，可以画一个依赖图出来。用子图的深度来衡量整个 block 的程度，也即反映了锁竞争的程度。

从事务到依赖图的叶子节点的路径深度，作为一个事务的优先级。

最大依赖集优先(LDSF)

因为我们不能考虑事务什么时候到达，什么时候结束，所以我们只能考虑当前执行中的事务。考虑事务之前的依赖图关系。

如果把依赖图画出来后，就会发现，“依赖子图深度优先” 跟 “最多 block 锁持有优先”，一种是反映图的垂直方向，一种是图的水平方向。把它两结合到一起考虑，就会变成“最大依赖集优先”。

将锁授予依赖集最大的事务，它能继续执行往前推进，则意味着依赖集里面的所有事务，都有潜在推进的可能。这样最有利于系统整体的向前推进。

修正的最大依赖集优先(bLDSF)

上面的最大依赖集优先是一个简化了的场景，假定只存在排它锁。实际上，如果存在共享锁，则问题会变得复杂一些。

共享锁会有一个"饥饿"问题，它被一直持有，导致排它锁加不上去，从而申请排它锁的事务时间会被拖长，造成系统整体的吞吐下降。所以论文里面还有一个结论是说，共享锁并不是分配给越多的事务就越好。

paper 里面有关于共享锁的处理细节，这里先略过。

算法实现

输入是依赖图，依赖对象；输出是应该将什么样的锁，分配给什么样的事务集合。

1. 如果还有其它事务仍然对象 o 上面持有锁，则返回空
2. 获取在对象 o 上面等待共享锁的集合 {t1,t2...tm}
3. 获取在对象 o 上面等待排它锁的集合 {ta,tb...tn**
4. 计算一个 共享锁的子集 ，使依赖集 {g(t1) |+ g(t2) |+ ...g(tk)} / f(k) 达到最大值
5. 取排它锁的依赖集的最大值
6. 如果是从共享锁依赖集算出来的最大值，大于排它锁算出来的值，则唤醒共享锁的一个子集的事务
7. 否则，唤醒依赖集最大的那个排它锁事务

这算法并不是来一个事务，就给它授予锁，或者遇到锁了将它排队(FIFO)。而是从头到尾的扫描整个 waiting 的事务，找出一个满足条件的并授予锁。

如何计算依赖集大小？

计算依赖集要遍历子图，而且每次依赖图变化了，每个节点要重新实时的计算，这种方式代价太高了。所以paper 里面是取一个近似值。如果一个事务 t，没有锁 block 这个事务，那么 g(t) = 1 。否则，它依赖某些锁，这些锁被事务集合 t1...tn 占着，则 g(t) = g(t1)+g(t2)...+g(tn) + 1 。这是一个近似算法，原因是依赖图不是一个树，而是一个 DAG，是有节点重叠的。

另外的麻烦的点是算共享锁的子图的依赖集情况，先略过了。

大致就这些，至于结果对比...各种吊打 FIFO 策略，就不提了。最后我想质疑一下的是，它的数据场景构造的有一些极端，发论文嘛，动不动就说 100x 提升...真实 case 里面达不到冲突严重到那种程度，所以数据肯定不会有那么好看。