【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的设计：
class LRUKReplacer {
//...
//...
std::list<frame_id_t> node_small_k_;
std::list<frame_id_t> node_not_small_k_;
private:
// TODO(student): implement me! You can replace these member variables as you like.
// Remove maybe_unused if you start using them.
std::unordered_map<frame_id_t, LRUKNode> node_store_;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> node_small_k_it_map_;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> node_not_small_k_it_map_;
size_t current_timestamp_{0};
size_t curr_size_{0};
size_t replacer_size_;
size_t k_;
std::mutex latch_;
void RemoveInternal(frame_id_t frame_id); //这个就是没有带锁的Remove函数
};把节点分成两类，小于k的，和不小于k的。key都是fid，value是list对应的迭代器。
然后展示一下Evict和Record函数：
auto LRUKReplacer::Evict() -> std::optional<frame_id_t> {
// std::cout << "Evict" << std::endl;
std::unique_lock<std::mutex> lock(latch_);
frame_id_t able_frame_id;
if (!node_small_k_.empty()) {
for (auto it = node_small_k_.rbegin(); it != node_small_k_.rend(); it++) {
auto fid = (*it);
auto node = node_store_;
if (!node.is_evictable_) {
continue;
}
able_frame_id = fid;
RemoveInternal(able_frame_id);
return able_frame_id;
}
}
size_t mmax_time = 0;
if (!node_not_small_k_.empty()) {
for (auto it = node_not_small_k_.rbegin(); it != node_not_small_k_.rend(); it++) {
auto fid = (*it);
auto node = node_store_;
if (!node.is_evictable_) {
continue;
}
if ((current_timestamp_ - node.history_.front()) > mmax_time) {
mmax_time = current_timestamp_ - node.history_.front();
able_frame_id = fid;
}
}
}
if (mmax_time != 0U) {
RemoveInternal(able_frame_id);
return able_frame_id;
}
return std::nullopt;
}
void LRUKReplacer::RecordAccess(frame_id_t frame_id, [] AccessType access_type) {
// 也有可能有等于号
std::unique_lock<std::mutex> lock(latch_);
BUSTUB_ASSERT(frame_id <= (int32_t)replacer_size_, "frame_id too large");
if (node_store_.count(frame_id) == 0U) {
node_small_k_.push_front(frame_id);
node_small_k_it_map_ = node_small_k_.begin();
}
auto it = node_store_.find(frame_id);
LRUKNode &node = it->second;
node.history_.push_back(current_timestamp_++);
if (node.is_large_k_) {
node.history_.pop_front();
return;
}
if (node.history_.size() < k_ && node.history_.size() > 1) {
return;
}
if (node.history_.size() >= k_) {
node.is_large_k_ = true;
auto it2 = node_small_k_it_map_.find(frame_id);
if (it2 != node_small_k_it_map_.end()) {
node_small_k_.erase(it2->second);
node_small_k_it_map_.erase(frame_id);
}
node_not_small_k_.push_front(frame_id);
node_not_small_k_it_map_ = node_not_small_k_.begin();
}
}Disk Scheduler
这个东西其实没有必要特别的细究他，因为我们的目标如果只是100的话，其实把他当做同步的队列去使用也没有什么问题。
就当在读page的时候，往往都会这样写：
auto promise = disk_scheduler_->CreatePromise();
auto future = promise.get_future();
disk_scheduler_->Schedule({true, frame_hd->GetDataMut(), frame_hd->GetPageId(), std::move(promise)});
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，起码我的函数是写在了这里。
例如：
void WritePageGuard::Unpin() {
bpm_latch_->lock();
frame_->pin_count_--;
if (frame_->pin_count_.load() == 0) {
replacer_->SetEvictable(frame_->GetFid(), true);
}
bpm_latch_->unlock();
}
void WritePageGuard::Pin() {
if (frame_->GetFid() != INVALID_FRAME_ID) {
// auto &frame_hd = frames_;
// frame_hd->pin_count_.fetch_add(1);
frame_->pin_count_++;
auto fid = frame_->GetFid();
replacer_->RecordAccess(fid);
replacer_->SetEvictable(fid, false);
}
}这里是WritePageGuard的其中Unpin和Pin的实现，这两个中，Pin是在构造的时候会被用到的，Unpin是在析构的时候被用到的。
ReadPageGuard::ReadPageGuard(page_id_t page_id, std::shared_ptr<FrameHeader> frame,
std::shared_ptr<LRUKReplacer> replacer, std::shared_ptr<std::mutex> bpm_latch)
: page_id_(page_id), frame_(std::move(frame)), replacer_(std::move(replacer)), bpm_latch_(std::move(bpm_latch)) {
// UNIMPLEMENTED("TODO(P1): Add implementation.");
is_valid_ = true;
Pin();
bpm_latch_->unlock();
frame_->RLatch();
}就像这样。（另外，关于这里的Pin，bpm的unlock，frame的读锁上锁的顺序不可以随便的调换，后面会提到这个问题)
值得一说的比较坑的地方是这里：
auto WritePageGuard::operator=(WritePageGuard &&that) noexcept -> WritePageGuard & {
if (this == &that) {
return *this;
}
Drop();
this->page_id_ = that.page_id_;
this->replacer_ = std::move(that.replacer_);
this->frame_ = std::move(that.frame_);
this->bpm_latch_ = std::move(that.bpm_latch_);
this->is_valid_ = that.is_valid_;
that.is_valid_ = false;
return *this;
}在测试的用例里面，我们可以知道，关于这个移动构造的时候，会有这种自己移动构造自己的情况，要对这种情况进行特判呢。说实在的我觉得这个挺少见的。
另外还有，也是去年里知道的一个地方，我们要先把当前的资源给drop掉，然后再得到that里的内容。否则原本自己拥有的资源没有被释放掉呢。
Buffer Pool Manager
说实在的，我觉得这个的设计比去年恶心了不少，倒不如说是今年本身的这个设计，就没有办法直接暴力上锁就可以处理了，导致不得不去思考这个锁的问题。就是这里卡了我不少。
首先先说一下这个辅助函数：
// 搞到一个OK的fid，同时把这个位置的数据清空掉
auto BufferPoolManager::GetAbleFid() -> std::optional<frame_id_t> {
if (!free_frames_.empty()) {
auto fid = free_frames_.front();
free_frames_.pop_front();
// auto &frame_hd = frames_;
// frame_hd->Reset();
return fid;
}
auto fid = replacer_->Evict();
if (!fid.has_value()) {
// std::cout << "GetAble FId: error : -1\n";
return std::nullopt;
}
frame_id_t frame_id = fid.value();
auto &frame_hd = frames_;
if (frame_hd->is_dirty_) {
// std::cout << "有脏页\n";
page_id_t page_id = frame_hd->GetPageId();
FlushPage(page_id);
// auto thread = std::thread([&] { FlushPageInternal(page_id); });
// thread.join();
}
page_table_.erase(frame_hd->GetPageId());
frames_->Reset();
return frame_id;
}
// 搞到page_id放到了哪一个fid上，同时我们会把page_id的内容写到fid对应的帧上
// 这里还会调用frame的setPageId函数
auto BufferPoolManager::GetAbleFid(page_id_t page_id) -> std::optional<frame_id_t> {
if (!free_frames_.empty()) {
auto fid = free_frames_.front();
free_frames_.pop_front();
page_table_ = fid;
frames_->SetPageId(page_id);
return fid;
}
auto fid = replacer_->Evict();
if (!fid.has_value()) {
return std::nullopt;
}
frame_id_t frame_id = fid.value();
auto &frame_hd = frames_;
if (frame_hd->is_dirty_) {
page_id_t page_id = frame_hd->GetPageId();
FlushPage(page_id);
}这个函数（以第二个为主)，作用是我们可以把我们的page_id去放到buffer pool里面，返回值是返回的放到了哪一个frame_id里。
主要的思路就是首先看一下free_frames里面有没有，如果有的话，就把那个多余的槽给用上。如果free_frames里面没有的话，我们就用replacer进行淘汰。还有就是如果我们当前取出来的槽上有Page，而且这个page脏了的话，我们要先把他刷盘。
另外NewPage里的定义也改了一下，返回值是返回的page_id_t，而不是一个Page。
auto BufferPoolManager::NewPage() -> page_id_t {
// UNIMPLEMENTED("TODO(P1): Add implementation.");
std::lock_guard<std::mutex> lock(*bpm_latch_);
auto fid = GetAbleFid();
if (!fid.has_value()) {
// std::cout << "fail New page\n";
return INVALID_PAGE_ID;
}
frame_id_t frame_id = fid.value();
page_id_t page_id = GetNextPageId();
disk_scheduler_->IncreaseDiskSpace(page_id);
frames_->SetPageId(page_id);
page_table_ = frame_id;
return page_id;
// disk_scheduler_->IncreaseDiskSpace(++next_page_id_);
// return next_page_id_ - 1;
}但是有一个奇怪的地方是，我这里其实是有些瞎写的成分在里面的，但是写的应该没啥问题?
但是交上去之后ScheduleTest一直报错，（虽然他不占分值，错了也可以是100pts)。改成下面注释里的那两行就可以过了（这个是直接看的别人)，我感觉这个主要是取决于打算怎么定义的吧，我是懒得看)。
别的像DeletePage，FlushPage都是老朋友了，这里就不详说了，也没有什么变化。
然后下面拿一个CheckReadPage来讲：
auto BufferPoolManager::CheckedReadPage(page_id_t page_id, AccessType access_type) -> std::optional<ReadPageGuard> {
// UNIMPLEMENTED("TODO(P1): Add implementation.");
if (page_id == INVALID_PAGE_ID) {
return std::nullopt;
}
bpm_latch_->lock();
if (page_table_.count(page_id) > 0) {
auto &fid = page_table_.at(page_id);
ReadPageGuard guard(page_id, frames_, replacer_, bpm_latch_);
return guard;
}
// 去尝试能不能可以，如果不可以的话，就return std::nullopt
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_->GetDataMut(), page_id, std::move(promise)});
future.get();
ReadPageGuard page_guard(page_id, frames_, replacer_, bpm_latch_);
return page_guard;
}这里就是一个简单的小分类讨论：
如果在我们的buffer_pool里的话，我们就直接找到他就好了。否则我们就先看可以不可以有空闲的槽位，然后就是读Page。
但是这里记得注意，我们没有用std::unqiue_lock和std::lock_guard这种东西了。而是直接使用的锁，还是先按下不表。
死锁问题
这是这个P1的比较关键的地方，关于并发的处理。
首先死锁是怎么产生的呢?
官方给的GTEST里的例子其实就比较恰当：
TEST(BufferPoolManagerTest, DeadlockTest) {
auto disk_manager = std::make_shared<DiskManager>(db_fname);
auto bpm = std::make_shared<BufferPoolManager>(FRAMES, disk_manager.get(), K_DIST);
auto pid0 = bpm->NewPage();
auto pid1 = bpm->NewPage();
auto guard0 = bpm->WritePage(pid0);
std::atomic<bool> start = false;
auto child = std::thread([&]() {
start.store(true);
auto guard0 = bpm->WritePage(pid0);
});
while (!start.load()) {
}
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
auto guard1 = bpm->WritePage(pid1);
guard0.Drop();
child.join();
}p1线程首先去获得bpm的锁，然后获得了一个page（pid0，也可以这样说)的读写锁。由于我们调用了WritePage，所以我们获得了pid0的读写锁，然后释放了bpm的锁。那么后来的p2线程去获得bpm的锁首先，然后尝试去获得pid0的锁，但是pid0已经被挡住了，无法过去，只能在这里阻塞，此时它获得的是bom的锁。然后，p1尝试去auto guard1 = bpm->WritePage(pid1);，但是由于p2手握着bpm的锁，所以双方都在等待，所以现在便是死锁状态。
那么对应的处理应该是什么呢?
只要锁不嵌套就好了，也就是说我们在得到读写锁之前释放掉bpm的锁就好了。
有几个小tips：
关于释放bpm锁的顺序
ReadPageGuard::ReadPageGuard(page_id_t page_id, std::shared_ptr<FrameHeader> frame,
std::shared_ptr<LRUKReplacer> replacer, std::shared_ptr<std::mutex> bpm_latch)
: page_id_(page_id), frame_(std::move(frame)), replacer_(std::move(replacer)), bpm_latch_(std::move(bpm_latch)) {
// UNIMPLEMENTED("TODO(P1): Add implementation.");
is_valid_ = true;
Pin();
bpm_latch_->unlock();
frame_->RLatch();
}这里是ReadPageGuard的构造函数（Write的也一样)，我们的做法是先Pin住，然后bpm释放锁，再得到读写锁。先Pin住了之后，才能保证不会被淘汰掉，然后再释放bpm的锁，然后再是给读写锁上锁。
这里是关于Pin函数的实现：
//注意Pin里不应该有对锁的释放和上锁，因为Pin的时候我们需要保证这个bpm的锁一直在我们这里，frame不会被
//释放掉，所以我们中间不能进行lock和unlock的操作
void ReadPageGuard::Pin() {
// bpm_latch_->lock();
if (frame_->GetFid() != INVALID_FRAME_ID) {
frame_->pin_count_++;
auto fid = frame_->GetFid();
replacer_->RecordAccess(fid);
replacer_->SetEvictable(fid, false);
}
// bpm_latch_->unlock();
}Unpin的实现
void ReadPageGuard::Unpin() {
bpm_latch_->lock();
frame_->pin_count_--;
if (frame_->pin_count_.load() == 0) {
replacer_->SetEvictable(frame_->GetFid(), true);
}
bpm_latch_->unlock();
}这里有一个注意的地方就是，我们要记得给bpm上锁，因为我们中间这里是在使用bpm的共享资源，这个frame_是bpm的，并不是page，对他操作需要保证并发安全。
CheckWritePage里的PageGuard与读page的顺序
auto BufferPoolManager::CheckedWritePage(page_id_t page_id, AccessType access_type) -> std::optional {// 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_->GetDataMut(), page_id, std::move(promise)});future.get();// std::cout
页:
[1]