B+樹並發協議

01-27

這是我的新專欄——B+樹，這個專欄將會圍繞用作於資料庫索引的B+樹的一些方面展開。

這篇文章將會介紹一份B+樹並發控制協議，之前在寫資料庫的時候自己嘗試出來的。

實現並發B+樹這方面的資料真的是少的可憐，幾乎只能啃paper，而且paper質量參差不齊。找了幾篇paper，挑了其中簡單的一篇實現了(Efficient Locking for Concurrent Operations on B-Trees)，但是這篇paper里鎖類型只有寫鎖，沒有讀鎖，而且讀取節點下降時是不加鎖的，讀paper時覺得有問題，實現之後發現果然行不通，所以不得不自己嘗試出一份協議。（後來才知道作者把讀取節點作為了原子操作，所以沒有讀鎖。）

文章分為2部分，第一部分通過偽代碼介紹這份協議，第二部分證明這份協議是正確的。

嚴格意義上來說這是B link樹而不是B+樹，具體區別在於B link樹每個節點上都會附加一個key和指針。附加的key（如下圖左邊的紅色圓點）值等於同一層下一節點的第一個key（右邊紅色圓點），附加的指針（紅色箭頭）指向同一層下一節點。附加部分用於在同層節點之間進行移動。

協議介紹（插入操作）：

下降函數：n鎖住根節點（讀鎖）nwhile　此節點不為葉子節點n 獲取下降位置n 解鎖此節點（讀鎖）n if 需要右移n 獲取同一層右節點，加鎖（讀鎖）n elsen 將此節點入棧n 獲取下一層節點，加鎖（讀鎖）n返回葉子節點（處於讀鎖狀態）nnn插入函數：n調用下降函數，獲取葉子節點n當前節點升級鎖（讀鎖->寫鎖）nwhile Truen 獲取插入位置n if 需要右移n 獲取同一層右節點，加鎖（寫鎖）n elsen breakn 解鎖當前節點（寫鎖）n 令當前節點等於右節點nif 節點不滿n 插入key，解鎖（寫鎖）nelsen 調用分裂函數nnn分裂函數：nwhile 當前節點已滿n 生成新節點（不加鎖）n 分裂當前節點n if 當前節點不為根節點n 獲取棧內父親節點，加鎖（寫鎖）n elsen 生成新的根節點，使之為父親節點n 將新節點插入父親節點（可能需要右移）n 當前節點解鎖（寫鎖）n 令當前節點等於父親節點n當前節點解鎖（寫鎖）n

具體的實現在這個資料庫里，Mushroom，趕緊去star!

主體代碼在btree.cpp這個文件里，因為我後來還加上了前綴壓縮，所以代碼稍微有些出入。

在不進行任何優化的情況下多線程B link樹比單線程快25%（多線程隊列很大程度上限制了這速度），最終內存會增加約9%。這是個比較保守的數據所以還是具備一定參考價值的，儘管性能還受影響於其他的具體實現，比如頁面緩存策略，鎖管理器的實現等。

下面是具體協議正確性的具體證明。

預警：證明篇幅大而且枯燥，如果不想深究的話直接使用協議就行了。

———————————————————

協議證明：

為了證明協議的正確性，我們需要對以下兩點進行證明：

不會發生死鎖（定理 1）
正確進行每一次操作

每一次操作在結束時都保證樹結構的正確性（定理 2）
除了對樹進行修改的那個線程外其他線程看到的樹是一致的（定理 3）

首先我們證明此協議不會發生死鎖。

引理1：鎖被插入線程按照一定的順序施加

我們定義B link樹節點具有以下大小順序：

兩節點在不同層，若節點a在節點b下方，則a < b
兩節點在同一層，若節點a在節點b左側，則a < b

所以對於插入操作而言，如果在 $t_{0}$ 時刻a < b，那麼在任意 $t > t_{0}$ 時刻都有a < b。

因為樹中節點的增加僅僅通過某個節點x的分裂，假設x分裂形成x和x，顯然滿足 $forall _{y} y < x Leftrightarrow y < x$ ，以及 $forall _{y} y < x Leftrightarrow y < xn$ 。

當插入操作加鎖節點時，永遠不會在擁有當前節點鎖的情況下，對小於（在其下方或左側）這個節點的節點進行加鎖，所以插入操作以一個良好的順序進行加鎖。

所以此協議不會產生死鎖，接下來我們證明此協議正確進行每一次操作。

為了保證樹結構的正確性，我們需要對每一個小操作進行檢查，首先我們檢查以下三個對於單個節點進行的操作：

修改一個非滿節點
將滿節點的右半部分寫入新節點
將滿節點的左半部分寫入當前節點

當修改一個非滿節點時，此節點不涉及分裂且處於寫鎖保護中，所以此操作沒問題。

引理2：分裂某個節點等於對樹結構進行單次改變。

當將滿節點的右半部分寫入新節點時，此時新節點不加鎖但是在這一個時刻沒有任何其他節點指向這個新節點，所以此操作沒問題。

當將滿節點的左半部分寫入當前節點時，此節點處於寫鎖保護中，所以操作沒有問題，還有一個需要考慮的是，分裂過程中會修改邊界指針，即A->B變成A->N->B，此時N（即滿節點右半部分）已經被寫入，所以改變指針剛好可以完美地將新節點引入到樹結構中（但直到在父親節點中插入才算完整地引入新節點）。

所以我們得到每一個操作都能夠被正確執行。

最後我們證明其它線程可以正確地被執行而不需要考慮當前正在對樹結構進行修改的線程。

為了證明這個定理我們首先考慮一個查找線程和一個插入線程交互，然後考慮兩個插入線程進行交互。

引理3： $t_{0}$ 時刻節點a被插入線程I進行修改，當讀取線程P在時刻 $t > t_{0}$ 讀取a節點時，P的正確性沒有被I所影響

首先在P到達a節點之前的路徑並沒有被I所影響。另外，通過定理2，任何I操作對樹結構作出的改變必定生成正確的樹，所以，P在 $t$ 時刻之後進行的操作會正確進行。

通過引理3，我們只需要考慮當查找或者插入線程P在插入線程I對樹結構進行改變之前的情況。

Part 1

考慮插入線程I在 $t_{0}$ 時刻改變節點a，以及查找線程S在 $t<t_{0}$ 讀取a節點，令a表示改變後的節點。因為查找線程在讀取時持有讀鎖，所以只有等讀取完畢後a節點才可能被I改變，所以交互不會出現問題。

Part 2

當兩個插入線程交互時，I會出現以下幾種情況：

查找正確節點來插入
向上回溯
試圖在當前節點插入

對於情況1，等同於Part 1中討論的情況。

對於情況2，I正在回溯，回溯時使用保存在棧上的上一層節點，考慮下面這個情況，在我們從下降到回溯的這段時間內，棧內的節點有可能已經發生了多次分裂，但是我們通過附加指針仍然可以到達正確的父親節點。

對於情況3，I此時不會擁有任何鎖，因為I正在對此節點進行修改，所以等到I釋放鎖時，I才可以修改此節點，然後I修改此節點或者隨著附加指針到達正確節點。

證明完畢。

這個協議有可能會發生活鎖。在隨著附加指針在同一層進行移動時，同一層的節點不斷地進行分裂，也就以為著我們可能永遠也到不了那個我們可以進行下降的節點。但是這幾乎是不可能的，因為CPU每個核運行速度是幾乎一致的而且分裂發生的概率還是比較小的，所以完全不需要擔心，提出這個只是讓你對這個協議有個全面的了解罷了。