[CMU-15445/645]p1 - Buffer Pool Manager

本次实验的要求是实现Buffer Pool Manager中的相关核心功能，总体来说相对于p0难度上升了不少：不仅涉及更复杂的系统逻辑，也是第一次较集中地使用c++特性、锁机制以及多线程并发，导致debug时间远远长于代码编写的时间。本文主要对整个实验过程进行回顾和总结，记录一下关键思路、踩过的坑以及相应的经验教训，为后续实验提供参考。

实验一介绍

本实验的目标是完成Buffer Pool Manager的具体实现。实验框架已经给出了完整的函数接口和整体结构，需要补充其内部逻辑实现。整体上，实验主要由以下三个部分组成：

  • Adaptive Replacement Cache（ARC）

  • Disk Scheduler

  • Buffer Pool Manager

下文将按照模块划分，分别总结各部分的设计思路，以及在实现过程中涉及到的C++用法和并发相关细节。

Arc Replacer

ARC Replacer主要负责记录页面的访问行为，并据此决定在页面换入与换出时应当淘汰的候选页。其核心目标是在不同访问模式下动态平衡最近访问与频繁访问页面，从而提升整体缓存命中率。

Arc Replacement Algorithm：

ARC的目标是在LRU（近期性）和LFU（频率性）之间自适应切换，避免人为设定比例，在不同访问模式下都能保持稳定性能。它的本质是通过ghost list观察“被淘汰后是否马上被访问”，动态调整MRU与MFU的比例（mru_target_size_），在LRU和LFU之间自动找到平衡点。

类型 含义 是否占用 frame
MRU 最近只访问过一次的页面 ✅
MFU 访问次数 ≥ 2 的页面 ✅
MRU ghost 最近被淘汰、原本在 MRU 的页面 ❌
MFU ghost 最近被淘汰、原本在 MFU 的页面 ❌

当访问一个页面时，通过RecordAccess函数记录页面访问，四种情况如下：

  • Case 1：page在MRU或者MFU中（真实命中）：将该页移动到MRU头部

  • Case 2：page在MRU ghost中命中：说明该页刚被淘汰又被访问，MRU不够大了，需要增大MRU target，

    若|MRU ghost|≥|MFU ghost|：+1，否则：+|MFU ghost|/|MRU ghost|，上限replacer_size_，等于上限时该算法退化为LRU

  • Case 3：page在MFU ghost中命中：说明工作集更偏向频繁访问，需要减小MRU target，

    若|MFU ghost|≥|MRU ghost|：−1，否则：−|MRU ghost|/|MFU ghost|，下限：0，等于下限时算法退化为LFU

  • Case 4：page完全不在replacer中（真miss）

    • 4-a：MRU + MRU ghost == capacity

      MRU相关历史已满，必须清理ghost，删除MRU ghost尾部，新page加入MRU头部

    • 4-b：MRU + MRU ghost < capacity

      若4表之和 == 2 x capacity：删除MFU ghost尾部，新page加入MRU头部；否则新page直接加入MRU头部

[!CAUTION]
mru_target_size_是如何影响决策过程？

mru_target_size_不直接决定谁被淘汰，它决定的是：当需要淘汰时，是优先从MRU还是MFU开刀。

它真正起作用的在Evict函数中：

1
const bool use_mfu_first = mru_.size() < mru_target_size_;

如果MRU比期望大，优先从MRU中淘汰；如果MRU比期望小，优先从MFU中淘汰

具体实现

C++ 匿名函数（Lambda）的使用

Evict()函数负责选择一个牺牲帧，并返回帧号，由于先从MRU中搜索和先从MFU中搜索代码结构相似，这里在Evict()内部定义了匿名函数。相比于单独定义成员函数，lambda函数有以下优势：

  • 作用域更小：匿名函数仅在当前函数内部可见，不会污染类接口或命名空间

  • 语义更集中：相关逻辑与其使用位置紧密相邻，阅读代码时更容易理解整体流程

  • 天然支持捕获上下文：可以直接访问当前对象的成员变量或局部状态，避免额外的参数传递

    在 C++ 中，lambda 通过 捕获列表（capture list） 指定其可访问的外部变量。常见的捕获方式包括：

    • 按值捕获 [x]：在定义 lambda 时拷贝变量的值，适合只读或不依赖外部变化的场景

    • 按引用捕获 [&x]：直接引用外部变量，允许在 lambda 内部修改其状态

    • 隐式捕获 [=] / [&]：分别表示按值或按引用捕获当前作用域内所需的所有变量

    • 捕获 this / [*this]：允许在 lambda 中访问类的成员变量，其中 this 捕获的是指针，而 *this（C++17 起）则按值拷贝当前对象

  • 减少样板代码：在不牺牲可读性的前提下显著降低重复代码量

一般来说，当某段逻辑只在当前函数中有意义、且与当前上下文强相关时，使用 lambda 往往是更合理的选择；而当逻辑本身具有独立语义或需要被多处调用时，仍应考虑将其提升为普通成员函数。

[!NOTE]
捕获列表的引入使得 lambda 不再只是语法糖形式的函数，而成为一种能够携带定义时上下文状态的轻量级函数对象。这一机制避免了通过冗长参数列表或额外成员函数来传递局部状态，使得局部逻辑的封装更加自然且安全。

std::list查找效率的优化

在 ARC Replacer 的实现过程中，MRU 和 MFU 采用了 std::list 以支持 O(1) 的插入、删除和移动操作。然而，std::list 本身并不支持高效的随机访问或查找：若仅通过遍历链表来定位某个元素，其时间复杂度为 O(n)，在高频访问场景下会带来明显的性能开销，无法通过实验的性能要求。

为了解决这一问题，引入了额外的 位置索引结构，即为每个链表维护一个从 frame_id 到对应链表节点迭代器的映射（总共4个映射）。通过这种方式，可以在 O(1) 时间内定位目标节点，并配合 std::list::splice 实现节点在不同链表之间的高效移动。

1
2
std::list<frame_id_t> mru_;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> mru_pos_;

这是一种典型的“链表 + 哈希索引”的组合设计模式，代价是额外的内存开销以及在插入、删除、移动节点时需要同步维护索引结构，但在性能敏感的场景下，这一权衡是合理且必要的。

Disk Scheduler

这一部分主要负责将读磁盘与写磁盘请求统一调度并提交给 DiskManager 执行。其核心职责在于对外提供异步接口，并将具体的 I/O 请求封装后放入任务队列中，由后台线程顺序取出并执行。在实现过程中需要正确处理线程编程相关的问题，包括后台工作线程的管理，以及基于 std::promise / std::future 的异步结果传递机制。

具体实现

std::thread的工作机制与使用总结

std::thread 是 C++ 标准库对操作系统原生线程的轻量级封装。每个 std::thread 对象对应一个实际的系统线程，线程之间共享进程地址空间中的堆、全局变量以及打开的系统资源，这是能用&对变量进行捕获的「前提条件」

std::thread 在构造时接收一个可调用对象作为线程入口，该对象可以是普通函数、成员函数指针，或更常见的 lambda 表达式。在工程实践中，lambda 由于能够自然地捕获上下文状态，往往是最常用的线程入口形式。

std::thread 采用的是**“构造即启动”**的执行模型：一旦 std::thread 对象被成功构造，线程便会立即向操作系统注册并进入可调度状态

后台线程的创建与启动过程：

1
background_thread_.emplace([&] { StartWorkerThread(); });

这行代码在语义上完成以下三个步骤：

  1. 在std::optional内部原地构建一个std::thread对象;

  2. 在构建过程中，向操作系统请求一个新的线程；

  3. 新创建的线程立即开着并执行传入的可调用对象。

主线程可以通过以下两种方式管理线程的结束：

  • 调用 join()，阻塞当前线程，直到目标线程执行完毕并完成资源回收；

  • 调用 detach()，将线程与 std::thread 对象分离，由系统在其结束后自动回收资源。

std::promise,std::future的工作机制

promise 和 future 是线程之间结构传递和同步的机制，promise / feature 的一切行为都是在操作同一块「共享状态」：

1
2
3
4
5
6
7
8
9
10
11
12
┌──────────────────────────┐
│      shared state        │
│--------------------------│
│ value / exception        │
│ ready flag (bool)        │
│ mutex                    │
│ condition_variable       │
│ ref count                │
└──────────────────────────┘
     ▲                ▲
     │                │
 promise handle   future handle
1
2
3

```c++
std::future<bool> future = promise.get_future();

promise已经拥有shared state，get_future提供一个future句柄，指向同一块state，state引用+1，此后future和promise各自独立

promise.set_value()写结果+唤醒等待着，如：

1
promise.set_value(true);

获取shared state的锁，然后写入结果，shared_state.value = true, 如果是异常则 shared_state.exception = exception，然后设置就绪状态，然后唤醒所有等待线程，最后释放锁

future.wait()只等，不取

1
future.wait();

获取shared state的锁，检查ready状态，ready==true则返回，否则阻塞等待，set_value()将其唤醒后再次检查。wait不会消耗结果，可以调用多次。

future.get()等 + 取 + 销毁读权限

1
bool x = future.get();

如果还没有ready，则等待，ready后读取结果，之后放弃shared state，所以get()只能调用一次，之后shared state可能随即被销毁（如果promise已经被销毁了）

Buffer Pool Manager

BufferPoolManager负责在磁盘与内存之间调度数据库页，并管理它们在内存中的生命周期。具体来说：

  • 从磁盘读page到内存

  • 将脏页写回内存

  • 内存满时，选择并淘汰page

  • 对外提供安全的page访问接口

1
2
3
DiskManager  ←  DiskScheduler  ←  BufferPoolManager  →  ArcReplacer
                                      ↓
                                 FrameHeader[]

DiskManager: 负责实际的磁盘读写工作

DiskScheduler: 负责异步调度disk read / write.

ArcReplacer: 负责决定 Evict 哪个frame

FrameHeader: 表示一个内存 Frame, 所有对 page 的访问必须通过 FrameHeader.

具体实现

CheckReadPage / CheckWritePage 实现

定位: CheckReadPage和CheckWritePage逻辑几乎相同, 负责由page_id → 找到/分配frame → 必要时flush/读入 → 返回对应PageGuard.

两把锁: bpm_latch_保护BPM的共享结构, frame rwlock保护每个frame的页内容与该frame的读写并发

基本锁顺序: 先拿bpm_latch_ 找 frame, 然后再拿rwlock

核心逻辑过程:

1
2
3
4
5
6
7
8
9
10
拿到 bpm_latch_ 后：
1. 查 page_table_：命中则得到 frame, 跳到第5步
2. 未命中：从 free_list 或 replacer->Evict() 选 victim frame_id, 拿到 frame 的 rwlock
3. 若 victim dirty：需要 flush
4. 更新 BPM 结构（必须在 bpm_latch_ 内完成）：
5. 更新 FrameHeader 元信息（也在 bpm_latch_ 内完成）：
6. 提交 IO 操作
7. 释放 bpm_latch_
8. 等待 IO 完成, 然后释放 frame rwlock
9. 返回 ReadPageGuard/WritePageGuard

[!CAUTION]
必须保证: 提交 IO 之前, 不能释放 bpm_latch_, 必须在持有 bpm_latch_ 的情况下发起 IO 请求.

假设 IO 不在 bpm_latch_内, 会出现语义不一致, 情景如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T1: 开始 eviction
  1.在bpm_latch_内:
    - 选中 victim frame F
    - 发现 F.page_id = old_page
    - old_page 是 dirty → 决定需要 flush
    - 从 page_table_ 删除 old_page → F 的映射
  2. 释放bpm_latch_
    - (IO 尚未 Schedule)

T2: 并发读 old_page
  1.拿 bpm_latch_
  2.在page_table_ 里查不到 old_page_id
  3.发起读 old_page 磁盘请求 (此时old_page 的 flush 还没有提交)
  4.读到未被修改的 old_page 内容

T2 以为自己读到的是 old_page 的最新内容, 但 dirty 数据尚未 flush, 磁盘上的 old_page 是旧内容

如果这时候已经提交了 IO 申请, 那么 T2 在读 old_page 磁盘内容时, 磁盘调度器知道这一页有一个 flush 请求, 它就能正确处理

NewPage: 并发安全生成 page_id

NewPage 需要在多线程下返回唯一的 page_id, 避免两个线程拿到同一个 id, 最开始没有把这个函数写成并发安全的, 导致没有通过测试

C++的原子计数器是可以把”自增+返回旧值”做成一个原子操作, CPU/编译器保证其为一个原子动作.

1
page_id_t pid = next_page_id_.fetch_add(1);

实验总结

随机初始化和ASan冲突

由于 ASLR, 在进程启动早期，libc / PIE 被随机映射到了虚拟地址空间中的某些位置, 如果这些映射恰好落在 ASan 预期的 shadow 区间内, 那么当 ASan runtime 随后尝试 mmap 该 shadow 区时, 就会发现地址冲突并直接 abort.

关闭 ASLR 后, 主程序与 mmap 区域落在固定, 可预测的位置, ASan就可以稳定映射它的shadow memory, 可用setarch关闭地址随机:

1
setarch $(uname -m) -R ./program

ASan的工作机制:

  • 编译时(-fsanitize=address), 编译器在每一次内存访问前后插入检查代码, 这些检查会在运行时验证是否越界, 是否use-after-free, 是否访问了非法区域

  • shadow Memory: ASan 为程序的真实内存建立一份影子内存, 映射关系固定，例如:

    8 bytes real memory → 1 byte shadow memory

    shadow byte 记录这 8 字节区域是否：可访问, 部分可访问, 不可访问, 从而触发错误报告

PIE与ASLR:

PIE(Position Independent Executable) 是一种编译/链接属性, 它决定生成的不是传统可执行文件, 而是ELF Type = ET_DYN 文件, 它决定的是这个程序能不能被随机加载

  • 非 PIE 程序: ELF Type = ET_EXEC, 链接时已确定固定虚拟地址

  • PIE 程序: ELT Type = ET_DYN, 链接时不绑定固定基址, 由 loader 运行时决定映射地址

ASLR(Address Space Layout Randomization)是操作系统/内核级机制, 为新进程随机选择地址空间布局, 它决定的是程序要不要随机加载

为什么ASLR会与ASan冲突

Linux 4.12 之后, 内核将 ET_DYN(PIE)可执行文件纳入与共享库相同的高地址 ASLR 随机区间, 这显著提高了进程早期映射落入 ASan shadow 区的概率，
从而导致 ASan 在初始化阶段发生地址空间冲突.

用到的同步工具总结

工具 解决的问题 BusTub 中的典型用途
std::atomic 单变量的并发读写与可见性保证 pin_count_ 等计数或轻量状态, 避免频繁加锁
std::mutex / std::shared_mutex 保护多变量组成的共享不变量(临界区) page_table_、free_list_、replacer 内部结构；frame 的读写锁
std::thread 提供独立的执行流 DiskScheduler 的后台 worker 线程, 持续处理 I/O 请求
std::promise / std::future 跨线程的结果传递与完成通知 磁盘读写请求的完成信号, 前台等待后台 I/O 结束