cmu15445 資料庫系統實驗一：buffer pool manager

語言: CN / TW / HK
時間 2022-10-13 04:15:16

「這是我參與2022首次更文挑戰的第 16 天，活動詳情檢視：2022首次更文挑戰」。

cmu15445 是一門關於資料庫管理系統（DBMS）設計與實現的經典公開課。該課程以 Database System Concepts 為教材，提供隨堂講義、筆記和影片，精心準備了幾個互相勾連的小實驗。該課程十分注重系統設計和程式設計實現，用主講教授 Andy Pavlo 的話說，這是一門可以寫在簡歷上、並且能幫你拿到好 offer 的課程。

這個假期得空，翻出這門課程，即被其翔實的內容、精當的組織所折服。無奈時間有限，只能以實驗為主線，輔以講義和筆記，簡單跟一跟。如果再有時間，就去掃下教材和影片。從實驗一開始，每個實驗 autograder 跑過之後，出一篇筆記，聊以備忘。 Andy Pavlo 教授建議不要公開實驗程式碼倉庫，因此文章儘量少貼程式碼，多寫思路。

本篇是實驗一，管理檔案系統的頁在記憶體中的快取 —— buffer pool manager。

概覽

實驗的目標系統 BusTub 是一個面向磁碟的 DBMS，但磁碟上的資料不支援位元組粒度的訪問。這就需要一個管理頁的中間層，但 Andy Pavlo 教授堅持不使用 mmap 將頁管理權力讓渡給作業系統，因此實驗一 的目標便在於主動管理磁碟中的頁（page）在記憶體中的快取，從而，最小化磁碟訪問次數（時間上）、最大化相關資料連續（空間上）。

該實驗可以分解為相對獨立的兩個子任務：

  1. 維護替換策略的： LRU replacement policy
  2. 管理緩衝池的： buffer pool manager

兩個元件都要求執行緒安全。

本文首先從基本概念、核心資料流總體分析下實驗內容，然後分別對兩個子任務進行梳理。

作者：木鳥雜記 http://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/

實驗分析

剛開始寫實驗程式碼的時候，感覺細節很多，實現時很容易丟三落四。但隨著實現和思考的深入，漸漸摸清了全貌，發現只要明確幾個基本概念和核心資料流，便能夠提綱挈領。

基本概念

buffer pool 的操作的基本單位為一段邏輯連續的位元組陣列，在磁碟上表現為頁（page），有唯一的標識 page_id；在記憶體中表現為幀（frame），有唯一的標識 frame_id。為了記下哪些 frame 存的哪些 page，需要使用一個頁表（page table）。

下邊行文可能會混用 page 和 frame，因為這兩個概念都是 buffer pool 管理資料的基本單位，一般為 4k，其區別如下：

  1. page id 是這一段單位資料的全域性標識，而 frame id 只是在記憶體池（frame 陣列）中索引某個 page 下標
  2. page 在檔案系統中是一段邏輯連續的位元組陣列；在記憶體中，我們會給其附加一些元資訊：pin_count_，is_dirty_

基本概念

而管理幀的記憶體池大小一般來說是遠小於磁碟的，因此在記憶體池滿了後，再從磁碟載入新的頁到記憶體池，需要某種替換策略（replacer）將一些不再使用的頁踢出記憶體池以騰出空間。

核心資料流

先說結論，buffer pool manager 的實現核心，在於對記憶體池中所有 frame 的狀態的管理。因此，如果我們能梳理出 frame 的狀態機，便可以把握好核心資料流。

buffer pool 維護了一個 frame 陣列，每個 frame 有三種狀態：

  1. free：初始狀態，沒有存放任何 page
  2. pinned：存放了 thread 正在使用的 page
  3. unpinned：存放了 page，但 page 已經不再為任何 thread 所使用

而待實現函式：

c++ FetchPageImpl(page_id) NewPageImpl(page_id) UnpinPageImpl(page_id, is_dirty) DeletePageImpl(page_id)

便是驅動狀態機中上述狀態發生改變的動作（action），狀態機如下：

frame 狀態機

對應到實現時資料結構上：

  1. 儲存 page 資料的 frame 陣列為 pages_
  2. 所有 free frame 的索引（frame_id）儲存在 free_list_ 中
  3. 所有 unpinned frame 的索引儲存在 replacer_ 中
  4. 所有 pinned frame 索引和 unpinned frame 的索引儲存在 page_table_ 中，並通過 page 中 pin_count_ 欄位來區分兩個狀態。

上圖中，NewPage1 和 NewPage2 表示在 NewPage 函式中，每次獲取空閒 frame 時，會先去空閒列表（freelist_）中取一個 free frame，如果取不到，才會去 replacer_ 中驅逐一個 unpinned 的 frame 後使用。這體現了 buffer pool manager 實現的一個目標：最小化磁碟訪問，原因後面分析。

實驗元件

把握了本實驗的基本概念和核心資料流後，再來分析兩個子任務。

TASK #1 - LRU REPLACEMENT POLICY

以前在 LeetCode 上寫過相關實現，因此很自然的帶入之前經驗，但隨後發現這兩個介面有一些不同。

LeetCode 上提供的是 kv store 介面，在 get/set 的時候完成新老順序的維護，並在記憶體池滿後自動替換最老的 KV。

但本實驗提供的是 replacer 介面，維護一個 unpinned 的 frame_id 列表 ，在呼叫 Unpin 時將 frame_id 加入列表並維護新老順序、在呼叫 Pin 時將 frame_id 從列表中摘除、在呼叫 Victim 的時候將最老的 frame_id 返回。

當然，本質上還是一樣，因此本實驗我也是採用 unordered_map 和 doubly linked list 的資料結構，實現細節不再贅述。需要注意的是，如果 Unpin 時發現 frame_id 已經在 replacer 中，則直接返回，並不改變列表的新老順序。因為邏輯上來說，同一個 frame_id，並不能被 Unpin 多次，因此我們只需要考慮 frame_id 第一次 Unpin。

放到更大的語境中，本質上，replacer 就是一個維護了回收順序的回收站，即我們將所有 pin_count_ = 0 的 page 不直接從記憶體中刪除，而是放入回收站中。根據資料訪問的時間區域性性原理，剛剛被訪問的 page 很可能再次被訪問，因此當我們不得不從回收站中真刪（Victim）一個 frame 時，需要刪最老的 frame。當之後我們想訪問一個剛加入回收站的資料時， 只需要將 page 從這個回收站中撈出來，從而省去一次磁碟訪問，這也就達到了最小化磁碟訪問的目標。

TASK #2 - BUFFER POOL MANAGER

在實驗分析部分已經把核心邏輯說的差不多了，這裡簡單羅列一下我實現中遇到的問題。

page_table_ 的範圍。在最初實現時，畫出 frame 的狀態機之後，感覺 page_table_ 中只放 pinned frame id 很完美：可以使 frame id 按狀態互斥的分佈在 free_list_ 、 replacer_ 和 page_table_ 中。但後來發現，如果不將 unpinned frame id 儲存在 page_table_ 中，就不能很好地複用 pin_count_ = 0 的 page 了，replacer 也就沒有了意義。

dirty page 的刷盤時機。有兩種策略，一種是每次 Unpin 的時候都刷，這樣會刷比較頻繁，但能保證異常掉電重啟後內容不丟；一種是在 replacer victimized 的時候 lazily 的刷，這樣能保證刷的次數最少。這是效能和可靠性取捨，僅考慮本實驗，兩者肯定都能過。

NewPage 不要讀盤。這個就是我寫的 bug 了，畢竟 NewPage 的時候，磁碟上根本沒有對應 page 的內容，因此會報如下錯誤：

2021-02-18 16:53:47 [autograder/bustub/src/storage/disk/disk_manager.cpp:121:ReadPage] DEBUG - Read less than a page 2021-02-18 16:53:47 [autograder/bustub/src/storage/disk/disk_manager.cpp:108:ReadPage] DEBUG - I/O error reading past end of file

複用 frame 時清空元資訊。在複用一個從 replacer 中驅逐的 frame 時尤其要注意，使用前一定要將 pin_count_\is_dirty_ 這些欄位清空。當然，在 DeletePage 的時候，也需要注意將 page_id_ 置為 INVALID_PAGE_ID 、清空上述欄位。否則，再次使用時， 如果 pin_count_ 在 Unpin 後，數值不為 0，會導致 DeletePage 時刪不掉該 page。

鎖的粒度。最粗暴的就是每個函式範圍粒度加鎖即可，後期如果需要優化，再將鎖的粒度變細。

實驗程式碼

以 FetchPageImpl 為例強調下一些實現的細節，注意到，實驗已經通過註釋給出了實現框架。

我使用中文註釋注出了一些我認為需要注意的點。

```c++ Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) { // a. 使用自動獲取和釋放鎖 std::scoped_lock lock(latch_);

// 1. Search the page table for the requested page (P). // 1.1 If P exists, pin it and return it immediately. auto target = page_table_.find(page_id); // b. 判斷存在與訪問資料只用一次查詢 if (target != page_table_.end()) { frame_id_t frame_id = target->second; // c. 通過指標運算獲取 frame_id 處存放的 Page 結構體 Page *p = pages_ + frame_id; p->pin_count_++; replacer_->Pin(frame_id); // d. 將對應 page 從“回收站”中撈出 return p; }

// 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. frame_id_t frame_id = -1; Page *p = nullptr; if (!free_list_.empty()) { frame_id = free_list_.back(); // e. 在結尾處操作效率高一點 free_list_.pop_back(); assert(frame_id >= 0 && frame_id < static_cast(pool_size_)); p = pages_ + frame_id;

// f. 從 freelist 中獲取的 dirty page 已經在 delete 時寫回了

} else { bool victimized = replacer_->Victim(&frame_id); if (!victimized) { return nullptr; } assert(frame_id >= 0 && frame_id < static_cast(pool_size_)); p = pages_ + frame_id;

// 2.     If R is dirty, write it back to the disk.
if (p->IsDirty()) {
  disk_manager_->WritePage(p->GetPageId(), p->GetData());
  p->is_dirty_ = false;
}
p->pin_count_ = 0; // g. 將元資訊 pin_count_ 清空

}

// 3. Delete R from the page table and insert P. page_table_.erase(p->GetPageId()); // h. 時刻注意區分 p->GetPageId() 與 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. p->page_id_ = page_id; p->ResetMemory(); disk_manager_->ReadPage(page_id, p->GetData()); p->pin_count_++; return p; } ```

實驗相關 autograder 可以在 FAQ 中找到註冊地址和邀請碼，提交程式碼的時候最好不要提交 github 倉庫地址，會有很多格式問題。可以每次按照實驗頁面的指示，將相關檔案按目錄結構達成 zip 包提交即可。

提交事項

仔細閱讀實驗描述，提交前需要注意的事項：

  1. 在 build 目錄執行 make format ，自動格式化。
  2. 在 build 目錄執行 make check-lint，檢查一些語法問題。
  3. 自己針對每個函式在本地設計一些測試，寫到相關檔案（本實驗 buffer_pool_manager_test.cpp ）中，並且開啟測試開關，在 build 資料夾下，編譯 make buffer_pool_manager_test，執行 ./test/buffer_pool_manager_test

貼一個 project1 autograder 的實驗結果：

autograder-result

小結

這是 cmu15445 第一個實驗，實現了在磁碟和記憶體間按需搬運頁（page）的 buffer pool manager。本實驗的關鍵之處在於把握基本概念，梳理出核心資料流，在此基礎上注意一些實現的細節即可。

我是青藤木鳥，一個喜歡攝影的儲存工程師，歡迎關注我的公眾號：“木鳥雜記”。

「」
「」