CMU 15-445 Fall 2020 Labs 实现笔记

之前在 YouTube 刷了一下数据库入门基础课程 CMU 15-445/645 的 Lecture Videos,感觉 Andy 是个很有个性也很有趣的人,课堂气氛很活跃,也将数据库的基础知识讲的深入浅出,例子生动。虽然之前大二也修读了数据库的相关课程,但是由于时间限制,并没有讲关于索引并发控制的问题(事务并发控制还是讲了的),也没有讲 Recovery 的知识(听师兄说有一年不仅没讲,期末考试还考了,开卷考考场现学 ARIES),倒是讲了很多 Funtional Dependency 相关的知识。所以看网课也主要看了课内没讲的东西。

当然,课程内容其实大同小异,精华部分还在课程配套的 Lab。当时我上课的课程项目并没有实现 RDBMS,而是小组实现了单线程版的 FPTree [1],用了 libpmem 模拟 PMEM。那个学期课程特别多,还特别硬,所以用五一假期和队友爆肝五天就做完了,就完成了单线程版的,虽然后面完成多线程版有加分,但确实没精力做了。这部分约等于实现了一个 PMEM 上的 Buffer Pool Manager 以及加了一点细节加速叶子节点查找的 B+ Tree。

CMU 15-445 的 Lab 代码可以在 https://github.com/cmu-db/bustub 下载,但是课程页面明确说明已经完成的代码不可以公开。据说这是 Andy Pavlo 花了钱请了实习生写了几个暑假的,他非常慷慨地开放源代码,让不是 CMU 的学生也能学习。每学期都有 4 个 Lab,其中 Buffer Pool Manager 和 Query Execution 是固定节目,Index 部分有 Linear Hash(2019)或者 B+ Tree(2020)。而 Lab 4 可能是 Logging Recovery(2019) 或者 Concurrency Control(2020)。GitHub 上的代码只提供了非常基本的测试,通过了这些测试不代表你的实现就是正确的。需要将代码提交到 Gradescope 上通过更多更严格的测试,Gradescope 的测试代码不会开放。这是为了鼓励学生自己编写测试用例,毕竟现实中的工程开发测试用例也要自己写的,自己的代码质量应该由自己保证。往年 Gradescope 测试都没有开放给非 CMU 学生,今年(2021)开放了测试,可以将自己完成的 Lab 上传上去进行更多测试。Access Code 是 5VX7JZ (https://github.com/cmu-db/bustub/issues/111 ),开放到 2021-12-31。不知道明年会不会开放,我对 Logging Recovery 还挺感兴趣的。

言归正传,15-445 的 Lab 也是完形填空,初始代码提供了类的定义以及接口,学生可以按需要添加更多的接口或者成员,但是不能修改已有的接口(测试代码可能会用到)。从第一个 Lab 开始,都要求实现是 Thread-safe 的,需要对共享的数据结构加锁保护。实话说,个人觉得 bustub 的接口设计比较令人迷惑,我其实花了很多时间去理解接口设计的用意……

Lab 1 Buffer Pool Manager

第一个实验是 Buffer Pool Manager。需要实现 LRUReplacer 以及 BufferPoolManager。我们知道,数据库是以页为单位管理数据存储的,同时为了加速 IO,会将一部分页面缓存在内存中,等到内存不足的时候再将修改过的页面刷写回磁盘。而 Replacer 实现不同的缓存算法,负责在内存不足的时候,决定将哪些页面淘汰以便给新页面腾出空间。当然,如果有线程正在读写某个页面的话,这个页面是不可以被淘汰的。而 BufferPoolManager 则提供接口供线程获取/释放某个页面,隐藏了磁盘操作(由 DiskManager 负责,课程代码已经提供好)以及页面元数据的细节,并在内存不足的时候调用 Replacer 算法决定淘汰页面并按需刷写回磁盘。

这里会接触两个概念,framepageframe 是内存中的空间,和页面大小一样,用来放置从磁盘读取的 page 的内容。一个 page 可以放在任意的空 frame 里,操作者无需关心 page 放在哪个 frame 里,而是由 Buffer Pool Manager 来管理映射关系。操作者只需要调用 FetchPage(page_id) 接口即可获取需要的 page。当 Buffer Pool Manager 需要新的 frame 来存放 page 的内容,会首先查询自己的 freelist 中是否有空闲的 frame,如果没有,再调用 Replacer 的 Victim() 接口决定淘汰某个 frame,并将 frame 的内容刷回 Disk,再将新的 page 读取到 frame 中。如果连 Replacer 都无法淘汰出 frame,那么就 OOM 了,直接返回错误。

这里需要实现的 LRUReplacer 和一般的 LRU 不大一样,只需要一个 list 即可。当然,为了加速操作,可以添加一个 unordered_mapframe_id 映射到 list 中的迭代器。

  • Pin() 接口代表一个 frame 有线程正在读写,不可以被淘汰,那么就直接将这个 framelist 中移除。
  • UnPin() 接口代表这个 frame 已经没有线程读写了,可以被淘汰,又因为这个 frame 最近被读写,所以直接插到 list 后面即可。如果一个 frameUnPin() 两次,我们不需要做任何操作。
  • Victim() 接口代表 Buffer Pool Manager 已经没有空闲的 frame 可以使用,需要淘汰出一个 frame。这时直接将队首的元素移除并返回即可,要是 list 为空,说明 Replacer 中的所有页面都正在被使用,需要返回错误。

而 Buffer Pool Manager 顾名思义,首先要有一个 Pool,Pool 中就是 frame 了,在 Lab 里是 pages_ 成员变量,可以看到它就是一个 Page 数组而已。而 frame_id 就是 pages_ 数组的下标。初始的时候我们将所有的 frame_id 加入到 free_list_ 中,并初始化 Replacer。Buffer Pool Manager 通过引用计数(Page 中的 pin_count 字段的方法跟踪一个 Frame 被多少线程引用。

  • FetchPageImpl() 负责根据 page id 读取一个页面,首先会检查这个页面是否已经在 Pool 中,有则直接返回,并将引用计数加 1。
  • UnpinPageImpl() 说明一个线程不再需要这个页面,可以释放。这时候 Buffer Pool Manager 直接将引用计数减 1。如果为 0,说明已经没有线程使用这个页面了,调用 Replacer 的 UnPin 接口来允许这个 Frame 重新分配。

修改页面元数据的时候,是不需要调用 PageWLatch 方法的,PageRLatchWLatch 是用来保护页面本身的数据(也就是会实际落盘的数据)。

Lab 2 B+ Tree Index

第二个实验是 B+ 树索引,我个人觉得接口设计很有槽点,有些函数例如 Split() 用了模板,但是 Internal Tree Page 和 Leaf Tree Page 的同名接口参数都不一样,需要自己补接口来用上模板。而且 Lab 指导里用的是 reinterpret_cast 直接简单粗暴地将 Page 里的 data 解释成数据结构。一般来说都是需要用序列化/反序列化来转换的。

这部分的代码量比较大,而且因为接口设计的问题,可能要花点时间来理解不同函数到底在做什么。每个 Page 存储了若干 Pair。根据 Internal 和 Leaf 的不同,Pair 的类型也不一样。

  • Internal Tree Page 中,Pair 的 Key 就是 Key,而 Value 是 Page ID。Key[i] <= PageID[i] < Key[i+1],而 Key[0] 是无效的,可以认为 PageID[0] 存放了比 Key[1] 小的所有 Key。自然,PageID[-1] 存放了比 Key[-1] 大的所有 Key。
  • Leaf Tree Page 中,Pair 的 Key 也是 Key,而 Value 则是 RID(RID 即是 PageID+SlotID,用来定位一条记录在哪个 Page 的具体哪个 Offset)。而 Leaf 中的 K-V 则是一一对应的,RID[i] 就是 Key[i] 对应的记录。

具体的数据结构实现也并不难,在插入删除的时候检查节点大小,如果溢出则进行分裂,不足则视兄弟节点情况进行合并或者重分配。在实现的时候注意维护好有序关系以及 KV 对应关系即可。

之前我只实现过单线程版的 B+ Tree,而 Lab 要求实现多线程,则需要加锁。当然,不能简单粗暴地直接对整棵树加锁,这样效率过低。我们可以用 Crab Locking 的方法来只对树的一部分加锁。这里的锁是 Latch,也就是一般常用的 (RW)Mutex。

  • 如果是读操作,那么从树的根节点开始加 RLatch,然后查找子节点,对子节点加 RLatch 成功后立即解锁父节点即可。
  • 如果是插入操作,那么首先从树的根节点开始加 WLatch,并将加了 WLatch 的 Page ID 存入一个队列中(可以用 Transaction 的 AddIntoPageSet 操作。如果检查子节点没有满,说明插入后到这里就不会继续分裂了,就可以释放之前所有父节点加的锁了。需要注意的是,解锁顺序要和加锁顺序一致,否则可能会导致死锁的情况发生。如果子节点满了,那么有可能子节点会需要分裂,从而导致父节点也会需要更新,这时候就不能解锁父节点的锁。
  • 如果是删除操作,相比插入操作会更复杂一些,加 WLatch 的规则是一样的,只是需要检查的条件变成了子节点是不是至少是半满的。而在合并操作后,可能需要删除某个页面,这时候需要用 AddIntoDeletedPageSet 添加需要删除的页面,然后在解锁完成之后删除。

Lab 3 Query Execution

第三个实验是查询执行。这一部分不需要考虑多线程的问题,而且也不需要我们解析 SQL、生成执行计划等,而是用代码手工构建执行计划来进行测试。这一部分比较简单,执行器采用了 Vocalno 模型,每个 Executor 只需要实现 Next() 接口和 Init() 接口即可。 Init() 接口则用于初始化执行器。Next() 接口返回 true 则代表这个执行器还有下一条记录需要返回;false 则代表执行器执行完了,没有更多记录了。简单的代码示意如下:

Tuple tuple;
RID rid;
vector<Tuple> result_set;
executor.Init();
while (exectuor.Next(&tuple, &rid)) {
    result_set.push_back(tuple);
}
return result_set;

Executor 是可以嵌套的,最上层的 Executor 就代表了整条 SQL 语句。

实现 Executor 的时候,涉及到更新的部分,例如插入删除等,要记得同时更新 Table 中的所有 Index。

Lab 4 Concurrency Control

第四部分则是将查询执行更改为支持事务。Executor Context 中可以获取到事务指针。实验中,事务获取锁的粒度是 Tuple,也就是以 RID 为 Key 来查询锁的信息。在 Executor 执行过程中,需要通过 Lock Manager 来获取锁,如果发生锁冲突的情况则会 Block 住锁请求。

不同于操作系统的锁,Lock Manager 是需要实现死锁检测的功能的,因此,需要将所有锁的信息保存在数据结构中,并定时检测锁之间的依赖是否产生了环,如果有,则想办法打破这个环即可解除死锁状态。

在实验提供的框架中,对于每一个 RID,都有一个对应的 Lock Queue 存放了当前已申请(可能没有被允许)并且还没释放的锁,当一个事务调用 LockShared 申请 S 锁的时候,只需要检测这个锁的前面是否有 X 锁即可,如果有,则不能申请成功。而当一个事务调用 LockExclusive 申请 X 锁的时候,则检测前面是否已经没有锁在排队,如果有,则同样不能申请成功。而一个事务持有 S 锁,需要对 Tuple 进行写操作的话,需要升级为 X 锁(不能先解锁再加锁),这时候和 LockExclusive 同理,只是不仅需要检测前面的锁是否冲突,还要检测后面是不是有锁已经被 Granted(例如后面也是 S 锁)。

实验中,死锁检测算法采用了有向图判环的算法来检测是否有死锁。Lock Manager 会在启动的时候启动一个后台线程,定时执行死锁检测算法。而死锁检测首先需要根据当前锁的排队情况生成等待图。等待图的每一个节点 V 表示一个事务,一条有向边 V1->V2 则代表 V1 需要 V2 当前持有/等待的锁。

生成等待图的算法也很简单,对于每一个 Queue 中的每一个锁请求,检测在它前面的锁是否和它冲突即可,冲突则在图中添加节点和边。只有 S 锁和 S 锁是兼容的,其他的情况都是不兼容的。构建好图之后,运行一次三色 DFS 算法判环即可,不过测试好像要求起点要根据事务 ID 从小到大排。

如果有环的话,需要选择一个事务终止,实验的策略是选择最年轻的事务,实际上就是 ID 最大的事务。

而 Executor 这边则需要在每个读取和修改 Tuple 的地方都添加申请锁的代码。需要注意的是,因为下层的 Executor 可能已经在这个事务中对 Tuple 加锁了,每次加锁前都需要从 Transaction 指针查询当前的 RID 是不是已经加了对应的锁。假如要申请 S 锁,那么已经申请了 S 锁和 X 锁都是可以的,如果要申请 X 锁,却发现已经申请了 S 锁,那就申请锁升级。

这一部分的测试感觉比较弱,个人觉得自己的 LockUpgrade 没有实现的很周全,一样通过了全部测试。

[1] Oukid, Ismail, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. “FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory.” In Proceedings of the 2016 International Conference on Management of Data, 371–86. San Francisco California USA: ACM, 2016. https://doi.org/10.1145/2882903.2915251.