完成了Project-2的checkpoint1之后，就可以開始搞并發控制了。在checkpoint1中雖然能過測例，但不一定是沒問題的，checkpoint-2必須解決考慮不完全的并發問題。

一、實驗內容

實現的接口

      Task #2c – Index Iterator

      Task #2d – Concurrency Control

      checkpoint1需要實現tree如下接口：Remove Insert GetValue

      迭代器接口：Begin End operator++

      并發控制：利用TransactionManager實現INSERT,UPDATE,SELECT,DELETE的并發版本和樂觀鎖版本

二、實現細節

A concurrency control protocol is the method that the DBMS uses to ensure “correct” results for concurrent operations on a shared object.

latch和lock的區別：

       在本課程的語境下，latch表示的是數據庫底層數據結構，保護操作安全性用到的鎖；lock則是更上層的用于保護邏輯結構行的鎖。

Locks
→ Protect the database's logical contents from other txns.
→ Held for txn duration.
→ Need to be able to rollback changes.
Latches
→ Protect the critical sections of the DBMS's internal data structure from other threads.
→ Held for operation duration.
→ Do not need to be able to rollback changes

因此project2里要實現的主要是B+tree的并發保護。在正確地實現B+樹的基礎上用鎖對數據進行保護。

最簡單的方式是對整個樹進行加鎖，而對header page即對整個樹進行加鎖；顯然可以看到邏輯結構的表跟物理結構的tree是一一對應的；

但是這樣以來并發性顯然很弱，因此實際每個page都持有鎖，盡量只加必要page的鎖，以提高并發性。

1.Crabbing Protocol鎖協議與性能優化

蟹行協議是一個形象的比喻，簡單來將就是從根到葉節點加鎖，再依次解鎖上層的鎖。其加鎖的軌跡就像螃蟹在走路。這個其實是比較基礎的細粒度鎖，在此基礎上還有其他的變種。

為了保護樹的結構，同時樹支持查詢SEARCH，插入INSERT，刪除DELETE的操作，使用了讀寫鎖，讀加讀鎖，插入和刪除加寫鎖。除此之外，樹中沒有UPDATE的操作。

crabbing協議的示例如下，對插入25的操作，從根節點開始加寫鎖。

其并發保護的規則如課程PPT所示：

Search : Starting with root page, grab read (R) latch on child. Then release latch on parent as soon as you land on the child page.

Insert : Starting with root page, grabwrite (W) latch on child. Once child is locked, check if it is safe, in this case,not full. If child is safe, release all locks on ancestors.

Delete : Starting with root page, grab write (W) latch on child. Once child is locked, check if it is safe, in this case, at least half-full. (NOTE: for root page, we need to check with different standards) If child is safe, release all locks on ancestors.

概括地說，查詢加讀鎖，意味著同一頁面，同時可以有其他的讀鎖，但是不能有寫鎖；插入，刪除加寫鎖。

插入可能造成節點分裂（新增節點），刪除可能造成節點合并（進而刪除某個節點），因此要判斷子節點是否安全，以決定在操作執行過程中是否釋放分裂節點上一層的鎖。

2.對根節點加的樂觀鎖

由于大部分情況下節點分裂是少數情況，基于這一假設，可以只在根節點加讀鎖（因為寫鎖會導致阻塞），如果最后也未發生分裂，則正常執行；否則要從頭再執行一遍根加寫鎖，接著釋放所有已獲得鎖的操作；

3.發生拆借、合并對sibling加鎖

葉節點、內部節點發生borrow/merge 時，要先對兄弟節點加寫鎖，即使已經判斷節點不安全且已經加了父節點的鎖。這是因為父節點加鎖可能在另一個操作釋放鎖到完成該操作之間；例如A,B是葉節點兄弟，t1刪除葉子節點A的值，t2刪除B的值，B是安全的，按照以下順序

1)t2加父節點鎖，發現B安全，釋放鎖；

2)t1加父節點鎖，發現A不安全，不釋放鎖；

3)t2刪除節點B內的值；

4)t1合并A,B。

t1必須在4進行的時候對B加鎖，直到B完成。參考[1]。

borrow時，兄弟節點的鎖要在操作完成后立刻釋放并且unpin。

4.樂觀鎖的實現

為了方便釋放父節點的鎖，需要用到事務transaction。這是個主要在P4用到的類，但是在P2中只需要用到事務的 PageSet、DeletedPageSet相關方法。其中PageSet是一個雙端隊列，DeletedPageSet是一個map。

這樣，在樂觀鎖的實現中，可以緩存訪問過的頁面，直接利用PageSet釋放各個祖先的鎖，而不用重新fetch頁面并unlock。

另一種情況是，由于分裂、合并節點的時候可能會發生遞歸向上的操作，如遞歸向上繼續分裂、合并，因此PageSet也可能記錄了當前頁（old_page）。

分裂、刪除每次操作的對象最多有三個，需要仔細地操作page, parent_id，lock，page_set，并區分各種情況。由于主體已經在P2的checkpoint1實現過了，因此這里主要就是考慮unpin的工作。

5.Index Iterator

       跟大部分容器一樣，b_plus_tree也有迭代器；而這里的index_iterator是為了實現對葉節點的遍歷，IndexScanExecutor是一個執行遍歷的類，在真正執行的時候會調用b_plus_tree去遍歷，但由于應對大量數據查詢避免內存過大的考慮，數據庫不會希望一次性全部給出數據，所以要使用迭代器記錄當前移動位置；

       由于支持多線程并發，對頁面的操作是臨界操作，因此index_iterator的內部實現必須加上鎖。具體來說，就是index_iterator維護當前保存的頁面數據，每次讀取一個頁面的時候加上鎖，并按調用依次讀出，更新當前位置；當一個頁面讀取完成的時候，解鎖當前頁，并獲取下一個頁面的鎖，直至遍歷完成。

       這便是遍歷的流程。然而有人可能會想到，如果遍歷的時候前面的頁面被修改或刪除，當前加鎖的頁面是否能正常工作，或者這樣遍歷出來的結果是不是我們一開始要的。這個考慮的其實是不可重復讀的問題，不是在這個層次解決的，要在隔離級別用其他粒度的鎖（行鎖或表鎖）進行解決。僅僅在頁面層次，加鎖保證的是頁面數據的更新的完整性。

       由于在22fall沒有自動處理unpin_page的邏輯（23spring用的是page_guard），所以iterator++移動到新page的時候也需要unpin_page。

6.Unpin操作的錯誤

       23spring對unpin實現PageGuard的重要原因，就在于unpin的時機比較難把握，要降低學生實現的負擔。那么unpin操作有哪些錯誤？因為頁緩沖區初始化的時候size是固定的，如果頁面沒有及時釋放，就會造成剩余區大小不足，造成分配失敗，實際上是一種內存泄漏。這樣可能造成一些分配就是空指針，直接造成段錯誤。

       而事實上在大小設置合理的情況下，頁面緩沖區是夠用的，可以存儲很大的結果集。

三、 調試技巧

       如果希望自動生成不同結構的B+樹操作序列case，可以用隨機的方式生成B+樹操作序列；并且用如下命令運行直到運行出錯；

INFO=concurrent; while true; do ./test/b_plus_tree_${INFO}_test; [ $? -ne 0 ] && break; done

References

[1]CMU 15445-2022 P2 B+Tree Concurrent Control  https://zhuanlan.zhihu.com/p/593214033

[2]https://15445.courses.cs.cmu.edu/fall2022 課程官網

[3]https://github.com/cmu-db/bustub Bustub Github Repo

[4] Database System Concepts 6^th version, Abraham.Silberschatz.

[5]自動測評網站 GradeScope，course entry code: PXWVR5 https://www.gradescope.com/