BusTub 通关总结

Project #0 - C++ Primer

是个前期热身项目，考察对 C++ 的掌握。

要求实现一个并发 Trie 支持的 kv 存储，存储 map 到任何类型的 value 的 string key。Trie 中的每个节点存储一个键的单个字符，并且可以有多个子节点，这些子节点表示不同的可能的下一个字符。当到达一个键的结尾时，将设置一个标志来指示其对应的节点是一个结束节点。

例如，考虑在 trie 中插入 kv 对(“ ab”，1)和(“ ac”，“ val”)。这两个键共享同一个父节点 “a”。在左边的子节点中，与键 “ab” 对应的值 1 存储在节点 “b” 中，与键 “ac” 对应的值 “val” 存储在节点 “c” 中。

Project #1 - Buffer Pool

解析

因为磁盘和内存的访问速度存在差异，为了权衡二者，需在内存中建立一个 Buffer Pool，并通过 Buffer Pool Manager (BPM) 管理 physical page 在内存与磁盘之间的移动。BPM 向系统提供获取 page 的接口，系统通过 page_id 向 BPM 索要对应的 page，而不关心该 page 具体存放位置。也就是说，系统并不关心（也不可见）获取这个 page 的过程（从 disk 或 memory 上读取），也不关心 page 可能发生的在 disk 和 memory 间的移动。这些内部的操作都交由 BPM 完成。

Project1 就要求我们实现一个 BPM。它包括三个组件：

• Extendible Hash Table
• LRU-K Replacer
• Buffer Pool Manager Instance

Extendible Hash Table 和 LRU-K Replacer 是 Buffer Pool Manager 内部的组件。Extendible Hash Table 用于实现 page table 做页面映射 (将 page id 映射为 Buffer Pool 中 frame 的 frame id)。 LRU-K Replacer 用于实现缓存驱逐策略，完成 Buffer Pool 空间不足时 frame 的移除工作。

Disk Manager 已经为我们提供，是实际在 disk 上读写数据的接口。

Project #2 - B+Tree

解析 (上)

解析 (下)

实现 BPM 之后，我们要考虑 BPM 之上的东西，也就是 Access Method，对数据库数据进行读/写的方式，为实现比 Sequential Scan 更快的数据检索，常用哈希索引和树索引。

Project2 要求我们实现一个 B+Tree 索引结构，支持插入 Insert()，点搜索 GetValue()，和删除 Delete(); 还要实现一个索引迭代器，来直接检索所有 leaf page。 并通过 latch crabbing 的方式支持索引并发。该 Project 中官方还提供了 B+Tree 的可视化工具来为本地代码实现生成可视化 B+Tree，并提供在线 B+Tree 生成网站，可通过二者对比进行 Debug。

这里要注意的是，B+Tree 的结点也存储在对应 page 中，我们要理清 B+Tree 涉及的 page 与普通 page 的差别：

另外要关注的就是 B+Tree 内部结点和叶结点的各自的最小和最大 kv 个数。

n 路B+树：n - 1 个 key，n 个 pointer

叶子结点使用 \([0 ～ n-2]\) 范围 array_

内部结点使用 \([0 ～ n-1]\) 范围 array_，第 0 个只有 value (即 pointer) 没有 key (key 设为 INVALID_PAGE_ID)

叶子结点 size 最大是 \(n-1\)，最小是 \(\lceil(n - 1)/2\rceil\) ，也即 \(\lfloor n/2\rfloor\)

内部结点 size 最大是 \(n\)，最小是 \(\lceil n/2\rceil\) ，也即 \(\lfloor(n+1)/2\rfloor\)

叶子结点设置 maxSize = n，MinSize = n / 2，叶子结点大小 minSize ≤ size < maxSize

内部结点设置 maxSize = n，MinSize = (n + 1) / 2，内部结点大小 minSize ≤ size ≤ maxSize

Project #3 - Query Execution

解析

BusTub 的整体架构如下：

Project3 我们要实现一个让 BusTub 执行 query 的组件。具体到代码上，要实现基于 火山模型 的 sql 执行器，完成 SeqScan, Insert, Delete, IndexScan, Aggregation, NestedLoopJoin, NestedIndexJoin, Sort, Limit 等 Executor 的逻辑，以及 Top-N 优化规则。

选做部分 Leaderboard Task 是实现 HashJoinExecutor，针对给出的三个 query 设计一些 optimizer rules，自由度也很高，可以自定义任意的优化比如列裁剪、谓词下推、常量折叠等等。

前两个 Project 是一个点，从 Project3 开始，点就连成了面，我们要在自己写的缓存池和 B+Tree 索引上真正的去跑一些算子，这个 Project 的一个难点在于要大量阅读相关源代码。完成 Project3 后，就可以当作一个单机数据库跑一些 sql 了，包括 select，insert/delete，inner/left join，agg，groub by，order by，limit 等。

这里我画了张图便于对代码 (主要是 Catalog, table, index 的结构以及它们之间的关系) 的理解：

Q：我们在 Project 1 中实现的 Buffer Pool 和在 Project 2 中实现的 B+Tree Index 在哪里？

A：实际上就在一系列算子下。例如 SeqScan 算子，需要遍历 table，首先通过数据库的 catalog 找到对应的 table，一个 table 由许多 page 组成，在访问 page 时，就用到了 Buffer Pool。在 Optimizer 中，假如发现 Sort 算子在对 indexed attribute 排序，会将 Sort 算子优化为 IndexScan 算子，这样就用到了 B+Tree Index。

Project #4 - Concurrency Control

解析

解析 (Leaderboard Task)

Project4 要求对并发事务的管理，保证多个事务在数据库并发执行时的隔离性。实现基于 2PL 的事务并发控制，自动为并发事务执行加锁解锁，支持 Repeatable Read、Read Commited、Read Uncommited 三种隔离级别。因为 2PL 不可避免产生死锁，还要实现一个后台死锁检测、死锁解除线程。在此基础上，最后我们还要修改之前实现的 SeqScan、Insert 和 Delete 算子，加上适当的锁以实现并发的查询。

选做部分 Leaderboard Task 要求实现 (1) 将谓词下推到 SeqScan 以锁定更少的 tuples; (2) 实现 UpdateExecutor 这样 tuples 就能被就地更新，而不用先 Delete 在 Insert; (3) 将谓词下推到 IndexScanExecutor 来做索引查询。

截止 2023.04.24，GradeScope 上的Leaderboard：

Project 1

这里我对 Extendible Hash Table 直接一把大锁摆烂了