CMU 15445 Project 2C 实现B+树并发INDE

暴力法

并发的最暴力解法，就是在每个FUNCTION，在B+树里就是GET ,REMOVE, INSERT，调用前上锁，做完释放锁。
针对这个作业，我大概写了11个测试，涵盖了方方面面，唯一没还有涵盖的是INDEX ITERATOR和基本操作的并发，因为会触发死锁，但是没有实现重试机制。但PROJECT里也有提到，这个不做考察重点。

用暴力加锁的做法，确实可以通过我写的所有并发测试。确保测试本身没有问题。

吐槽

下面碰巧在学习别人的解法时候（GIT HUB上搜了几个最高票数的解法），发现所有的他们的解法根本过不了我的这11个测试。正确性都没满足啊。

整个CRABING PROTOCAL的解法 对之前实现的B+树的算法的正确性 和 简洁性 有很高的依赖。也就是说之前的B+树的算法越严谨，实现这个协议就越容易。不然代码会改的坑坑洼洼，还写不对。

新的不变量

上一节，我已经介绍了B+树本身的一些不变量验证，也确保了我的算法没有破坏这些不变量，同时过了INSERT,DELETE和PAGE和TREE的测试

但是再实现CRABING PROTOCAL的时候，依然有个很严重的问题。

首先，老师给的提示里，有这么一句话

You have to release the latch on that page BEFORE you unpin the same page from the buffer pool.

这很重要，因为一旦有个PAGE被UNPIN到0，当POOL里的PAGE不够用的时候，这个PAGE会被回写磁盘，然后给牺牲掉。这时如果还没释放锁就会产生问题。

基于这个思考，我们有了一个新的不变量，也就是要求我们的B+树，在释放锁的时候，那时PAGE的PIN COUNT一定不应该为0. 如果为0，就说明之前算法是有问题的。

加上这个代码来确保这个情况不会发生。

image.png

当然在单线程的测试环境里，下一个ASSERT是可以被满足的，如果不满足，说明DELETE PAGE写的有问题（多线程的时候允许这个情况发生，我后面会介绍WHY）

image.png

根据新的不变量，优化代码

基于上述新的不变量，我上次提交的2B作业 是不满足的。因为我利用UNPIN PAGE 如果已经为0，就RETURN FALSE，来保证了幂等。但是多线程的情况下，他可能会造成先UNPIN到0,在FREE LOCK的悲剧。所以这里必须改掉。

巧合的是，在上个版本的代码实现里，我确实很多方法的BOOL值没有用上，也违背了CMU的作业设计。

在解决这个问题的时候，我发现这些变量正好可以派上用场。

比如

image.png

算法本身

首先我还是来讲一下B+树，并发INDEX的算法。
https://15445.courses.cs.cmu.edu/fall2018/slides/09-indexconcurrency.pdf

首先LATCH，是用来保护DB自己需要保护的数据的，LOCK是用来保护CLIENT的TRANSACTION的

LATCH 分为读，写2个模式。可以有多个读锁，但是写锁是排他的。

image.png

如果不用锁来保护INDEX，会发生2种悲剧。

1. 2个线程同时修改一个索引。
2. 一个线程再遍历的时候，另一个再做合并或分裂。

下图就举个一个CASE 2，找41的时候，另一个做了REBALANCE，41不见了。

image.png image.png

下面就开始介绍LATCH CRABBING/COUPLING 算法。

对于查询操作，从根节点开始，首先获取根节点的读锁，然后在根节点中查找key应该出现的孩子节点，获取孩子节点的读锁，然后释放根节点的读锁，以此类推，直到找到目标叶子节点，此时该叶子节点获取了读锁。

对于删除和插入操作，也是从根节点开始，先获取根节点的写锁，一旦孩子节点也获取了写锁，检查根节点是否安全，如果安全释放孩子节点所有祖先节点的写锁，以此类推，直到找到目标叶子节点。节点安全定义如下：如果对于插入操作，如果再插入一个元素，不会产生分裂，或者对于删除操作，如果再删除一个元素，不会产生并合。

image.png

查找

image.png

插入

image.png

算法本身应该是改动不多的。
基本上在实现了上述的思想后，如果不引入ITERATOR的横向遍历，几乎可以不用改别的地方。比如DELETE 的SIBLING PAGE是可以不用上锁保护起来，因为动到这个，PARENT一定是锁住的，不会有第2个线程可以走到这个SIBLING。 前提是不利用叶子节点的横向指针，之能事从ROOT走下来的情况。

实现思路

基于上述思想，整个2C 大概分为这么几个步骤。

1. 优化代码，解决新的不变量的问题。

2. 重写FIND LEAF PAGE，以及做完INSERT ，GET, REMOVE ，需要释放TRANSACTION里的PAGE，同时需要对SIBING 加锁保护

3.实现逻辑可以保护ROOT_PAGE_ID 在并发时不出问题。

上面三步可以确保能过所有测试了。

4. 实现ITERATOR的线程安全。

上面这步可以确保，在没有删除叶子节点的时候，去找左SIBLING的情况下，线程安全，如果有这样的操作，会发生死锁。
因为DELETE锁住了右边的叶子，要去找左SIBILING（读锁锁住了），ITERATOR先拿到左SIBLING的读锁，去等下一个右边的叶子节点的锁（被DELTEE的写锁占用）
产生死锁。

鉴于这个LAB想实现正确难度还是非常大，所以我带着大家一点点实现出来。本解法基于我的PROJECT 2B的代码，需要的同学可以去我的GIT上取。
https://github.com/yixuaz/CMU-15445

第一步，移除多余的UNPIN PAGE

加上2处，ASSERT，确保过测试的时候不会走到这里，还有一处上面写了。

image.png

基于报错和小数据集来研究为啥会重复UNPIN，也可以基于分析代码。下面给出如何SOLUTION。

加了2个ASSERT，后测试INSERT没问题。基本上引入问题的是REMOVE。

第一处

image.png

修改REMOVE的时候，我的假设是这样的。 如果这个PAGE已经被MOVE 完了，没有作用了，当下会直接UNPIN 然后DELETE，同时返回TRUE给外层。 外层只有发现是FALSE的时候，会帮忙去做UNPIN。
这样就不会重复UNPIN了。

image.png image.png image.png image.png

重跑TEST 测试全过。
我们这个基础，提交到PROJECT2C 里的2C-PREPARATION

第二步 重写FIND LEAF PAGE

下面是原来的代码

image.png

基于思考，我们需要把FETCH PAGE这个地方做个加强。
里面的逻辑大概是，首先拿到PAGE，锁住，然后看这个节点是不是SAFE，是的话，释放掉TRANSACTION里管理的PAGE。然后把这个PAGE加进去。

但是我写到后面发现ITERATOR BEGIN()的时候，是不会有TRANSACTION传过来，这个时候我们需要额外维护一个逻辑，直接释放前一个PAGE（释放包括先UNLOCK,再UNPIN）

实现3个辅助函数

在TREE PAGE里加这个PAGE是否是SAFE

image.png image.png image.png

新的FIND LEAFPAGE

image.png

第三步 做完INSERT ，GET,需要释放TRANSACTION里的PAGE

image.png image.png

通过INSERT TEST的测试

image.png

第四步 做完REMOVE 的改动

有2点，除了像上面那样更新2个方法。还有一个是要把所有UNPIN+DELETE的地方延后。加入到DELETED PAGE SET

image.png

因为节点如果有被删除的风险，一定是会UNSAFE被送进TRANSACTION里。
所以我们需要统一在最后处理他们。
为了达到这个效果，我们需要把所有要删除TRANSACTION节点的地方给延迟。就加到TRANSACTION的另外一个叫DELETED SET的集合里

但是有个地方我们做了一次SWAP，这样在方法内部会混淆谁是原来的节点。为了记住这个信息，我们用负号来表示交换过。

image.png
image.png
image.png

跑DELETE 测试通过。

image.png

跑综合测试，通过

image.png

上面的做法，在后来跑并发测试时遇到问题

经过仔细研究DEBUG时的现象，大概琢磨出问题的来源在于下面这个情况。

image.png

所以DELETE的时候，SIBLING是一定要锁上的。

修改代码如下，就是无论是redistribute 还是 Coalesce 都不用去UNPIN了，
然后取SIBLING的时候，要加写锁，随后送进TRANSACTION PAGESET。最后统一释放。

image.png
image.png
image.png
image.png

分裂的时候同理

image.png
image.png

第五步 实现逻辑可以保护ROOT_PAGE_ID 在并发时不出问题。

ROOT PAGE ID 的重要性，因为在INSERT的时候 是读后写。
什么意思，如果判断ROOT PAGE ID 是INVALID，就要START NEW ROOT
所以要做保护，必须是COVER住全部的。
还有就是在FIND LEAF PAGE 的时候 都会去读，这个时候 可能需要一直保护到 ROOT PAGE 被FREE掉的时候。

基于上述思考，我决定再用一把读写锁，然后加一个抽象层来封装加锁放锁逻辑，同时为了记录自己加锁的次数 （因为是读写锁）需要一个THREAD LOACL INT。 如果没有这个变量，可能会错误的释放了其他线程加的保护ROOT PAGE ID的锁。

image.png
image.png
image.png image.png
image.png
image.png
image.png

第六步 ITERATOR 线程安全

image.png

通过全部11个测试1000次

测试脚本

image.png

单个测试耗时

image.png

全部

image.png

内存泄漏

image.png

因为这个实现 是一个里程碑，我会把整个PROJECT 的SNAPSHOT 给放进2C
https://github.com/yixuaz/CMU-15445