项目准备

项目地址：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 再来试试。

作业准备

项目地址：Homework #1 - SQL。

准备工作：阅读 Chapters 1-2 27 3-5，学习 Lecture #01 #02，以及阅读课堂笔记。

Q1 [0 points] (q1_sample):

Ctrl + C，Ctrl +V。

Q2 [5 points] (q2_not_the_same_title):

查询只涉及 titles 表，比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

SELECT
	premiered,
	primary_title || ' (' || original_title || ')'
FROM
	titles
WHERE
	primary_title != original_title
	AND type = 'movie'
	AND genres LIKE '%Action%'
ORDER BY
	premiered DESC,
	primary_title
LIMIT
	10;

Q3 [5 points] (q3_longest_running_tv):

题目描述很不清晰啊，类型都不知道具体是什么。

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT
	primary_title,
	IIF(ended IS NULL, 2023, ended) - premiered AS runtime
FROM
	titles
WHERE
	primary_title IS NOT NULL
	AND type = 'tvSeries'
ORDER BY
	runtime DESC,
	primary_title
LIMIT
	20;

Q4 [10 points] (q4_directors_in_each_decade):

唯一要注意的就是使用 DISTINCT。

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT
	CAST(born / 10 * 10 AS TEXT) || 's' AS decade,
	COUNT(DISTINCT(people.person_id)) AS num_directors
FROM
	people
	INNER JOIN crew USING(person_id)
WHERE
	category = 'director'
	AND born >= 1900
GROUP BY
	decade
ORDER BY
	decade;

Q5 [10 points] (q5_german_type_ratings):

德语的缩写是 de。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

SELECT
	t.type,
	ROUND(AVG(r.rating), 2) AS avg_rating,
	MIN(r.rating),
	MAX(r.rating)
FROM
	akas as a
	INNER JOIN ratings as r USING(title_id)
	INNER JOIN titles as t USING(title_id)
WHERE
	a.language = 'de'
	AND a.types IN ('imdbDisplay', 'original')
GROUP BY
	t.type
ORDER BY
	avg_rating;

Q6 [10 points] (q6_who_played_a_batman):

坑点就是模糊查询时 Batman 两边要加上双引号，即 "Batman"。以及在连接 people 和 crew 表时，顺序很重要，如果使用 crew INNRE JOIN people USING(person_id) 会很慢（查询大概有 5 秒），具体不知道为什么，以下是它们的执行计划。

1
2
3
4
5
6
7
8
9
10
11
12
13

crew INNER JOIN people USING(person_id)

QUERY PLAN
|--SCAN crew USING INDEX ix_crew_person_id
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT

people INNER JOIN crew USING(person_id)

QUERY PLAN
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT

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

WITH t AS (
	SELECT
		DISTINCT(person_id),
		name
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		category = 'actor'
		AND characters LIKE '%"Batman"%'
)

SELECT
	name,
	ROUND(AVG(rating), 2) AS avg_rating
FROM
	t
	INNER JOIN crew USING(person_id)
	INNER JOIN ratings USING(title_id)
GROUP BY
	person_id
ORDER BY
	avg_rating DESC
LIMIT
	10;

Q7 [15 points] (q7_born_with_prestige):

SQL 很容易写，但是性能和官解差两秒，等以后学习怎么优化再来看吧。

1
2
3
4
5
6
7
8
9

SELECT
	COUNT(DISTINCT(person_id))
FROM
	titles
	INNER JOIN people ON titles.premiered = people.born
	INNER JOIN crew USING(person_id)
WHERE
	primary_title = 'The Prestige'
	AND category IN ('actor', 'actress');

1
2
3
4
5

QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--SEARCH titles USING INDEX ix_titles_primary_title (primary_title=?)

Q8 [15 points] (q8_directing_rose.sql):

比官解快一秒。注意使用 Rose% 而不是 Rose %。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

SELECT
	DISTINCT(name)
FROM
	crew
	INNER JOIN people USING(person_id)
WHERE
	category = 'director'
	AND title_id IN (
		SELECT
			title_id
		FROM
			crew
			INNER JOIN people USING(person_id)
		WHERE
			category = 'actress'
			AND name LIKE 'Rose%'
	)
ORDER BY
	name;

Q9 [15 points] (q9_ode_to_the_dead):

这就是窗口函数么，学习了。

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
31
32
33
34
35
36
37
38
39

WITH t AS (
	SELECT
		category,
		name,
		died,
		primary_title,
		runtime_minutes,
		DENSE_RANK() OVER(
			PARTITION BY category
			ORDER BY died, name
		) AS rank_died_name,
		DENSE_RANK() OVER(
			PARTITION BY category, person_id
			ORDER BY runtime_minutes DESC, title_id
		) AS rank_runtime_title
	FROM
		crew
		INNER JOIN people USING(person_id)
		INNER JOIN titles USING(title_id)
	WHERE
		died IS NOT NULL
		AND runtime_minutes IS NOT NULL
)

SELECT
	category,
	name,
	died,
	primary_title,
	runtime_minutes,
	rank_died_name
FROM
	t
WHERE
	rank_died_name <= 5
	AND rank_runtime_title = 1
ORDER BY
	category,
	rank_died_name;

Q10 [15 points] (q10_all_played_by_leo):

不会。。json_each 函数有点神奇，也看了下递归 CTE 的实现，只能说真想不出来。

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

WITH t1(characters) AS (
	SELECT
		characters
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		name = 'Leonardo DiCaprio'
		AND born = 1974
),
t2(value) AS (
	SELECT
		DISTINCT(value)
	FROM
		t1,
		json_each(t1.characters)
	WHERE
		value != ''
		AND value NOT LIKE '%SELF%'
	ORDER BY
		value
)

SELECT
	GROUP_CONCAT(value)
FROM
	t2;

作业小结

最难的是最后两题，前面几题还可以接受。因为比较在意连接顺序对查询性能的影响，所以多花了点时间。（虽然还没弄明白就是了）