[[382283]]

本文轉(zhuǎn)載自微信公眾號「分布式點(diǎn)滴」，作者穆尼奧。轉(zhuǎn)載本文請聯(lián)系分布式點(diǎn)滴公眾號。  

本篇是實(shí)驗(yàn)一，管理文件系統(tǒng)的頁在內(nèi)存中的緩存 —— buffer pool manager。

概覽

實(shí)驗(yàn)的目標(biāo)系統(tǒng) BusTub 是一個(gè)面向磁盤的 DBMS，但磁盤上的數(shù)據(jù)不支持字節(jié)粒度的訪問。這就需要一個(gè)管理頁的中間層，但 Andy Pavlo 教授堅(jiān)持不使用 mmap 將頁管理權(quán)力讓渡給操作系統(tǒng)，因此實(shí)驗(yàn)一 的目標(biāo)便在于主動管理磁盤中的頁(page)在內(nèi)存中的緩存，從而，最小化磁盤訪問次數(shù)(時(shí)間上)、最大化相關(guān)數(shù)據(jù)連續(xù)(空間上)。

該實(shí)驗(yàn)可以分解為相對獨(dú)立的兩個(gè)子任務(wù)：

• 維護(hù)替換策略的：LRU replacement policy
• 管理緩沖池的：buffer pool manager

兩個(gè)組件都要求線程安全。

本文首先從基本概念、核心數(shù)據(jù)流總體分析下實(shí)驗(yàn)內(nèi)容，然后分別對兩個(gè)子任務(wù)進(jìn)行梳理。

作者：青藤木鳥 https://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/, 轉(zhuǎn)載請注明出處

實(shí)驗(yàn)分析

剛開始寫實(shí)驗(yàn)代碼的時(shí)候，感覺細(xì)節(jié)很多，實(shí)現(xiàn)時(shí)很容易丟三落四。但隨著實(shí)現(xiàn)和思考的深入，漸漸摸清了全貌，發(fā)現(xiàn)只要明確幾個(gè)基本概念和核心數(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，需要使用一個(gè)頁表(page table)。

下邊行文可能會混用 page 和 frame，因?yàn)檫@兩個(gè)概念都是 buffer pool 管理數(shù)據(jù)的基本單位，一般為 4k，其區(qū)別如下：

page id 是這一段單位數(shù)據(jù)的全局標(biāo)識，而 frame id 只是在內(nèi)存池(frame 數(shù)組)中索引某個(gè) page 下標(biāo)

page 在文件系統(tǒng)中是一段邏輯連續(xù)的字節(jié)數(shù)組;在內(nèi)存中，我們會給其附加一些元信息：pin_count_，is_dirty_

基本概念

而管理幀的內(nèi)存池大小一般來說是遠(yuǎn)小于磁盤的，因此在內(nèi)存池滿了后，再從磁盤加載新的頁到內(nèi)存池，需要 某種替換策略(replacer)將一些不再使用的頁踢出內(nèi)存池以騰出空間。

核心數(shù)據(jù)流

先說結(jié)論，buffer pool manager 的實(shí)現(xiàn)核心，在于對內(nèi)存池中所有 frame 的狀態(tài)的管理。因此，如果我們能梳理出 frame 的狀態(tài)機(jī)，便可以把握好核心數(shù)據(jù)流。

buffer pool 維護(hù)了一個(gè) frame 數(shù)組，每個(gè) frame 有三種狀態(tài)：

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

而待實(shí)現(xiàn)函數(shù)：

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

便是驅(qū)動狀態(tài)機(jī)中上述狀態(tài)發(fā)生改變的動作(action)，狀態(tài)機(jī)如下：

frame 狀態(tài)機(jī)

對應(yīng)到實(shí)現(xiàn)時(shí)數(shù)據(jù)結(jié)構(gòu)上：

1. 保存 page 數(shù)據(jù)的 frame 數(shù)組為 pages_
2. 所有 free frame 的索引(frame_id)保存在 free_list_ 中
3. 所有 unpinned frame 的索引保存在 replacer_ 中
4. 所有 pinned frame 索引和 unpinned frame 的索引保存在 page_table_ 中，并通過 page 中 pin_count_ 字段來區(qū)分兩個(gè)狀態(tài)。

上圖中，NewPage1 和 NewPage2 表示在 NewPage 函數(shù)中，每次獲取空閑 frame 時(shí)，會先去空閑列表(freelist_)中取一個(gè) free frame，如果取不到，才會去 replacer_ 中驅(qū)逐一個(gè) unpinned 的 frame 后使用。這體現(xiàn)了 buffer pool manager 實(shí)現(xiàn)的一個(gè)目標(biāo)：最小化磁盤訪問，原因后面分析。

實(shí)驗(yàn)組件

把握了本實(shí)驗(yàn)的基本概念和核心數(shù)據(jù)流后，再來分析兩個(gè)子任務(wù)。

TASK #1 - LRU REPLACEMENT POLICY

以前在 LeetCode 上寫過相關(guān)實(shí)現(xiàn)，因此很自然的帶入之前經(jīng)驗(yàn)，但隨后發(fā)現(xiàn)這兩個(gè)接口有一些不同。

LeetCode 上提供的是 kv store 接口，在 get/set 的時(shí)候完成新老順序的維護(hù)，并在內(nèi)存池滿后自動替換最老的 KV。

但本實(shí)驗(yàn)提供的是 replacer 接口，維護(hù)一個(gè) unpinned 的 frame_id 列表 ，在調(diào)用 Unpin 時(shí)將 frame_id 加入列表并維護(hù)新老順序、在調(diào)用 Pin 時(shí)將 frame_id 從列表中摘除、在調(diào)用Victim 的時(shí)候?qū)⒆罾系?frame_id 返回。

當(dāng)然，本質(zhì)上還是一樣，因此本實(shí)驗(yàn)我也是采用 unordered_map 和 doubly linked list 的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)細(xì)節(jié)不再贅述。需要注意的是，如果 Unpin 時(shí)發(fā)現(xiàn) frame_id 已經(jīng)在 replacer 中，則直接返回，并不改變列表的新老順序。因?yàn)檫壿嬌蟻碚f，同一個(gè) frame_id，并不能被 Unpin多次，因此我們只需要考慮 frame_id 第一次 Unpin。

放到更大的語境中，本質(zhì)上，replacer 就是一個(gè)維護(hù)了回收順序的回收站，即我們將所有 pin_count_ = 0 的 page 不直接從內(nèi)存中刪除，而是放入回收站中。根據(jù)數(shù)據(jù)訪問的時(shí)間局部性原理，剛剛被訪問的 page 很可能再次被訪問，因此當(dāng)我們不得不從回收站中真刪(Victim)一個(gè) frame 時(shí)，需要?jiǎng)h最老的 frame。當(dāng)之后我們想訪問一個(gè)剛加入回收站的數(shù)據(jù)時(shí)， 只需要將 page 從這個(gè)回收站中撈出來，從而省去一次磁盤訪問，這也就達(dá)到了最小化磁盤訪問的目標(biāo)。

TASK #2 - BUFFER POOL MANAGER

在實(shí)驗(yàn)分析部分已經(jīng)把核心邏輯說的差不多了，這里簡單羅列一下我實(shí)現(xiàn)中遇到的問題。

page_table_ 的范圍。在最初實(shí)現(xiàn)時(shí)，畫出 frame 的狀態(tài)機(jī)之后，感覺 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 的刷盤時(shí)機(jī)。有兩種策略，一種是每次 Unpin 的時(shí)候都刷，這樣會刷比較頻繁，但能保證異常掉電重啟后內(nèi)容不丟;一種是在 replacer victimized 的時(shí)候 lazily 的刷，這樣能保證刷的次數(shù)最少。這是性能和可靠性取舍，僅考慮本實(shí)驗(yàn)，兩者肯定都能過。

NewPage 不要讀盤。這個(gè)就是我寫的 bug 了，畢竟 NewPage 的時(shí)候，磁盤上根本沒有對應(yīng) page 的內(nèi)容，因此會報(bào)如下錯(cuò)誤：

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 時(shí)清空元信息。在復(fù)用一個(gè)從 replacer 中驅(qū)逐的 frame 時(shí)尤其要注意，使用前一定要將 pin_count_\is_dirty_ 這些字段清空。當(dāng)然，在 DeletePage 的時(shí)候，也需要注意將 page_id_ 置為 INVALID_PAGE_ID 、清空上述字段。否則，再次使用時(shí)， 如果 pin_count_ 在 Unpin 后，數(shù)值不為 0，會導(dǎo)致 DeletePage 時(shí)刪不掉該 page。

鎖的粒度。最粗暴的就是每個(gè)函數(shù)范圍粒度加鎖即可，后期如果需要優(yōu)化，再將鎖的粒度變細(xì)。

實(shí)驗(yàn)代碼

以 FetchPageImpl 為例強(qiáng)調(diào)下一些實(shí)現(xiàn)的細(xì)節(jié)，注意到，實(shí)驗(yàn)已經(jīng)通過注釋給出了實(shí)現(xiàn)框架。

我使用中文注釋注出了一些我認(rèn)為需要注意的點(diǎ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. 通過指針運(yùn)算獲取 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é)尾處操作效率高一點(diǎn) 
    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 時(shí)寫回了 
  } 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. 時(shí)刻注意區(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; 
} 

實(shí)驗(yàn)相關(guān) autograder 可以在 FAQ 中找到注冊地址和邀請碼，提交代碼的時(shí)候最好不要提交 github 倉庫地址，會有很多格式問題。可以每次按照實(shí)驗(yàn)頁面的指示，將相關(guān)文件按目錄結(jié)構(gòu)達(dá)成 zip 包提交即可。

提交事項(xiàng)

仔細(xì)閱讀實(shí)驗(yàn)描述，提交前需要注意的事項(xiàng)：

1. 在 build 目錄運(yùn)行 make format ，自動格式化。
2. 在 build 目錄運(yùn)行 make check-lint，檢查一些語法問題。
3. 自己針對每個(gè)函數(shù)在本地設(shè)計(jì)一些測試，寫到相關(guān)文件(本實(shí)驗(yàn) buffer_pool_manager_test.cpp )中，并且打開測試開關(guān)，在 build 文件夾下，編譯 make buffer_pool_manager_test，運(yùn)行 ./test/buffer_pool_manager_test

貼一個(gè) project1 autograder 的實(shí)驗(yàn)結(jié)果：

autograder 結(jié)果

小結(jié)

這是 cmu15445 第一個(gè)實(shí)驗(yàn)，實(shí)現(xiàn)了在磁盤和內(nèi)存間按需搬運(yùn)頁(page)的 buffer pool manager。本實(shí)驗(yàn)的關(guān)鍵之處在于把握基本概念，梳理出核心數(shù)據(jù)流，在此基礎(chǔ)上注意一些實(shí)現(xiàn)的細(xì)節(jié)即可。