CMU15445實驗總結(Spring 2023)

背景

菜鳥博主是2024屆畢業生，學歷背景太差，導致23年秋招無果，準備奮戰春招。此前有讀過LevelDB源碼的經歷，對數據庫的了解也僅限于LevelDB。奔著”有對比才能學的深“的理念，以及緩解自身就業焦慮的想法，于是乎在2024.2.16日開始CMU15445（關系性數據庫）實驗之旅。截止到2.26日：將P2做完了。

因為C++的基礎還湊合，而且時間緊迫，于是跳過了p0實驗，建議之前沒學過C++同學，可以做做p0以熟悉現代C++的語法。

課程主頁鏈接：https://15445.courses.cs.cmu.edu/spring2023/

B站有一位up主“Moody-老師”，對著CMU15445的ppt按照自己的理解復現了每一次的講座，鏈接如下：https://space.bilibili.com/23722270

Project #1 - Buffer Pool

總結

該模塊是基于LRU-K Replacement Policy實現了一個內存池。簡單來講LRU-K Replacement Policy就是類似操作系統的內存頁面置換。

P1模塊實現的內存池，和LevelDB的Cache有相似的作用，只是LevelDB的Cache中實現的內存替換策略是最簡單的LRU算法，同時，LevelDB并沒有像本實驗中那樣一上來就分配那么多內存進行內存復用，而是采用了動態內存分配與釋放的方式，新的Block(或者Table)加到Cache中時，使用malloc分配內存，淘汰時，使用free直接釋放內存。可能這就是在BusTub中叫內存池，而在LevelDB中叫Cache的原因。

本實驗進行的比較順利，唯一主要弄清楚的是Frame和Page的區別。

Frame(4K): 就是內存頁，相應的frame_id就是Buffer Manager最開始申請的每個內存頁的唯一id號。
Page(4K): 就是磁盤頁，相應的page_id就是磁盤上每一頁的id號。

理清這兩個術語，接下來直接復現本模塊的業務代碼即可。

在實現class BufferPoolManager時，可以實現一個NewFrameUnlocked成員函數，方便在BufferPoolManager中獲得空閑內存頁(Frame)。
明確class Page的讀寫鎖是保護data_的，在class BufferPoolManager中無需對Page加讀寫鎖，從實現上也可以想清楚這點。

Gradescope測試

關于6個Fail的解釋

前三個是關于代碼規范的測試，沒有通過。。。

后三個是關于PageGuard的測試，我的實現參考了std::lock_guard，在構造時加讀寫鎖、在析構時，解讀寫鎖。但是因為出現了死鎖，猜測測試程序可能不支持這么實現，但其實并沒有錯誤。而且后續的B+樹索引實驗在使用PageGuard時并沒有出現死鎖。

gradescope測試

Project #2 - B+Tree

總結

該模塊就是基于磁盤（結合Buffer Pool Manager）實現一個B+樹的增刪查改，另外要保證線程安全。

和LevelDB對比，LevelDB使用LSM Tree的結構，其數據結構使用的是跳表、內存按層的方式，每層內部存儲SSTable文件的元數據，作為表級索引，SSTable文件尾部存儲著數據塊的索引，作為塊級索引，而每個數據塊的尾部存儲著數據索引，作為數據索引。在檢索一個key-value對時，由于LevelDB一層的各個部分之間是有序不重疊的，所以以二分為主。查詢方面，可能LevelDB會略差，但是增刪改，LevelDB可以做到“O(1)”（忽略內存插入跳表的操作）的時間復雜度，而使用B+的數據庫增刪查改時間復雜度都是O(logn)。LevelDB其實將真正的刪改延遲到了壓縮階段。具體細節有興趣的讀者可以自行看LevelDB的源碼。

B+樹的實現

考慮到遞歸方式調試困難，我采用了迭代式實現了B+樹

由于B+樹只在葉節點存數據，所有迭代式只需要保存從根節點定位到key的路徑然后根據規則進行調整即可。

約定：

internal_page的kv關系如下：… key1 <= value1（value所代表的page中的key） < key2 <= value2 …

需了解的是：B+樹internal_page，索引為0的entry，其key是無效value是有效。即，B+樹internal_page中，key的數量 = value數量 - 1。而leaf page中，kv數量一樣。也正是存在這種關系，使得在插入和刪除時，internal page的處理更為復雜。

關于對我幫助很大的鏈接：

調試B+樹可視化調試方式可以參考這篇文章：https://www.cnblogs.com/wangzming/p/17479777.html

經驗貼：https://zhuanlan.zhihu.com/p/665802858?utm_id=0

B+樹-查找

我實現了一個輔助函數：

INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::FindPath(const KeyType &key, Context& ctx, bool write, Transaction *txn)

可以查找key并保存路徑。后面的插入和刪除都用到了該函數。

流程如下：

從root_page開始，根據key找到leaf_page，同時保存沿路的internal_page。

官方提供的查找偽代碼：

查找偽代碼

B+樹-插入

插入也是先調用FindPath記錄并鎖住沿路的page，然后自下而上迭代操作。

插入需要注意的是節點達到MAXSize時需要分裂。

對于leaf page的分裂

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>…

要分裂page_id為vn-1的leaf_page，流程如下：

以leaf_page的1/2處的kv作為分裂點，假設為<ki, vi>
將leaf_page節點中，索引為i（包括i）之后的所有的entry移動到new_leaf_page（index從0開始）中。
將leaf_page的next_page_id賦值給new_leaf_page的next_page_id。
將new_leaf_page_id賦值給leaf_page的next_page_id。
左孩子為vn-1（leaf_page的id），key為ki，右孩子為new_leaf_page_id（new_leaf_page的id）
將ki插到parent_page中。（即插到parent_page的index為n的地方）

分裂后parent_page的entry如下：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<ki, new_page_id>、<kn, vn> 、<kn+1, vn+1>…

由于new_leaf_page中index為0處key還是有效的，所以，leaf page的分裂中，分裂點ki是復制并上移的。

對于internal page的分裂

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>…

要分裂page_id為vn-1的internal_page，流程如下：

以internal_page的1/2處的kv作為分裂點，假設為<ki, vi>
將internal_page節點中，索引為i（包括i）之后的所有的entry移動到new_internal_page（index從0開始）中。
左孩子為vn-1（internal_page的id），key為ki，右孩子為new_internal_page_id（new_internal_page的id）
將ki插到parent_page中。（即插到parent_page的index為n的地方）

分裂后parent_page的entry如下：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<ki, new_page_id>、<kn, vn> 、<kn+1, vn+1>…

注意和leaf_page分裂時的區別。

由于new_internal_page中index為0處key是無效的，所以，internal page的分裂中，分裂點ki是上移的。

官方提供的插入偽代碼：

插入偽代碼1

插入偽代碼2

Gradescope測試

關于3個Fail的解釋

這三個是關于代碼規范的測試，所以沒有通過。

gradescope測試

B+樹-刪除

刪除也是先調用FindPath記錄并鎖住沿路的page，然后自下而上迭代操作。

刪除比較麻煩，需要考慮的情況比較多，但是一步一步，理清思路還是很好實現的。按規律來說，不能拆借就一定能合并，反之亦然。至于拆借和合并的時機，本文不過多贅述。

對于leaf page的拆借與合并

向left sibling拆借

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的leaf_page向left sibling借其最右端的entry，流程如下：

找到left sibling的page_id假設中是vn-2。移除并獲得其最右端的entryi，假設為<ki, vi>
根據上面的[約定1]，將parent_page中的entryn-1（<kn-1, vn-1>）中的key更新為：ki。
將<ki, vi>插到page_id為vn-1的leaf page最前方。

向left sibling拆借后，parent_page的entry如下：

… 、<kn-2, vn-2>、<ki, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

向left sibling合并

我實現的合并，以大頁向小頁追加為原則

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的leaf_page和left sibling合并，流程如下：

找到left sibling的page_id假設中是vn-2。
將leaf_page所有的entry都追加到left_sibling中去。
將leaf_page的next_page_id賦值給left sibling的next_page_id。
刪除parent_page中index為n-1的entry。

和left sibling合并后，parent_page的entry如下：

… 、<kn-2, vn-2>、<kn, vn> 、<kn+1, vn+1>、…

向right sibling拆借

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的leaf_page向right sibling借其最左端的entry，流程如下：

找到right sibling的page_id假設中是vn。移除并獲得其最左端的entryi，假設為<ki, vi>，為方便將entryi的下一個entry設為entryi+1<ki+1, vi+1>。
根據上面的[約定1]，將parent_page中的entryn（<kn, vn>）中的key更新為：ki+1。
將<ki, vi>插到page_id為vn-1的leaf page最后方。

向right sibling拆借后，parent_page的entry如下：

… 、<kn-2, vn-2>、<ki, vn-1>、<ki+1, vn> 、<kn+1, vn+1>、…

向right sibling合并

還是以大頁向小頁追加為原則

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的leaf_page和right sibling合并，流程如下：

找到right sibling的page_id假設中是vn。
將right_sibling所有的entry都追加到leaf_page中去。
將right_sibling的next_page_id賦值給leaf_page的next_page_id。
刪除parent_page中index為n的entry。

和right sibling合并后，parent_page的entry如下：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn+1, vn+1>、…

對于internal page的拆借與合并

向left sibling拆借

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的internal_page向left sibling借其最右端的entry，流程如下：

找到left sibling的page_id假設中是vn-2。移除并獲得其最右端的entryi，假設為<ki, vi>
根據上面的[約定1]，parent_page的key更新如下：
- entryn-1（<kn-1, vn-1>） -> entryn-1（<ki, vn-1>）
- entryi（<ki, vi>） -> entryi（<kn-1, vi>）（描述成<vi, kn-1>更合適）
將<kn-1, vi>按kv關系插到page_id為vn-1的internal page最前方。

向left sibling拆借后，parent_page的entry如下：

… 、<kn-2, vn-2>、<ki, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

向left sibling合并

以大頁向小頁追加為原則

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的internal_page和left sibling合并，流程如下：

找到left sibling的page_id假設中是vn-2。
將internal_page所有的entry（包括index為0，盡管key是無效的）都追加到left_sibling中去。
在left sibling中找到原來internal_page中index為0的entry（其key是無效key），將kn-1設為其key。
刪除parent_page中index為n-1的entry。

和left sibling合并后，parent_page的entry如下：

… 、<kn-2, vn-2>、<kn, vn> 、<kn+1, vn+1>、…

向right sibling拆借

假設parent_page中有如下entry：

… 、<kn-2, vn-2>、<kn-1, vn-1>、<kn, vn> 、<kn+1, vn+1>、…

page_id為vn-1的internal_page向right sibling借其最左端的entry，流程如下：

找到right sibling的page_id假設中是vn。取right sibling的entry0的value，以及entry1的key，組成entryi，假設為<k1, v0>。（描述成<v0, k1>更合適）
根據上面的[約定1]，parent_page的key更新如下：
- entryn（<kn, vn>） -> entryn（<k1, vn>）
- entryi（<k1, v0>） -> entryi（<kn, v0>）
將<k1, v0>插到page_id為vn-1的internal page最后方。

向right sibling拆借后，parent_page的entry如下：