P1 - Buffer Pool Manager

Problem Description

在這個 project 中，我們需要實現一個 buffer pool manager，總共有 3 個 Task :

• LRU-K Replacement Policy : 修改 /src/buffer/lru_k_replacer.cpp 來實現 LRU-K replacement policy
• Disk Scheduler : 修改 /src/storage/disk/disk_scheduler.cpp 來實現 disk scheduler
• Buffer Pool Manager : 修改 /src/buffer/buffer_pool_manager.cpp 跟 /src/storage/page/page_guard.cpp 來實現 buffer pool manager

Solution

我採取的做法都是只求通過不求效能，如果想要進行效能優化，可以參考最下方 Reference 中的文章。

Task 1: LRU-K Replacement Policy

這個 Task 主要是要實現 LRU-K replacement policy，用於判斷哪個頁面要被移出記憶體。

不考慮效能的話只需要全部都使用 std::scoped_lock 即可，可以順便對 LRUKNode 寫一些 get function 來方便取得資料。

• Evict() -> std::optional<frame_id_t> : 優先度是先找有 inf 的，都是 inf 就比第一次讀取的時候哪個最早，如果都沒有 inf 的話就也找第一次讀取的時候哪個最早 (this->history_.back())
• RecordAccess(frame_id_t frame_id) : 更新 history_ 中的資料
• Remove(frame_id_t frame_id) : 檢查是否是 evictable 之後就可以直接刪除
• SetEvictable(frame_id_t frame_id, bool set_evictable) : 判斷 IsEvictable 的情況並刪除即可
• Size() -> size_t : 直接回傳 curr_size_

cd build
make lru_k_replacer_test -j$(nproc)

./test/lru_k_replacer_test

Task 2: Disk Scheduler

這個 Task 主要是要實現 disk scheduler，主要是用來處理 IO 的請求，將請求排到 queue 中，最後背景執行的 worker thread 會將請求處理完。

需要修改兩個 function :

• Schedule(DiskRequest r) : 只需要將 r 使用 std::move 丟到 request_queue_ 中即可
• StartWorkerThread() : 設計一個沒有終止的 while 迴圈，並將 request 依據 read / write 的情況來執行，最後再設定 callback 為 true 即可

以及要注意註解掉建構子中的 throw error，這樣才能正常執行 test。

cd build
make disk_scheduler_test -j$(nproc)

./test/disk_scheduler_test

Task 3: Buffer Pool Manager

這個 Task 應該是這個 project 中最難的部分，主要是要實現 Page Guard 跟 Buffer Pool Manager 的功能。

Page Guard 應該是 2024 版本才有的新東西，它是一個可以對記憶體進行讀寫的資料結構，是 Buffer Pool Manager 中用來保證安全讀寫頁面 (follow RAII) 的工具。

Buffer Pool Manager 則是用來管理 buffer pool 的資料結構，主要維護 page 跟 frame 的對應關係，除此之外也包含了 replacer_ 跟 disk_scheduler_ 來做頁面替換以及硬碟的讀寫。

我們先把在單線程下的功能寫好，然後再來討論鎖的問題，我們總共要處理以下幾個 function :

• ReadPageGuard::ReadPageGuard() : 取得 frame_->rwlatch 的共享鎖，並把 is_valid 設定為 true
• ReadPageGuard::ReadPageGuard(ReadPageGuard &&that) : 先 Drop 掉原本 PageGuard 的資料，再使用移動語意來把資料移過來，特別注意需要先檢查 this 跟 that 是否相同，以及把舊的 is_valid 設定為 false
• ReadPageGuard::operator=(ReadPageGuard &&that) -> ReadPageGuard & : 類似前面
• ReadPageGuard::Drop() : 先檢查 is_valid 是否為 true，如果是的話處理 pin_count 跟 SetEvictable 的情況，然後再把 is_valid 設定為 false

WritePageGuard 的部分大部分跟 ReadPageGuard 一樣，只是要改成使用獨佔鎖。

• NewPage() -> page_id_t : 把 nextpage_id +1 之後使用 disk_scheduler->IncreaseDiskSpace() 新增空間即可

• DeletePage(page_id_t page_id) -> bool : 先確定這個 page 有在 page_table 中，接著再檢查 pin_count 是否為 0，然後再檢查 is_dirty 看是否需要 FlushPage，最後再 Reset() 即可

• CheckedWritePage(page_id_t page_id) -> std::optional<WritePageGuard>

• CheckedReadPage(page_id_t page_id) -> std::optional<ReadPageGuard> :

  這兩個函數是這個 Task 最重要的函數，都分成三種情況 :

  • 這個 page 已經在 buffer pool 中了，那我們就要更新他的資料 (pin_count, evictable, recordaccess) 並回傳
  • page_id 不在 buffer pool 中，但是 free_frame 中有空間，那我們就可以 pop_front 一個 frame，然後一樣更新 metadata
  • page_id 不在 buffer pool 中，free_frame 也沒有空間，那我們就要使用 lru_k_replacer 來 evict 一個 frame，然後一樣更新 metadata

• FlushPage(page_id_t page_id) -> bool : 檢查 page_id 是否在 page_table 中，然後檢查 is_dirty ，可以使用 disk_scheduler 來把資料寫回 disk，不用特別使用 bpm 的大鎖

• FlushAllPages() : 遍歷 page_table 中的資料，然後使用 FlushPage 來寫回 disk

• GetPinCount(page_id_t page_id) : 一樣遍歷檢查即可

討論完基本功能之後我認為最重要的部分就是 concurrency 的問題，需要注意到在這個 Task 中我們有兩個鎖，一個是 bpm 的大鎖，另一個是 frame 的小鎖，我們需要確保這兩個鎖在使用上不會發生 deadlock。

我們可以從提供的 DeadlockTest 來尋找方向，這個測試如下 :

test/buffer/buffer_pool_manager_test.cpp

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);

  // A crude way of synchronizing threads, but works for this small case.
  std::atomic<bool> start = false;

  auto child = std::thread([&]() {
    // Acknowledge that we can begin the test.
    start.store(true);

    // Attempt to write to page 0.
    auto guard0 = bpm->WritePage(pid0);
  });

  // Wait for the other thread to begin before we start the test.
  while (!start.load()) {
  }

  // Make the other thread wait for a bit.
  // This mimics the main thread doing some work while holding the write latch on page 0.
  std::this_thread::sleep_for(std::chrono::milliseconds(1000));

  // If your latching mechanism is incorrect, the next line of code will deadlock.
  // Think about what might happen if you hold a certain "all-encompassing" latch for too long...

  // While holding page 0, take the latch on page 1.
  auto guard1 = bpm->WritePage(pid1);

  // Let the child thread have the page 0 since we're done with it.
  guard0.Drop();

  child.join();
}

先簡單敘述一下這個 Test 的邏輯，首先主執行緒會先取得 page 0 的獨佔鎖，接著啟動一個子執行緒也來讀取 page 0 的獨佔鎖，這時候主執行緒會先睡 1 秒鐘，然後再取得 page 1 的獨佔鎖，最後主執行緒再釋放 page 0 的獨佔鎖。

如果我們直接在 CheckedWritePage 中使用 std::scoped_lock 來鎖住 bpm 的大鎖，那麼這個測試就會死鎖，主要的流程如下 :

1. 主執行緒取得 bpm 的大鎖
2. 主執行緒取得 page 0 的獨佔鎖
3. 主執行緒放棄 bpm 的大鎖
4. 子執行緒取得 bpm 的大鎖
5. 子執行緒等待 page 0 的獨佔鎖
6. 主執行緒等待 bpm 的大鎖 (準備讀取 page 1)
7. 由於兩邊都在等待對方的鎖，所以就會死鎖

由上面的範例我們可以知道，我們必須要讓低級的鎖 (rwlatch) 取得的時候高級的鎖不會同時被鎖住，這樣才能避免死鎖的問題。

我在實作上採取的方法是在 CheckedWritePage 中使用 std::unique_lock 來取得 bpm 的大鎖，接著在創建 WritePageGuard 前解鎖，接著在 WritePageGuard 的 constructor 中取得 page 的小鎖，最後在 Drop() 的時候先釋放 page 的小鎖，再使用 bpm 的大鎖更新 page 的 metadata。

邏輯上大致如下 :

auto BufferPoolManager::CheckedWritePage() -> std::optional<WritePageGuard> {
  std::unique_lock latch(*bpm_latch_);

  // case 1: bpm have this page in memory
  if (case1) {
    // update metadata here
    latch.unlock();
    return std::make_optional(WritePageGuard());
  }

  // case 2: bpm does not have this page in memory but has free frames
  if (case2) {
    // update metadata here
    latch.unlock();
    return std::make_optional(WritePageGuard());
  }
  // anything else
  return std::nullopt;
}

WritePageGuard::WritePageGuard(){
  frame_->rwlatch_.lock();
  // update metadata here
}

void WritePageGuard::Drop() {
  frame_->rwlatch_.unlock();
  {
    std::scoped_lock lock(*bpm_latch_);
    // update metadata here
  }
}

其中我認為最重要的地方在於在更新如 pin_count 之類的 metadata 時，必須要在 bpm 的大鎖下進行，這樣才能確保不會有其他的執行緒同時修改這些資料。

cd build

make page_guard_test -j$(nproc)
./test/page_guard_test

make buffer_pool_manager_test -j$(nproc)
./test/buffer_pool_manager_test

Submit

make format
make check-format
make check-lint
make check-clang-tidy-p1

make submit-p1

Reference

• CMU 15445 Project 1
• CMU 15-445 2023 P1 优化攻略
• CMU 15445 2024 Fall Project 1 记录
• CMU Fall 2024 15-445 P1&P2[优化 P2]