CMU15445 數(shù)據(jù)庫系統(tǒng)實驗一：Buffer Pool Manager
本文轉(zhuǎn)載自微信公眾號「分布式點滴」，作者穆尼奧。轉(zhuǎn)載本文請聯(lián)系分布式點滴公眾號。
本篇是實驗一，管理文件系統(tǒng)的頁在內(nèi)存中的緩存 —— buffer pool manager。
概覽
實驗的目標(biāo)系統(tǒng) BusTub 是一個面向磁盤的 DBMS，但磁盤上的數(shù)據(jù)不支持字節(jié)粒度的訪問。這就需要一個管理頁的中間層，但 Andy Pavlo 教授堅持不使用 mmap 將頁管理權(quán)力讓渡給操作系統(tǒng)，因此實驗一 的目標(biāo)便在于主動管理磁盤中的頁(page)在內(nèi)存中的緩存，從而，最小化磁盤訪問次數(shù)(時間上)、最大化相關(guān)數(shù)據(jù)連續(xù)(空間上)。
該實驗可以分解為相對獨立的兩個子任務(wù)：
- 維護替換策略的：LRU replacement policy
- 管理緩沖池的：buffer pool manager
兩個組件都要求線程安全。
本文首先從基本概念、核心數(shù)據(jù)流總體分析下實驗內(nèi)容，然后分別對兩個子任務(wù)進行梳理。
作者：青藤木鳥 https://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/, 轉(zhuǎn)載請注明出處
實驗分析
剛開始寫實驗代碼的時候，感覺細節(jié)很多，實現(xiàn)時很容易丟三落四。但隨著實現(xiàn)和思考的深入，漸漸摸清了全貌，發(fā)現(xiàn)只要明確幾個基本概念和核心數(shù)據(jù)流，便能夠提綱挈領(lǐng)。
基本概念
buffer pool 的操作的基本單位為一段邏輯連續(xù)的字節(jié)數(shù)組，在磁盤上表現(xiàn)為頁(page)，有唯一的標(biāo)識 page_id;在內(nèi)存中表現(xiàn)為幀(frame)，有唯一的標(biāo)識 frame_id。為了記下哪些 frame 存的哪些 page，需要使用一個頁表(page table)。
下邊行文可能會混用 page 和 frame，因為這兩個概念都是 buffer pool 管理數(shù)據(jù)的基本單位，一般為 4k，其區(qū)別如下：
page id 是這一段單位數(shù)據(jù)的全局標(biāo)識，而 frame id 只是在內(nèi)存池(frame 數(shù)組)中索引某個 page 下標(biāo)
page 在文件系統(tǒng)中是一段邏輯連續(xù)的字節(jié)數(shù)組;在內(nèi)存中，我們會給其附加一些元信息：pin_count_，is_dirty_
基本概念
而管理幀的內(nèi)存池大小一般來說是遠小于磁盤的，因此在內(nèi)存池滿了后，再從磁盤加載新的頁到內(nèi)存池，需要 某種替換策略(replacer)將一些不再使用的頁踢出內(nèi)存池以騰出空間。
核心數(shù)據(jù)流
先說結(jié)論，buffer pool manager 的實現(xiàn)核心，在于對內(nèi)存池中所有 frame 的狀態(tài)的管理。因此，如果我們能梳理出 frame 的狀態(tài)機，便可以把握好核心數(shù)據(jù)流。
buffer pool 維護了一個 frame 數(shù)組，每個 frame 有三種狀態(tài)：
- free：初始狀態(tài)，沒有存放任何 page
- pinned：存放了 thread 正在使用的 page
- unpinned：存放了 page，但 page 已經(jīng)不再為任何 thread 所使用
而待實現(xiàn)函數(shù)：
- FetchPageImpl(page_id)
- NewPageImpl(page_id)
- UnpinPageImpl(page_id, is_dirty)
- DeletePageImpl(page_id)
便是驅(qū)動狀態(tài)機中上述狀態(tài)發(fā)生改變的動作(action)，狀態(tài)機如下：
frame 狀態(tài)機
對應(yīng)到實現(xiàn)時數(shù)據(jù)結(jié)構(gòu)上：
- 保存 page 數(shù)據(jù)的 frame 數(shù)組為 pages_
- 所有 free frame 的索引(frame_id)保存在 free_list_ 中
- 所有 unpinned frame 的索引保存在 replacer_ 中
- 所有 pinned frame 索引和 unpinned frame 的索引保存在 page_table_ 中，并通過 page 中 pin_count_ 字段來區(qū)分兩個狀態(tài)。
上圖中，NewPage1 和 NewPage2 表示在 NewPage 函數(shù)中，每次獲取空閑 frame 時，會先去空閑列表(freelist_)中取一個 free frame，如果取不到，才會去 replacer_ 中驅(qū)逐一個 unpinned 的 frame 后使用。這體現(xiàn)了 buffer pool manager 實現(xiàn)的一個目標(biāo)：最小化磁盤訪問，原因后面分析。
實驗組件
把握了本實驗的基本概念和核心數(shù)據(jù)流后，再來分析兩個子任務(wù)。
TASK #1 - LRU REPLACEMENT POLICY
以前在 LeetCode 上寫過相關(guān)實現(xiàn)，因此很自然的帶入之前經(jīng)驗，但隨后發(fā)現(xiàn)這兩個接口有一些不同。
LeetCode 上提供的是 kv store 接口，在 get/set 的時候完成新老順序的維護，并在內(nèi)存池滿后自動替換最老的 KV。
但本實驗提供的是 replacer 接口，維護一個 unpinned 的 frame_id 列表 ，在調(diào)用 Unpin 時將 frame_id 加入列表并維護新老順序、在調(diào)用 Pin 時將 frame_id 從列表中摘除、在調(diào)用Victim 的時候?qū)⒆罾系?frame_id 返回。
當(dāng)然，本質(zhì)上還是一樣，因此本實驗我也是采用 unordered_map 和 doubly linked list 的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)細節(jié)不再贅述。需要注意的是，如果 Unpin 時發(fā)現(xiàn) frame_id 已經(jīng)在 replacer 中，則直接返回，并不改變列表的新老順序。因為邏輯上來說，同一個 frame_id，并不能被 Unpin多次，因此我們只需要考慮 frame_id 第一次 Unpin。
放到更大的語境中，本質(zhì)上，replacer 就是一個維護了回收順序的回收站，即我們將所有 pin_count_ = 0 的 page 不直接從內(nèi)存中刪除，而是放入回收站中。根據(jù)數(shù)據(jù)訪問的時間局部性原理，剛剛被訪問的 page 很可能再次被訪問，因此當(dāng)我們不得不從回收站中真刪(Victim)一個 frame 時，需要刪最老的 frame。當(dāng)之后我們想訪問一個剛加入回收站的數(shù)據(jù)時， 只需要將 page 從這個回收站中撈出來，從而省去一次磁盤訪問，這也就達到了最小化磁盤訪問的目標(biāo)。
TASK #2 - BUFFER POOL MANAGER
在實驗分析部分已經(jīng)把核心邏輯說的差不多了，這里簡單羅列一下我實現(xiàn)中遇到的問題。
page_table_ 的范圍。在最初實現(xiàn)時，畫出 frame 的狀態(tài)機之后，感覺 page_table_ 中只放 pinned frame id 很完美：可以使 frame id 按狀態(tài)互斥的分布在 free_list_ 、 replacer_ 和 page_table_ 中。但后來發(fā)現(xiàn)，如果不將 unpinned frame id 保存在 page_table_ 中，就不能很好地復(fù)用 pin_count_ = 0 的 page 了，replacer 也就沒有了意義。
dirty page 的刷盤時機。有兩種策略，一種是每次 Unpin 的時候都刷，這樣會刷比較頻繁，但能保證異常掉電重啟后內(nèi)容不丟;一種是在 replacer victimized 的時候 lazily 的刷，這樣能保證刷的次數(shù)最少。這是性能和可靠性取舍，僅考慮本實驗，兩者肯定都能過。
NewPage 不要讀盤。這個就是我寫的 bug 了，畢竟 NewPage 的時候，磁盤上根本沒有對應(yīng) page 的內(nèi)容，因此會報如下錯誤：
- 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
復(fù)用 frame 時清空元信息。在復(fù)用一個從 replacer 中驅(qū)逐的 frame 時尤其要注意，使用前一定要將 pin_count_\is_dirty_ 這些字段清空。當(dāng)然，在 DeletePage 的時候，也需要注意將 page_id_ 置為 INVALID_PAGE_ID 、清空上述字段。否則，再次使用時， 如果 pin_count_ 在 Unpin 后，數(shù)值不為 0，會導(dǎo)致 DeletePage 時刪不掉該 page。
鎖的粒度。最粗暴的就是每個函數(shù)范圍粒度加鎖即可，后期如果需要優(yōu)化，再將鎖的粒度變細。
實驗代碼
以 FetchPageImpl 為例強調(diào)下一些實現(xiàn)的細節(jié)，注意到，實驗已經(jīng)通過注釋給出了實現(xiàn)框架。
我使用中文注釋注出了一些我認(rèn)為需要注意的點。
- 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. 判斷存在與訪問數(shù)據(jù)只用一次查找
- if (target != page_table_.end()) {
- frame_id_t frame_id = target->second;
- // c. 通過指針運算獲取 frame_id 處存放的 Page 結(jié)構(gòu)體
- Page *p = pages_ + frame_id;
- p->pin_count_++;
- replacer_->Pin(frame_id); // d. 將對應(yīng) 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. 在結(jié)尾處操作效率高一點
- free_list_.pop_back();
- assert(frame_id >= 0 && frame_id < static_cast<int>(pool_size_));
- p = pages_ + frame_id;
- // f. 從 freelist 中獲取的 dirty page 已經(jīng)在 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. 時刻注意區(qū)分 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;
- }
實驗相關(guān) autograder 可以在 FAQ 中找到注冊地址和邀請碼，提交代碼的時候最好不要提交 github 倉庫地址，會有很多格式問題。可以每次按照實驗頁面的指示，將相關(guān)文件按目錄結(jié)構(gòu)達成 zip 包提交即可。
提交事項
仔細閱讀實驗描述，提交前需要注意的事項：
- 在 build 目錄運行 make format ，自動格式化。
- 在 build 目錄運行 make check-lint，檢查一些語法問題。
- 自己針對每個函數(shù)在本地設(shè)計一些測試，寫到相關(guān)文件(本實驗 buffer_pool_manager_test.cpp )中，并且打開測試開關(guān)，在 build 文件夾下，編譯 make buffer_pool_manager_test，運行 ./test/buffer_pool_manager_test
貼一個 project1 autograder 的實驗結(jié)果：
autograder 結(jié)果
小結(jié)
這是 cmu15445 第一個實驗，實現(xiàn)了在磁盤和內(nèi)存間按需搬運頁(page)的 buffer pool manager。本實驗的關(guān)鍵之處在于把握基本概念，梳理出核心數(shù)據(jù)流，在此基礎(chǔ)上注意一些實現(xiàn)的細節(jié)即可。
