【CMU15445 2024fall】Project #1 - Buffer Pool Manager 记录

日期：2025.7.15 2025.7.16（凌晨)

个人总结：

先来说一下自己消失了这么久干了什么。
自己打完比赛之后闲来无事，没有事干，所以就打算进军数据库（也算是为了就业搞搞)。正巧有人拉我打计算机系统能力大赛里的数据库的比赛，所以就接受了。（虽然就是被别人拉去当苦力，只有自己一个人打)。然后最开始的时候因为数据库自己什么都不懂，连数据库的课也没有上过，所以就开始乱学模式，不会的直接AI，也没有听课，直接开始搞CMU15445的2023fall的lab，没错，是2023.
但是后来由于比赛的时间紧迫，我不得不放下这个CMU的lab，直接开始搞比赛的题目。然后就是爆肝半个多月，竟然打进了前60，勉强混一个国赛名额的吊车尾。所以数据库的比赛看来还没有结束，打算这个暑假再精进一下，于是又回到了这个lab。关于lab，当时爆肝了好几天，把前三个lab弄完了，但是后面两个却没有办法在弄了。因为正好这个2023fall的lab在6.30号截止提交，以后只能搞2024及以后的了。
于是现在只能开始搞2024的lab了，正好23年的没有B+树，前面的自己估计也忘了差不多了，从头再来了直接。
本篇主要是记录自己在做这个P1的时候的经历。
LRU-K Replacement

这个东西其实就是一个小模拟，这个内容其实和23年的没有什么太大变化，加上这个模块本身其实比较独立，所以就直接复制粘贴了去年的代码。
有一个变化的地方，就是Evict函数的返回值加上了optional，这个东西就是相当于返回值有可能会是空，或者也可以理解成一个特殊值(std::nullopt)，可以用来帮助我们判断返回值的结果分类讨论。本质上来说，和之前的返回值是bool，然后参数传一个指针，把对应的结果直接通过参数指针来修改那种类型差不多，不过这种确实看着比较顺眼一些。
这边就大概说一下LRUKReplacer的设计：

1. class LRUKReplacer {
2. //...
3. //...
4.   std::list<frame_id_t> node_small_k_;
5.   std::list<frame_id_t> node_not_small_k_;
7. private:
8.   // TODO(student): implement me! You can replace these member variables as you like.
9.   // Remove maybe_unused if you start using them.
10.   std::unordered_map<frame_id_t, LRUKNode> node_store_;
11.   std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> node_small_k_it_map_;
12.   std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> node_not_small_k_it_map_;
14.   size_t current_timestamp_{0};
15.   size_t curr_size_{0};
16.   size_t replacer_size_;
17.   size_t k_;
18.   std::mutex latch_;
20.   void RemoveInternal(frame_id_t frame_id); //这个就是没有带锁的Remove函数
21. };

复制代码

把节点分成两类，小于k的，和不小于k的。key都是fid，value是list对应的迭代器。
然后展示一下Evict和Record函数：

1. auto LRUKReplacer::Evict() -> std::optional<frame_id_t> {
2.   // std::cout << "Evict" << std::endl;
4.   std::unique_lock<std::mutex> lock(latch_);
6.   frame_id_t able_frame_id;
8.   if (!node_small_k_.empty()) {
9.     for (auto it = node_small_k_.rbegin(); it != node_small_k_.rend(); it++) {
10.       auto fid = (*it);
11.       auto node = node_store_[fid];
12.       if (!node.is_evictable_) {
13.         continue;
14.       }
15.       able_frame_id = fid;
16.       RemoveInternal(able_frame_id);
17.       return able_frame_id;
18.     }
19.   }
21.   size_t mmax_time = 0;
22.   if (!node_not_small_k_.empty()) {
23.     for (auto it = node_not_small_k_.rbegin(); it != node_not_small_k_.rend(); it++) {
24.       auto fid = (*it);
25.       auto node = node_store_[fid];
26.       if (!node.is_evictable_) {
27.         continue;
28.       }
29.       if ((current_timestamp_ - node.history_.front()) > mmax_time) {
30.         mmax_time = current_timestamp_ - node.history_.front();
31.         able_frame_id = fid;
32.       }
33.     }
34.   }
35.   if (mmax_time != 0U) {
36.     RemoveInternal(able_frame_id);
37.     return able_frame_id;
38.   }
39.   return std::nullopt;
40. }
42. void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
43.   // 也有可能有等于号
44.   std::unique_lock<std::mutex> lock(latch_);
45.   BUSTUB_ASSERT(frame_id <= (int32_t)replacer_size_, "frame_id too large");
46.   if (node_store_.count(frame_id) == 0U) {
47.     node_small_k_.push_front(frame_id);
48.     node_small_k_it_map_[frame_id] = node_small_k_.begin();
49.   }
50.   auto it = node_store_.find(frame_id);
51.   LRUKNode &node = it->second;
52.   node.history_.push_back(current_timestamp_++);
53.   if (node.is_large_k_) {
54.     node.history_.pop_front();
55.     return;
56.   }
57.   if (node.history_.size() < k_ && node.history_.size() > 1) {
58.     return;
59.   }
60.   if (node.history_.size() >= k_) {
61.     node.is_large_k_ = true;
62.     auto it2 = node_small_k_it_map_.find(frame_id);
63.     if (it2 != node_small_k_it_map_.end()) {
64.       node_small_k_.erase(it2->second);
65.       node_small_k_it_map_.erase(frame_id);
66.     }
67.     node_not_small_k_.push_front(frame_id);
68.     node_not_small_k_it_map_[frame_id] = node_not_small_k_.begin();
69.   }
70. }

复制代码

Disk Scheduler

这个东西其实没有必要特别的细究他，因为我们的目标如果只是100的话，其实把他当做同步的队列去使用也没有什么问题。
就当在读page的时候，往往都会这样写：

1.   auto promise = disk_scheduler_->CreatePromise();
2.   auto future = promise.get_future();
3.   disk_scheduler_->Schedule({true, frame_hd->GetDataMut(), frame_hd->GetPageId(), std::move(promise)});
4.   future.get();

复制代码

非常的方便，直观。
关于promise和future的使用，写过线程池的一般都会了解到，知乎上搜手写线程池，印象中里面就用到了这个特性，问问AI就好了。
另外值得一提的是，24年里，并没有直接与Page接触，而是用了一个FrameHead去处理。其实这个东西和Page的感觉差不多，倒不如说是我道行太浅，在这个类里的成员变量又加上了读写锁和page_id，所以本质上我就是在把他当做Page使用。无法充分的get到设计人的用意。
话扯回来，这个的实现其实也比较的easy。
Schedule函数就直接把DiskRequest放进队列里就好了。
StartWorkerThread函数就直接开一个while1循环，然后把队头取出来，根据第一个参数（是否是写操作)来判断一下就好了。
Page Guard

这个其实我印象中是去年的第二题里面的，但是今年挪了过来。这个变化说大不大，说小不小。其实我目前也没有特别的理解设计人的用意，凭着自己的感觉瞎写了基本上。一开始甚至理解错了，以为要把这个当做Page去使用了，sb了也是。其实和去年的设定差别不大，主要是有了它之后，可以给Page上读写锁比较的方便。但说实在的，这里有大坑。（先按下不表)
关于这里的移动构造，移动复制等之类的设计就不展示了，就是直接把that的成员函数挪过来就好了，然后把that的is_vaild赋值为false就好了。不要无脑的把that给Drop就可以了，因为我们不希望造成一个page会被释放多次这种错误。
另外根据我的理解，这里还负责着Page的Pin和Unpin，起码我的函数是写在了这里。
例如：

1. void WritePageGuard::Unpin() {
2.   bpm_latch_->lock();
3.   frame_->pin_count_--;
4.   if (frame_->pin_count_.load() == 0) {
5.     replacer_->SetEvictable(frame_->GetFid(), true);
6.   }
7.   bpm_latch_->unlock();
8. }
10. void WritePageGuard::Pin() {
11.   if (frame_->GetFid() != INVALID_FRAME_ID) {
12.     // auto &frame_hd = frames_[fid];
13.     // frame_hd->pin_count_.fetch_add(1);
14.     frame_->pin_count_++;
15.     auto fid = frame_->GetFid();
16.     replacer_->RecordAccess(fid);
17.     replacer_->SetEvictable(fid, false);
18.   }
19. }

复制代码

这里是WritePageGuard的其中Unpin和Pin的实现，这两个中，Pin是在构造的时候会被用到的，Unpin是在析构的时候被用到的。

1. ReadPageGuard::ReadPageGuard(page_id_t page_id, std::shared_ptr<FrameHeader> frame,
2.                              std::shared_ptr<LRUKReplacer> replacer, std::shared_ptr<std::mutex> bpm_latch)
3.     : page_id_(page_id), frame_(std::move(frame)), replacer_(std::move(replacer)), bpm_latch_(std::move(bpm_latch)) {
4.   // UNIMPLEMENTED("TODO(P1): Add implementation.");
5.   is_valid_ = true;
6.   Pin();
7.   bpm_latch_->unlock();
8.   frame_->RLatch();
9. }

复制代码

就像这样。（另外，关于这里的Pin，bpm的unlock，frame的读锁上锁的顺序不可以随便的调换，后面会提到这个问题)
值得一说的比较坑的地方是这里：

1. auto WritePageGuard::operator=(WritePageGuard &&that) noexcept -> WritePageGuard & {
2.   if (this == &that) {
3.     return *this;
4.   }
5.   Drop();
6.   this->page_id_ = that.page_id_;
7.   this->replacer_ = std::move(that.replacer_);
8.   this->frame_ = std::move(that.frame_);
9.   this->bpm_latch_ = std::move(that.bpm_latch_);
10.   this->is_valid_ = that.is_valid_;
12.   that.is_valid_ = false;
14.   return *this;
15. }

复制代码

在测试的用例里面，我们可以知道，关于这个移动构造的时候，会有这种自己移动构造自己的情况，要对这种情况进行特判呢。说实在的我觉得这个挺少见的。
另外还有，也是去年里知道的一个地方，我们要先把当前的资源给drop掉，然后再得到that里的内容。否则原本自己拥有的资源没有被释放掉呢。
Buffer Pool Manager

说实在的，我觉得这个的设计比去年恶心了不少，倒不如说是今年本身的这个设计，就没有办法直接暴力上锁就可以处理了，导致不得不去思考这个锁的问题。就是这里卡了我不少。
首先先说一下这个辅助函数：

1. // 搞到一个OK的fid，同时把这个位置的数据清空掉
2. auto BufferPoolManager::GetAbleFid() -> std::optional<frame_id_t> {
3.   if (!free_frames_.empty()) {
4.     auto fid = free_frames_.front();
5.     free_frames_.pop_front();
6.     // auto &frame_hd = frames_[fid];
7.     // frame_hd->Reset();
8.     return fid;
9.   }
11.   auto fid = replacer_->Evict();
12.   if (!fid.has_value()) {
13.     // std::cout << "GetAble FId: error : -1\n";
14.     return std::nullopt;
15.   }
16.   frame_id_t frame_id = fid.value();
17.   auto &frame_hd = frames_[frame_id];
19.   if (frame_hd->is_dirty_) {
20.     // std::cout << "有脏页\n";
21.     page_id_t page_id = frame_hd->GetPageId();
22.     FlushPage(page_id);
23.     // auto thread = std::thread([&] { FlushPageInternal(page_id); });
24.     // thread.join();
25.   }
27.   page_table_.erase(frame_hd->GetPageId());
28.   frames_[frame_id]->Reset();
30.   return frame_id;
31. }
33. // 搞到page_id放到了哪一个fid上，同时我们会把page_id的内容写到fid对应的帧上
34. // 这里还会调用frame的setPageId函数
35. auto BufferPoolManager::GetAbleFid(page_id_t page_id) -> std::optional<frame_id_t> {
36.   if (!free_frames_.empty()) {
37.     auto fid = free_frames_.front();
38.     free_frames_.pop_front();
40.     page_table_[page_id] = fid;
41.     frames_[fid]->SetPageId(page_id);
42.     return fid;
43.   }
45.   auto fid = replacer_->Evict();
46.   if (!fid.has_value()) {
47.     return std::nullopt;
48.   }
49.   frame_id_t frame_id = fid.value();
50.   auto &frame_hd = frames_[frame_id];
52.   if (frame_hd->is_dirty_) {
53.     page_id_t page_id = frame_hd->GetPageId();
54.     FlushPage(page_id);
55.   }

复制代码

这个函数（以第二个为主)，作用是我们可以把我们的page_id去放到buffer pool里面，返回值是返回的放到了哪一个frame_id里。
主要的思路就是首先看一下free_frames里面有没有，如果有的话，就把那个多余的槽给用上。如果free_frames里面没有的话，我们就用replacer进行淘汰。还有就是如果我们当前取出来的槽上有Page，而且这个page脏了的话，我们要先把他刷盘。
另外NewPage里的定义也改了一下，返回值是返回的page_id_t，而不是一个Page。

1. auto BufferPoolManager::NewPage() -> page_id_t {
2.   // UNIMPLEMENTED("TODO(P1): Add implementation.");
3.   std::lock_guard<std::mutex> lock(*bpm_latch_);
4.   auto fid = GetAbleFid();
5.   if (!fid.has_value()) {
6.     // std::cout << "fail New page\n";
7.     return INVALID_PAGE_ID;
8.   }
9.   frame_id_t frame_id = fid.value();
10.   page_id_t page_id = GetNextPageId();
11.   disk_scheduler_->IncreaseDiskSpace(page_id);
12.   frames_[frame_id]->SetPageId(page_id);
13.   page_table_[page_id] = frame_id;
15.   return page_id;
16.   // disk_scheduler_->IncreaseDiskSpace(++next_page_id_);
17.   // return next_page_id_ - 1;
18. }

复制代码

但是有一个奇怪的地方是，我这里其实是有些瞎写的成分在里面的，但是写的应该没啥问题?
但是交上去之后ScheduleTest一直报错，（虽然他不占分值，错了也可以是100pts)。改成下面注释里的那两行就可以过了（这个是直接看的别人)，我感觉这个主要是取决于打算怎么定义的吧，我是懒得看)。
别的像DeletePage，FlushPage都是老朋友了，这里就不详说了，也没有什么变化。
然后下面拿一个CheckReadPage来讲：

1. auto BufferPoolManager::CheckedReadPage(page_id_t page_id, AccessType access_type) -> std::optional<ReadPageGuard> {
2.   // UNIMPLEMENTED("TODO(P1): Add implementation.");
3.   if (page_id == INVALID_PAGE_ID) {
4.     return std::nullopt;
5.   }
6.   bpm_latch_->lock();
7.   if (page_table_.count(page_id) > 0) {
8.     auto &fid = page_table_.at(page_id);
9.     ReadPageGuard guard(page_id, frames_[fid], replacer_, bpm_latch_);
10.     return guard;
11.   }
12.   // 去尝试能不能可以，如果不可以的话，就return std::nullopt
13.   auto fid = GetAbleFid(page_id);
14.   if (!fid.has_value()) {
15.     bpm_latch_->unlock();
16.     return std::nullopt;
17.   }
18.   auto frame_id = fid.value();
19.   auto promise = disk_scheduler_->CreatePromise();
20.   auto future = promise.get_future();
21.   disk_scheduler_->Schedule({false, frames_[frame_id]->GetDataMut(), page_id, std::move(promise)});
22.   future.get();
24.   ReadPageGuard page_guard(page_id, frames_[frame_id], replacer_, bpm_latch_);
25.   return page_guard;
26. }

复制代码

这里就是一个简单的小分类讨论：
如果在我们的buffer_pool里的话，我们就直接找到他就好了。否则我们就先看可以不可以有空闲的槽位，然后就是读Page。
但是这里记得注意，我们没有用std::unqiue_lock和std::lock_guard这种东西了。而是直接使用的锁，还是先按下不表。
死锁问题

这是这个P1的比较关键的地方，关于并发的处理。
首先死锁是怎么产生的呢?
官方给的GTEST里的例子其实就比较恰当：

1. TEST(BufferPoolManagerTest, DeadlockTest) {
2.   auto disk_manager = std::make_shared<DiskManager>(db_fname);
3.   auto bpm = std::make_shared<BufferPoolManager>(FRAMES, disk_manager.get(), K_DIST);
4.   auto pid0 = bpm->NewPage();
5.   auto pid1 = bpm->NewPage();
6.   auto guard0 = bpm->WritePage(pid0);
7.   std::atomic<bool> start = false;
8.   auto child = std::thread([&]() {
9.     start.store(true);
10.     auto guard0 = bpm->WritePage(pid0);
11.   });
12.   while (!start.load()) {
13.   }
14.   std::this_thread::sleep_for(std::chrono::milliseconds(1000));
15.   auto guard1 = bpm->WritePage(pid1);
16.   guard0.Drop();
17.   child.join();
18. }

复制代码

p1线程首先去获得bpm的锁，然后获得了一个page（pid0，也可以这样说)的读写锁。由于我们调用了WritePage，所以我们获得了pid0的读写锁，然后释放了bpm的锁。那么后来的p2线程去获得bpm的锁首先，然后尝试去获得pid0的锁，但是pid0已经被挡住了，无法过去，只能在这里阻塞，此时它获得的是bom的锁。然后，p1尝试去auto guard1 = bpm->WritePage(pid1);，但是由于p2手握着bpm的锁，所以双方都在等待，所以现在便是死锁状态。
那么对应的处理应该是什么呢?
只要锁不嵌套就好了，也就是说我们在得到读写锁之前释放掉bpm的锁就好了。
有几个小tips：
关于释放bpm锁的顺序

1. ReadPageGuard::ReadPageGuard(page_id_t page_id, std::shared_ptr<FrameHeader> frame,
2.                              std::shared_ptr<LRUKReplacer> replacer, std::shared_ptr<std::mutex> bpm_latch)
3.     : page_id_(page_id), frame_(std::move(frame)), replacer_(std::move(replacer)), bpm_latch_(std::move(bpm_latch)) {
4.   // UNIMPLEMENTED("TODO(P1): Add implementation.");
5.   is_valid_ = true;
6.   Pin();
7.   bpm_latch_->unlock();
8.   frame_->RLatch();
9. }

复制代码

这里是ReadPageGuard的构造函数（Write的也一样)，我们的做法是先Pin住，然后bpm释放锁，再得到读写锁。先Pin住了之后，才能保证不会被淘汰掉，然后再释放bpm的锁，然后再是给读写锁上锁。
这里是关于Pin函数的实现：

1. //注意Pin里不应该有对锁的释放和上锁，因为Pin的时候我们需要保证这个bpm的锁一直在我们这里，frame不会被
2. //释放掉，所以我们中间不能进行lock和unlock的操作
3. void ReadPageGuard::Pin() {
4.   // bpm_latch_->lock();
5.   if (frame_->GetFid() != INVALID_FRAME_ID) {
6.     frame_->pin_count_++;
7.     auto fid = frame_->GetFid();
8.     replacer_->RecordAccess(fid);
9.     replacer_->SetEvictable(fid, false);
10.   }
11.   // bpm_latch_->unlock();
12. }

复制代码

Unpin的实现

1. void ReadPageGuard::Unpin() {
2.   bpm_latch_->lock();
3.   frame_->pin_count_--;
4.   if (frame_->pin_count_.load() == 0) {
5.     replacer_->SetEvictable(frame_->GetFid(), true);
6.   }
7.   bpm_latch_->unlock();
8. }

复制代码

这里有一个注意的地方就是，我们要记得给bpm上锁，因为我们中间这里是在使用bpm的共享资源，这个frame_是bpm的，并不是page，对他操作需要保证并发安全。
CheckWritePage里的PageGuard与读page的顺序

[code]auto BufferPoolManager::CheckedWritePage(page_id_t page_id, AccessType access_type) -> std:ptional {  // UNIMPLEMENTED("TODO(P1): Add implementation.");  //...  //...  //...  auto fid = GetAbleFid(page_id);  if (!fid.has_value()) {    bpm_latch_->unlock();    return std::nullopt;  }  auto frame_id = fid.value();  auto promise = disk_scheduler_->CreatePromise();  auto future = promise.get_future();  disk_scheduler_->Schedule({false, frames_[frame_id]->GetDataMut(), page_id, std::move(promise)});  future.get();  // std::cout