CMU-15445匯總
本文對應的project版本為CMU-Fall-2023的project2
由于Andy要求，本博客只提供思路，不會公開任何代碼
本博客默認讀者已懂可擴展哈希的插入刪除理論知識，若不清楚流程可以看這篇博客

通關記錄

目前的rank還比較低，后續會優化下

Task1 Read/Write Page Guards

Task1要求實現三種PageGuard類，分別是BasicPageGuard、ReadPageGuard和WritePageGuard。三種PageGuard類都使用RAII的思想保護Buffer Pool Manager的緩沖頁，防止用戶遺漏調用Unpin方法導致緩沖頁被固定無法驅逐，與智能指針相似，當PageGuard對象生命周期結束時，在析構函數中調用Unpin方法來確保釋放緩沖頁；進一步的，ReadPageGuard和WritePageGuard還會保護緩存頁的讀寫一致性，且避免死鎖（若其他時候后忘記解鎖，則在析構時解鎖）。當然，PageGuard類也要對外提供方法用于手動釋放。實現Task1中的類會為后面Task3的可擴展哈希做鋪墊，后面用到的時候就知道多好用了。
三種類中的主要成員有：

• BufferPoolManager *bpm_
• Page *page_
• bool is_dirty_

三種類中主要實現的方法有：

• 三種PageGuard的移動構造函數、移動賦值運算符、Drop方法與析構函數
• BasicPageGuard類中的UpgradeRead()函數和UpgradeWrite函數

在實現完三種PageGuard類中的方法后，我們需要使用這三種PageGuard，實現BufferPoolManager類中的FetchPageBasic、FetchPageRead、FetchPageWrite和NewPageGuarded函數。

移動構造函數

移動構造函數的實現比較簡單，將參數中的成員復制到待構造對象，然后清空參數的所有成員即可。

Drop方法

Drop函數為對外提供的釋放頁接口，它需要做的事情就是調用一下BufferPoolManager的UnpinPage函數，將page_中維護的頁釋放（如果有的話）；在ReadPageGuard和WritePageGuard中，則還需要解鎖（讀鎖或寫鎖）

移動賦值運算符

移動賦值與移動構造差不多，不同點在于如果運算符左右兩邊的對象不同，需要將左邊對象維護的緩沖頁釋放掉，并解開讀鎖或寫鎖，再將右邊對象中的成員復制到左邊，最后情況右邊對象。

析構函數

調用Drop方法釋放頁并解鎖即可。

UpgradeRead函數

利用BasicPageGuard中的成員構造出一個ReadPageGuard，并加寫鎖返回即可。UpgradeWrite同理。

FetchPageBasic、FetchPageRead、FetchPageWrite、NewPageGuarded

這幾個方法的實現都比較簡單，先調用bpm中對應的函數FetchPage或NewPage，然后構造BasicPageGuard或者ReadPageGuard或者WritePageGuard返回即可。值得注意的是在返回后兩種之前需要先加RLatch或WLatch。

Task2 Extendible Hash Table Pages

Task2要求實現三種可擴展哈希中使用的數據結構，也就是三層結構中每一層的頁面布局。分別是HeaderPage、DirectoryPage和BucketPage，如下圖：

HeaderPage

HeaderPage的成員包括第二層DirectoryPage的PageId數組，以及一個位深度x，PageId數組的大小為$2^x$，且使用哈希值的最高有效x位進行索引。如位深度為2，32位哈希值為0x5f129982，最高有效位前2位為01，則會被索引到01對應的DirectoryPage上。

DirectoryPage

DirectoryPage的成員包含第三層的BucketPage的PageId數組，全局位深度global_depth和每一個Bucket的局部位深度local_depth數組，PageId數組的大小為$2^{global\_depth}$，且使用哈希值的最低有效global_depth位進行索引。如全局位深度為2，32位哈希值為0x51129982，最低有效位后兩位為10，則會被索引到10對應的BucketPage上。

BucketPage

BucketPage的成員包含一個Key-Value數組，以及數組大小size。被索引到該Bucket的Key-Value會追加到該Bucket上進行存儲。

以上三個類的實現都比較簡單，跟著頭文件中的注釋實現就是了。值得注意的是DirectoryPage的IncrGlobalDepth方法，在增加global_depth的同時還需要設置PageId數組中新增的PageId（具體見插入時的操作，見引言中的理論博客）

Task3 Extendible Hashing Implementation

Task3要求利用Task1和Task2中實現的類與方法，實現可擴展哈希類DiskExtendibleHashTable的方法，主要就是可擴展哈希的插入和刪除。
理論知識見引言中的理論博客，大致跟著理論實現就行，需要注意的細節有：

• 不需要使用的PageGuard需要及時釋放，防止頁面緩沖池滿了
• 關于插入，當Bucket滿了導致分裂，可能分裂后的重新分配仍會產生Bucket滿的情況，此時需要繼續分裂，直到可以正常插入新tuple，我的實現方法是遞歸，也可以循環實現。
• 關于刪除，我刪除空白頁的方法是，每當刪除一條tuple后，檢查當前是否有空白的Bucket，如果有，判斷global_depth與該Bucket的local_depth是否相等，相等則刪除，不相等則后續縮短DirectoryPage之后再考慮；刪除tuple導致的DirectoryPage縮短也需要循環的進行，直到無法再縮短為止。

Task4 Concurrency Control

Task4要求保證可擴展哈希的并發安全性，其實在Task3中如果FetchPageGuard和NewPageGuard使用正確的話，自然就保證并發安全性了，故不需要額外考慮這個Task。