bustub通过disk_manager_memory管理磁盘中的数据，可以通过数据在数据库中的标识符page_it_t对磁盘中的数据进行读写。我们要实现的Buffer Pool src/buffer/buffer_pool_manager.cpp通过帧标识frame_id来管理缓冲池中的page_id。需要通过src/buffer/lru_k_replacer.cpp制定的LRU-K策略来决定帧的保留或者淘汰（Evicted），还需要实现src/storage/page/page_guard.cpp保证读写安全。

资源管理流程如下：

page = bpm->FetchPage(...) // 获取资源（Pin Count +1）
page->WLatch() // 获取资源（加写锁）
... 对页面进行读写操作 ...
page->WUnlatch() // 必须手动释放锁（PageGuard不需要）
bpm->UnpinPage(...) // 必须手动释放Pin（PageGuard不需要）

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

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据。

LRU-K在LRU的基础上提出要求，只有达到K次访问之后，才能被加入到访问历史中（LRU是可被看作LRU-1）。

原理#

LRU最经典的实现方式是通过双链表+哈希表的方式来实现。双链表实现对历史数据的添加与淘汰，而哈希表则保证能通过O(1)的复杂度访问历史数据。参考：Leetcode - LRU缓存

LRU-K可以在LRU的基础上，可是使用两个双链表（cache_list, history_list）来维护。对于没有达到K次访问的链表history_list，可以通过最后一次访问与当前访问的时间戳的差来进行淘汰，而达到K次访问的cache_list链表则可以通过LRU的规则来进行淘汰。

代码实现#

数据结构

1
class LRUKNode {
2
 public:
3
  std::list<size_t> history_;
4
  size_t k_;
5
  frame_id_t fid_;
6
  bool is_evictable_{false};
7
};
8

9
class LRUKReplacer {
10
  std::unordered_map<frame_id_t, LRUKNode> node_store_;  // 索引到正确的LRUKNode
11
     size_t current_timestamp_{0};
12
     size_t curr_size_{0};
13
     size_t replacer_size_;
14
     size_t k_;
15
     std::mutex latch_;
16
}

任务2: 缓冲池管理器#

缓冲池管理器的实现主要依赖于以下两个核心机制：Pin/Unpin 机制 (引用计数)与读写锁 (RLatch/WLatch)

Pin/Upin 机制#

类似shared_ptr的引用计数器。当一个线程通过FetchPage或NewPage从BPM获取一个页面时，BPM会将该页面的pin_count_加1。而当线程使用完这个页面后，它必须调用UnpinPage。BPM会随之将该页面的pin_count_减1。

这样的机制能保证一个正在被使用的界面不会被意外淘汰。

读写锁（RLatch/WLatch）#

通过Page对象内部的读写锁（RLatch()与WLatch）实现读写的线程安全。其中读锁RLock为共享锁std::shared_mutex，写锁为独占锁std::unique_lock

除此之外，Page中的is_dirty_参数标记了一个页面是否被修改过，当页面重新被调用时，一定会先调用WritePage()将页面写到磁盘上，确保此时的界面是同步的。

任务3: 读写守护程序（Page Guards）#

任务三的核心原理是 RAII (Resource Acquisition Is Initialization)，即“资源获取即初始化”。

在整个资源管理流程中，调用缓冲池内容时，锁和Page的计数器没有正确处理，会导致死锁或缓冲池泄漏（页面永远无法被淘汰）的问题。

需要考虑的页面属性：

pin_cout：访问当前页面线程数量
WLatch/RLatch：读写锁
is_dirty：是否已经被写入内容

原理#

RAII通过C++的语言特性（构造函数和析构函数）来根治上述问题：

资源获取 (Acquisition): 在一个对象的构造函数中获取资源（例如，调用FetchPage、加锁）。
资源释放 (Release): 在这个对象的析构函数中释放资源（例如，调用UnpinPage、解锁）。

实现#

1. 构造#

在src/include/storage/page_guard.h中可以看到实现Page Guard需要实现BasicPageGuard以及专门的读写守护ReadPageGuard和WritePageGuard。

BasicPageGuard

核心：负责核心Pin\Unpin管理
- Page*
- BufferPoolManager*
ReadPageGuard和WritePageGuard

都继承自BasicPageGuard，分别执行读和写的操作。

核心：读写锁的管理，WritePageGuard在被构造时需自动标记脏页(dirty)
- Page::RLatch/Page::WLatch

2. 所有权管理#

禁止拷贝： 拷贝构造函数和拷贝赋值运算符都应该被删除 (= delete)。因为如果可以拷贝，两个PageGuard对象就会指向同一个页面，当它们先后析构时，会导致同一资源被释放两次（例如，Unpin两次），引发程序崩溃。
允许移动： 移动构造函数和移动赋值运算符需要被实现。这允许一个函数安全地返回一个PageGuard对象，或者将所有权从一个变量转移到另一个。
- 移动构造函数逻辑： PageGuard new_guard(std::move(old_guard));
  1. 将old_guard的bpm_和page_指针“窃取”过来，赋给new_guard。
  2. 关键一步： 将old_guard的bpm_和page_指针设为nullptr。这“解除”了old_guard，当old_guard析构时，它会发现自己无事可做，从而避免了双重释放。

3. 析构#

析构函数中应该考虑锁和资源之间的释放关系，释放资源的顺序必须是：先释放Page的资源，解锁，再Unpin页面。在解锁时，页面仍然被Pin住，能保证内容是稳定的，否则BPM中的其他使用这个Page线程会因为当前Pin计数为0，提前释放当前Page的资源（特别是锁指针），导致当前线程的锁指针指向错误的锁。解锁后，再Unpin，允许BPM安全地回收它。

正确析构逻辑：{ page_->WUnlatch(); /\* BasicGuard的析构函数，完成Unpin \*/ }
错误析构逻辑： { page_->WUnlatch(); bpm_->UnpinPage(...); }

参考#

环境搭建#

使用docker进行部署：

1
docker build . -t bustub  # 编译bustub容器
2
docker create -t -i --name bustub -v $(pwd):/bustub bustub bash  # 创建bustub容器
3
docker start bustub  # 后台运行bustub容器