CMU15445-2024fall-project1踩坑經歷

p1目錄：

lRU\_K替換策略
- LRU
- LRU\_K
- 大體思路
- - SetEvictable
  - RecordAccess
  - Size
  - Evict
  - Remove
Disk Scheduler
BufferPool
- NewPage
- DeletePage
- FlashPage/FlashAllPage
- CheckReadPage/CheckWritePage
- - PageGuard
  - 并發設計
  - 主邏輯

感謝CMU的教授們給我們分享了如此精彩的一門課程，希望您能尊重教授們和TAs的勞動成果！

本篇文章記錄本人對實驗中各個板塊的理解以及踩坑，如果您發現我過多的涉及到了實驗的內容，有違學術誠信，請告訴我！

正文：

Project1要實現的是一個Buffer pool Manager。 Buffer pool Manager的作用是能夠對磁盤中的數據進行預緩存。數據庫的數據是保存在磁盤中的，要對其中的數據進行處理，就要將磁盤的數據加載到內存中，但是如果當每次要用這個數據的時候再從磁盤中取出，那么就會消耗大量的時間。 Buffer Pool Manager的作用就是預先從磁盤中將數據取出來，當需要使用到時候再把數據從內存中直接提取使用。

在本project中，我們要實現三個組件：

lru_k替換策略
Disk Scheduler 磁盤管理器
Buffer pool Manager 緩沖池管理器。

lRU_K替換策略

Buffer pool manager通過lru_k的替換策略來替換掉緩沖池中的不常用頁面。這個lru_k的替換策略類似于操作系統中的三大調度算法 —— 進程替換、頁面置換、磁盤調度算法。

為了解釋lru_k，這里用lru進行輔助理解。下面是兩者的執行策略和思想：

LRU

執行策略：選擇最長時間沒有被使用過的頁面進行替換。
思想：過去訪問頻繁的頁面，未來也會頻繁訪問；過去訪問最少的頁面，未來也會很少訪問。

如果兩個數據的訪問次數相同，那么刪除訪問時間最早的那一個。或者說是訪問時間距離現在最遠的那一個。

LRU_K

執行策略：設置一個k，然后規定一個后向距離k，刪除后向距離k最大的節點。
- ```
后向距離k的計算方式為（除紅框框外的論述）：
```
- 當節點被訪問的次數大于等于k：k = 當前時間戳 - 第前k次訪問該節點時的時間;
  - 比如當前時間戳為1000， k為3。有節點1、節點2。其中節點1的訪問次數為4，訪問時間戳依次為：100， 200， 300， 400; 節點2的訪問次數為5，訪問時間戳依次為:10, 20, 50, 800, 900。那么對于節點1的后向k為: 1000 - 200 = 800。節點2的后向k為: 1000 - 50 = 950。所以刪除節點2。
- 當節點被訪問的次數小于k：k = +inf，如果兩個節點的訪問次數均小于k，那么會刪除第一次時間戳距離當前時間戳最久的節點。
  - - 對于當訪問次數小于k的時候我之前也有過疑問，文檔中寫的意思按照我的理解是：刪除節點中最近訪問的時間戳最小的節點，但是我這么寫線上測試沒過。所以這里的節點訪問次數小于k應該是對于最早的一次訪問的時間戳與當前時間戳的比較。
- 綜上lru_k的策略其實很簡單：就是如果有訪問次數小于k的節點，優先刪除訪問節點小于k的，如果存在多個這樣的節點，那么就刪除第一次訪問的時間戳最早的節點。如果沒有訪問次數小于k的節點，那么計算后向k距離，刪除后向k距離最大的節點。

大體思路

LRU_K的代碼集中在了lru_k_replacer.h和cpp文件中。您可以閱讀lru_k_replacer.h中的注釋和類的定義來獲取實現所需要的各種信息。

在這里插入圖片描述

（上圖為官方倉庫）LRUKNode是lru_k中的節點。根據注釋的描述， histroy_用來存儲訪問的timestamps(時間戳）、k_為規定的k、 fid_為與當前節點綁定的緩沖池中的頁面id、is_evicatable_為當前頁面是否可以被刪除。

另外，在該項目中，我們的變量如果定義后沒有使用，編譯是會報錯的，所以請將不使用的變量刪掉或者不確定使用可以加[[maybe_unused]]修飾。

在這里插入圖片描述

（上圖為官方倉庫）LRUKReplacer是lru_k數據結構，作為移除器使用。這里面可能有一些我們可能需要的屬性以及要實現的方法。

SetEvictable

修改指定的lru_k節點是否可以刪除。可以為true，否則為false。需要注意同時修改lru_k移除器中的可移除節點的數量。

RecordAccess

頁面被訪問時調用，更新頁面對應節點的使用情況。先查找lru_k移除器有沒有維護該頁面。如果沒有，則添加維護信息；如果已經維護，添加時間戳，同時全局時間戳要增加。

Size

返回移除器中可移除節點的數量。

Evict

lru_k板塊的核心。找出要移除的節點。大體思路就是設置一個指向刪除節點的標記位。遍歷所有可移除節點，計算后向k距離，與被標記的節點對比。如果兩個后向k都為inf，標記兩者中最小時間戳更小的那一個；如果其中一個inf，標記該節點。如果兩個都不為inf，標記后向k更大的。

Remove

Remove也是移除某個節點。不同的是，它是指定某個可移除幀，確定該幀要被刪除。而Evict是從可以出幀中選出一個不常用的刪除。 Remove面向外部的 “我要刪除特定的幀”； Evict面向外部的"我需要一個幀”。

Disk Scheduler

這部分記不太清了，印象中實現起來很簡單。難點是要使用C++17的語法promise 和 future，學習一下新語法就可以通過了。

BufferPool

實現BufferPool，其實就是實現PageGuard的創建和刪除，在該組件中，核心的功能就是 創建新頁面、從磁盤讀取頁面、刪除頁面，將頁面刷新到磁盤。

NewPage

NewPage，即創建新頁面。就是在磁盤中創建新的頁面。注意！不是將頁面放到緩沖池的frames中，而是直接在磁盤上創建一個頁面，無需讀取到frames。利用DiskScheduler的函數。

DeletePage

刪除頁面的操作，這個刪除是在磁盤中刪除，而不是只從緩沖池中刪除。如果目標頁面在緩沖池的幀中，那么刷新到磁盤，再從磁盤中刪除。注意：只從緩沖池刪除p1不會測試出現問題，但是在p3的外排序任務中需要檢測磁盤的刷新和加載。

FlashPage/FlashAllPage

將頁面刷新到磁盤。（刷新磁盤的操作都是使用Disk Scheduler中的刷新函數)

CheckReadPage/CheckWritePage

p1的核心，最難的地方。需要理解pin_count的增加和減少的時機、SetEvict的時機；以及大鎖（整個BufferPool的鎖）和小鎖（單個頁面的讀寫鎖) 的獲取與釋放的時機。

我們下面就先討論并發設計：

PageGuard

對于CheckReadPage和CheckWritePage, 他們兩個獲取的是指定page_id的PageGuard。這個PageGuard，可以理解為BufferPool內frame幀的RAII管理器。創建ReadPageGuard的時候，會增加幀的引用計數，修改幀的lru_k屬性, 同時也會獲取幀的讀鎖，此時如果獲取了讀鎖，那么別的線程再獲取寫鎖，即WritePageGuard, 就會阻塞；創建WritePageGuard的時候，同樣也會增加幀的引用計數，修改幀的lru_k屬性，同時也會獲取幀的寫鎖，此時如果獲取了寫鎖，那么別的線程再獲取ReadPageGuard或者WritePageGuard，就會阻塞。

當ReadPageGuard釋放的時候，會減少幀的引用計數，修改幀的lru_k屬性，同時會釋放讀鎖，銷毀資源；當WritePageGuard釋放的時候，同樣會減少幀的引用計數，修改幀的lru_k屬性，同時會釋放寫鎖。

以上就是PageGuard的理解。

并發設計

并發設計要保證三個順序：

當獲取和釋放PageGuard的時候，對于讀寫鎖和pin_count，我們要保證一個順序：pin->lock->unlock->unpin。
- 大概的主要原因是因為如果lock->pin，那么在線程獲取小鎖被鎖住后，該頁面的pin_count只有1，如果持有頁面的線程釋放該頁面，在lock -> pin + SetEvict()中間的空擋，該頁面可能會被設置為可移除，進而被刷新回磁盤。那么線程再lock， lock的是什么？我們要知道， lock是frame幀里面的成員，作用是鎖住該幀。而如果原本的頁面被替換成別的頁面，那么此時lock，鎖住的就不是原本的頁面，而是新替換來的頁面了，與預期結果不符，程序出錯。（TODO。這里不太懂，可能就是先 lock再pin會導致頁面被刷新替換，導致lock了自己不想要的頁面，導致邏輯錯誤。）
保證獲取小鎖之前要將大鎖釋放掉。在本地測試的DeadLockTest有下面這種情況:
- 線程TA想要獲取頁面A，所以進入CheckPage函數，獲取了大鎖，然后創建頁面A的PageGuard獲取頁面A的小鎖。退出CheckPage函數釋放大鎖。
- 此時線程TB也想要獲取頁面A，所以進入CheckPage函數，獲取了大鎖，然后創建頁面A的PageGuard時因為A的鎖被占用，所以阻塞。此時TB占據著大鎖阻塞。
- 如果此時TA想要再獲取任何一個頁面，都要進入CheckPage函數獲取大鎖，但是大鎖被TB占用，就形成了一種情況：TA占據著頁面A的小鎖，想要獲取TB占用的的大鎖； TB占據著大鎖，想要獲取TA占用的小鎖。形成死鎖。
- 所以我們要確保TB在阻塞之前把大鎖釋放掉。但是這樣我們必須說服自己一件事，就是這樣做可能導致插隊，此時執行會不會不符合預期？
- 如果TA和TB兩個獲取不同的頁面PageGuard那么不會造成插隊情況， TA獲取頁面A的PageGuard之前釋放大鎖， TB進入獲取TB的PageGuard。兩個線程針對不同的frame，即BufferPool中不同的內存塊。互相不干預，而且因為減少了鎖粒度，可以讓并發更快。
- 如果TA和TB獲取相同的頁面， TA獲取頁面A的PageGuard，在獲取小鎖之前釋放大鎖；TA剛剛釋放大鎖，此時一個TB速度極快，迅速獲取大鎖，然后搶在TA之前獲取小鎖。
- 如果TA和TB獲取的都是讀鎖，那么不沖突，兩者都可以獲取到頁面A的小鎖。
- 如果TA獲取讀鎖， TB獲取寫鎖。或者TA獲取寫鎖， TB獲取讀鎖。那么TA會被插隊， TB會成功獲取到頁面A。此時的結果相當于TB獲取到頁面A后，TA才執行。頁面A此時pin_count為二，TBpin了一次， TApin了一次，并且頁面A的可移除狀態為false。結果在可接受范圍之內。
保證pin/unpin和SetEvictable()被綁定為原子。即兩個操作一定是在一起，原子的。所以要保證pin和SetEvictable()以及unpin 和SetEvictable()是在大鎖的保護下。因為如果pin和SetEvictable不被綁定為原子操作，就會出現以下這種情況：
- 對于頁面A，線程A本來持有該頁面。然后線程Aunlock->unpin->pin_count == 0。線程A想要進入SetEvictable。
- 此時另一個線程B在正在獲取頁面A，并且執行速度非常快。很快就pin->pin_count == 1了。然后比線程A更快進入SetEvictable，修改了頁面的狀態變成”不可移除“。
- 最后線程A才進入SetEvictable修改頁面變成”可移除“。程序出錯。