项目准备

项目地址：Project #3 - Query Execution。

准备工作：阅读 Chapter 15 16 22，学习 Lecture #10 #11 #12 #13 #14，以及阅读课堂笔记。

项目结构

通过查看 sqllogictest.cpp，可以知道 SQL 语句的整个执行流程。首先调用 SQLLogicTestParser::Parse 将测试文件解析为多个测试记录，然后根据记录的类型分别处理。目前我们主要关注查询语句，只需查看 BustubInstance::ExecuteSqlTxn 函数的代码。如项目介绍描述的那样，代码分别执行 Binder,Planner,Optimize,ExecutionEngine。然后，本来想详细分析一下整个流程，但是由于时间原因，以及项目确实比较复杂，所以暂时搁置。

Task #1 - Access Method Executors

实现

① 遇到第一个问题，如何在 SeqScanExecutor 中遍历表，可以发现 exec_ctx 成员所属的类 ExecutorContext 中有一个 GetCatalog 方法，只要拿到 Catalog 就可以根据 plan_ 中的信息拿到 TableHeap 的迭代器 TableIterator。然后第二个问题就是如何存储迭代器，TableIterator 是不可复制的，我们可以使用 unique_ptr 来存储迭代器，并使用 make_unique 初始化。（注意，不能在构造函数初始化，一定要在 Init 函数中初始化，不然多次全表扫描会出问题！）

② 实现 Insert 时报错 “The executor will produce a single tuple of integer type as the output, indicating how many rows have been inserted into the table”，并且可以看到 Next 函数的注释中表示 “tuple The integer tuple indicating the number of rows inserted into the table”。说实话有点难以理解，我一开始以为每次调用 Next 会像迭代器模式一样，只执行一次插入，但是这样实现就会报上面的错误。然后通过查看 Discord 的讨论，发现是一次性插入所有记录，因为只要返回 true 就会打印插入的行数，返回 false 就不会打印。当插入零行时，还必须打印一个零，这说明，Next 必定要先返回 true，再返回 false。并且在构造 tuple 时需要使用 BIGINT 类型，不然会报其他错误（明明注释说的是 INTEGER 额）。

③ 在 Insert 的同时需要更新索引，一开始我是直接用普通的 tuple 作为 InsertEntry 的参数，结果在测试 p3.05-index-scan.slt 时报 stack buffer overflow 错误。通过 Debug 发现，在 InsertEntry 时会调用 GenericKey 类的 SetFromKey 函数，该函数会将 tuple 的数据拷贝到该类的 data_ 成员中，作为索引的 key 使用。所以传入的 tuple 必须只包含 key，那么如何确定 tuple 中的哪个数据是 key 呢。可以发现 Tuple 类中有 KeyFromTuple 函数，它的会生成只包含 key 的 tuple，因为需要的索引的 key，那么该函数必定需要传入和索引相关的模式，以及 key 所在列的下标，这些信息可以在 IndexInfo 中找到。（之前我有点迷糊，当成 MySQL 默认使用主键索引了，BusTub 使用的是 TableHeap，也就是说表默认是没有索引的）

④ 实现时不要使用 GetTableOid 函数，因为线上测试的函数名是 TableOid，可能是因为我 fork 的版本太新了，仓库的代码和测试代码不一样，所以只能直接使用 table_oid_ 成员。

⑤ 实现 update 时要注意，在创建新 tuple 时，使用的是 child_executor_->GetOutputSchema()，而不是 GetOutputSchema()。

⑥ 实现 index_scan 时，会使用到 b_plus_tree_index.h 中定义的别名，如 BPlusTreeIndexIteratorForTwoIntegerColumn。

⑧ 在 IndexScan 的提示中有这么一句话，“do not emit tuples that are deleted”，但是当从表中删除 tuple 时，也会从索引中删除对应的 key，所以应该不会遍历到已经删除的 key 才对，也就是说此时应该不用特判 TupleMeta 中的 is_deleted_ 成员。

⑨ 测试 p3.06-empty-table.slt 时，遇到 B+Tree 迭代器实现问题。当 B+Tree 的为 empty 时，获取迭代器我原来是抛出异常，现在改为返回一个默认构造的迭代器。

补充

① 当没有显示声明复制/移动构造函数或复制/移动运算符，以及析构函数时，编译器才会隐式生成这些函数（其他更复杂的情况可以查看 cppreference.com）。

② 创建 TupleMeta 时，会将 insertion_txn 和 deletion_txn_ 都初始化为 INVALID_TXN_ID，提示表示这些成员会在以后切换到 MVCC 存储时使用，有点遗憾没能体验一下。

③ vector 的 reserve 只会影响 capacity 的大小，而不会影响 size，讨论在此。

④ 重载前置和后置 ++ 的区别，前置 ++ 的重载声明为 operator++()，后置 ++ 的重载声明为 operator++(int)。

⑤ 为什么应该将移动构造声明为 noexcept，可以阅读 Friendly reminder to mark your move constructors noexcept。

Task #2 - Aggregation & Join Executors

实现

① 一开始实现真摸不着头脑，AggregationPlanNode 里面怎么这么多东西。group_bys 是指 GROUP BY 时对列的求值表达式，aggregates 是指使用聚合函数时对列的求值表达式，agg_types 是指聚合函数的类型。例如：GROUP BY DAY(col)、MIN(col1 + col2)。我们使用 InsertCombine 函数向哈希表插入值，参数可以使用 MakeAggregateKey 和 MakeAggregateValue 函数获得。

② 根据项目介绍，AggregationExecutor::Next 返回的 tuple 应该包含 key 和 value（我没看到，找错好难）。特别需要注意，当哈希表为空时，应该返回什么：如果是对某列进行 GROUP BY 操作，那么就返回 false，因为有个测试用例有注释 no groups, no output；否则，返回 true，并且 tuple 存储聚合函数的默认值。（可以通过判断 key 模式的列数是否为零，或者 value 模式的列数是否等于 plan_ 输出模式的列数，来判断当前是否对某列进行 GROUP BY 操作）

③ 实现 NestedLoopJoinExecutor：外层循环遍历左表，内层循环遍历右表，只有当右表遍历完，才会获取下一个左表中的元组。但是，因为每找到一个匹配就会返回，所以我们应该将左表的元组作为数据成员，并且添加一个标志表示右表是否遍历完。每当右表遍历完成，都需要重置标志，获取左表中的下一个元组，并且重新 Init 右表。我们调用 EvaluateJoin 判断元组是否匹配，如果匹配，就将两个元组合并为一个元组。特别注意，如果当前是左连接，并且左元组没有匹配任何右元组，仍然需要返回一个为右元组填充 null 值的合并元组。比较迷惑的是怎么表示 null，我的想法是根据列类型获取对应的 null 值，但是找不到这样的函数，所以我就直接返回 BUSTUB_INT32_NULL 了。突然看到聚合执行器里用到 ValueFactory::GetNullValueByType 函数，太久没写项目给忘了。我还遇到一个 BUG，调试半天，发现我没有在 Init 函数中初始化 SeqScanExecutor 的迭代器，导致重复调用 Init 时不会重置迭代器。

④ 实现 HashJoin：根据提示我们可以参考 SimpleAggregationHashTable 的实现建立一个哈希表，我们创建一个 JoinKey 类作为键，然后创建一个 hash<bustub::JoinKey> 类，直接复制 aggregation_plan.h 中的代码改个名字就行（不然 C++ 真不熟，又要搞半天）。在哈希表中，将 vector<Tuple> 作为值以处理哈希冲突。搞定哈希的方式之后，我们可以像 aggregation_executor.h 一样添加两个辅助函数 MakeLeftJoinKey 和 MakeRightJoinKey。然后直接在 Init 中对左表建立哈希表，在 Next 中遍历右表，类似 NestedLoopJoinExecutor 的实现，只不过此时需要维护更多的数据成员。特别需要注意如何处理左连接，因为我们是将左表建为哈希表，那么在遍历完右表后，还需要处理没有任何匹配的左表中的元组。这可以在匹配时将元组的地址存储在 unordered_set 中，然后在遍历完右表后再遍历一次左表，并检查 unordered_set 来判断是否输出。（之前我是将元组的 RID 存储到集合中作为标识，但是这是错误的，因为左表可能是临时表，其中元组的 RID 是无效的内容；我们也可以为右表建立哈希表而不是左表，这样对于左连接来说，更好处理）

⑤ 实现 Optimizing NestedLoopJoin to HashJoin：非常的神奇，参考 nlj_as_index_join.cpp 瞎改，感觉代码是一坨，但是竟然没有任何错误，直接通过测试（激动半天）。具体实现的话，一开始我以为传入的参数就是 NestedLoopJoin 计划节点，但是似乎不是，所以我们需要遍历当前计划的子节点，递归的进行优化。之前比较令我迷惑的一点，怎么判断表达式是否是某个类型，我查找很久 API 都没有找到类似的函数，然后想到 Project #0 中好像是直接做 dynamic_cast 转换，如果返回值为 nullptr 就表示类型不匹配，查看 nlj_as_index_join.cpp 发现果然是这样。搞定表达式类型判断之后，就可以根据 ColumnValueExpression::GetTupleIdx 值来交换左右表达式，并返回转换后的节点。

Task #3 - Sort + Limit Executors and Top-N Optimization

Easy！只有两点需要注意：一个是每次调用 Init 时都要初始化所有数据成员，不然下次调用会包含上次调用的数据；第二个是 C++ 的 priority_queue 默认是大顶堆，并且比较器和 Java 中的用法完全相反。

Optional Leaderboard Tasks

① 初次提交。

② 之后优化。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/bin/bash
make sqllogictest -j$(nproc)

./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.01-seqscan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.02-insert.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.04-delete.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.03-update.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.05-index-scan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.06-empty-table.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.07-simple-agg.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.08-group-agg-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.09-group-agg-2.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.10-simple-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.11-multi-way-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.12-repeat-execute.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.14-hash-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.15-multi-way-hash-join.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.16-sort-limit.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.17-topn.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.18-integration-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.19-integration-2.slt --verbose

make format
make check-lint
make check-clang-tidy-p3
make submit-p3

项目小结

项目难度主要在项目理解上，常常是不理解某些变量的实际含义，或者知道该怎么做，却找不到对应的 API，或者对返回值理解有错误，而函数文档也不清晰。最后，看到实现的代码能够执行各种 SQL 语句，感觉还是很不错的。

项目准备

项目地址：Project #2 - B+Tree

准备工作：阅读 Chapter 14.5 24.5 14.1-14.4 18.10.2，学习 Lecture #07 #08 #09，以及阅读课堂笔记。

Task #1 - B+Tree Pages

实现

① 第一个比较迷惑的点就是 max_size_ 的含义，对官方提供的B+Tree进行插入操作，发现叶子节点的 size_ 不会到达 max_size_。难道叶子节点实际只能包含 max_size_ - 1 个 key 吗？通过查看项目地址中的 Requirements and Hints 可以发现，官方建议叶子节点在插入后大小达到 max_size_ 时，进行分裂，内部节点在插入前大小达到 max_size_ 时进行分裂。所以对于内部节点，max_size_ 表示它能包含的指针数量；对于叶子节点，max_size_ 表示它能包含的键值对数量。

② GetMinSize 的实现，同样参考官方示例，对于非叶子节点，返回 (max_size_ + 1) / 2；对于叶子节点，返回 max_size_ / 2。为什么要这样，参考第 ① 点也就明白了，这样可以保证分裂后的两个节点的大小都至少为最小大小，所以该方法的实现实际上取决于分裂的具体实现（即何时分裂）。

补充

① 如何理解 MappingType array_[0]，注释表示它是 Flexible array member for page data，参见维基百科Flexible array member。似乎是 C 语言的特性，C++ 标准不支持，但是 C++ 的编译器普遍会支持。

② 在内部节点和叶子节点中，array_ 的唯一区别就是在搜索内部节点时不能使用 array[0]_.first，因为它并不能准确表示 array_[0].second 中 key 的范围（向 array_[0].second 中插入一个更小的 key，它就失效了）。

Task #2a - B+Tree Insertion and Search for Single Values

实现

① 比较纠结的是既然要使用二分查找，如何保证节点内部 key 的有序性，因为是使用数组存储的，所以似乎只能花费 \(O(n)\) 时间来移动元素了？或者可以加一个数据结构存下标，来保证有序性，但是涉及分裂和删除操作还是比较难搞的，暂时不优化。

② 可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Search 函数，来实现二分查找指定 key。内部节点一定可以找到一个满足条件的位置（因为我们找的实际上是指针），而叶子节点如果找不到指定 key，那么就返回 -index - 1（方便之后插入，类似 Java 中的 BinarySearch）。具体的实现逻辑：

• 内部节点从位置 1 开始找第一个大于 key 的键，返回它左边位置，即 index - 1。
• 叶子节点从位置 0 开始找第一个大于等于 key 的键，如果越界或者键值不等于 key，则返回 -index - 1，否则返回 index。

③ 特别注意 PageGuard 的使用，只有当操作完页面之后，才对其进行 Drop 操作（移动赋值以及匿名对象的析构都会导致该操作）。并且用完页面后及时 Drop，这样可以尽早释放页面的锁以及 Unpin 页面。插入时，利用 latch crabbing 技巧，先拿到下个页面的锁，然后根据页面大小判断是否 Drop 上个页面（使用 Context）。注意拿锁和 Drop 的顺序，以及该大小判断依赖于分裂的实现，详细见 Task #1 - B+Tree Pages ①。

④ 获取页面需要进行类型转换，如果只读不写就使用 page_guard.h 中提供的 As 函数，只有需要写页面时才使用 AsMut 函数，因为该函数会将页面置为脏页。先将其转换为 BPlusTreePage，然后再根据页面类型，将其转换为内部节点或叶子节点，注意 BPlusTree 类中已经为我们提供了别名：

1
2

using InternalPage = BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator>;
using LeafPage = BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>;

一开始我没有注意，在对内部节点转换时，误将其 page_id_t 转为 ValueType，导致完全误解了整个项目的结构。

⑤ 分裂叶子节点和内部节点时，注意判断当前节点是否是根节点。我们可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Split 函数，来实现分裂。

叶子节点的分裂操作比较简单，就是移动然后设置大小，为了不让页面类和其他类耦合（BufferPoolManager，Context），我将分裂函数的参数设计为 BPlusTreeInternalPage &new_page，它会返回将插入到上层的 key，即新节点的第一个 key。

内部节点的分裂操作比较复杂，并发测试时遇到边界样例才发现，因为内部节点的分裂是插入前分裂，所以还需要考虑插入的那个键的大小。如果 key 比 array_[GetMinSize() - 1] 小，则插入到当前节点，否则插入到新分裂的节点。并且，在插入新分裂的节点时，可能会插入到索引为 0 的位置，这一点要特别注意。最后，也是返回新节点的第一个 key（指的是 array_[0].first，因为分裂的时候复制了）。

⑥ 同理，在内部页面和叶子页面类中可以添加 Insert 函数。需要注意的是，这两个函数的实现有些点不同。对于内部节点，当 B+Tree 的根节点分裂时，该情况会将 page_id 插入到内部节点的第一个没有键的位置，所以我们可以将参数设计为 const std::optional<KeyType> &opt 来区分这种情况。对于叶子节点，由于不能有相同的键，所以根据 Search 的实现，当 index ≥ 0 时返回 false，否则继续插入。

调试

调试时可以先使用可视化网站查看 B+ 树，方便定位问题，我们可以使用 shell 脚本一键生成文件（解决方案）：

1
2
3

#!/bin/bash
make b_plus_tree_printer -j$(nproc)
{ echo 2 3; echo i 1; echo i 2; echo g my-tree.txt; echo q; } | ./bin/b_plus_tree_printer

在生成文件时可能会报 [b_plus_tree.cpp:356:Draw] WARN - Drawing an empty tree 错误，原因是我们没有实现 b_plus_tree.cpp 中的 IsEmpty 函数。

补充

① 如何使用 upper_bound 和 lower_bound（Java 选手表示踩了很多坑），可以看看 cppreference 的示例代码，尤其注意 lambda 表达式的使用（参数顺序，以及大小的比较）。

② 测试时忽略 iterators 的测试。

③ GetValue 注意特判根节点是否存在，否则可能引发空指针异常（依赖于 BufferPoolManager 的实现）。

Task #2b - B+Tree Deletions

实现

① 删除操作可以分为两种情况，相邻节点重新分配和相邻节点合并。进一步可以划分为操作当前节点的左节点，还是右节点。需要注意的是，我们只有对相同父节点的两个子节点执行上述操作，一个非根节点必定有一个同父的左节点或右节点。（如果不这样限制，实现起来会很麻烦，需要找到最近公共祖先，做键值的替换。）为了能够获取左右节点的页面，我们在从上到下找 key 对应的页面时，可以同时保存左右页面的 page_id。

② 重新分配操作，需要区分左右。如果从右节点取，则需要更新右节点对应父节点中的 key；如果从左节点取，则需要更新当前节点对应父节点中的 key。操作完可以直接返回。

③ 合并操作同理，只不过不是更新，而是删除对应父节点中的 key（递归删除）。注意，如果合并叶子节点，需要同时更新 next_page_id_。（合并之后右侧的页面永远都不会被使用，或许需要对其执行 DeletePage 操作，在 DeletePage 之前需要 Drop/Unpin 页面。有个疑问，DeletePage 之前 Drop 之后，如果有线程 Fetch，那么删除页面的操作就会失败。）

调试

实现的思路弄明白后，大方向上就不会出错，但是很多细节容易写错：变量名字，重复执行 pop_back() 操作，删除页面后对页面进行操作等等。不过，说实话官方提供的可视化类真好用，Debug 全靠可视化来定位问题。磨磨蹭蹭，花费一天时间，做得有点慢。

Task #3 - An Iterator for Leaf Scans

基本上没有难度，遇到唯一的错误就是把 GetSize 打成了 GetMaxSize（因为用的自动补全）。

Task #4 - Concurrent Index

① 遇到问题，先定位它是什么问题。首先，应该解决非并发问题，我们可以在插入和删除的开头加一把大锁，然后利用并发测试 MixTest2，来混合查找、插入和删除操作，看看是否存在问题。为了尽可能引发问题，可以将叶子节点和内部节点的最大大小修改为 2 3，将 total_keys 修改为 1000，尽可能的触发分裂和合并操作（这个测试，比线上测试还强，多跑几次线上能过的给报错了）。在混合时，可以分别混合查找和插入，查找和删除，插入和删除，这样方便定位问题出在哪里。然后，再去进行并发优化，一点一点优化，边优化边测试，这样就不会因为找不到 Bug 的位置而发愁啦。

② 遇到错误，[disk_manager_memory.h:104:ReadPage] WARN - page not exist，发现是 BufferPoolManager 的 Bug，需要跑回去修复。一天后，终于真正的把 Bug 修好了，代码也稍微重构了一下，哈哈，真的 99% 不会报错（有个 FetchPageBasic/Read/Write 返回 nullptr 的错误没修复，报错概率很低，以后有问题再修），不得不说本地测试用例修改后是真的强劲，线上强度不够啊。（但是重构了个寂寞，效率没变，难受啊）

③ B+Tree 的并发问题其实基本没有，都是单线程问题或者 BPM 的并发问题，B+Tree 的并发只要注意 Fetch 和 Drop 的顺序就 OK。

(Optional) Leaderboard Task

① 初次提交通过，排名还挺高。额，多次提交能差七八万。感觉测试有问题，平均 QPS 也就十万多。

② 优化暂时搁置。

测试结果

Checkpoint #1 说简单也不简单，感觉有些细节总是写错，包括下标的处理，C++ 二分查找函数的使用，变量名称，以及一些边界条件。说难也不难，线上测试首次提交就通过了。总共花了一天半吧。

Checkpoint #2 总共花了两天，任务三四没什么难度，主要时间还是在删除操作，以及修复插入操作中的 Bug。

1
2
3
4
5
6
7
8
9
10

#!/bin/bash
make b_plus_tree_insert_test b_plus_tree_sequential_scale_test b_plus_tree_delete_test b_plus_tree_concurrent_test -j$(nproc)
./test/b_plus_tree_insert_test
./test/b_plus_tree_sequential_scale_test
./test/b_plus_tree_delete_test
./test/b_plus_tree_concurrent_test
make format
make check-lint
make check-clang-tidy-p2
make submit-p2

项目小结

开始做项目之前，对插入和删除具体怎么操作还是比较迷糊的，实际实现起来发现原来是这样的。特别需要注意别打错变量名，我用自动补全总是搞混 MaxSize 和 MinSize，还有各种变量都敲错，运行起来找 Bug 就头疼了。还要注意，内部节点和叶子节点分裂的时机不同，实现也不同，以及在分裂时如何对待内部节点的第一个 key。然后删除操作就是个分类讨论，弄明白就不难了。并发错误我也真是见识到了，BPM 优化需谨慎啊。（做得还是很慢，对大佬来说，其实就是个复杂点的模拟题吧）

项目准备

项目地址：Project #1 - Buffer Pool

准备工作：阅读 Chapter 12.1-12.4 13.2-13.3 24.2，学习 Lecture #03 #04，以及阅读课堂笔记。

项目结构

buffer_pool_manager

pages_ 数组相当于缓冲池，frame_id 是该数组的下标，也就唯一标识一个 Page，即标识一个缓冲页面。一个 Page 可以存储不同的物理页面，Page 的数据成员 page_id_ 唯一标识一个物理页面。因为不管是 FetchPage，还是 DeletePage 等函数，我们都是针对实际的物理页面做操作，所以 buffer_pool_manager 中的函数的形参都是提供 page_id。

lru_k_replacer

该类提供缓冲页面的淘汰策略，即淘汰某个 fram_id 对应的缓冲页面。一个缓冲页面会有一个对应的 LRUKNode，它负责记录该缓冲页面的访问历史。

page_guard

主要有三个类：BasicPageGuard，ReadPageGuard 和 WritePageGuard。BasicPageGuard 的作用是保证缓冲页面在使用完后会进行 UnpinPage 操作。而 ReadPageGuard 和 WritePageGuard，它们和 BasicPageGuard 是组合关系，它们的作用在 BasicPageGuard 的基础上保证页面在使用完后会解除读写锁。

Task #1 - LRU-K Replacement Policy

实现

① 一开始以为 current_timestamp_ 自动就是当前时间戳，调试时发现一直是 \(0\)，我真笨。可以直接从 \(0\) 开始手动模拟时间戳，调用 RecordAccess 时，让当前时间戳加 \(1\) 即可。

② 在 Evict 的注释中有：If multiple frames have inf backward k-distance, then evict frame with earliest timestamp* based on LRU。我以为淘汰的是最后一次访问时间最早的 frame，结果淘汰的是第一次访问时间最早的 frame。

③ 在 ListNode 中使 history_ 的长度不超过 k_，如果超过就调用 pop_front()，这样每次获取之前第 k_ 个访问记录只需要调用 front() 函数。

④ 在 RecordAccess 的注释中有：If frame id is invalid (ie. larger than replacer_size_), throw an exception。但其实应该是大于等于吧，因为 BufferPoolManager 构造函数的实现如下：

1
2
3
4
5
6
7
8

// we allocate a consecutive memory space for the buffer pool
pages_ = new Page[pool_size_];
replacer_ = std::make_unique<LRUKReplacer>(pool_size, replacer_k);

// Initially, every page is in the free list.
for (size_t i = 0; i < pool_size_; ++i) {
    free_list_.emplace_back(static_cast<int>(i));
}

上述代码说明 frame_id 是小于 pool_size 的，所以大于等于 pool_size 的 fram_id 都应该抛出异常。（或许小于零的也应该抛出异常）

补充

① 测试时将 DISABLED_SampleTest 改为 SampleTest。

② 忘记 C++ 的 = 是拷贝，传引用加上 &：

1

auto node = node_store_.at(frame_id); // 错误：拷贝

③ LRU 的中文翻译是“最近最少使用”，实在让人很无语，我以后就将其称为“最久未被使用”吧。

Task #2 - Buffer Pool Manager

实现

① NewPage 和 FetchPage 有很多逻辑相同的部分，可以加个辅助函数来获取 frame_id。

② 注意，在 FetchPage 时，如果页面在内存中并且 pin_count_ = 0，则需要将其设置为不可淘汰的。

③ 在 UnpinPage 中，更新 is_dirty 属性时使用或运算，因为可能某个线程修改了页面数据，而其他线程没有修改。

④ 在 FlushPage 中，注释表示 REGARDLESS of the dirty flag，应该说的是函数调用者，我们在实现时可以根据 is_dirty 来判断是否实际刷盘。

补充

① 提交 GradeScope 报错时，下面会显示一堆 LeakSanitizer: detected memory leaks。但是没有关系，这应该是由于测试程序提前终止引发的，直接解决上面的错误就行。

② 实现 FetchPage 时，有个情况我忘记调用 RecordAccess，竟然通过所有线上测试了，后来检查代码才发现，修改后 QPS 快了一些。

Task #3 - Read/Write Page Guards

实现

① 使用移动构造和移动赋值后，需要清除 that 的元数据。

② 移动赋值的调用者，也就是 this，如果其 page_ != nullptr，那么需要先将其 Drop，再进行赋值操作。

③ 实现读写页面守卫的移动构造函数，可以直接赋值 std::move(that.guard_)，相当于调用之前实现的 BasicPageGuard 的移动赋值运算符。

④ 实现读写页面守卫的 Drop 时，需要注意在调用 guard_.Drop() 之后再解锁页面，所以在 Drop 之前需要保存一下指向页面的指针。

⑤ 在实现 BufferPoolManager 中的 FetchPageRead 和 FetchPageWrite 时，为页面加读写锁。

⑥ 和 PageGuard 有关的 FetchPage 函数会返回一个 PageGuard 对象，但是如果所有缓存页已经被 pin，那么该返回什么。一开始我是直接拿 nullptr 构造 PageGuard，但是发现不对，因为 PageGuard 对象并没有检查 page_ == nullptr 的函数，所以页面必须被 Fetch 到。要不就一直自旋，要不就使用条件变量，但是使用条件变量又要加个锁，防止通知丢失，那样锁竞争会很激烈啊。（不是很想改，BufferPoolManager 和 B+Tree 的线上测试都能过，暂时不管）

Leaderboard Task (Optional)

准备

性能分析

看到CMU 15-445 2023 P1 优化攻略中使用火焰图做性能分析，之前从来没听说过，打算学习一下。以下是几个不错的网站，奈何感觉很复杂啊。一开始我是用 perf 做分析，然后使用 speedscope 进行可视化，但是捣鼓半天还没弄明白，遇到很多问题，有空再搞吧。

• Brendan Gregg’s Homepage
• How to use flamegraphs for performance profiling
• profiling 与性能优化总结
• speedscope

LRU-K（对优化似乎没有帮助）

关于 LRU-K 的论文：The LRU-K Page Replacement Algorithm For Database Disk Buffering。

LRU 存在的问题：仅根据页面的最后一次访问时间进行淘汰，它不知道页面是否经常访问，从而可能将不经常访问的页面长时间保留在缓冲区中。（论文中对此有两个场景分析）

解决方案：① 页面池调优，缺点是需要人工操作，并且不能适应移动热点；② 查询执行计划分析，缺点是在多用户的场景下，查询优化器可能会以复杂的方式重叠；③ LRU-K，自适应的。（有点不是很懂）

LRU-K 和 LFU 的区别：LRU-K 有一个“老化”的概念，即只考虑对页面的最后 K 次引用，而 LFU 无法区分最近和过去的引用频率，因此无法应对不断变化的访问模式。

LRU-K 存在的问题：① Early Page Replacement，新加入缓冲池的页面因为访问次数不足 K（\(K\geq 2\)），所以相对于有 K 次访问历史的页面更容易被淘汰，但是该页面之后可能会有相关访问（原文是称作 Correlated References，并介绍了事务内、事务重试、进程内、进程间的相关访问）；② Page Reference Retained Information Problem，当页面被淘汰时，它的访问历史需要保留一段时间，如果超时再进行删除操作。

实现

更新：以下内容存在一些错误，将会在下一节纠正。

① 初次提交，所有函数开头一把大锁。提交相同的代码，排名波动挺大的，可能是因为没优化的代码跑分都差不多，QPS 大概四五千左右。

② 并行 IO 优化，尝试在进行 IO 操作时将大锁切换为单独的页锁（针对 frame_id，即缓冲池页面的锁），简单来说就是在 IO 之前拿到页锁，然后释放大锁。一定需要注意加锁和解锁的顺序，如果有部分代码先加大锁再加页锁，另一部分代码先加页锁再加大锁，那么就会产生死锁。优化半天，遇到不少 BUG，但是没遇到死锁，QPS 提升至五万多。（注意，我们优化的是磁盘页面读写，而不是缓存页面读写，不要混淆，说的就是我）

③ 死锁警告，调试最久的一次，线上提交五十多次（当时不知道本地有 bpm-bench 测试），结果发现是我理解有问题。尝试使用读写锁在 BufferPoolManager 内部锁定页面，但是读写锁是依赖于访问类型的，因为有 Unknown 类型的存在，实际上根本无法执行该优化，并且该优化并不会提高 IO 的并行量。PS：仔细想想后发现甚至根本就不可能这样做，因为 FetchPage 时需要修改共享变量肯定不能用读写锁。并且根本就不可能有什么性能提升，因为优化的部分不涉及 IO 等耗时操作，所以瞎折腾半天后放弃。

④ 参考CMU 15-445 2023 P1 优化攻略，似乎用的是写时复制的思想，刷盘的时候复制一份数据在新线程刷，这样就可以让当前线程做 ResetMemory 操作而不会产生冲突，具体的优化思路见文章。单纯的写时复制优化我觉得还行，刷盘之后就会释放复制页面占用的内存空间，读取的时候也可以重复利用。但是如果像文中那样固定为每个页面都保存缓存，那就相当于变相增加了缓冲池的容量，那还不如用下面的方法简单粗暴，并且时间和空间都应该是更优的。

⑤ 有个无耻的优化方式，把所有页面全部存到内存缓存中，读盘的时候读缓存，刷盘的时候刷缓存，最后析构的时候再进行实际的物理刷盘。具体实现的时候，不能在析构的时候刷盘，因为线上测试会在析构 BufferPoolManager 之前析构 DiskManager，但是这样也是可以通过线上测试的，QPS 两百多万（其实大部分测试结果只有一百多万）。然而，这已经不能算优化了，磁盘数据库不可能这么操作的，因为内存不太可能存下所有页面。

⑥ 本来想优化 LRU-K 的，但是想不到怎么根据访问类型来优化，怎么利用 zipfian 分布，暂时搁置。突然想到优化方法了，因为 Scan 线程是进行全表扫描，所以只被 Scan 线程访问过的页面就可以直接淘汰掉。我们可以在 LRUKNode 中维护一个布尔值，表示当前页面是否只被 Scan 线程访问，如果是就可以在 Evict 中直接淘汰，并且优先淘汰此类页面。回归正轨，基于 ② 优化提升大概三万 QPS，排名 12。（这优化完全是针对基准测试做的，没有什么适用性）

重做

实现纠错

在做 B+Tree 时发现上面第 ② 个实现有个 Bug，如果我新建一个缓存页面，然后它被淘汰刷盘，在刷盘之前，我会拿到该缓存页面的锁，然后释放缓冲池的独占锁，这会存在问题。为了避免死锁，加锁解锁的顺序是固定的，所以我释放缓冲池的独占锁后，不会再去尝试对它加锁。那么我就需要释放独占锁之前，修改完所有和缓冲池有关的共享变量（例如 page_table_），但是，如果在刷盘过程中，有另一个线程读取该页面，它在 page_table_ 中找不到该页面，所以它会去读取磁盘，这时页面还没有写入磁盘中，就会出现 “page not exist” 错误，错误在 disk_manager_memory.h 中被检测：

1
2
3
4

if (page_id >= static_cast<int>(data_.size()) || page_id < 0) {
    LOG_WARN("page not exist");
    return;
}

所以第 ② 种优化方式是不完善的。可以额外搞个哈希表存正在进行刷盘的 page_id 和 frame_id，然后加个锁，在刷盘的时候加到该表里，刷完的时候删除（注意在添加到表时持有 page_table_ 的锁，以确保在其他线程 FetchPage 时，表中已有该 page_id）。这时如果有其他线程 Fetch 该 page_id，不会直接从磁盘读，而是读这个表拿到之前的 frame_id，然后拷贝到当前缓存页。（之所以另开哈希表，而不是保留在原来的表里，是因为如果这样会导致混乱，当有其他线程 FetchPage 该 page_id 时，会发生已淘汰又被 pin 的情况，还会发生其他很复杂的情况）

如何优化

既然 B+Tree 把我打回来修复 Bug，那么我就想，有没有更好的优化方案。自己独自优化总觉得找不到方向，并且可能设计就是错的，而且优化方式很幼稚。在网上搜也搜不到具体的优化方案，我就想尝试看一看开源数据库都是怎么做的，最后在 PostgreSQL 项目中发现一份超级详细的 README（MySQL 为什么没有），省去我看源码的时间，以下是对它的简单概述（使用我们项目中的变量来解释）：

① 缓存页面的访问规则

• 读写页面时必须 pin 页面，并拿到相应的读写锁。（文中要求必须在上锁之前 pin）
• 在读页面时，可以释放页面的读锁，因为已经拿到页面的 pin。
• 在写页面时，必须拿到 pin 和写锁，并且需要检查 pincount_ == 1，如果不相等，则释放写锁并返回或者使用条件变量等待唤醒。（因为在读页面时会提前释放读锁，但没有 unpin，所以拿到写锁时，还需要等待）当进行写操作时，有可能页面会被 pin，但是没有关系，因为当前线程拿到写锁，其他线程 pin 之后还需要拿锁才能读写页面。

我们的项目和上面的描述不一样，但是无伤大雅，基本上 PageGuard 和 FetchPage 等函数已经提供了这些功能。

② 缓冲池管理器的内部锁定

• 访问 page_table_ 前需要拿到 page_table 的读写锁（文中称作 BufMappingLock）。如果是读页面，则在释放锁之前，需要拿到缓存页面的 pin。在修改 page_table_，或者修改缓存页面头部字段（应该是指 Page 的除 data_ 以外的成员变量，在本项目中就是 page_id_、pin_count_ 和 is_dirty_），或者从磁盘读物理页面到缓存页面时，需要拿到 page_table_ 的写锁。
• 可以将 BufMappingLock 拆分为 NUM_BUFFER_PARTITIONS 个锁，每个锁负责映射的一部分。每个 page_id_ 属于哪个分区，由 page_id_ 的哈希值的低比特位决定（其实就是有多个 page_table_，每个 page_id 会根据哈希函数来确定存放在哪个 page_table_ 中）。如果要同时锁定多个分区，则需要按照分区编号顺序锁定，以避免死锁。
• 为空闲列表和页面替换提供独占的自旋锁 buffer_strategy_lock ，当拿到该锁时，不应该去获取任何其他锁。
• 每个缓存页面都有一个自旋锁，在读写缓存页面头部字段时使用（疑问，如果有这个锁，在修改头部字段时似乎就不需要持有 BufMappingLock 锁）。
• BM_IO_IN_PROGRESS 标志是一种锁，用来等待缓存页面的 IO。在从磁盘读物理页面到缓存页面，或者将缓存页面刷到磁盘的过程中，会将该标志置位，操作完成后清除标志位。等待标志位被清除的线程会使用条件变量休眠（疑问，如果有这个标志，那么在从磁盘读物理页面到缓存页面时，就不需要持有 BufMappingLock 锁吧）。

缓冲池管理器的优化就靠这部分内容，但是有些描述还是不太清晰（是不是我理解错误，并且文中涉及日志相关的内容，不是很好懂），实现的时候再想吧。然后文中还提出了如何对线性扫描做优化，但是我认为单纯在缓冲池管理器里面做不了这个优化，因为没办法识别当前操作是否是线性扫描，而且优化需要另开一个小缓冲池，这应该是查询优化器的任务。

③ 后台线程刷盘

• 按照淘汰顺序扫描页面，选择 is_dirty_ == true && pin_count_ == 0 的页面，然后 pin 该页面并刷盘，最后回收到空闲列表。
• 还有一些优化方式，没看懂就不翻译了。

总结一下，该文件中提到的优化，有一些可能跟它的页面替换算法相关（PostgreSQL 使用的是时钟扫描算法），或者和该数据库的其它特性相关（提示位之类的），看得云里雾里的，我们能够做的优化大概就是上面提到的这些，具体怎么实现还是走一步看一步吧。

尝试实现

重构代码，轻松通过本地测试，哭死。惊了，线上就一个测试没过。

① FetchPage 在判断 page_id 是否在 page_table_ 时，需要使用 page_table_ 的独占锁。并且如果页面不在 page_table_ 中，则在函数返回 nullptr 或修改 page_table_ 之前不能释放该锁，以防止多次 FetchPage 同一个 page_id 时，多次从 free_list_ 中获取页面或者多次淘汰页面。

② 因为在 FetchPage 将淘汰页面刷盘时，我会释放所有锁，这时页面是可以被 pin 的，所以之后设置 pin_count_ 时，不能直接设置为 1，而是进行 ++ 操作。

第一次重构没有拆分 BufMappingLock，没有使用自旋锁，其他的锁基本都加了。QPS 和之前的第 ② 个优化差不多，其实也可以想到，毕竟只是加了一些锁保证正确性，基本上没有提高并行性。本来想使用自旋锁的，但是因为需要条件等待，而条件变量只能用 unique_lock 作为参数，并且 atomic_flag 的原子等待只有在 C++ 20 才有，不好实现，遂放弃挣扎（而且估计不会有什么提升）。不搞了，像个小丑，没意思。

调试

① 优化的时候一步一步优化，然后进行测试，要不然调试半天，都不知道 BUG 在代码的哪个位置。

② 优化时容易出问题的点就是 NewPage 和 FetchPage，以及 UnpinPage。像是 FlushPage、FlushAllPage 以及 DeletePage 都可以暂时不管（可以直接 return），这样比较方便调试。

补充

① 在 C++ 20 之前，结构化绑定不能被 lambda 表达式捕获。

② 遇到 Reference to non-static member function must be called 问题，解决方案在此。

③ MySQL Buffer Pool 的实现 15.5.1 Buffer Pool。

④ Linus Torvalds 发表的一篇评论：do not use spinlocks in user space, unless you actually know what you’re doing。

⑤ 条件变量如果使用不当，可能会导致唤醒丢失，必须利用锁保证不会在等待前执行唤醒操作。

⑥ 发现一个感觉不错的博客：MC++。

测试结果

测试通过！本地的测试数据比较弱，而且没有并发测试。如果线上测试遇到问题，可以通过添加打印语句，线上看输出来调试。基本上没遇到什么大问题，都是细节问题，很容易漏判断一些条件。另外，加锁优化是可选的，暴力加锁就可以通过测试。

优化任务让我的提交记录暴涨，特别是在尝试第 ③ 个优化方案时。一般等 4 分钟才能出结果，有时候评测机还会出问题，算下来等结果的时间都有 8 小时，离谱。

每次本地测试都需要输入很多命令，提交线上又要格式化，如果手动输入太麻烦了，可以写个 shell 脚本来执行：

1
2
3
4
5
6
7
8
9

#!/bin/bash
make lru_k_replacer_test buffer_pool_manager_test page_guard_test -j$(nproc)
./test/lru_k_replacer_test
./test/buffer_pool_manager_test
./test/page_guard_test
make format
make check-lint
make check-clang-tidy-p1
make submit-p1

项目小结

① 在做项目的时候，总是会想某个地方是不是有更优的写法，但是当时对整个项目结构不太清楚，以及代码实现是否正确也不清楚，所以基本上都是浪费时间。据此，我的收获就是先让代码跑起来，其他的之后再说。

② 虽然做的时候很艰辛，但是做完之后发现，好像也没有什么工作量，bpm 优化也就是简单减少锁的粒度，lru 的优化也完全是针对基准测试做的，感觉我的优化方式很烂，有没有更牛逼的优化方式啊。

③ 我好菜啊！！！前三个任务花了两天，优化花了好几天。

更新：发现 Lecture #06 就是讲 BufferPool 优化的（课堂笔记），不知道能不能在这用上，等做完所有 Project 再来试试。