Database · 理论基础 · B link Tree

这篇文章将会介绍一份B+树并发控制协议。

论文链接：Efficient Locking for Concurrent Operations on B-Trees

文章分为2部分，第一部分通过伪代码介绍这份协议，第二部分证明这份协议是正确的。

严格意义上来说这是B link树而不是B+树，具体区别在于B link树每个节点上都会附加一个key和指针。附加的key（如下图左边的红色圆点）值等于同一层下一节点的第一个key（右边红色圆点），附加的指针（红色箭头）指向同一层下一节点。附加部分用于在同层节点之间进行移动。

协议介绍（插入操作）：

下降函数：
锁住根节点（读锁）
while　此节点不为叶子节点
    获取下降位置
    解锁此节点（读锁）
    if 需要右移
        获取同一层右节点，加锁（读锁）
    else
        将此节点入栈
        获取下一层节点，加锁（读锁）
返回叶子节点（处于读锁状态）


插入函数：
调用下降函数，获取叶子节点
当前节点升级锁（读锁->写锁）
while True
    获取插入位置
    if 需要右移
        获取同一层右节点，加锁（写锁）
    else
        break
    解锁当前节点（写锁）
    令当前节点等于右节点
if 节点不满
    插入key，解锁（写锁）
else
    调用分裂函数


分裂函数：
while 当前节点已满
    生成新节点（不加锁）
    分裂当前节点
    if 当前节点不为根节点
        获取栈内父亲节点，加锁（写锁）
    else
        生成新的根节点，使之为父亲节点
    将新节点插入父亲节点（可能需要右移）
    当前节点解锁（写锁）
    令当前节点等于父亲节点
当前节点解锁（写锁）

在不进行任何优化的情况下多线程B link树比单线程快25%（多线程队列很大程度上限制了这速度），最终内存会增加约9%。这是个比较保守的数据所以还是具备一定参考价值的，尽管性能还受影响于其他的具体实现，比如页面缓存策略，锁管理器的实现等。

下面是具体协议正确性的具体证明。

预警：证明篇幅大而且枯燥，如果不想深究的话直接使用协议就行了。

———————————————————

协议证明：

为了证明协议的正确性，我们需要对以下两点进行证明：

不会发生死锁（定理 1） 正确进行每一次操作　 每一次操作在结束时都保证树结构的正确性（定理 2） 除了对树进行修改的那个线程外其他线程看到的树是一致的（定理 3）

首先我们证明此协议不会发生死锁。

引理1：锁被插入线程按照一定的顺序施加

我们定义B link树节点具有以下大小顺序：

两节点在不同层，若节点a在节点b下方，则a < b 两节点在同一层，若节点a在节点b左侧，则a < b

所以对于插入操作而言，如果在时刻a < b，那么在任意时刻都有a < b。

因为树中节点的增加仅仅通过某个节点x的分裂，假设x分裂形成x’和x’‘，显然满足，以及。

当插入操作加锁节点时，永远不会在拥有当前节点锁的情况下，对小于（在其下方或左侧）这个节点的节点进行加锁，所以插入操作以一个良好的顺序进行加锁。

所以此协议不会产生死锁，接下来我们证明此协议正确进行每一次操作。

为了保证树结构的正确性，我们需要对每一个小操作进行检查，首先我们检查以下三个对于单个节点进行的操作：

修改一个非满节点 将满节点的右半部分写入新节点 将满节点的左半部分写入当前节点

当修改一个非满节点时，此节点不涉及分裂且处于写锁保护中，所以此操作没问题。

引理2：分裂某个节点等于对树结构进行单次改变。

当将满节点的右半部分写入新节点时，此时新节点不加锁但是在这一个时刻没有任何其他节点指向这个新节点，所以此操作没问题。

当将满节点的左半部分写入当前节点时，此节点处于写锁保护中，所以操作没有问题，还有一个需要考虑的是，分裂过程中会修改边界指针，即A->B变成A->N->B，此时N（即满节点右半部分）已经被写入，所以改变指针刚好可以完美地将新节点引入到树结构中（但直到在父亲节点中插入才算完整地引入新节点）。

所以我们得到每一个操作都能够被正确执行。

最后我们证明其它线程可以正确地被执行而不需要考虑当前正在对树结构进行修改的线程。

为了证明这个定理我们首先考虑一个查找线程和一个插入线程交互，然后考虑两个插入线程进行交互。

引理3：时刻节点a被插入线程I进行修改，当读取线程P在时刻读取a节点时，P的正确性没有被I所影响

首先在P到达a节点之前的路径并没有被I所影响。另外，通过定理2，任何I操作对树结构作出的改变必定生成正确的树，所以，P在时刻之后进行的操作会正确进行。

通过引理3，我们只需要考虑当查找或者插入线程P在插入线程I对树结构进行改变之前的情况。

Part 1

考虑插入线程I在时刻改变节点a，以及查找线程S在读取a节点，令a’表示改变后的节点。因为查找线程在读取时持有读锁，所以只有等读取完毕后a节点才可能被I改变，所以交互不会出现问题。

Part 2

当两个插入线程交互时，I’会出现以下几种情况：

查找正确节点来插入 向上回溯 试图在当前节点插入

对于情况1，等同于Part 1中讨论的情况。

对于情况2，I’正在回溯，回溯时使用保存在栈上的上一层节点，考虑下面这个情况，在我们从下降到回溯的这段时间内，栈内的节点有可能已经发生了多次分裂，但是我们通过附加指针仍然可以到达正确的父亲节点。

对于情况3，I’此时不会拥有任何锁，因为I正在对此节点进行修改，所以等到I释放锁时，I’才可以修改此节点，然后I’修改此节点或者随着附加指针到达正确节点。

证明完毕。

这个协议有可能会发生活锁。在随着附加指针在同一层进行移动时，同一层的节点不断地进行分裂，也就以为着我们可能永远也到不了那个我们可以进行下降的节点。但是这几乎是不可能的，因为CPU每个核运行速度是几乎一致的而且分裂发生的概率还是比较小的，所以完全不需要担心，提出这个只是让你对这个协议有个全面的了解罢了。

PS:

这个算法的具体实现，UncP/aili。