Bustub 闯关记 (三): B+ 树的并发控制

April 14, 2023

2023   ·   CS1951@SJTU   Learning   Chinese     ·   acm-class  

在完成了基础的 B+ 树实现之后, 我们开始着手实现并发控制. 在 Project #1 里面实现的 Write/ReadPageGuard 此时就能起到关键的帮助. 在设计这一部分前, 最好还是自己在纸上画一画, 考虑在各种读/写的情况下, 对锁的设计会不会出问题, 下面是一些我最开始想到的比较麻烦的情况.

  • 插入/删除的时候, 当我完成在一个 InternalPage 中的定位后, 准备继续往下走, 这个时候能不能释放 WritePageGuard 呢? 答案是不一定能. 如果这个时候放锁了, 结果下面的节点需要并块/裂块, 那我后面又得回来重新获取写锁, 这个过程中, 假设有另一个线程获取了这个 InternalPage 的写锁并且更改了一些节点索引, 那立马就 g 了.
  • 在顺序查询 (15-445 的测试点并没有这个需求, 但是 ACM 班的大作业 TicketSystem 需要) 的情况下, 我们需要从左到右遍历所有的叶子节点, 这个时候我们能不能直接释放前面遍历过的节点的锁? (需要实现上进行一些 modification)
  • 借儿子和还儿子的时候, 会不会出现死锁?

其他关于 B+ 树的一些锁设计的细节就不多赘述了, 下面主要讲一些我印象深刻的部分.

Concurrency

记录一些 B+ 树并发的基础问题, 万一以后要讲课 / 面试的时候用得上呢.

如果没有锁保护的话:

  1. 线程 T1 想要删除44
  2. 线程 T2 想要查找41


  1. 假设 T2 在执行到 D 位置的时候又切换到线程 T1
  2. 这个时候 T1 进行重新分配，会把 41 借到 I 结点上
  3. T1 执行完成切换回 T2 这时候 T2 再去原来的执行寻找 41 就会找不到


就会出现下面的情况


RAII

听说这是本学期 迟先生 当 TA 之后才加上的 feature, 真的非常好用… 我后面在写 TicketSystem 的时候一些地方也用到了这个理念. 在传统的数据库系统和缓存池中, 我们获取并释放一个 page 往往需要下面几步操作:

  1. FetchPage, 从磁盘中获取一个 page
  2. LockPage, 获取这个 page 的锁
  3. DoSomething, 对这个 page 进行一些操作
  4. UnlockPage, 释放这个 page 的锁
  5. UnpinPage, 标记这个 page 不再使用
  6. EvictPage, 将这个 page 写回磁盘

这个过程可谓非常的蛋疼, 因为在这之中, 你一旦忘记其中的某一步, 就会导致一些非常难以 debug 的问题. 但是如果我们使用 RAII, 我们就可以将这个过程简化为:

{
    WritePageGuard guard;
    auto page = FetchPage();
    DoSomething(page);
}

这样一来, 我们就可以保证在这个 block 结束的时候, guard 会自动释放锁, page 会自动标记为不再使用, 也不用担心忘记释放锁或者忘记标记 page 的问题了.

Optimistic/Pessimistic Locking

上面提到过插入和删除的时候不应该释放前面节点的锁, 不然有可能会导致并块/裂块时的 data racing. 但是如果我们不释放锁, 插入删除操作都只能单线程进行, 这样明显是效率非常低下的, 根据实际测试, 这样的效果还不如给整个 B+ 树加一把大的读写锁, 然后允许多个线程同时进行读操作.

所以网上很多 bustub 相关文章都介绍了 Optimistic Locking, 也就是在插入删除的时候, 先乐观地假设这个操作不会发生并块/裂块, 全部只获取 ReadPageGuard, 直到最后一层叶子节点的时候再获取 WritePageGuard.


如果发生了并块/裂块或其他会影响上层节点的操作, 就回滚, 重新获取锁, 重新执行操作. 这样一来, 我们就可以允许多个线程同时进行插入删除操作了.


Debug

说来有趣, 这应该是我第一次 Debug 多线程程序… 之前的 Bookstore 就寒假写完随便搞了点小测试就放过去了, 这次终于体会到了传说中的折磨… 这一方面好像也没有什么普适性的建议, 我还是简单分享一下自己的 Debug 经验吧 (如果后面有人看到这个帖子, 有更好的建议欢迎在评论区留言):

  • 输出调试信息, 这个是最基础的调试模式 (不过中学搞 OI 的时候, 最开始不会打断点, 训练了这种方法若干年) 但是在多线程程序中确实唯一有用的方法了.
    • 用不同颜色区分不同线程的输出
    • 打印每个输出的时间, 便于定位问题
  • 通过控制延时手动创造极端情况, 因为并发 bug 往往难以复现

Garbage Collection

这是一个 TicketSystem 的 bonus, 原版的 bustub 并不支持这一操作. 因为 bustub 里面记录当前节点编号是用一个 atomic<int> 来做的, 只能单调递增, 所以后面也想了一下怎样改变 bustub 的架构以支持垃圾回收, 主要问题其实就下面两点.

  • 怎么实现一个支持并发的垃圾桶?
  • 怎样把垃圾桶存在外存里面?

最后的解决方案是, 手写了一个支持并发的 AVL 树来当垃圾桶, 最后用前序遍历将垃圾桶的内容写入外存. 这个过程中也遇到了一些并发问题, 但是因为 AVL 树的特性, 一般不会出现死锁的情况, 所以最后还是比较顺利地完成了这个 bonus.

总结

完成了这些内容之后, bustub 的 project #2 终于完结撒花了, 在这里也给向我推荐这个项目的 wly 学长和耐心陪我 debug 的 lxy 献上 special thank!