前言

去年暑假完成了 CMU15-445 Fall 2019 的四個實驗，分別對應下述部落格：

今年打算接著完成 Fall 2020 的四個實驗，同時解讀一下課程組寫好的那一部分程式碼，比如資料儲存和頁面佈局的程式碼，加深自己對資料庫系統的理解。

環境搭建

在 GitHub 上新建一個私有倉庫，命名為 CMU15445-Fall2020，然後將官方倉庫克隆到本地：

git clone [email protected]:cmu-db/bustub.git ./cmu15445-fall2020
cd cmu15445-fall2020

目前官方的程式碼應該更新到 Fall2023 了，需要回滾到 Fall2020，並將程式碼傳到自己的遠端倉庫：

git reset --hard 444765a

git remote rm origin
git remote add origin [email protected]:zhiyiYo/cmu15445-fall2020.git #新增自己倉庫作為遠端分支
git push -u origin main

實驗環境為 Ubuntu20.04 虛擬機器器，所以執行下述程式碼安裝依賴包：

sudo build_support/packages.sh

和去年一樣，因為 googletest 倉庫將 master 分支重新命名為 main 了，所以需要將 build_support/gtest_CMakeLists.txt.in 的內容改為：

cmake_minimum_required(VERSION 3.8)

project(googletest-download NONE)

include(ExternalProject)
ExternalProject_Add(googletest
        GIT_REPOSITORY [email protected]:google/googletest.git
        GIT_TAG main
        SOURCE_DIR "${CMAKE_BINARY_DIR}/googletest-src"
        BINARY_DIR "${CMAKE_BINARY_DIR}/googletest-build"
        CONFIGURE_COMMAND ""
        BUILD_COMMAND ""
        INSTALL_COMMAND ""
        TEST_COMMAND ""
        )

最後編譯一下，如果編譯成功就說明環境搭建完成：

mkdir build
cd build
cmake ..
make

快取池

由於磁碟讀寫速度遠慢於記憶體，所以資料庫會在記憶體中開闢一塊連續空間，用於儲存最近存取的頁，這塊空間稱為快取池。執行引擎不會直接從磁碟讀取頁，而是向快取池要。如果快取池中沒有想要的頁，就會從磁碟讀入到池中，然後返回給執行引擎。頁內資料更新後也不會立即寫入磁碟，而是打上了一個 Dirty 標誌位並暫存在快取池中，等到時機成熟再寫入。

緩衝池的本質是一個陣列，只能存一定數量的頁。如果執行引擎想要的 Page 不在快取池中，且快取池已滿，這時候需要從中踢出一個頁來騰出空間給新 Page，被踢出的 Dirty 頁需要被儲存到磁碟中來保證資料一致性。需要指出的是，不是任何 Page 都能被換出，那些正在被使用的頁不能換出，而判斷一個頁是否正被使用的依據是 Page 內部儲存的 Pin/Reference 計數器，只要計數器的值大於 0，就說明至少有一個執行緒在使用它。

緩衝池內部維護著一個 page_id 到 frame_id 的對映表，用來指出頁和內部陣列索引的對映關係。同時內部還有一個互斥鎖來保證並行安全，對快取池的增刪改查都需要上鎖。

實驗要求

任務 1：LRU Replacement Policy

Fall2019 要求實現的是時鐘替換演演算法，而 Fall2020 則改成了 LRU 替換演演算法，實現方式一般使用雙向連結串列 + 雜湊表，C艹可以直接用標準庫中的 std::list 和 std::unordered_map。雙向連結串列中存放允許被換出的 frame_id，雜湊表中存 frame_id 及其對應的雙向連結串列迭代器，這樣可以實現 \(O(1)\) 複雜度的讀寫。連結串列的表頭處存放最近存取的 frame_id，而尾處則是距離上次存取時間最遠的的 frame_id。

class LRUReplacer : public Replacer {
 public:
  /**
   * Create a new LRUReplacer.
   * @param num_pages the maximum number of pages the LRUReplacer will be required to store
   */
  explicit LRUReplacer(size_t num_pages);

  ~LRUReplacer() override;

  /**
   * Remove the victim frame as defined by the replacement policy.
   * @param[out] frame_id id of frame that was removed, nullptr if no victim was found
   * @return true if a victim frame was found, false otherwise
   */
  bool Victim(frame_id_t *frame_id) override;

  /**
   * Pins a frame, indicating that it should not be victimized until it is unpinned.
   * @param frame_id the id of the frame to pin
   */
  void Pin(frame_id_t frame_id) override;

  /**
   * Unpins a frame, indicating that it can now be victimized.
   * @param frame_id the id of the frame to unpin
   */
  void Unpin(frame_id_t frame_id) override;

  /** @return the number of elements in the replacer that can be victimized */
  size_t Size() override;

 private:
  size_t num_pages_;
  std::list<frame_id_t> list_;
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> map_;
  std::shared_mutex mutex_;
};

具體實現如下所示，可以看到 LRUReplacer 對緩衝池中存了多少頁以及存了哪些頁是一無所知的，它只關心能被換出的 frame_id，外界通過呼叫 LURReplacer::Unpin() 新增一個能被換出的 frame_id，呼叫 LRUReplacer::Pin() 來移除一個 frame_id：

LRUReplacer::LRUReplacer(size_t num_pages) : num_pages_(num_pages) {}

LRUReplacer::~LRUReplacer() = default;

bool LRUReplacer::Victim(frame_id_t *frame_id) {
  lock_guard<shared_mutex> lock(mutex_);

  if (Size() == 0) {
    return false;
  }

  *frame_id = list_.back();
  list_.pop_back();
  map_.erase(*frame_id);

  return true;
}

void LRUReplacer::Pin(frame_id_t frame_id) {
  lock_guard<shared_mutex> lock(mutex_);

  // frame 需要在緩衝池中
  if (!map_.count(frame_id)) {
    return;
  }

  auto it = map_[frame_id];
  map_.erase(frame_id);
  list_.erase(it);
}

void LRUReplacer::Unpin(frame_id_t frame_id) {
  lock_guard<shared_mutex> lock(mutex_);

  // 緩衝池滿了不能插入新的 page，不能重複插入 page
  if (Size() == num_pages_ || map_.count(frame_id)) {
    return;
  }

  list_.push_front(frame_id);
  map_[frame_id] = list_.begin();
}

size_t LRUReplacer::Size() {
  return list_.size();
}

在終端輸入命令：

mkdir build
cd build
cmake ..
make lru_replacer_test
./test/lru_replacer_test

測試結果如下：

任務2：Buffer Pool Manager

BufferPoolManager 用於管理緩衝池，內部有一個 DiskManager 來讀寫磁碟資料，LRUReplacer 執行替換演演算法。這個類要求我們實現五個函數：

FetchPageImpl(page_id)
NewPageImpl(page_id)
UnpinPageImpl(page_id, is_dirty)
FlushPageImpl(page_id)
DeletePageImpl(page_id)
FlushAllPagesImpl()

下面會一個個實現上述函數。

FetchPageImpl(page_id)

該函數實現了緩衝池的主要功能：向上層提供指定的 page。緩衝池管理器首先在 page_table_ 中查詢 page_id 鍵是否存在：

如果存在就根據 page_id 對應的 frame_id 從緩衝池 pages_ 取出 page
如果不存在就通過 GetVictimFrameId() 函數選擇被換出的幀，該函數首先從 free_list_ 中查詢緩衝池的空位，如果沒找到空位就得靠上一節實現的 LRUReplacer 選出被換出的冤大頭

具體程式碼如下：


Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
  lock_guard<mutex> lock(latch_);

  // 1.     Search the page table for the requested page (P).
  Page *page;
  auto it = page_table_.find(page_id);

  // 1.1    If P exists, pin it and return it immediately.
  if (it != page_table_.end()) {
    auto frame_id = it->second;
    page = &pages_[frame_id];
    replacer_->Pin(frame_id);
    page->pin_count_++;
    return page;
  }

  // 1.2    If P does not exist, find a replacement page (R) from either the free list or the replacer.
  //        Note that pages are always found from the free list first.
  auto frame_id = GetVictimFrameId();
  if (frame_id == INVALID_PAGE_ID) {
    return nullptr;
  }

  // 2.     If R is dirty, write it back to the disk.
  page = &pages_[frame_id];
  if (page->IsDirty()) {
    disk_manager_->WritePage(page->page_id_, page->data_);
  }

  // 3.     Delete R from the page table and insert P.
  page_table_.erase(page->page_id_);
  page_table_[page_id] = frame_id;

  // 4.     Update P's metadata, read in the page content from disk, and then return a pointer to P.
  disk_manager_->ReadPage(page_id, page->data_);
  page->update(page_id, 1, false);
  replacer_->Pin(frame_id);

  return page;
}

frame_id_t BufferPoolManager::GetVictimFrameId() {
  frame_id_t frame_id = INVALID_PAGE_ID;

  if (!free_list_.empty()) {
    frame_id = free_list_.front();
    free_list_.pop_front();
  } else {
    replacer_->Victim(&frame_id);
  }

  return frame_id;
}

上述程式碼中還用了一個 Page::update 輔助函數，用於更新 page 的後設資料：

/**
* update the meta data of page
* @param page_id the page id
* @param pin_count the pin count
* @param is_dirty is page dirty
* @param reset_memory whether to reset the memory of page
*/
void update(page_id_t page_id, int pin_count, bool is_dirty, bool reset_memory = false) {
  page_id_ = page_id;
  pin_count_ = pin_count;
  is_dirty_ = is_dirty;
  if (reset_memory) {
    ResetMemory();
  }
}

NewPageImpl(page_id)

該函數在緩衝池中插入一個新頁，如果緩衝池中的所有頁面都正在被執行緒存取，插入失敗，否則靠 GetVictimFrameId() 計算插入位置：


Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
  // 0.   Make sure you call DiskManager::AllocatePage!
  lock_guard<mutex> lock(latch_);

  // 1.   If all the pages in the buffer pool are pinned, return nullptr.
  auto frame_id = GetVictimFrameId();
  if (frame_id == INVALID_PAGE_ID) {
    return nullptr;
  }

  // 2.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
  auto page = &pages_[frame_id];
  if (page->IsDirty()) {
    disk_manager_->WritePage(page->page_id_, page->data_);
  }

  // 3.   Update P's metadata, zero out memory and add P to the page table.
  *page_id = disk_manager_->AllocatePage();
  page_table_.erase(page->page_id_);
  page_table_[*page_id] = frame_id;
  page->update(*page_id, 1, false, true);
  replacer_->Pin(frame_id);

  // 4.   Set the page ID output parameter. Return a pointer to P.
  return page;
}

DeletePageImpl(page_id)

該函數從緩衝池和資料庫檔案中刪除一個 page，並將其 page_id 設定為 INVALID_PAGE_ID：

bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
  // 0.   Make sure you call DiskManager::DeallocatePage!
  lock_guard<mutex> lock(latch_);

  // 1.   Search the page table for the requested page (P).
  // 1.   If P does not exist, return true.
  auto it = page_table_.find(page_id);
  if (it == page_table_.end()) {
    return true;
  }

  // 2.   If P exists, but has a non-zero pin-count, return false. Someone is using the page.
  auto frame_id = it->second;
  auto &page = pages_[frame_id];
  if (page.pin_count_ > 0) {
    return false;
  }

  // 3.   Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
  disk_manager_->DeallocatePage(page_id);
  page_table_.erase(page.page_id_);
  free_list_.push_back(frame_id);
  page.update(INVALID_PAGE_ID, 0, false);

  return true;
}

UnpinPageImpl(page_id, is_dirty)

該函數用以減少對某個頁的參照數 pin count，當 pin_count 為 0 時需要將其新增到 LRUReplacer 中：


bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
  lock_guard<mutex> lock(latch_);

  auto it = page_table_.find(page_id);
  if (it == page_table_.end()) {
    return false;
  }

  auto frame_id = it->second;
  auto &page = pages_[frame_id];
  if (page.pin_count_ <= 0) {
    return false;
  }

  page.is_dirty_ |= is_dirty;
  if (--page.pin_count_ == 0) {
    replacer_->Unpin(frame_id);
  }
  return true;
}

FlushPageImpl(page_id)

該函數將緩衝池中的頁寫入磁碟以保持同步，這裡不管頁是否為髒，一律寫入磁碟，不然並行的測試用例過不了：

bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
  // Make sure you call DiskManager::WritePage!
  lock_guard<mutex> lock(latch_);

  auto it = page_table_.find(page_id);
  if (it == page_table_.end()) {
    return false;
  }

  auto &page = pages_[it->second];
  disk_manager_->WritePage(page_id, page.data_);
  page.is_dirty_ = false;
  return true;
}

FlushAllPagesImpl()

該函數將緩衝池中的所有 page 寫入磁碟：

void BufferPoolManager::FlushAllPagesImpl() {
  lock_guard<mutex> lock(latch_);

  for (auto &[page_id, frame_id] : page_table_) {
    auto &page = pages_[frame_id];
    if (page.IsDirty()) {
      disk_manager_->WritePage(page_id, page.data_);
      page.is_dirty_ = false;
    }
  }
}

測試

在終端輸入指令：

cd build

make buffer_pool_manager_test
./test/buffer_pool_manager_test

# 下面是從 gradescope 扒下來的測試用例
make buffer_pool_manager_concurrency_test
./test/buffer_pool_manager_concurrency_test