Post

CMU-15445 Project 1 Buffer Pool Manager

CMU实验-存储引擎缓存池管理

Posted Updated
By Payne
15 min read

写在前面

Bustub的实验1，Bustub的实验都是循序渐进的，前一个实验是后一个实验的基础，所以还是要尽量做好一点避免给后面挖坑。

实验主要目的是为存储引擎实现一个缓存池(BufferPool)。缓存池的主要作用是将内存的物理页面移动到磁盘上，其允许DBMS支持大于系统可用内存量的数据库。缓存池的操作对于系统的其他部分是透明(transparent)的。比如，系统中通过唯一标识page_id_t向缓存池获取页面，但是不知道该页面已存在内存中或系统必须从磁盘中读取。

需要保证实现是线程安全的。多个线程同时访问数据时需要保证其关键部分收到latch/锁的保护。

需要实现几个组件：

实验要求

不要修改预定义的函数签名，有可能影响评分代码运行。不应该删除已有数据成员，如果需要的话可以新增数据成员。

可以用标准库容器，但仍然要保证代码是线程安全的。不要用boost。

页面替换策略

该组件负责跟踪缓冲池中的帧使用情况.

需要完成：

  • src/include/buffer/lru_k_replacer.h中的LRUReplacer类；
  • src/buffer/lru_k_replacer.cpp中LRUReplacer类对应实现；

只需要实现LRU-K替换策略，不需要实现LRU或其他时钟替换策略。LRU-K的核心思想是通过跟踪帧的历史访问记录，优先替换那些长时间未被访问的帧，从而提高缓存命中率。LRU-K算法在某些情况下比传统的LRU（最近最少使用）算法更有效，因为它考虑了帧的多次访问历史，而不仅仅是最近一次访问。本次实验中，优先淘汰长时间未访问的帧。

参考资料：

需要实现src/include/buffer/lru_k_replacer.h和src/buffer/lru_k_replacer.cpp中的方法：

  • Evict(frame_id_t* frame_id): 在所有可淘汰的帧中选择要淘汰的帧，返回需要淘汰的帧和True，或者返回False；
  • RecordAccess(frame_id_t frame_id)：标记当前时间戳访问了给定帧，该接口应在BufferPoolManager中固定页面时访问；
  • Remove(frame_id_t frame_id)：清除帧的所有访问记录，该方法在BufferPoolManager中页面被删除时调用；
  • SetEvictable(frame_id_t frame_id, bool set_evictable)：此方法设置帧是否可被淘汰，也控制着LRUKReplacer的大小。
  • Size(): 返回当前LRUKReplacer中追踪的可淘汰的帧。

可以随意使用STL，假设内存没有限制，但必须保证实现是线程安全的。

磁盘调度

该组件负责调度对DiskManager的读写操作。需要在src/include/storage/disk/disk_scheduler.h和src/storage/disk/disk_scheduler.cpp中分别声明和实现DiskScheduler类。

磁盘调度器接受其他组件（例如任务 #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;
  • StartWorkerThread()：启动处理已调度请求的后台工作线程的方法。工作线程在DiskScheduler构造函数中创建，并调用此方法。此方法负责获取排队的请求并将其分派给DiskManager。记得在DiskRequest 的回调中设置值，以通知请求发起者请求已完成。此方法在DiskScheduler的析构函数被调用之前不应返回。

最后，DiskRequest的一个字段是std::promise。不熟悉的话可以查阅相关文档。在本项目中，它们主要提供了一种回调机制，使线程能够知道其调度的请求何时完成。要查看它们的使用示例，可以参考disk_scheduler_test.cpp。

再次强调，具体的实现细节由你决定，但必须确保你的实现是线程安全的。

Disk Manager

Disk Manager类 (src/include/storage/disk/disk_manager.h) 负责从磁盘读取和写入页面数据。磁盘调度器在处理读或写请求时需使用 DiskManager::ReadPage() 和DiskManager::WritePage()方法。

缓存池管理器

实现缓冲池管理器（BufferPoolManager）。BufferPoolManager负责使用磁盘调度器（DiskScheduler）从磁盘中获取数据库页面并将其缓存在内存中。缓冲池管理器还可以在明确指定页面或需要淘汰页面以腾出内存空间时，调度脏页面的写操作，将其写回磁盘。

为了确保您的实现的兼容，提供了一些预先实现的函数。另外也不需要实现实际读取和写入磁盘数据的代码（实现为 DiskManager）。我们将提供该功能。但是，需要实现DiskScheduler来处理磁盘请求并将它们分派给DiskManager（这是任务 #2）。

系统中的所有内存页面都由Page对象表示。BufferPoolManager不需要了解这些页面的内容。但作为系统开发人员，您必须了解Page对象只是缓冲池中内存的容器，因此并不特定于某个页面(因为页面并不一定指向一个实际内存页面)。也就是说，每个Page对象都包含一个内存块，内存块用作存放DiskManager从磁盘读取的物理页面内容的拷贝。在数据来回移动到磁盘时，将重用同一个对象来存储数据。这意味着在系统的整个生命周期内，同一个对象可能包含不同的物理页面。对象的标识符（page_id）标识它包含的物理页面；如果对象不包含物理页面，则必须将其设置为INVALID_PAGE_ID.

每个Page对象维护一个引用计数，用来表示正使用该页面的线程数量。BufferPoolManager不能释放还在被使用的Page对象。Page还标记了是否脏页，你需要在页面取消锁定之前标记其是否为脏页。BufferPoolManager需要将脏Page对象中的内容写到磁盘上之后才可以复用对象。

BufferPoolManager的实现将使用前面创建的LRUKReplacer和DiskScheduler类。LRUKReplacer负责跟踪Page对象的访问时间，以便在需要释放一个框架以腾出空间来复制新的物理页面时，决定淘汰哪个页面。在缓冲池管理器中映射 page_id 到 frame_id 时，请注意 STL 容器不是线程安全的。DiskScheduler负责调度对DiskManager的读写操作。

本节需要实现头文件src/include/buffer/buffer_pool_manager.h和源文件src/buffer/buffer_pool_manager.cpp的以下函数:

  • FetchPage(page_id_t page_id)
  • UnpinPage(page_id_t page_id, bool is_dirty)
  • FlushPage(page_id_t page_id)
  • NewPage(page_id_t* page_id)
  • DeletePage(page_id_t page_id)
  • FlushAllPages()

FetchPage当所有页面都被锁定且无可用页面时返回nullptr。无论页面是否锁定，FlushPage都会将页面写入磁盘。

UnpinPage函数的is_dirty参数标记该页面是否在锁定期间被修改。

BufferPoolManager在函数NewPage()中需要创建新页面时可以使用私有函数AllocatePage获取一个唯一的新page id，另外，DeletePage()实现中需要调用DeallocatePage()方法，该方法模拟释放磁盘上页面（无操作，no-op）。

在实现缓冲池管理器（BufferPoolManager）时，你不需要追求极致的效率——在每个对外公开的缓冲池管理器函数中，从开始到结束持有缓冲池管理器锁应该已经足够。然而，你仍然需要确保你的缓冲池管理器具有合理的性能，否则在未来的项目中可能会遇到问题。为了评估你的实现是否具有合理的性能，你可以将你的基准测试结果（QPS.1 和 QPS.2）与其他学生的结果进行比较。如果你的实现速度过慢，这可能表明需要进一步优化。

更多信息参考相关头文件中的文档。

排行榜（可选）

本项目的排行榜挑战使用特殊的存储后端对您的缓冲池管理器进行基准测试。针对排行榜进行优化是可选的（即，完成所有前面的任务后，您可以在项目中获得满分）。但是，您的解决方案必须以正确的结果完成排行榜测试，并且没有死锁和段错误。

排行榜测试是使用发布配置文件编译的：

1
2
3
4
5

mkdir cmake-build-relwithdebinfo
cd cmake-build-relwithdebinfo
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo
make -j`nproc` bpm-bench
./bin/bustub-bpm-bench --duration 5000 --latency 1

基准测试中使用多线程访问页面，多个线程分别扫描和获取页面。基准测试将运行三次，测试结果根据扫描和获取操作的加权QPS计算获得。

建议的优化：

  • 更优的替换算法；
  • 并行 I/O；
  • 为了在磁盘调度程序中实现真正的并行性，您还需要允许缓冲池管理器 FetchPage同时处理多个请求并驱逐多个页面。您可能需要在缓冲池管理器中引入一个条件变量来管理空闲页面；
  • 所有页面数据都应存储在缓冲池管理器页面数组中。您不得为页面数据使用额外的内存（即在 BusTub 中实现页面缓存）。您必须正确处理所有读/写请求并将数据持久保存到磁盘管理器；
  • 可以使用提供的无锁队列实现third_party/readerwriterqueue，也可以创建自己的promise兼容的实现，std::promise以降低线程间通信的开销。请注意，在本项目中，所有请求都必须通过DiskScheduler的后台线程。

测试和提交

可以使用预定义好的测试代码，包括三部分：

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

以lru-k的测试为例：

1
2

make lru_k_replacer_test -j$(nproc)\
./test/lru_k_replacer_test

提交前需要格式化代码：

1
2

make format
make check-clang-tidy-p1

打包代码，注意带上Gradescope声明

1

make submit-p1
Tech, CMU-15/445
database distributed cmu 15-445
This post is licensed under CC BY 4.0 by the author.