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

語言: CN / TW / HK

「這是我參與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。本實驗的關鍵之處在於把握基本概念,梳理出核心資料流,在此基礎上注意一些實現的細節即可。


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