CMU15445 數據庫系統實驗一：Buffer Pool Manager
本文轉載自微信公眾號「分布式點滴」，作者穆尼奧。轉載本文請聯系分布式點滴公眾號。
本篇是實驗一，管理文件系統的頁在內存中的緩存 —— buffer pool manager。
概覽
實驗的目標系統 BusTub 是一個面向磁盤的 DBMS，但磁盤上的數據不支持字節粒度的訪問。這就需要一個管理頁的中間層，但 Andy Pavlo 教授堅持不使用 mmap 將頁管理權力讓渡給操作系統，因此實驗一 的目標便在于主動管理磁盤中的頁(page)在內存中的緩存，從而，最小化磁盤訪問次數(時間上)、最大化相關數據連續(空間上)。
該實驗可以分解為相對獨立的兩個子任務：
- 維護替換策略的：LRU replacement policy
- 管理緩沖池的：buffer pool manager
兩個組件都要求線程安全。
本文首先從基本概念、核心數據流總體分析下實驗內容，然后分別對兩個子任務進行梳理。
作者：青藤木鳥 https://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，其區別如下：
page id 是這一段單位數據的全局標識，而 frame id 只是在內存池(frame 數組)中索引某個 page 下標
page 在文件系統中是一段邏輯連續的字節數組;在內存中，我們會給其附加一些元信息：pin_count_，is_dirty_
基本概念
而管理幀的內存池大小一般來說是遠小于磁盤的，因此在內存池滿了后，再從磁盤加載新的頁到內存池，需要 某種替換策略(replacer)將一些不再使用的頁踢出內存池以騰出空間。
核心數據流
先說結論，buffer pool manager 的實現核心，在于對內存池中所有 frame 的狀態的管理。因此，如果我們能梳理出 frame 的狀態機，便可以把握好核心數據流。
buffer pool 維護了一個 frame 數組，每個 frame 有三種狀態：
- free：初始狀態，沒有存放任何 page
- pinned：存放了 thread 正在使用的 page
- unpinned：存放了 page，但 page 已經不再為任何 thread 所使用
而待實現函數：
- FetchPageImpl(page_id)
- NewPageImpl(page_id)
- UnpinPageImpl(page_id, is_dirty)
- DeletePageImpl(page_id)
便是驅動狀態機中上述狀態發生改變的動作(action)，狀態機如下：
frame 狀態機
對應到實現時數據結構上：
- 保存 page 數據的 frame 數組為 pages_
- 所有 free frame 的索引(frame_id)保存在 free_list_ 中
- 所有 unpinned frame 的索引保存在 replacer_ 中
- 所有 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 為例強調下一些實現的細節，注意到，實驗已經通過注釋給出了實現框架。
我使用中文注釋注出了一些我認為需要注意的點。
- Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
- // a. 使用自動獲取和釋放鎖
- std::scoped_lock<std::mutex> 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<int>(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<int>(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 包提交即可。
提交事項
仔細閱讀實驗描述，提交前需要注意的事項：
- 在 build 目錄運行 make format ，自動格式化。
- 在 build 目錄運行 make check-lint，檢查一些語法問題。
- 自己針對每個函數在本地設計一些測試，寫到相關文件(本實驗 buffer_pool_manager_test.cpp )中，并且打開測試開關，在 build 文件夾下，編譯 make buffer_pool_manager_test，運行 ./test/buffer_pool_manager_test
貼一個 project1 autograder 的實驗結果：
autograder 結果
小結
這是 cmu15445 第一個實驗，實現了在磁盤和內存間按需搬運頁(page)的 buffer pool manager。本實驗的關鍵之處在于把握基本概念，梳理出核心數據流，在此基礎上注意一些實現的細節即可。
