CMU 15-445 Project #1

Project #1 Buffer Pool Manager

本文记录一下我完成 CMU-15-445 Project #1 的历程，讲讲 what & why，包含了我的思考历程，但不会包含任何具体的实现方法。

本文出现的所有单词中，heap file 代表数据库文件，储存数个无序的数据库页； page 代表数据库页；frame 代表内存中的数据库页； bpm 代表 buffer pool manager；

下面进入正文 ——

buffer pool manager，即数据库缓冲池，它提供两个功能：

数据库磁盘 I/O 交互，缓存失效时才进行磁盘读写
CRUD 数据库页，即 CRUD frame

bpm 包含 3 个组件：

replacer 页面置换器
disk scheduler 磁盘请求队列
buffer pool manager 缓冲池管理器

本课程的目标就是实现这 3 个组件，完成一个 thread-safe buffer pool manager。

Task #1 LRU-K Replacement Policy

实现一个基于 LRU-K 算法的 replacer。

与 LRU 类似，LRU-K 也是用于淘汰掉最不常用的元素（cold data）。

LRU-K 计算时会遍历所有元素，查找其访问的历史记录，不足 k 次则可以直接淘汰。否则找出所有元素的 前 k 次访问 与 当前时间步 的差值最大值。

注意，这里使用的概念是 时间步 (timestep) 而非讲义里面所说的 时间戳 (timestamp) 。

讲义的原句是 Backward k-distance is computed as the difference in time between the current timestamp and the timestamp of kth previous access.。我一开始就误以为 timestamp 是现实世界的时间戳，我想，毫秒级的精度肯定不够吧，于是调查了一番 c++ 时间戳。感到不对劲但是又没有其他提示后，便去翻了之前课程的实现，才发现是一个计数…踩了个坑。

具体来说，时间步是一个计数概念，从 0 开始，每个访问元素便 +1 即可。

此外，bpm 还有 evictable（可淘汰）的概念，当 frame 设置为 evictable 时，replacer 才能淘汰它。

Task #2 Disk Scheduler

一个磁盘请求调度器。挺简单，10 分钟可以搞定。

DiskScheduler 调用 DiskManager 管理物理磁盘。

DiskManager 中，page id 从 0 开始，长度为 4096，比如 0-4096 比特范围为 page 0 的内容。为了减少系统调用，文件会初始化 16 个 page 大小的空间，在需要扩充的时候 x2 。 IncreaseDiskSpace 虽然命名上看是增加，但实际上是传入总的 page 数量，然后它内部再判断是否需要扩容。以及 DiskManager 内部储存了 page 数量，但是实际上没有作用。还有 DeletePage 方法也没有实现（虽然也没这个必要），DiskManagerMemory 用了但是用途不一样。这两点稍微有点设计问题和误导性。

底层的 disk manager 磁盘操作已经预先写好了，需要实现的 disk scheduler 就是管理一个 worker 线程，将读写 page 的请求放入队列，返回 promise。

这里就不得不提一下 c++ 的 promise / future 协程模型了。

promise: set_value / set_exception / get_future 用于存放任务的值
future: get / wait / wait_for 用于等待任务和获取结果

但是呢，python 的协程模型中，future 用于存放任务的值，task 才是用于管理任务的。 javascript 和 c# 也类似。

包括上面的，c++ 这些奇怪的协程接口设计 😅，比如 promise.get_future() 、std::move(promise) 等操作让我写起来感觉非常难受。

Task #3 Buffer Pool Manager

完成了 LRU-K 替换策略和磁盘调度器后，就可以着手开始解决最复杂的部分 —— Buffer Pool Manager 的实现。

首先，我觉得最重要的是搞懂这一套流程是怎么工作的、为什么要这么设计。

这些细节内容是讲义里面没有的，基本上都需要靠自己摸索、碰壁，最终才能理解并实现。之前做 CS144 也是类似的感觉，细节的东西都需要靠自己做。相比之下，CMU 15-445 提供了基本数据类型定义，至少你知道这个字段是有用的，我没有用到的话那可能是我实现错了。

在做开源软件的时候，我们经常能看到 Tech Specification，一份好的设计文档可以受益整个群体，并且能够跟踪项目的细节变更，比如 Python PEPs 或者 RLPx。

但是在现实工作中，我们很难见到这样的案例，原因是编写和维护起来非常困难。你说业务发展快，那么就算假设有慢速的业务，会有人去为公司（无论什么行业）写 Spec 吗？我想答案是没有，包括我自己。原因是没有意义，不能给你带来绩效，甚至没有认可。你走了之后的人受益了，那又与你何关。

我曾经为此深恶痛绝，如果你做 infrastructure 相关的工作（想想看你做的工具要被公司很多小组用到），那就更为如此。这都是公司管理层的偏好问题，你没法控制。

但至少我们自己要做有意义的事情，将来某天要组建自己的团队时，我们可以用到这些经验。

Page Guard 核心理念

思考一下面向接口编程，用户接口首先是越简洁越好，符合单一职责，不希望让用户使用锁，更不希望用户知道 buffer pool manager 里面的 frame 机制。

为了实现这个，当用户申请读写某个页面时，buffer pool manager 返回一个 page guard 对象，这个对象可以理解为 python 里面的上下文管理器、c# 里面的 IDisposable。 page guard 的具体实现使用了 C++ 的 RAII 机制，利用对象生存周期来管理资源，这是 C++ 中普遍的最佳实践。利用 RAII，page guard 创建时可以自动上锁，析构时可以自动释放锁，防止对 frame 的读写产生数据竞争或者脏读。

这个 frame 锁存在哪里其实不重要，但是在这个项目里面 frame 算是单例对象，所以锁就存在 frame 上即可，写入时独占锁，读取时共享锁。

frame 的读写锁，具体来说，创建一个 write page guard 时，在堆栈变量的上下文内持有一个独占锁，防止其他线程读取或写入；创建一个 read page guard 时，在堆栈变量的上下文内持有一个共享锁，允许多个线程读取，但不允许拥有独占锁。这个 rwlock 在 c++ 里面就是 std::shared_mutex，具体用的什么公平策略在这里也不重要。

再次总结和理解一下 PageGuard 的 RAII 机制和锁：

WritePageGuard 持有时，则无法拥有任何其他 WritePageGuard 和 ReadPageGuard 对象。跨线程锁住此对象，析构时释放锁
没有 WritePageGuard 持有时，可以拥有多份 ReadPageGuard。有 ReadPageGuard 存在时，则无法创建 WritePageGuard
管理 frame pin count，构造时 +1，析构时 -1，为 0 时设置 frame evictable

特别要注意的是，C++ 的 RAII 还包含了移动语义，和复制语义类似。移动语义首先会为类实例分配一个未定义的内存空间，然后通过右值引用传入的参数和 std::move 来构造该对象，所以需要注意不要引发 UB 和 double free (double move)。善用项目里面给的 is_valid 来处理 RAII 语义。

原文对 pin count 的解释是 The pin count of a frame is the number of threads that have access to the page's data.，这个解释应该是有点毛病的，正确来说是 guard 持有数，因为同一个线程是允许持有两份相同 ReadPageGuard 的。

我写了个测试，你可以试试：

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


TEST(BufferPoolManagerTest, MyCustomTest) {
  auto disk_manager = std::make_shared<DiskManager>(db_fname);
  auto bpm = std::make_shared<BufferPoolManager>(FRAMES, disk_manager.get(), K_DIST);

  auto pid0 = bpm->NewPage();
  {
    auto guard0 = bpm->WritePage(pid0);
    char str[] = "Hello world!";
    char *data = guard0.GetDataMut();
    snprintf(data, sizeof(str), "%s", str);
    auto pin = bpm->GetPinCount(pid0);
    ASSERT_EQ(1, pin);
  }

  {
    auto guard1 = bpm->ReadPage(pid0);
    auto guard2 = bpm->ReadPage(pid0);
    auto pin = bpm->GetPinCount(pid0);
    // This explains that pin count is not just
    // `The pin count of a frame is the number of threads that have access to the page's data.`
    // said in project #1 instruction.
    ASSERT_EQ(2, pin);
  }
}

Buffer Pool Manager 实现

我的实现顺序：

先完成不带锁的 replacer，因为没有测试担心后面出错
完成 disk scheduler
理解 bpm 的 page guard，完成不带锁版本并通过测试
完善代码并通过 bpm 的 basic test，到这里就完成了大部分了，后面都是锁和 debug
添加 page guard 和 replacer 锁，可以完成本地的所有测试
添加 bpm 锁，完成 gradescope 所有测试

死锁

对于死锁，讲义里面给了提示 holding the buffer pool latch from beginning to end should be enough (except for when you need to release it early to prevent deadlocks)

但是我依旧思考了很久，最终在阅读了 DeadlockTest 这个测试用例后，才恍然大悟。

死锁的情况是这样的：当主线程持有了 page0 的互斥锁后，子线程尝试获取 page0 的互斥锁时会等待。如果子线程里 bpm 的锁未释放，主线程再调用一次 bpm 的带锁函数，就会卡死。

理解了问题所在之后，就很好解决了，这里就不具体讲了。

其他并发问题

在为已缓存的 frame 建立 page guard 之前，注意首先将 frame 设为 non-evictable，否则 page guard 等待锁的时候，其他线程可能会 evict frame
atomic 如果自增并且需要获取旧值，一定记得用 fetch_add(1) 或者 i++

gradescope 的测试用例并非完美，如果代码中有细微的差错，就会出现一些偶发性问题，比如：

BufferPoolManagerTest.ConcurrentWriterTest (0/5)

 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
40
41
42
43
44
45
46
47
48
49
50


> GTEST_COLOR=yes ctest . -R ^BufferPoolManagerTest.ConcurrentWriterTest$ --no-tests=error --verbose
UpdateCTestConfiguration  from :/autograder/source/bustub/build/DartConfiguration.tcl
UpdateCTestConfiguration  from :/autograder/source/bustub/build/DartConfiguration.tcl
Test project /autograder/source/bustub/build
Constructing a list of tests
Done constructing a list of tests
Updating test list for fixtures
Added 0 tests to meet fixture requirements
Checking test dependency graph...
Checking test dependency graph end
test 18
    Start 18: BufferPoolManagerTest.ConcurrentWriterTest

18: Test command: /autograder/source/bustub/build/test/grading_buffer_pool_manager_test "--gtest_filter=BufferPoolManagerTest.ConcurrentWriterTest" "--gtest_also_run_disabled_tests" "--gtest_output=xml:/autograder/source/bustub/build/test/grading_buffer_pool_manager_test.xml" "--gtest_catch_exceptions=0"
18: Test timeout computed to be: 120
18: Running main() from gmock_main.cc
18: Note: Google Test filter = BufferPoolManagerTest.ConcurrentWriterTest
18: [==========] Running 1 test from 1 test suite.
18: [----------] Global test environment set-up.
18: [----------] 1 test from BufferPoolManagerTest
18: [ RUN      ] BufferPoolManagerTest.ConcurrentWriterTest
18: /autograder/source/bustub/test/buffer/grading_buffer_pool_manager_test.cpp:991: Failure
18: Expected equality of these values:
18:   0
18:   bpm->GetPinCount(page_ids[i])
18:     Which is: (1)
18:
18: [  FAILED  ] BufferPoolManagerTest.ConcurrentWriterTest (1184 ms)
18: [----------] 1 test from BufferPoolManagerTest (1184 ms total)
18:
18: [----------] Global test environment tear-down
18: [==========] 1 test from 1 test suite ran. (1184 ms total)
18: [  PASSED  ] 0 tests.
18: [  FAILED  ] 1 test, listed below:
18: [  FAILED  ] BufferPoolManagerTest.ConcurrentWriterTest
18:
18:  1 FAILED TEST
1/1 Test #18: BufferPoolManagerTest.ConcurrentWriterTest ...***Failed    1.22 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) =   1.23 sec

The following tests FAILED:
	 18 - BufferPoolManagerTest.ConcurrentWriterTest (Failed)
Errors while running CTest
Output from these tests are in: /autograder/source/bustub/build/Testing/Temporary/LastTest.log
Use "--rerun-failed --output-on-failure" to re-run the failed cases verbosely.

Program exited with 8 in 1.238s

最后，提交的时候遇到了 clang-format 的错误。

它原本的代码在我使用 clang-format-18 格式化之后就变了，应该是版本的差异导致的。直接在上下文使用 // clang-format off 和 // clang-format on 搞定。

提交

没做优化。

可优化的地方很多，比如 disk manager 就可以实现为并发的多线程版本，这个应该还算容易实现。以后可能有空写写。

Leaderboard QPS Benchmark: 3917.82663

排名算中游，一共评分的也就 70 多个，外校的学生还是比较少，不过官方的 discord 群挺活跃的。

后记

零零散散花了一个月时间，我终于写完了！公司的工作虽然枯燥，但胜在事少，可以让我有足够的时间完成这个项目。

总体来说，Project #1 完成的还算顺利。

从最初看 bpm 时一头雾水，到迷茫但是决定先写 page guard，到通过了 page guard 测试，到逐步完成 bpm，最终掌握它的实现原理。

在无数次提交中，终于有一次提交达到满分，还是挺高兴的。

Project #2 还会更难，但是我并没有觉得任何的痛苦和退缩。

做这门课的意义是什么？我突然想到这个问题。似乎从 csdiy.wiki 上看到这门课之后，我就直接开始做了，并没有什么特殊的理由。单纯的数据库理论知识直接背八股文就行了，但是我不喜欢，做这门课至少能让我觉得有意思。

其他

将博客头像旧的 jsdelivr 资源转移到了 sm.ms 图床上，另外还发现 sm.ms 的直链变为了 s2.loli.net。

将主头像源转移到了 Gravatar 代理镜像。原本考虑使用 gravatar.loli.net 镜像，但是 size 参数无效，就放弃了。现在用的是 weavatar 速度很棒。

发现 iyume.live 域名可以注册，$24.10 似乎也还能接受。

想写个自己的 Astro 博客，现在这个主题用起来问题还是挺多的。刚发现的问题是没有按需载入、也没法关掉 photoswipe 功能。关心起性能后，才发现好多问题…😣 希望以后有空可以改进。

最近想要多写点博文，看看能不能把日本旅行和 2024 年终总结写一写。