CMU 15-445 Fall 2020 Labs 实现笔记

1 Lab 1 Buffer Pool Manager
2 Lab 2 B+ Tree Index
3 Lab 3 Query Execution
4 Lab 4 Concurrency Control

之前在 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 算法决定淘汰页面并按需刷写回磁盘。

这里会接触两个概念，frame 和 page：frame 是内存中的空间，和页面大小一样，用来放置从磁盘读取的 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_map 将 frame_id 映射到 list 中的迭代器。

Pin() 接口代表一个 frame 有线程正在读写，不可以被淘汰，那么就直接将这个 frame 从 list 中移除。
UnPin() 接口代表这个 frame 已经没有线程读写了，可以被淘汰，又因为这个 frame 最近被读写，所以直接插到 list 后面即可。如果一个 frame 被 UnPin() 两次，我们不需要做任何操作。
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 重新分配。

修改页面元数据的时候，是不需要调用 Page 的 WLatch 方法的，Page 的 RLatch 和 WLatch 是用来保护页面本身的数据（也就是会实际落盘的数据）。

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.