CMU 15-445 Project 2 B+ Tree 技术总结

首先是教科书的伪代码

感觉基本都要按这个来写，不然（可能）写不出来的，PPT 的讲解也不够详细。Project 的代码结构的确是根据这个伪代码来设计的。不过我感觉这种写法的伪代码有点难看。

并发的要点

基本做 lab 的过程就是全程对着上面两个 guideline 来操作。

然后是我的一些技术总结踩坑的地方（可能会没有帮助 ）

1. 锁的顺序，死锁。
2. 实现的方法是某些方法保证进来之前获取锁，谁用到锁谁释放。
3. 学习了怎么用条件编译实现无虚函数继承的多态方法。
4. 边界条件不知道怎么解决只想到用 bool 来暴力编程。
5. 异常的问题，理论上不 unique 的应该正常返回，which 要求 release 所有的锁。

all tests passed 之后总结一下

首先是浪费时间 accidental 的事情

• 这里感谢 discord 的一个主管人的解释以及discord上各位前人的探索，autograder fail 的情况可能是超时或者内存，部分前人提到与不兼容的C++17有关，我于是解决了第一个 auto [] 解包的不兼容，但是这里我的思考不够坚定，我看到了有人用 constexpr + NOLINT（这个 NOLINT 也感谢 discord 的小伙伴）还点赞的（说明他通过了），但是我还是纠结在 constexpr 导致花了一些时间去掉 constexpr 和尝试其他的语句会不会有不兼容，但是实际我也看到了有的人提到了 log 的问题，但是一开始我还是没有尝试 upload 我的 logger，最后还是靠  upload logger 来解决的。。还要感谢一个人说的从 base code 开始一点添加和修改直到不能通过（二分法）。我的思考方法还得提升 since 之前我 buffer pool 里面是改了 bug 才通过的，由此应该能够得到结论是 bufferpool 超时（deadlock） 了，和标准和 assert include 头无关。而 local test 的时候也的确发现了打 log 花的时间是几千倍。
• 第一个是我没有去掉 log 然后就 上传，导致运行不了（花时间太长了）。
• 而 autograder 的 logger 又是没用的, 他用 constexpr 定义了 logger 这个无法生效，需要改成 define 的，然后上传的时候避免超时必须禁用所有（默认开 debug 和 trace）。

第二个是一些错误点（解决 logger 问题后从35分到满分只花不到一个小时而且有 25 名在一堆没用 constexpr if 的情况下）

• 我一开始因为有的地方（比如 root page）需要 acquire 到 latch 之后马上 enqueue，所以我把这两布写在一起了。然而实际是你 acquire 到 child  的 latch 之后要判断 ancestor 的之后保留自己的。所以必须先保存这个 latch，等判断玩 ancestor 的之后再 出que。
• Unpin 的问题，我做的时候写了一个 PageResource RAII 类来进行 Page 的 unpin ，dirty 写回，删除等管理。当时出了问题。Debug 的时候我一开始把所有的 PageResource 都去掉了，导致 delete 的时候可能会有一些 pined 值大于等于 1 的情况，这个很明显是我搞错了。
• 在 FindLeafPage 里面 enque 那些是不用 unpin 的，因为他们的 unpin 会延迟进行，但是其他函数比如 CoalesceOrRedistibute 和 Redistibute 都会 fetch parent 或者中间的 sibling，其实 sibling 可以加入到 queue 里也可以不加（因为有 parent 被锁了，安全），这些 pin 是没有对应的 unpin 的所以 RAII PageResource 还是要到位的。
• 但是奇怪的是好像我拿满分的那个版本的确会去掉了部分 PageResource，我还认为这是正确方案。
• 用了 constexpr if 的结果反而没有加快，（4.33->4.34），这一点不管了，不过可能是我 get value 改用了 统一返回 tuple 的 FindLeafPagePro 进行了更多数据相关引发的平衡了 constexpr 的效果？或者编译器本来就把我那些非 constexpr if 优化成 constexpr if。这个的确难讲）。
• 然后还有一个多谢博客园大佬，于是我改了 FindLeafPage 的 return value 。主要是他对一个问题的分析：

我发现，在执行删除操作之间，有另一个线程，对需要被删除的叶子节点进行了Fetch、加锁、解锁，但并没有unpin。

也就是说，问题的根源在于，解锁与Unpin不是原子的。

要想解决这个问题，方案有两个：

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

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

From <CMU15-445 Lab2 B+Tree全记录 - sun-lingyu - 博客园>

为了适合多核的情况，我没有修改 BufferPool （since 这个本来就不是 buffer pool 的问题），只需要在 remove 的函数里 delete 失败（根据 bufferpool 的API规定 pined 值大于 0 必须 return false 而不进行 deletee）的话就 spin 一定的次数，直到 delete 成功。这个能 work 是因为 spin 的话，多核如果执行到了 unpin 那么下一个循环过程马上就能 delete 成功。

其他总结

• 这次总的时间花了挺长的，到现在也差不多半个月了，buffer pool 之后国庆节基本没动手，到 10 月 8日才开始做这个，checkpoint 1 通过是 10 月 12 日，之后一致拖到今天（10月22日）才全部完成。历时 16 天，checkpoint 2 历时 10 天，虽然其中学 Cmake 花了一些时间。总的来说压力还是不够大，接下来事情很多得加大压力才行了。同时马上开始了 query 的 project 3。
• C++ 也重温了不少东西，一个是一开始我感觉那个不用虚函数的多态太坑了，当时是必要的不然虚函数表就能把on disk数据结构打乱，但是其实 C++ 也提供了 元编程的工具编译器生成代码，is_same_v 和 constexpr if 还是不错的，用上之后 runtime 应该没有这么多 if else 负担。所以通过 template 来实现多态（duck typing）其实也是一个方案。
• 然后是 tuple，实际编程才体会到多返回值是有用的，虽然用参数也不是不行。之后多习惯 auto 解包吧（虽然445 编程不能用 auto 解包）。
• RAII 的确很好，但是这里他的框框太多了，我有点难说怎么实现一个好的 PageResource 反而让这个 RAII 类很臃肿，所以我实际是简单问题复杂化了，实际如果可以手动管理所有的情况，上RAII包装类可能复杂化了，或者说我提供的选项不够多？除非修改他原有的函数的传参的方法。不过最终起码还是解决我忘记 unpin 的问题的，之后继续学习熟悉。
• const 的理解，一定要用 clang-tidy 等静态分析工具，这次加深了 code review 的重要。我一开始以为 const & 是可以修改他本身的，但是我错了。必须加深这个记忆，即 const 和 非 const 函数也是搬过来的。总之就一定是修改对象本身的时候用 pointer，读取对象的话才用 const & 而永远不要单独使用 &。（虽然 effective c++ 看到过，但是果然不实践的话是记不住的）。
• 对多线程的东西更加魔怔了，首先断点的不能用的，必须要打 log，因此也养成写 LOG 的好习惯，一开始我的 log 乱写，导致看起来很难受。然后是 thread id，这里我没办法（而且他的 logger 本身好像并不是线程安全的，有一些乱序，之后研究一下异步 logger 怎么写吧）。
• 然后就是测试的 down scale 和找特征，不一定要很大规模才能复现，这里 B+ tree 的话主要就是和 page 支持的 size 和 插入的数量有关，多用二分法。
• 数据结构体这个 debug 思路真的值得学习。
• 对于原子性更加理解，就是博客园大佬说的那个情况，这个分析和情况都很值得记住。
• 思考过程就是说怎么排除问题怎么分析问题，这个在 accidental 分析里说了，之后还要持续优化提高才行。
• B+ tree 本身的话，我一开始没有理解为什么判断的时候用的条件不一样，我感觉 project 设计得的确有些不妥。这一种 B+ tree 本身的规定是
  • 每个结点至多有m 个键；
  • 除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；

如果定义的时候用的是至多 m 个子女又另说了。所以这部分很歧义（主要是他计算一个 4096 bytes 的 page 内的数量又没有留空一个来 move）。