週刊(第23期):圖解Blink-Tree:B+Tree的一種併發優化結構和演算法

語言: CN / TW / HK

2022-08-07

8分鐘閱讀時長

週刊 , 儲存引擎

2022週刊

引言: 《Efficient Locking for Concurrent Operations on B-Trees 》 論文中提出了一種稱為“Blink-Tree”的資料結構,這個資料結構提供了B+Tree併發訪問的一些優化方式,本文對這篇論文進行解讀。

概論

由於Blink-Tree本質上是B+Tree的一種優化,所以要理解它首先要對B+Tree有一些瞭解,在這以前介紹過B+Tree,就不在這裡闡述了,可以參考:

我們來看如果同時存在兩個讀寫操作併發訪問一顆B+Tree,會出現什麼問題,見下圖:

程序P1查詢資料15,而程序P2寫入資料9,當P2寫入資料完畢時,樹結構變成了下圖這樣:

由於原先的葉子節點要滿足B+Tree的性質,所以分成了兩個葉子節點,而這時P1程序對此並沒有感知,還停留在舊的節點上,於是就導致了查詢資料15失敗。

一種最直觀的優化方式是讀、寫的時候加全域性鎖,但是這樣做的效率不高。Blink-Tree就是為了高效解決這類併發訪問問題引入的一種結構和演算法。

資料結構

Blink-Tree本質上還是一顆B+Tree,即資料儲存在葉子節點上的B-Tree。

對於一顆 k-degree 的Blink-Tree而言,它有如下的性質:

  • 所有葉子節點是同一高度的,即從根節點到每個葉子節點都是同一長度。(Each path from the root to any leaf has the same length, h.)
  • 對於每個內部節點而言,除非是根節點,否則都至少有 k+1 子節點。(Each node except the root and the leaves has at least k + 1 sons.)
  • 根節點要麼是葉子節點,否則至少有兩個子節點。(The root is a leaf or has at least two sons.)
  • 內部節點最多有 2k+1 個子節點(Each node has at most 2k + 1 sons),結合上面的內容即內部節點的子節點數量在 [k+1,2k+1] 之間。
  • 資料都儲存在葉子節點上。

可以看到,上面的性質和B+Tree很相似,在此基礎上Blink-Tree還增加了以下資料:

  • 在每個節點(包括內部節點和葉子節點)中,鍵以遞增順序排列。

  • 內部節點還儲存了稱為“高鍵(high key)”的資料,這個資料用於儲存本節點中最大鍵的資料。

  • 同層的兄弟節點之間,以 “指標” 相連線。

如下圖就是增加了high key和link指標之後的blink-tree示意圖:

演算法

對資料結構有了解之後,來看看演算法的實現,不過在具體展開之前,還要先了解幾個概念。

high key引入的變化

有了high key之後,如果在插入資料之後發生了split,新舊節點會發生以下的變化(這裡假設舊節點為 a ,split之後的節點從左到右為 a'b' ):

b'
a'

以上流程可以看看下面的圖示:

上圖中:

  • split之前:舊節點 a 的high key為74,這個值同時也做為父節點的key儲存在父節點中。
  • split之後:新節點 b' 的high key還是舊節點 a 的high key(74),而新節點 a' 的high key為51,同時這個新的high key也更新到了父節點中。

這是引入high key這個資料最重要的變動,後面會講到這個資料的作用。

safe和unsafe節點

在類B-tree類結構中,當插入、刪除資料之後,可能會導致節點的資料量不滿足條件,對應的就需要進行分隔(split)以及合併(merge)節點操作,於是就有了 safeunsafe 節點的定義:

  • safe節點:
    • 在insert時,如果μ < 2k,這意味著即便插入資料完成也不會違反上面的節點資料量條件,這樣就不需要分隔節點。
    • 在delete時,如果μ > k,這意味著即便刪除資料完成也不會違反上面的節點資料量條件,這樣就不需要合併節點。
  • 除了上面這兩個條件之外,其他所有的更新資料操作都會導致節點變成 unsafe 節點。

演算法

查詢流程

下面虛擬碼中的 scannode(v,A) 表示在記憶體中的節點 A 中查詢 v 的子流程,就不在虛擬碼中表示出來了。

虛擬碼的流程其實很簡單:從根節點開始,按照樹形的結構查詢資料,首先查內部節點,然後再查詢葉子結點,這與常見的樹形結構體查詢流程並無太大區別,就不再展開解釋了。值得注意的是前面討論過的併發訪問時的問題,這將在下面討論。

procedure Search()
/* 讀入根節點到記憶體 */
current <- root; /* Get ptr to root node */
A <- get(current); /* Read node into memory */

/* 依次查詢路徑上的內部節點 */
while currentt is not a leaf do
begin /* Scan through tree */
	current <- scannode(u,A)/*Find correct(maybelink)ptr */
	A <- get(current) /* Read node into memory */
end;

/* 到了這裡意味著查詢到了葉子節點 */
/*Now we have reached leaves. */
while t< scannode(u,A)= link ptr of A do /*Keep movingright if necessary
begin
	current <- t;
	A <- get(current)/* Get node */
end;/* Now we have the leaf node in which U shouldexist.*/

/* 根據結果返回查詢結果 */
if u is in A then done "success" else done “failure"

寫入流程

原論文中,寫入資料流程這部分的虛擬碼太長,我做一下精簡和濃縮,如下:

向樹中插入資料v:
	初始化儲存路徑上經過節點的棧
	
	// 第一部分:內部節點的遍歷
	如果當前的節點還是內部節點:
		載入節點t到記憶體中
		將當前節點t儲存到棧中
		查詢路徑上的下一個內部節點
		
	// 到了這裡意味著到了葉子節點這一層
	
	// 第二部分:在葉子節點上遍歷找到資料所在的葉子節點
	對上一步最後的內部節點加鎖
	在葉子節點所在的層逐步向右遍歷找到節點所在的葉子節點,流程如下:
	如果當前節點不是v所在的葉子節點,且不為空節點:
		加鎖當前節點
		釋放上一個被鎖住的節點
		將當前節點讀入記憶體中
	
	// 到了這裡意味著找到了所在的葉子節點,下面進行插入操作
	// 第三部分:修改所在的葉子節點插入資料
	修改所在的葉子節點A插入資料:
	如果葉子節點A是安全(safe)節點:
		插入資料
		解鎖葉子節點A
		返回
	否則如果是不安全(unsafe)的節點:
		插入操作時不安全意味著就要進行split操作
		分配新頁面用於儲存split後的新頁面B'
		插入的資料v寫入節點A',需要split出去的資料寫入節點B'
		y為split後的A'的high key
		寫入B
		寫入A,同時修改父節點對應節點A的key為y
		從棧中彈出上一個層次的節點,繼續回溯做可能的平衡節點操作
		解鎖當前節點

上面流程中,查詢資料的流程與上面的查詢流程大體相同,不同的是如果修改的葉子節點是unsafe節點的情況,以論文中的圖例來說明這個流程:

在上圖中,如果最終插入的資料在葉子節點 a 中,同時該節點是非安全節點,要做split操作,假設新的節點為 a'b' ,流程是這樣的:

  • 首先分配 b' 的頁面,而 a' 複用舊節點 a 的頁面。
  • 圖(b):修改 b' 的link指標,指向舊節點 a 的下一個節點 c
  • 圖(c):修改 a' 的link指標指向 b' ,這一步修改完畢之後,舊節點 a 就能被 a' 替換掉了,即原先父節點、左子樹的指標都從指向 a 修改成指向 a'
  • 圖(d):修復父節點的指標及key指向新增的 b' ,至此修改完成。

除了上面這個修改非安全節點的流程需要特別解釋意外,還有幾點需要注意的:

  • 關於加鎖:從上面的流程裡可以看到,每次加鎖的流程大體都是:

    • 先加鎖當前的節點
    • 再釋放掉上一個被加上的鎖。

    這樣的做法,讓鎖的粒度會更細,換言之提高了併發度。

  • 棧和回溯操作:在修改路徑上任一個被遍歷到的內部節點,都儲存到一個棧中,這是因為split之後的平衡操作是自底向上的,即:當修改了葉子節點進行split平衡操作之後,可能又會導致父節點不平衡,於是又要對父節點繼續平衡,這一操作自底向上一直進行到某個父節點平衡為止。而要知道父節點,依賴的就是儲存到棧中的節點資訊,每次要繼續向上平衡父節點,就從棧中彈出一個節點即可。

衝突的解決

以上大體清楚了 BLink-Tree 的查詢和寫入流程,回到本文最開始的問題:在讀寫併發的情況下,該資料結構如何保證不會出現待查詢的資料剛好所在頁面被split而查不到資料的問題?

答案是要藉助high key的判斷,還是把上面的high key示意圖放在這裡:

需要重複一下修改前後high key性質:當split出來之後的新節點 a'b' ,其中 a' 的high key在split之後需要進行重新計算,同時這個high key需要更新到父節點的key中,也就是上圖中的 51 ;而 b' 節點的high key繼續為舊節點的high key,也就是圖中的 74

於是,查詢到資料之後,如果資料所在的頁面是非安全頁面,那麼頁面可能發生split,即資料可能在 a' 或者 b' 這兩個頁面中,就有了以下兩種可能的處理情況:

  • 假設要找的資料落在了 a' 中,那麼不需要其它動作,直接返回即可,如圖中的42、47還在 a' 中。
  • 否則就是落到了 b' 中,這時候需要沿著 a' 的link指標繼續到右兄弟 b' 中查詢,如圖中的 71 ,原先在舊頁面 a 中,split之後落到了 b' 中。

問題來了:查詢流程如何判斷落在了split之後哪個頁面中呢?答案是查詢到資料之後,將資料與頁面當前的high key進行對比即可,比如:

  • 如圖中如果查詢的是42,比split之後的 a' 的high key 51還小,於是就只會落到 a' 中。
  • 否則如果查詢的是 71 ,比split之後的 a' 的high key 51還大,於是就只會落到 b' 中。

可見:引入high key和link指標,解決了樹在修改過程中發生平衡操作時的查詢定位問題。

總結

  • Blink-Tree是B+Tree的一種變形,引入了high key和指向右兄弟節點的link指標。
  • 通過這兩個資料的引入,在併發查詢時可以做為節點是否發生變更的根據。
  • 同時Blink-Tree的併發度更優,加鎖粒度更細。