Project #1 - Buffer Pool Manager 最后更新：Sep 30, 2024

不要将你的项目发布到公开的 Github 仓库。

概述

本学期，你将构建一个面向磁盘的数据库管理系统（DBMS），名为 BusTub。面向磁盘的架构意味着 DBMS 的主要存储位置在持久化存储中，如硬盘（HDD）或闪存（SSD）。这与内存型 DBMS 不同，后者将数据存储在易失性内存中。

第一个编程项目是实现 DBMS 的缓冲池管理器。缓冲池负责在内存缓冲区和持久化存储之间来回移动物理数据页。它还充当缓存，将频繁使用的页保留在内存中以加快访问速度，并淘汰未使用或冷数据页回存储。

BusTub 中的一个页是 4096 字节（4 KB）的数据，这意味着缓冲池以 4 KB 为单位管理数据。由于 BusTub 中的页具有固定大小，缓冲池管理器将这些页存储到固定大小的缓冲区中，称为帧。页和帧之间的区别有些微妙。页是 4 KB 的逻辑（虚拟）数据，可以存储在内存中、磁盘上，或同时存在于两者中。而帧是一个固定长度的 4 KB 内存块（即指向该内存的指针），用于存储单个页的数据。这里的类比是将（逻辑）页存储在（物理）固定帧内部。

除了充当缓存之外，缓冲池管理器还允许 DBMS 支持大于系统可用内存量的数据库。假设一台计算机有 1 GB 的内存（RAM）。如果我们要管理一个 2 GB 的数据库，缓冲池管理器使我们能够与这个数据库交互，而无需将其全部内容放入内存。

缓冲池执行的 I/O 操作被抽象化，与 DBMS 的其他部分隔离。例如，当 DBMS 的某个组件（如执行引擎）使用唯一标识符（page_id_t）向缓冲池管理器请求一个数据页时，该组件不需要知道该页是否已在内存中，或者系统是否需要从磁盘检索它。同样，缓冲池管理器不需要理解这些页的内容，它只需要知道数据存储在哪里。

实现

你的缓冲池实现必须是线程安全的。多个线程将并发访问你的缓冲池的内部数据结构，你必须确保临界区受到锁存器（latches）的保护（在操作系统中称为"锁"）。

你必须实现以下存储管理器组件：

• LRU-K 替换策略
• 磁盘调度器
• 缓冲池管理器

这是一个个人项目，必须独立完成（即不允许组队）。

• 发布日期： Sep 09, 2024
• 截止日期： Sep 29, 2024 @ 11:59pm

项目规范

记得从 BusTub 仓库拉取最新代码。

对于以下每个组件，我们提供了包含你必须实现的 API 的存根类。你不应修改这些类中预定义函数的签名。如果你修改了签名，我们的评分测试代码将无法工作，你将无法获得该项目的学分。

如果一个类已经包含数据成员，你不应删除它们。例如，BufferPoolManager 类包含 DiskScheduler 和 LRUKReplacer 成员，这些是系统其余部分所需功能所必需的。你可以向这些类添加数据成员和辅助函数以正确实现所需的功能。

除非另有说明，你可以在项目中使用任何内置的 C++17 容器。由你来决定使用哪些容器。请注意，这些容器不是线程安全的，你需要使用锁存器来保护对它们的访问。你不能使用额外的第三方库（例如 Boost）。

任务 #1 - LRU-K 替换策略

该组件负责跟踪缓冲池中的页使用情况，以确定要淘汰出内存并写回磁盘的候选页/帧。

你将在 src/include/buffer/lru_k_replacer.h 中实现一个名为 LRUKReplacer 的类，并在 src/buffer/lru_k_replacer.cpp 中实现其对应的实现文件。注意 LRUKReplacer 是一个独立的类，与任何其他 Replacer 类无关。你只需要实现 LRU-K 替换策略，不需要实现 LRU 或 Clock 替换策略（即使有对应的文件）。

LRU-K 算法淘汰的帧是其反向 k-距离 在所有替换器中的帧中最大的那个。反向 k-距离计算为当前时间戳与第 k 次前访问时间戳之间的时间差。历史访问次数少于 k 次的帧，其反向 k-距离为 +inf。如果多个帧的反向 k-距离都是 +inf，替换器淘汰总体时间戳最早的帧（即其最近记录访问时间是所有帧中最早的那个）。

LRUKReplacer 的最大大小与缓冲池的大小相同，因为它包含 BufferPoolManager 中所有帧的占位符。然而，替换器中并非所有帧在任何给定时间都可以被视为可淘汰的。LRUKReplacer 的大小由可淘汰帧的数量表示。LRUKReplacer 初始化时其中没有任何帧。只有当帧被标记为可淘汰时，替换器的大小才会增加。类似地，当帧被固定或不再使用时，替换器的大小会减小。

你需要为 LRU-K 实现以下方法，如头文件（src/include/buffer/lru_k_replacer.h ）和源文件（src/buffer/lru_k_replacer.cpp ）中所定义：

• Evict() -> std::optional<frame_id_t>：淘汰具有最大反向 k-距离的帧，与 Replacer 跟踪的所有其他可淘汰帧相比。如果没有可淘汰的帧，返回 std::nullopt。
• RecordAccess(frame_id_t frame_id)：记录给定帧在当前时间戳被访问。此方法应在页被 BufferPoolManager 固定后调用。
• Remove(frame_id_t frame_id)：清除与帧关联的所有访问历史。此方法仅在 BufferPoolManager 中删除页时调用。
• SetEvictable(frame_id_t frame_id, bool set_evictable)：此方法控制帧是否可淘汰。它还控制 LRUKReplacer 的大小。当你实现 BufferPoolManager 时就会知道何时调用此函数。具体来说，当页的固定计数降为 0 时，其对应的帧应被标记为可淘汰。
• Size() -> size_t：此方法返回当前在 LRUKReplacer 中的可淘汰帧的数量。

实现细节由你决定。你可以使用内置的 STL 容器。你可以假设不会为这些数据结构的内存不足（但你不能对任务 #3 中的缓冲池做同样的假设，你会遇到可用帧不足的情况）。你必须确保你的实现是线程安全的。

如果你想了解更多关于 LRU-K 替换算法的信息，请参阅这篇论文。

任务 #2 - 磁盘调度器

该组件负责调度 DiskManager 上的读写操作。你将在 src/include/storage/disk/disk_scheduler.h 中实现一个名为 DiskScheduler 的类，并在 src/storage/disk/disk_scheduler.cpp 中实现其对应的实现文件。

磁盘调度器可以被其他组件（在本例中是任务 #3 中的 BufferPoolManager）用来排队磁盘请求，这些请求由 DiskRequest 结构体表示（已在 src/include/storage/disk/disk_scheduler.h 中定义）。磁盘调度器将维护一个后台工作线程，负责处理已调度的请求。

磁盘调度器将使用共享队列（通道）来调度和处理 DiskRequest。一个线程将请求添加到队列中，磁盘调度器的后台工作线程将处理排队的请求。我们在 src/include/common/channel.h 中提供了一个 Channel 类，用于促进线程之间数据的安全共享，但如果你觉得有必要，可以使用自己的实现。

DiskScheduler 的构造函数和析构函数已经实现，分别负责创建和加入后台工作线程。你只需要实现以下方法，如头文件（src/include/storage/disk/disk_scheduler.h ）和源文件（src/storage/disk/disk_scheduler.cpp ）中所定义：

• Schedule(DiskRequest r)：调度一个请求供 DiskManager 执行。DiskRequest 结构体指定请求是读还是写，数据应该从哪里读取/写入哪里，以及操作的页 ID。DiskRequest 还包含一个 std::promise，一旦请求被处理，其值应设为 true。有关 std::promise 的更多信息，请参见下文。
• StartWorkerThread()：后台工作线程的启动方法，负责处理已调度的请求。工作线程在 DiskScheduler 构造函数中创建并调用此方法。该工作线程负责接收排队的请求并将它们分派给 DiskManager。记得在 DiskRequest 的回调上正确设置值，以向请求发起者发出请求已完成的信号。在 DiskScheduler 的析构函数被调用之前，此方法不应返回。

我们提到 DiskRequest 的一个字段是 std::promise。如果你不熟悉 C++ 的 promise 和 future，可以在这里查看文档。就本项目而言，它们本质上提供了一种回调机制，让线程知道其调度的请求何时完成。要查看它们的使用示例，请查看 disk_scheduler_test.cpp。

同样，实现细节由你决定。你必须确保你的实现是线程安全的。

磁盘管理器

包含 DiskManager 类的头文件位于（src/include/storage/disk/disk_manager.h ）。它从磁盘读取页数据并向磁盘写入数据。你的磁盘调度器在处理读或写请求时将使用 DiskManager::ReadPage() 和 DiskManager::WritePage()。

任务 #3 - 缓冲池管理器

最后，你必须实现缓冲池管理器（BufferPoolManager）！回顾本页开头，BufferPoolManager 负责使用 DiskScheduler 从磁盘获取数据库页并将它们存储在内存中。BufferPoolManager 还可以在明确指示或需要淘汰页以为新页腾出空间时，调度将脏页写回磁盘。

你的 BufferPoolManager 实现将使用你在本作业前几步中创建的 LRUKReplacer 和 DiskScheduler 类。LRUKReplacer 将跟踪页的访问时间，以便在需要为新页腾出空间时决定淘汰哪个帧。DiskScheduler 将在 DiskManager 上调度对磁盘的读写操作。

我们提供了一个名为 FrameHeader 的辅助类，用于管理内存中的帧。所有对页数据的访问都应通过 FrameHeader。FrameHeader 有一个名为 GetData 的方法，返回指向其帧内存的原始指针，DiskScheduler / DiskManager 将使用此指针将磁盘上物理页的内容复制到内存中。

提醒一下，缓冲池管理器不需要理解这些页的内容。BufferPoolManager 关于页所知道的信息只有页 ID（page_id_t）和它们存储在内的 FrameHeader。此外，BufferPoolManager 将重用相同的 FrameHeader 对象来存储数据，因为数据在磁盘和内存之间来回移动。换句话说，所有 FrameHeader 在系统的整个生命周期中将存储许多不同的页。

并发

在实现多线程缓冲池管理器时，我们必须注意同步数据访问。这意味着我们不希望在缓冲池的不同帧中存在同一页的多个副本。如果我们允许这样做，就会遇到以下场景：

• 线程 T₁ 将页 X₁ 从磁盘加载到一个帧中并开始修改页 X₁，我们称这个新版本为页 X₂。
• 线程 T₂ 将页 X₁ 从磁盘加载到另一个帧中并开始修改这个版本的页 X₁，我们称这个修改后的版本为页 X₃。
• 线程 T₂ 完成写入并将 X₃ 写回磁盘。
• 线程 T₁ 完成写入并将 X₂ 写回磁盘。
• 数据竞争 ☠️！

因此，我们在内存中只保留一个页的 1 个版本，以防止数据同步竞争。此外，为了防止在线程访问页时淘汰它，我们维护存储该页的帧的引用计数/固定计数。最后，为了跟踪哪些页存储在哪些帧中，我们还使用哈希表维护一个页表，将页 ID 映射到帧。

帧的固定计数是可以访问该页数据的线程数。只要帧的固定计数大于 0（意味着至少有 1 个线程正在访问该页的数据），缓冲池管理器就不允许淘汰正在存储的页。你可以使用 FrameHeader 类中的原子字段 pin_count_ 来维护固定计数。请注意，pin_count_ 与 LRUKReplacer::SetEvictable 是分开的，因此你需要确保它们正确同步。你还需要在认为必要时更新 FrameHeader 的 is_dirty_ 标志。如果你在淘汰页时此标志被设置，你将需要采取相应措施来维护内存和磁盘之间的数据同步。

最后但同样重要的是，你必须实现 ReadPageGuard 和 WritePageGuard。这些类是 RAII 对象，提供对底层页的线程安全读/写访问。更多信息请参见下面的实现部分。你可能需要与 BufferPoolManager 的 CheckedReadPage 和 CheckedWritePage 方法协同实现。但是，如果你想确保页守卫实现正确，可以选择先实现 BufferPoolManager::GetPinCount，然后拼凑出能通过页守卫测试的代码。

实现

你需要实现以下页守卫方法，如头文件（src/include/storage/page/page_guard.h ）和源文件（src/storage/page/page_guard.cpp ）中所定义：

• ReadPageGuard::ReadPageGuard()
• ReadPageGuard::ReadPageGuard(ReadPageGuard &&that)
• ReadPageGuard::operator=(ReadPageGuard &&that) -> ReadPageGuard &
• ReadPageGuard::Drop()
• WritePageGuard::WritePageGuard()
• WritePageGuard::WritePageGuard(WritePageGuard &&that)
• WritePageGuard::operator=(WritePageGuard &&that) -> WritePageGuard &
• WritePageGuard::Drop()

你不需要在 BufferPoolManager 方法之前实现这些方法。你应该同时进行开发。

这些方法实现了页守卫的移动语义和 RAII。如果你不熟悉这些概念，请通过在线学习资料进行了解。有很多优秀的资源（包括文章、微软教程、YouTube 视频）深入解释了这些内容。在没有扎实理解 RAII 和移动语义工作原理的情况下，你不应该尝试实现这些方法。

这里可能会有很多代码重复（即两个守卫除了少数几行外应该完全相同）。如果你想基于自己创建的类来派生这些类，欢迎这样做。只需确保不改变任何接口和方法签名！

你还需要实现以下 BufferPoolManager 方法，如头文件（src/include/buffer/buffer_pool_manager.h ）和源文件（src/buffer/buffer_pool_manager.cpp ）中所定义：

• NewPage() -> page_id_t
• DeletePage(page_id_t page_id) -> bool
• CheckedWritePage(page_id_t page_id) -> std::optional<WritePageGuard>
• CheckedReadPage(page_id_t page_id) -> std::optional<ReadPageGuard>
• FlushPage(page_id_t page_id) -> bool
• FlushAllPages()
• GetPinCount(page_id_t page_id)

所有这些方法在源文件中都有详细的文档注释。确保完整阅读所有注释！它们包含许多有用的提示。

你不需要让缓冲池管理器非常高效。对于所有公共的 BufferPoolManager 方法，从头到尾持有缓冲池锁存器应该就够了（除了需要提前释放以防止死锁的情况）。但是，你确实需要确保缓冲池管理器具有合理的性能，否则在后续项目中会出现问题。你可以将自己的基准测试结果（QPS.1 和 QPS.2）与其他同学进行比较，看看你的实现是否太慢。

请参阅源文件（src/storage/page/page_guard.cpp 和 src/buffer/buffer_pool_manager.cpp ）以获取更为详细的规范和文档。

排行榜任务（可选）

在本项目的排行榜挑战中，我们将使用特殊的存储后端对你的缓冲池管理器进行基准测试。

针对排行榜进行优化是可选的（即完成所有之前的任务后，你可以获得满分）。 但是，你的解决方案必须在排行榜测试中以正确的结果完成，且不能出现死锁和段错误。

排行榜测试使用 release 配置文件编译：

mkdir cmake-build-relwithdebinfo
cd cmake-build-relwithdebinfo
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo
make -j `nproc` bpm-bench
# The command below is just for illustrating how the bpm-bench test works.
# We are NOT running tests with the same parameter for the leaderboard test.
./bin/bustub-bpm-bench --duration 5000 --latency 1

我们强烈建议你在针对排行榜测试进行优化之前先备份代码，这样如果这些优化在后续项目中出现问题，你总是可以回退。

在排行榜测试中，我们将有多个线程访问磁盘上的页。基准测试中有两种类型的线程运行：

1. 扫描线程。每个扫描线程将顺序读取磁盘上的页。将有 8 个扫描线程。
2. 获取线程。每个获取线程将使用 zipfian 分布随机选择并更新一个页。 将有 8 个获取线程。

我们将在内存存储后端上运行基准测试三次，每次 30 秒。第一次和第二次将直接使用不同的缓冲池和替换器设置运行。 第三次，我们将为每次随机读/写操作添加 1 毫秒的延迟，为顺序/局部读/写操作添加 0.1 毫秒的延迟。更多信息请参见 DiskManagerUnlimitedMemory 类。

最终得分计算为扫描和获取操作的加权 QPS，分别包含和不包含延迟：

scan_qps_large / 1000 + get_qps_large / 1000 + scan_qps_small / 1000 + get_qps_small / 1000 + scan_qps_1ms + get_qps_1ms

推荐优化

1. 更好的替换器算法。鉴于获取负载是倾斜的（即某些页比其他页更频繁地被访问）， 你可以设计你的 LRU-k 替换器将页访问类型考虑在内，以减少页缺失。
2. 并行 I/O 操作。不是在磁盘调度器中一次处理一个请求，你可以同时向磁盘管理器发出多个请求。 这个优化在现代存储设备中非常有用，因为对磁盘的并发访问可以更好地利用磁盘带宽。你应该处理同一页的多个操作在队列中的情况， 这些请求的最终结果应该如同按顺序处理一样。在单线程中，它们应该具有写后读一致性。
3. 要在磁盘调度器中实现真正的并行，你还需要允许缓冲池管理器同时处理多个 ReadPage 和 WritePage 请求以及同时淘汰多个页。你可能需要在缓冲池管理器中引入条件变量来管理空闲页。
4. 你可以使用我们在 third_party/readerwriterqueue 中提供的无锁队列实现，并 创建你自己的与 std::promise 兼容的 promise 实现，以降低 线程间通信的开销。请注意，在本项目中，所有请求都必须通过 DiskScheduler 的后台线程。

排行榜政策

• 带有排行榜加分的提交将由助教进行人工审查。
  • "审查"意味着助教将手动查看你的代码，或者如果他们不确定某个优化是否正确，他们将对现有测试用例进行简单修改，以查看你的排行榜优化是否正确处理了你想优化的特定情况。
  • 简单修改的一个例子：更改基准测试的缓冲池管理器大小。
• 你的优化不应影响正确性。你可以针对特定情况进行优化，但在你优化的情况下，它应该对所有输入都有效。
  • 不允许：将计划与排行榜测试进行比较，并将其转换为 ValueExecutor 与项目 3 中的输出表。因为你的优化应该适用于所有表内容。硬编码答案在某些情况下会产生错误的结果。
• 你不应该通过使用辅助信息来检测你的提交是否在运行排行榜测试。
  • 除非我们允许你这样做。
  • 不允许：使用 #ifdef NDEBUG 等。
• 具有明显正确性问题的提交将不会被授予排行榜加分。
• 你不能使用迟交日来处理排行榜测试。
• 如果你不确定某个优化是否合理，请在 Piazza 上发帖或访问助教的答疑时间。

说明

请参阅 Project #0 说明了解如何创建你的私有仓库和搭建开发环境。

测试

你可以使用我们的测试框架来测试本作业的各个组件。我们使用 GTest 进行单元测试。有三个独立的文件包含每个组件的测试：

• LRUKReplacer: test/buffer/lru_k_replacer_test.cpp
• DiskScheduler: test/storage/disk_scheduler_test.cpp
• PageGuard: test/storage/page_guard_test.cpp
• BufferPoolManager: test/buffer/buffer_pool_manager_test.cpp

你可以从命令行单独编译和运行每个测试：

$ make lru_k_replacer_test -j `nproc`
$ ./test/lru_k_replacer_test

你也可以运行 make check-tests 来运行所有测试用例。请注意，某些测试被禁用了，因为你还没有实现后续项目。你可以在 GTest 中通过添加 DISABLED_ 前缀来禁用测试。

重要提示：这些测试只是我们用来评估和评分你项目的所有测试的一个子集。你应该自己编写额外的测试用例来检查实现的完整功能。

格式化

你的代码必须遵循 Google C++ 风格指南。我们使用 Clang 自动检查你的源代码质量。如果你的提交未通过这些检查，你的项目成绩将为零。

执行以下命令检查你的语法。format 目标将自动修正你的代码。check-lint 和 check-clang-tidy-p1 目标将打印错误并指导你如何修复以符合我们的风格指南。

$ make format
$ make check-clang-tidy-p1

内存泄漏

在本项目中，我们使用 LLVM Address Sanitizer (ASAN) 和 Leak Sanitizer (LSAN) 来检查内存错误。要启用 ASAN 和 LSAN，请在调试模式下配置 CMake 并正常运行测试。如果存在内存错误，你将看到内存错误报告。请注意，macOS 仅支持地址检测器而不支持泄漏检测器。

在某些情况下，地址检测器可能会影响调试器的可用性。在这种情况下，你可能需要通过配置 CMake 项目来禁用所有检测器：

$ cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..

开发提示

你可以在调试模式下使用 BUSTUB_ASSERT 进行断言。请注意，BUSTUB_ASSERT 中的语句在发布模式下不会被执行。 如果你需要在所有情况下进行断言，请使用 BUSTUB_ENSURE 代替。

请在 Piazza 上发布你关于本项目的所有问题。不要直接通过电子邮件向助教提问。

如果你遇到问题，我们鼓励你使用图形化调试器来调试项目。

如果你遇到编译问题，运行 make clean 并不能完全重置编译过程。你需要删除构建目录并重新运行 cmake ..，然后再运行 make。

评分标准

每个项目提交将根据以下标准进行评分：

1. 提交是否成功执行所有测试用例并产生正确答案？
2. 提交是否在没有内存泄漏的情况下执行？
3. 提交是否遵循代码格式化和风格政策？

请注意，我们将使用额外的测试用例来评分你的提交，这些测试用例比我们提供的示例测试用例更复杂。

迟交政策

请参阅课程大纲中的迟交政策。

提交

完成作业后，你可以将实现提交到 Gradescope：

• https://www.gradescope.com/courses/817456

在 build/ 目录中运行 make submit-p1 将在项目根目录下生成一个名为 project1-submission.zip 的 zip 压缩包，你可以将其提交到 Gradescope。

你可以尽可能多次提交答案并获得即时反馈。

Gradescope 和自动评分器说明

1. 如果你在 Gradescope 上超时，很可能是因为你的代码中存在死锁或代码太慢无法在 60 秒内运行。如果你的代码太慢，可能是因为你的 LRUKReplacer 不够高效。
2. 如果你在提交中打印太多日志，自动评分器将无法工作。
3. 如果自动评分器无法正常工作，请确保你的格式化命令有效，并且你提交的是正确的文件。
4. 排行榜基准测试分数将通过压力测试你的 buffer_pool_manager 实现来计算。

CMU 学生应使用 Piazza 上公布的 Gradescope 课程代码。

协作政策

• 每个学生必须独立完成本作业。
• 学生可以与他人讨论项目的高层次细节。
• 学生不允许在与其他学生的小组会议后复制白板上的内容。
• 学生不允许从其他同学那里复制解决方案。

警告：本项目的所有代码必须是你自己的。你不能从其他学生或网上找到的其他来源复制源代码。抄袭不会被容忍。有关更多信息，请参阅 CMU 的学术诚信政策。