CMU 15-445 Bustub Project 1 - Buffer Pool Manager - Note

前言

因为可能有机会去做与云数据库相关的工作，所以捡起这门之前一直想学但是没学的课做一下。

感觉难度确实很超标。

我基本是 AI 的“半推半就”下完成的，纯手写确实有点超出我的难度阈值了...（和 xv6 一样）。为自己的手写能力哀悼。

配环境

我的开发机是 Arch Linux，系统工具链是 clang 22 和 libstdc++ 16，而 Fall 2025 的 BusTub 使用 clang 15，但是 AUR 也不提供了，除非自己编译一个，但是这要太久了。

最后使用 Ubuntu 22.04 Docker 镜像统一编译环境。镜像安装 clang、clang-format、clang-tidy 15、CMake 和 BusTub 的构建依赖，仓库挂载进容器，构建产物放在独立的 build/ubuntu 目录。

仓库中的 build_support/run_in_ubuntu.sh 会在首次运行时自动构建镜像。先配置项目：

./build_support/run_in_ubuntu.sh cmake -S . -B build/ubuntu \
  -DCMAKE_BUILD_TYPE=Debug \
  -DCMAKE_C_COMPILER=/usr/bin/clang-15 \
  -DCMAKE_CXX_COMPILER=/usr/bin/clang++-15 \
  -DCLANG_FORMAT_BIN=/usr/bin/clang-format-15 \
  -DCLANG_TIDY_BIN=/usr/bin/clang-tidy-15

Debug 构建默认启用 AddressSanitizer。P1 的公开测试可以直接在容器内编译和运行：

for test in arc_replacer_test disk_scheduler_test page_guard_test buffer_pool_manager_test; do
  ./build_support/run_in_ubuntu.sh cmake --build build/ubuntu --target "$test" -j 4
  ./build_support/run_in_ubuntu.sh "./build/ubuntu/test/$test"
done

提交前再检查格式和 clang-tidy：

./build_support/run_in_ubuntu.sh cmake --build build/ubuntu --target check-format
./build_support/run_in_ubuntu.sh cmake --build build/ubuntu --target check-clang-tidy-p1

Project 的前置知识

其实也不多，只需要明晰「page」和「frame」之间的关系即可：

• page 是磁盘中的实际存在的页，虽然在 OS 里面被称作 Block
• frame 是内存里面对于磁盘的 page 的缓存，虽然这个在 OS 里面被叫 page

Task 1

Task 1 主要是要理清楚这个驱逐算法的根本。为了理清楚 ARC 的内涵：MRU、MFU 和两个 Ghost 列表之间的转换，这里画个状态机：

stateDiagram-v2
    state "未记录" as None
    state "MRU" as MRU
    state "MFU" as MFU
    state "MRU Ghost" as MRUG
    state "MFU Ghost" as MFUG

    [*] --> None
    None --> MRU: 首次访问
    MRU --> MFU: 再次访问
    MFU --> MFU: 再次访问
    MRU --> MRUG: Evict
    MFU --> MFUG: Evict
    MRUG --> MFU: 再次访问，增大 MRU 目标
    MFUG --> MFU: 再次访问，减小 MRU 目标
    MRUG --> None: 历史记录被裁剪
    MFUG --> None: 历史记录被裁剪
    MRU --> None: Remove
    MFU --> None: Remove

图里画的是一个页目前在哪个列表里。MRU、MFU 记录还在内存中的页，Ghost 只留下被驱逐的页号，与 frame 无关。某个页此刻能不能被驱逐，由 evictable_ 控制。

理清楚之后其实就是翻译代码了。

不过，理解为什么要这样做，比单纯把自然语言翻译成代码要更有益。如果真的理解了 ARC，那么 MRU、MFU 和 Ghost 之间的转换都很自然：

• 命中 MRU Ghost，就说明刚被驱逐的页又被访问了，MRU 的目标大小往上调；
• 命中 MFU Ghost 则往下调。
• 驱逐时：如果 |mru_| >= mru_target_size_： 优先从 mru_ 淘汰 否则： 优先从 mfu_ 淘汰。BusTub 注释里有两个特殊点：
  1. mru_.size() == mru_target_size_ 时，也从 mru_ 淘汰。
  2. 如果优先侧全是 pinned / non-evictable，就尝试另一侧。 综上，简单来说就是根据 mru_.size() 和 mru_targetsize 决定优先淘汰侧，如果找不到就找对方，都没有就返回

我一开始的实现都是使用 std::find() 去链表里找，时间复杂度很差。后面在 FrameStatus 里面加了对应的迭代器：

• 节点放进列表时，将其列表中的迭代器存入，以后通过 map 直接找到。
• map 的查找平均是 $O(1)$，而且移动后原来的迭代器仍然有效。

不过，这只是省去了查找节点的那遍扫描；Evict() 找可驱逐节点时仍可能遍历列表。还有可优化的空间，但是我没做。

和 LLM 的问答记录里面总结的错过的点

• alive_map_ 用 frame_id 查当前在内存中的记录，ghost_map_ 用 page_id 查历史记录，所以 Ghost 命中后不能直接把存着 page_id 的节点搬进存 frame_id 的 MRU/MFU。
• splice() 的目标位置也必须是目标列表的迭代器。
• 优先扫描的列表里没有可驱逐节点，不代表另一个列表也没有。

Task 2

Task 2 的话，其实理解了这些 API 之后就不难。换句话说，我觉得理解难度主要落在对框架代码和 C++ 不熟悉上面。

Disk Scheduler 有一个工作线程负责处理排队的请求。Schedule() 把 DiskRequest 放进 Channel，StartWorkerThread() 在后台取出请求，再调用 DiskManager 的 ReadPage() / WritePage()。对于 Go 程序员来说，Channel 其实很熟悉。这里工作线程退出靠的是往队列里放一个 std::nullopt，析构函数 join()，然后读到了 std::nullopt 就结束。

还有需要注意的是 std::promise<bool> 和 std::future<bool>。它们用来在线程之间传一次处理结果：

• 发起请求的线程调用 future.get()，结果还没准备好时就阻塞；
• 工作线程做完 I/O，再通过 request 里的 promise.set_value(true) 通知它，有点像用 Go 的 Channel 等一个结果。
• 不过我觉得和 JavaScript 的 Promise 毫无关系就是了，虽然名字一样。

Task 3

Task 3 的话就变得复杂起来了。主要还是代码之间的依赖太过于复杂，单纯读也理不清，让 AI 把调用链画出来也记不住，还不如先上手写，这样就自然了。

核心就是 PageGuard 和 BufferPoolManager。PageGuard 是访问一个页的唯一合法途径，里面封装了对页的操作。本来是分成 Read 和 Write 的，不过我拆成了继承的模式，把共同的成员和函数挪进抽象基类 PageGuard 里。

还有一个重点就是需要加成员变量，因为注释里面有说到 PageGuard 需要时刻持锁：

However, the existence of any ReadPageGuard on a page implies that no thread can be mutating the page's data.

所以，读 Guard 持有页面的共享锁，写 Guard 持有独占锁：

// ReadPageGuard
std::shared_lock<std::shared_mutex> read_lock_{frame_->rwlatch_};
// WritePageGuard
std::unique_lock<std::shared_mutex> read_lock_{frame_->rwlatch_};

需要注意的是 PageGuard 持有页面锁是从构造到 Drop() 的整段时间，因此不需要任何的临时上锁。

然后对于 BufferPoolManager，最复杂的还是 CheckedReadPage() 和 CheckedWritePage()。注释里说了三种情况，考虑是：

1. page_table_ 里已经有这个页：找到对应的 frame，不用读盘。
2. 页不在内存，但是 free_frames_ 里有空闲的 frame：拿来装这个页，需要读盘。
3. 没有空闲的 frame：让 ARC 找一个可以驱逐的 frame，旧页如果是脏的就先写回磁盘，再读入要访问的页；如果谁都不能驱逐，就返回 std::nullopt。

里面并发锁的控制也很麻烦。最值得注意的，是 pin 的增减要和池锁配合：在 pin 从 0 变成 1、或者从 1 变成 0 时，还要同步修改 ARC 对这个 frame 的可驱逐状态。

不过我还是觉得 Flush 系列的函数最复杂，主要还是因为并发代码太难写了。什么时候上锁、什么时候不上，池锁和帧锁之间的关系，确实很复杂。

这里最值得注意的是：PageGuard::Flush() 可以依赖 Guard 已经持有的帧锁；BPM 的 FlushPage() 没有 Guard，所以要先在池锁下找到 frame、临时 pin++ 并设置不可驱逐，放开池锁后再取得帧锁写盘，最后把 pin-- 并按需设置可驱逐。

FlushPageUnsafe() 不允许持帧锁，但允许用池锁，来维护 page_table_ 访问的线程安全性。