Bustub 闯关记 (三): B+ 树的并发控制
在完成了基础的 B+ 树实现之后, 我们开始着手实现并发控制. 在 Project #1 里面实现的 Write/ReadPageGuard 此时就能起到关键的帮助. 在设计这一部分前, 最好还是自己在纸上画一画, 考虑在各种读/写的情况下, 对锁的设计会不会出问题, 下面是一些我最开始想到的比较麻烦的情况.
- 插入/删除的时候, 当我完成在一个 InternalPage 中的定位后, 准备继续往下走, 这个时候能不能释放 WritePageGuard 呢? 答案是不一定能. 如果这个时候放锁了, 结果下面的节点需要并块/裂块, 那我后面又得回来重新获取写锁, 这个过程中, 假设有另一个线程获取了这个 InternalPage 的写锁并且更改了一些节点索引, 那立马就 g 了.
- 在顺序查询 (15-445 的测试点并没有这个需求, 但是 ACM 班的大作业 TicketSystem 需要) 的情况下, 我们需要从左到右遍历所有的叶子节点, 这个时候我们能不能直接释放前面遍历过的节点的锁? (需要实现上进行一些 modification)
- 借儿子和还儿子的时候, 会不会出现死锁?
其他关于 B+ 树的一些锁设计的细节就不多赘述了, 下面主要讲一些我印象深刻的部分.
Concurrency
记录一些 B+ 树并发的基础问题, 万一以后要讲课 / 面试的时候用得上呢.
如果没有锁保护的话:
- 线程 T1 想要删除44
- 线程 T2 想要查找41
![](/assets/img/project/bustub/bustub-bpt-cc1.png)
- 假设 T2 在执行到 D 位置的时候又切换到线程 T1
- 这个时候 T1 进行重新分配,会把 41 借到 I 结点上
- T1 执行完成切换回 T2 这时候 T2 再去原来的执行寻找 41 就会找不到
![](/assets/img/project/bustub/bustub-bpt-cc2.png)
就会出现下面的情况
![](/assets/img/project/bustub/bustub-bpt-cc3.png)
RAII
听说这是本学期 迟先生 当 TA 之后才加上的 feature, 真的非常好用… 我后面在写 TicketSystem 的时候一些地方也用到了这个理念. 在传统的数据库系统和缓存池中, 我们获取并释放一个 page 往往需要下面几步操作:
- FetchPage, 从磁盘中获取一个 page
- LockPage, 获取这个 page 的锁
- DoSomething, 对这个 page 进行一些操作
- UnlockPage, 释放这个 page 的锁
- UnpinPage, 标记这个 page 不再使用
- 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.
![](/assets/img/project/bustub/bustub-bpt-cc4.png)
如果发生了并块/裂块或其他会影响上层节点的操作, 就回滚, 重新获取锁, 重新执行操作. 这样一来, 我们就可以允许多个线程同时进行插入删除操作了.
![](/assets/img/project/bustub/bustub-bpt-cc5.png)
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!
![](/assets/img/project/bustub/bustub-bpt.png)