写在前面

最近在学CMU15-445。趁着实习的间隙，晚上，还有周末，看看视频，写写lab。
CMU15-445的lab与MIT6.824的lab风格很不一样。前者定义好了函数原型，提示更多，但是禁锢了思维，发挥空间变小了。后者只提供了最基础的接口，在代码架构上的可发挥性更高。
由于函数原型都给好了，我以为这个lab会简单很多。结果没成想，写着写着，发现B+树这个lab给我整不会了。花了足足一个月，才把lab写完，目前代码在gradescope上已经通过。通关截图：

在做这个lab的过程中，学到了不少东西。在这里简单总结下。

整体架构

lab的整体架构很清晰。先实现internal_page、leaf_page这两个数据结构，作为B+树的内部节点和叶子节点。然后实现B+树的插入、删除，最后支持并发。
难点主要有四处：

1. 内部节点和叶子节点的实现没有专门的测试。需要自己写测试。
2. 插入和删除的细节需要仔细思考。
3. 并发部分的具体实现方式。
4. debug

内部节点与叶子节点

在这一部分中，我们要实现一系列的小函数。整个过程比较繁琐，但难度不大。
在我最初的版本中，所有的搜索都是线性时间复杂度的。这样做实现简单，可以确保正确性。但是在后续性能调优中，发现此处的性能瓶颈很严重。于是改为了二分搜索。这是后话。
在完成所有的小函数后，我自己手写了一组测试，用来检测内部节点的正确性。（叶子节点比较简单，就没有写测试。）
本来以为，这些简单的小函数，我是绝不可能出错的。但是通过测试，还是发现了两个小bug。
心得是：永远不要过于相信自己。用测试结果说话。

插入与删除

插入与删除的部分需要仔细思考。
对于内部节点，在插入删除时需要考虑middle key。这里以删除时redistribute为例：

插入与删除时，分裂以及合并的具体实现会影响内部节点、叶子节点的相关函数实现。
具体来说，出于性能考虑，我做了以下设计：

1. 分裂时，新建一个右节点，将需要分裂的节点的后一半移动到新建的右节点中，剩下的一半保持不动。这样与新建一个左节点相比，减少了将剩下一半前移的开销。
2. 合并时，默认将右节点合并到左节点。这样与将左节点合并到右节点相比，减少了将右节点全部节点后移的开销。

在理清思路后，插入与删除部分就顺理成章地完成了。

并发

并发是难度最大的点。
难点如下：

1. 怎样实现latch crabbing过程中的加锁和解锁。
2. 怎样实现节点的删除，不要让删除与加锁解锁相冲突。
3. 如何对根节点相关的信息加锁，以及如何及时释放根节点的锁。

latch crabbing

latch crabbing的思想很简单。但在实现时比较复杂。
读取的情况比较简单：加锁过程中，我们跟踪当前节点和它的父节点（用两个指针实现），对它们进行加解锁。
插入/删除的情况相比而言更复杂：我们不仅要考虑父节点，还要考虑所有的祖先节点。

---下面这一段是记录给自己看的，可以略过---

在实现过程中，我首先考虑的实现方式是这样的：（后面舍弃了）
在FindLeafPage函数中，先对所有需要加锁的祖先进行加锁。但并不记录下这些祖先。在Remove/Insert函数中，每当要分裂/合并/重分布时，都通过GetParentId获取父节点（“顺藤摸瓜”）。当然，这时父节点已经在FindLeafPage中被latch住了，因此不用再获取锁。当使用完父节点后，解锁之。
这样做的优点在于，可以在祖先使用完毕后，立即及时释放祖先的锁。
但是采用这种方式，正确性是有问题的：若Remove时仅进行Redistribute，那么上溯将在Redistribute后停止。但是这一层上面可能还有已经加锁的祖先节点。我们将无法对它们进行解锁。这可以通过额外的丑陋机制加以解决。
最重要的时：正确性之外，代码实现变得非常丑陋--解锁分散在代码的各个位置，还要考虑大量解锁的corner case，实现和维护难度极大。

在痛苦地挣扎了一周后，我决定放弃这种思路。改为如下实现：

---结束---

最终的实现如下：
在FindLeafPage函数中，记录下latch crabbing过程中Fetch并加锁的祖先（例如：用一个队列），在

1. FindLeafPage中发现安全的节点后
2. 整个Insert/Remove函数最后

清空队列，把所有的祖先都解锁并Unpin。（使用队列的原因是，可以先释放最上层的祖先）
乍一看，似乎按照第二条的做法，并不能及时地在使用完祖先后，立即释放祖先的锁。而是要等到整个修改操作完成后，才能释放祖先的锁。
但要注意的是：Insert/Remove函数是从树的底层向树的上层递归的。在递归的最后，才会接触到最上层的祖先。在这之前，提前解锁下层的节点并不能带来什么好处。由于最上层的祖先仍然被锁住，即使下层的节点被解锁，其他线程也无法访问到它们。
因此，采用队列记录的方案，并不会对解锁的及时性产生影响。

采用这种方案，解锁变得异常整洁：在Insert与Remove函数及其调用的所有函数中，我们都不用考虑与锁相关的事情。
心得：代码可维护性很重要。当代码逻辑过于复杂时，要考虑使用一些数据结构等，简化代码逻辑。

节点删除

如果我们在Remove函数及其调用的子函数中，直接解锁unpin，并调用buffer_pool_manager_->DeletePage删除页，会与解锁的流程冲突。这是因为，被删除的页可能会在加锁队列中。当Remove函数执行到最后时，会再次试图解锁已经被删除的页。
为了解决这个问题，我引入一个unordered_map，记录所有要被删除的节点。在需要删除节点时，仅将节点加入map中。在Remove函数最后解锁所有祖先后，再真正删除map中记录的所有节点。
在解锁后再删除节点并不会引起并发问题。这是因为要被删除的节点已经与B+树断开了所有的连接，其他的线程已经不再能够访问到它们了。

对根节点加锁

在b_plus_tree类中，有一个成员变量root_page_id，它记录了B+树根节点的page id。任何一个线程在对B+树进行任何操作前，都需要读取root_page_id；插入和删除时，有些情况下需要修改root_page_id。因此这个变量需要用锁保护。
在作业要求中，老师建议使用std::mutex进行保护。因此我引入了root_latch锁。
在我最初的版本中，对root_latch的加解锁方案是这样的：

1. 在GetValue/Insert/Remove函数开始时，对root_latch加锁
2. 在获取了根节点的读锁后，释放root_latch
3. 在释放了根节点的写锁后，释放root_latch

前两条都是合理的。但是第三条对性能有一定影响：当根节点的内容需要修改时，我们会获取根节点的写锁。但并不是所有需要修改根节点的情况下，都需要修改root_page_id。例如：根节点的子节点分裂，需要在根节点中添加新项，但并不会导致根节点分裂。
因此在后续版本中，为了优化性能，在FindLeafPageComplex中添加了一段代码。将第三条修改为：在获取根节点的写锁后，检查其Size。若根节点“安全”，则释放写锁。

其他优化

在课上Andy提到，latch crabbing有乐观加锁的版本。具体而言，在插入/删除时，并不是直接一路向下添加写锁。而是先一路添加读锁，在遇到叶子节点时添加写锁。若叶子节点“安全”，则直接进行插入/删除操作。若叶子节点不“安全”，则解除叶子节点的写锁，重头再来，一路向下添加写锁。
在完成上面的部分之后，我心血来潮，想要把插入/删除的并发控制改成乐观的。
改成乐观控制并不难。要想支持这个功能，需要让每个内部节点，都能够判断其子节点是否为叶子节点，从而判断对其加读锁还是写锁。因此我在内部节点类中添加了一个成员变量is_child_leaf，并在分裂时维护这个变量。
在完成乐观控制后，我发现这并不会提高性能。在gradescope上的leaderboard中，乐观版本的执行时间和悲观版本一样。
心得：过早的优化是万恶之源

debug

在完成上述内容后，我开始对代码进行测试。使用的测试代码是15-445学习群中获得的，gradescope的测试代码。
在测试过程中，并发插入总能通过。但是在并发删除与混合测试中，我一直遭遇两种错误：

1. 锁相关的报错:pthread_mutex_lock.c:62: __pthread_mutex_lock: Assertion mutex->__data.__owner == 0‘ failed`
2. 在调用buffer_pool_manager_->DeletePage删除节点时，有节点的Pin Count不为0。在大多数错误情况下，这些节点的Pin Count为1。少数情况下，Pin Count为2。

这两个错误困扰了我一周多的时间。在此期间，我对代码进行了多次review，发现了第一个错误的原因：
在Remove函数中，需要访问当前节点的sibling时，必须要对sibling加锁。这是因为，sibling节点可能在上一次插入/删除操作中，是被加锁的最古老的祖先。在执行本次删除操作时，上一次插入/删除操作还没有完成，sibling仍在被使用。

但是第二个问题迟迟得不到解决。
首先，我进行了大量的单线程测试，确保单线程的Remove并不会发生任何问题。那么可以确认问题是出在多线程上。
接下来，我进行了并发测试，添加了大量log。甚至采用了从6.824助教那里学来的方法：对log加颜色。（不过加颜色真心好用！）
在这个过程中，我逐渐对问题进行定位。发现错误总是发生在如下场景：一个线程多次对同一个叶子节点执行删除操作，直至该节点不再安全，需要执行合并，需要删除该节点。在该线程执行删除操作时，发现Pin Count不为0。
看起来，有另一个线程也正在访问这个叶子节点。这就很奇怪了。要想访问某个节点，必须对其进行加锁。既然正在执行删除的线程可以修改叶子节点，那么其它线程必然没有获取到写锁，因此不能访问叶子节点。
接下来，我又对代码中负责对叶子节点加锁的部分进行了严密的检查，但并没有发现问题。可以认为，加锁的逻辑是正确的。错误隐藏的比我想象的更深。
那么我能做的，就只有再多跑测试，多打log，直到找到一次能够揭示问题原因的测试结果为止了！
幸运的是，一个下午过后，这样的测试结果出现了。
我发现，在执行删除操作之间，有另一个线程，对需要被删除的叶子节点进行了Fetch、加锁、解锁，但并没有unpin。
也就是说，问题的根源在于，解锁与Unpin不是原子的。
要想解决这个问题，方案有两个：

1. 让解锁与Unpin变成原子的。这需要引入一把新的锁。
2. 在删除时，若发现Pin Count不为0，则sleep一段时间。等待另一个线程unpin。若苏醒后发现Pin Count仍不为0，则不断循环。

方案2比较简单，因此我选择了方案2。在这之后，问题迎刃而解，测试通过。

性能调优

将代码提交到gradescope上。发现无法通过memory safety测试。经查找，确认这是由于代码太慢。
那么工作的重点就转移到性能调优上了。
首先我引入了一个解锁优化，即“对根节点加锁”这一节中，对第三条的优化。但是并未对代码速度产生什么影响。这样一来，似乎代码太慢不是由于多线程锁争用导致的。

那么我们就必须弄清楚，性能问题到底是由于单线程太慢，还是由于并发锁冲突导致的。

首先观察测试花费的时间：

1. 对于单线程插入测试，插入1000个记录，用时34ms。
2. 对于多线程混合测试Mixtest1，两个线程（一个插入，一个删除），分别插入/删除1000个记录，循环100次，用时4367ms。
3. 对于多线程混合测试Mixtest1，十个线程（五个插入，五个删除），分别插入/删除1000个记录，循环100次，用时15622ms。

观察1和2，4367与34*100大约在同一个数量级。考虑到两线程必然会发生一些锁冲突，可以认为两个线程的冲突并不严重。
观察2和3，线程数量变为五倍，用时变为3倍多。考虑到Mixtest1中插入的记录数量不多（1000个。与之相比，节点的MaxSize有200多。），树较浅（应该只有两层），这个冲突情况可以接受。

那么导致超时的主要原因，应该是单线程太慢。

恰好前段时间在The Missing Semester of Your CS Education中，了解到了“火焰图”这个工具，感觉很酷炫，这次正好拿来尝试一下。
火焰图的github链接
火焰图与perf搭配使用，可以分析各个函数调用所使用的时间。火焰图是交互式的svg图，使用很直观，也很方便。
但需要注意，这种方式只能分析on-cpu time，也就是说，线程等待锁的时间是无法被计入的。
不过没关系，我们正是要分析单线程的执行情况的。

作图如下：(其实这里应该对单线程测试作图。但我当时只对并发混合测试MixTest1做了图。其实不太严谨，但问题解决了就好。)

图里面有两个MixTest1相关的部分。我不知道是为什么。但这不影响我们的分析。

放大来看：

Remove:

可以很明显地看到，Remove中占大头的是LookUp函数。Insert中占大头的是KeyIndex函数。
这个时候我回想起来，我的这两个函数都是线性时间复杂度的。这里一个节点中记录的个数在200多。如果把它们改成二分查找，最多只需要8次查找（log2(200)），应该可以大大提速。

在改为二分查找之后，成功地通过了gradescope的所有测试，用时显示为5.16，排34位，还不错！

写在最后

这次lab做了超级超级久，中间一度想过放弃。但是很庆幸，自己最后还是坚持了下来。通过这次实验，我第一次写了测试代码，第一次尝试带颜色的log，第一次用火焰图进行了性能分析。收获颇丰！
（不要问我为什么6.824的lab4还没有更新。咕咕咕！

CMU15-445 Lab2 B+Tree全记录