長路漫漫- 從 Blink-tree 到 Bw-tree -上-

天不生我 bw-tree, 索引萬古如長夜

背景

在前面的文章路在腳下, 從 BTree 到 Polar Index 中提到, 我們已經將 InnoDB 裏面 Btree 替換成 Blink Tree, 高併發壓力下, 在標準的 TPCC 場景中最高能夠有 239% 的性能提升, 然後我們對 InnoDB 的 file space 模塊也進行了優化, 在分配新 page 的時候, 可以允許不進行填 0 操作, 從而儘可能的減少 fsp->mutex 的開銷, 在這之後我們發現瓶頸卡在了 page latch 上, 而且越是在多核的場景, page latch 的開銷也越大.

目前 latch 衝突的主要場景

讀寫衝突場景, 典型場景對 Page 進行 write 操作的時候, 另外一個 read 操作進行要讀取 page.
寫寫衝突場景, 典型 autoinc, 或者 update_index 對同一個 page 進行更新場景.
“讀讀衝突” 場景. 頻繁的對 btree root 附近 level 進行 s lcok 和 unlock 操作.

前面兩個場景比較常見, 爲什麼會有讀讀衝突這樣的問題?

現有 blink-tree + lock coupling 的實現中, 我們加鎖的順序是自上而下的, 每一次訪問 page 都需要 lock, 然後 unlock.

在 InnoDB 自己實現的 rw_lock 中 (大部分的 rw_lock 實現也都類似), 每一個 latch 都有 lock_word 用於記錄持有 s lock thread 數目, 所以即使是 read 操作加 s lock 的場景, 也是需要修改內存裏面的 rw_lock->lock_word, 然後釋放的時候繼續對 lock_word 進行減 1 操作.

這樣帶來的問題是在 multi-core 場景中, 需要頻繁的修改一個 share memory(rw_lock->lock_word). 而對於 share memory 的頻繁修改會大量增加 CPU cache coherence protocol.

即使 read only 的場景, 對於 Blink-tree 的 root page 依然有大量的 s lock, s unlock 操作, 從而造成瓶頸.

在 PolarDB 中, 這樣的場景對我們的性能有多大的影響呢?

我們修改了 InnoDB 代碼, 在 sysbench read_only 的場景下, 將所有的 lock 都去掉 vs 僅僅持有 s lock 的場景.

before 表示的是 s lock 場景

after 表示的是不持有 Lock 場景

因爲是 read_only 場景, 不會有任何數據寫入, 所以不加鎖也就不會出錯

從上面兩個圖可以看到, 在 Intel 128 core 的場景下, 不持有 lock 的性能對比持有 s lock 有 10% 的提升, 在 AMD 256 core 的場景下, 這個提升更加明顯, 有 20% 左右的提升.

所以我們認爲這裏在 read only 的場景中, 因爲 cache coherence protocol 引入的開銷差不多有 10%~20% 之間.

但是, 其實 Btree 是一個非常扁平的 tree, 絕大多數訪問的是並不衝突的 leaf page. 能否避免大家都去加鎖訪問 root page 呢?

學術界如何處理 Page 衝突的問題呢?

筆者主要參看 CMU Advanced Database Systems 裏面推薦的 OLTP Indexex(B+Tree Data Structures) 和 OLTP Indexes (Trie Data Structures) 對這一塊進行了解.

其實早在 2001 年的時候, 在論文 OLFIT 裏面, 作者 Cha 第一個提出簡單的 lock coupling 是無法在現代的 multi-core CPU 進行 scability 的. 即使在沒有衝突的場景, 也會因爲 cache coherence protocol 的開銷, 導致性能下降.

在 OLFIT 文章裏面, 介紹了這樣的場景

上圖中, 在 Main-Memory 裏面有一個包含 7 個 node btree, 爲了簡化問題, 有 4 個 core, p1, p2, p3, p4. 有各種的 cache block.

在初始的時刻, 所有 core 裏面的 cacheline 都是空的, P1 訪問的路徑是 n1->n2->n4. 訪問完以後, 會把 n1, n2, n4 放在自己的 cache block 中, 也會把對應的 latch 放在自己的 cache block 中. P2 訪問的路徑是 n1->n2->n5. 在 P2 訪問 n1, n2 的時候, 由於修改了 n1 和 n2 的 latch, 因此就必須增加了 Invalidate 在 P1 裏面的 n1, n2 的 latch 的開銷, 同時如果 P1 再次訪問 n1 的時候, 依然要重新衝 main-memory 中去獲得對應的 latch. 並且這裏可以看到 c1 的 cache block 即使有足夠多的空間, 也依然會被 Invalidate 掉的.

整體而言 OLFIT 這個文章描述了 Btree 在 Multi-core 場景下的性能問題, 給出了一個較爲簡單的樂觀加鎖解決方案 OLFIT.

OLFIT(Optimistic, Latch-Free Index Traversal CC)

OLFIT 實現讀操作不需要加鎖, 只有寫操作需要加鎖, 但是很重要的一個前提是, write 操作的修改一定要是原子性的.

OLFIT 大致流程:

Algorithm UpdateNode
Update 的算法:
U1. Acquire latch.
U2. Update the content. 
U3. Increment version. 
U4. Release latch.

Algorithm ReadNode
Read 的算法:
R1. Copy the value of version into a register R. 
R2. Read the content of the node.
R3. If latch is locked, go to R1.
R4. If the current value of version is different fromthe copied value in R, go to R1.

Update 的算法:

操作的時候, 修改之前對 page 進行 lock, 然後修改完成以後增加版本號, 最後放鎖.

Read 的算法:

整體 Read 過程是不需要加鎖的.

R1 操作將 page 內容拷貝到本地, R2 讀取內容.

由於 OLFIT 不對 page 進行 lock 操作, Read 進行 R2 操作的時候, 有可能有新的 Update 操作進來, 進行 U2 操作, 也就是修改了 page 裏面的內容. 因此 OLFIT 需要在讀操作完成以後, 通過 R3/R4 操作, 判斷 Page 版本號是否被修改以及 Page 是否被持有 lock 來確認讀取過程中該 Page 是否被修改了, 如果被修改那麼就需要發起重試操作了.

但是, 在工程上, 雖然最後 R3/R4 會保證如果 U2 進行了修改, Read 操作會進行重試, 但是如果這個 U2 update 非 atomic, 會導致 R2 讀取出來的內容是 corrupt 的. 所以在工程上必須保證 U2 操作還應該是 atomic 的. 但是目前看來在工程上是無法實現的.

比如現有 InnoDB 的 update the content 就是非 atomic 的, 因爲需要修改的是 16kb 大小 page 的內容. 那麼讀取操作有可能讀取到了 corrupt page, 那麼這裏就無法判斷 page corrupt 是由於真的 page 出錯導致 corrupt, 還是由於讀取非 atomic 導致的 corrupt. 當然可以通過重試來讀取 Page 來進一步驗證, 但還是無法準確確定 Page 的正確性.

所以這麼看來在實際的工程實現中 OLFIT 似乎是不可能實現的, OLFIT 很大的一個假設前提 read content 是 atomic 操作.

OLFIT 如何解決 SMO 的問題?

Insert and delete operations can also initially acquire read locks before upgrading them to write locks if necessary.

並且由於 read 操作可以不進行加 s lock 操作, 那麼在 btree 中進行 x lock 加鎖操作的時候自然可以自下而上了. 因爲不存在之前 search 自上而下的 Lock, 而 modify 自下而上的 Lock 導致的死鎖問題了.

但是由於 read 操作不再進行加鎖操作, 那麼可能在上述 Algorithm ReadNode R2 操作中, Page 進行了 split 操作. 即使我們能夠保證 Read Content of node 是原子操作, 也有可能該 Page 發生了 SMO 操作, 要訪問的 key 已經不在當前 Page 了. 那麼該如何處理?

目前 OLFIT 通過和 blink-tree 類似方法, 增加 high key, 並且保證所有的 SMO 操作是自左向右, 那麼如果訪問的 page 發生了 SMO 操作, 那麼可以查看一下當前 page 是否有 high key, 如果有的話, 那麼說明正在發生 SMO 操作, 那麼如果要訪問的 key 超過了 high key, 那麼就直接去訪問 next node 即可.

對於刪除操作, 和大部分的無鎖算法有點類似, Page 被刪除以後無法確認沒有其他的讀取操作正在讀取該 Page, 因此目前的刪除操作是將當前的 Page 從當前 Btree 中刪除, 然後添加到 garbage collector list 中. 後續有專門的 garbage collector 線程進行 garbage collector 操作.

在 OLFIT 之後, Btree 在 multi-core 場景下的性能問題也越來越熱門, 並且隨着現代 CPU 技術的發展, CPU 上的 core 數會越來越多, 因此該問題會隨着 core 數的增長愈發嚴重. 因此後面又有很多文章對該問題進行了探索, 典型的代表是 Bw-Tree 和 ART Tree.

我們先來看看 ART Tree 怎麼解決這樣的問題.

ART Tree

ART Tree 其實提出了兩個方案

Optimistic Lock Coupling (OLC)
Read-Optimized Write Exclusion (ROWEX)

OLC

OLC 的思想就是從 OLFIT 裏面出來的, 但是 OLFIT 最大的問題在於 page version 一旦進行了修改就需要進行重試, 但是很多時候如果 page 裏面只是增加了數據, 並沒有發生 SMO, 其實是可以不用 retry 的. 所以後續的 masstree, ART tree 都是類似的思路.

另外一個優化是, OLC 可以在同一時刻 snapshot 多個節點, 而 OLFIT 可以認爲同一時刻只能 snapshot 1 個節點的.

比如下圖中, 右邊是 OLC 的流程, OLC 的流程是持有父節點的 version, 然後去遍歷子節點, 此刻最多持有 2 個節點的 version, 當然也可以繼續持有父節點的 version 去遍歷下一個子節點, 這樣持有的 snapshot 就是 3 個, 但是這樣的併發就降低了.

但是這樣 OLC 還是有一個前提, 需要對 page 的修改是 atomic 的, 工程上依然是無法實現的.

工程上無法實現對 page 的 atomic 修改本質原因是當前的修改方案是 Inplace update, 如果可以做 non-inplace update 修改, 那麼就可以做到 atomic 了. bw-tree 和 ROWEX 對 Page 的修改就是這樣的思路, 但是還是有細微的區別. 下面會講到.

ROWEX

ROWEX 稱爲 Read-Optimized Write EXclusion, 也就是 Read 操作不需要加鎖, 甚至不需要讀取版本號, 但是寫操作需要加鎖.

ROWEX 和 RCU 非常像, 讀操作不需要任何加鎖, 寫操作需要加鎖. 由於寫操作不會對老 page 進行修改, 所以讀操作很容易實現 atomic, 但是讀操作需要保證讀取到的是舊版本的數據也能夠處理. 對比 OLC, 讀取到舊版本就要 retry 的行爲, 性能肯定好很多.

ROWEX 改動肯定就比 OLC 大很多了, 並且並不是所有的數據結構都能改成 ROWEX, 因爲需要保證讀操作讀取到老的版本程序的正確性.

那麼 ROWEX 如何解決工程上提到的 page 修改 non-atomic 的問題呢?

通過 Node replacement 的方法, 具體 ROWEX Node replacement 的流程如下:

Both the node and its parent are locked.
A new node of the appropriate type is created and initialized by copying over all entries from the old node.
The location within the parent pointing to the old node is changed to the new node using an atomic store.
The old node is unlocked and marked as obsolete. The parent node is unlocked.

這裏最大的區別是寫入的時候將 node 拷貝出來, 然後在新的 node 上進行改動, parent node 指向 old node 和 new node 的指針通過 atomic cas (這裏保證了修改 content 是 atomic) 進行切換即可. 然後 old node 被標記成 unlocked and obsolete.

與 OLC 區別在於, OLC 一個 Page 只有一個版本, 因此所有的請求都訪問該版本. 而 ROWEX 有多個版本, 在修改 new page 過程中, 老的請求繼續訪問 old page, 等這次修改完成以後, 把 new page cas 到 parent node 之下, 替換 old page. 之後再進來的新請求就可以訪問 new page 了.

最後等這些老的請求都結束了以後, old node 纔會被真的物理刪除.

那麼我們能直接將 ROWEX 用於 InnoDB 中麼?

也很難, 因爲這裏每一次修改都需要 copy node, 開銷還是非常大.

Bw-tree

bw-tree 做法整體而言是 page 多版本, 多個版本通過 delta-chain 連接到一起, 由於 page 存在多個版本, 每次讀取操作訪問的是不同版本 Page, 那麼自然就需要引入了 mapping table. 所以可以說 delta-chain + mapping table 實現無鎖化.

對比 ROWEX, ROWEX 將 node replacement 的方法常態化, 但是對於 page 中每一行的修改都使用 copy node 的做法對內存的開銷太大, 工程中很難採用.

具體做法是將修改的內容 append 到 page delta-chain, 然後通過 cas 的方式原子的添加到 page 的 deltai-chain 中, 從而老版本 page 不會被修改, 那麼讀操作自然就可以不需要加鎖. 由於讀操作不需要加鎖, 那麼自然就不存在讀寫衝突. 同樣由於讀操作不需要加鎖, 那麼” 讀讀” 操作自然也就不會有衝突.

在之前的 OLC/ROWEX 實現中, 依然還是對 page 進行加鎖操作, 因此 write-write 還是衝突的, 而在 bw-tree 通過引入 delta-chain, 改動都是追加到 page delta-chain 中, 因此不同的寫入操作可以也可以通過 cas 的操作順序添加到 delta-chain, 從而也可以將這些操作無鎖化, 所以保證 write-write 操作也是無衝突的.

其實可以看到這裏對於避免 inplace update 的做法, 只有 ROWEX 和 bw-tree 這兩種做法了.

每做一次修改都 copy node, 然後進行修改, 然後再進行 cas 回去. => ROWEX
通過 delta-chain 的方式連接到之前的 node, 然後再進行 cas 回去. => bw-tree

bw-tree 具體實現, 主要兩個主要流程:

正常的數據 append 過程

在 append page 過程, 增加 delta chain 的過程, mapping table 裏面 page id => memory 中 parse buffer 地址

當比如超過 16 個, 進行一次 consolidate 以後, 但是該 page 並沒有進行 smo, 那麼我們的做法是儘可能不去修改 Parent node, 那麼會純生存 new page, 該 page 同樣和 Delta chain 連在一起. 就變成這樣的結構

page id => new page -> delta1 -> delta2 -> delta3 -> oldpage

這裏 new page = delt1 + delt2 + delta3 + oldpage 的內容.

如果進行 consolidate 需要發生 smo 操作, 那麼就不得不修改 parent node, 這個時候會給 page 增加一個 split deltas, 然後合適的實際進行 SMO 操作
smo 過程

bw-tree 的 smo 流程是這樣, 整體而言和 blink-tree 類似, 分成了 2 個階段. 上圖的 a + b 是階段 1(處理子節點), c 是階段 2(添加到父節點).

圖 a 需要計算出 seperate key Kp, 增加 Page Q, 然後將 Page P 上面 >=Kp 的 keys 拷貝到 Page Q, Q 指向 Page R.

注意: 圖 a 階段就已經確定了 seperate key Kp

圖 b 需要增加 split delta, 包含

增加 seperate key Kp, 用來記錄哪些 record 遷移到 Q 上
增加 logic point 指向 Page Q.

最後通過 CAS 操作, 將 Page P 指向 split delta.

階段 1 只處理了 child node, 並沒有把新增加的 Page Q 添加的 Parent node O 上, 和 Blink-tree 類似, 訪問的時候有可能一半的內容已經遷移到 Page Q 了, 但 Page O 上面記錄的範圍還在 Page P 裏面, (因此 Page P 需要有一個信息, 這個信息可以記錄在 Split delta 記錄中), 所以和 Blink tree 類似, 先訪問 Page P, 知道 Page P 處在 SMO 狀態中, 然後通過 Page P 的 link page 到 Page Q.

和 Blink-tree 類似, 階段 1 和階段 2 之前不需要在同一個 mtr 裏面完成, 到階段 1 完成以後, 是一個合法的 Btree. 只不過查詢的時候需要額外多走一個 Page.

階段 2 做的事情就是把 Page Q 添加到父節點 Page O 中.

這裏 Index entry delta 做 3 個事情

Page O 需要增加一個 seperate key, 訪問從 [P, R] 變成 [P, Q] + [Q, R] 兩個, Page Q 負責 [Q, R] 的區間
Page O 需要增加一個 point 指向 Page Q
Page Q 和 Page R 的 seperate key(其實可以複用 Page P 和 Page R, 這個可以忽略)

最後通過 CAS 操作, 將 Page O 指向這個 Index entry delta.

我們來看看這個時候有 Read 操作如何保證正確性, 在圖 a 中時候, 只是增加了 Page Q 對任何操作都是不可見的, 因此沒有問題.

圖 b 增加了 Split delta, Page P + Delta 是最新版本, 這是一次 cas 操作, 完成以後 P ->next = Q. Q->next = R(圖 a 中修改), 那麼此時的訪問依然沒有正確性問題.

如果此刻有一個 mtr 訪問的是 Old Page P(不包含 Delta), 然後訪問 next page, 依然是正確的.

圖 c 同樣通過一個 cas 操作將 Page Q 添加到 Page O 中, 依然沒有正確性問題.

如果這裏 Page P 已經把一半的內容遷移到 Page Q 了, 那麼這個時候 Page P 還有寫入, 這個時候該如何處理?

也就是 SMO 和正常寫入的衝突, 以及 SMO 和 SMO 的衝突.

bw-tree 文章在 C. Serializing Structure Modifications and Updates 講的過程

文章裏面說的是, 對於同一個 row 的修改, 通過事務鎖去保證. 目前 InnoDB 也是這麼做的. 在 lock 模塊就已經衝突了, 就不可能拿到 page latch.

這裏需要處理 SMO 和 SMO 的關係, 以及 SMO 和正常寫入的關係.

因爲 bw-tree 是無鎖的. 所以 SMO 過程中 (階段 1 和階段 2 中間) 比如會穿插正常的查詢和寫入操作, 甚至 SMO 操作.

bw-tree 選擇的操作是, 如果候選的查詢或者寫入遇到了處在 smo 中間狀態的節點, 那麼該操作會幫助完成這次 smo 操作.

原因是如果 Page P 正在做 SMO 期間, 又有寫入操作, 假設寫入的內容應該寫入到遷移完成的 Page Q 上, 因爲 SMO 操作還未完成, 也就是已經完成了圖 a, 確定了 seperate Key Kp, 這個時候其實應該把新的內容寫入到 Page Q 的 delta chain 上, 但是此時該操作是不知道的.

因此 bw-tree 選擇的是 Page P 上標記正在進行 smo 的狀態, 那麼寫入操作幫忙 Page P 完成這次 SMO, 然後等 SMO 結束以後已經知道 Page Q 了, 再把要寫入的內容寫入到 Page Q 上.

bw-tree 爲了解決 write SMO 的時候同時有新的 write 進來的時候, Bw-tree 讓新的 write 完成前面 write SMO 操作, 但是具體工程實現上, 這樣的操作想想就過於複雜, InnoDB 的 btree 需要同時承擔事務鎖相關能力, 更增加了複雜度.

結論

筆者主要站在工業界的視角看學術界如何解決 btree 在 multi-core 場景下的性能問題, 瞭解這些學術界的實現, 看是否對工業界有幫助.

目前看來, 學術界這些新型的數據結構在工程上落地都有一定的難度.

比如 OLFIT 假設讀取一個 page 是 atomic 的, 這個在工程上是無法實現的. 也就是讀取的時候如果有寫入, 雖然後面可以通過版本號判斷是舊的, 但是可能存在的問題是讀取了一半的內容, 那麼使用這一半內容的 MySQL 程序本身就會 corrupt.

比如 ART Tree 通過 copy node 的方式實現 Atomic 修改, 但是這樣拷貝的開銷工程上是無法接受的.

比如 Bw-tree 處理 SMO 的時候如果有 write 操作, SMO 和 SMO 的衝突的解決方案過於複雜等等.

有些方案是 latch-based, 有些方案是 latch-free, 有些是 hybrid, 在工程上我們一般如何考慮呢?

在文章 “Latch-free Synchronization in Database Systems: Silver Bullet or Fool’s Gold?” 給出了比較有意義的結論:

Latch free Algorithm 通常在線程數超過 CPU 核數的場景下, 比 latch-based 的算法要來的好.

In this traditional database system architecture, the progress guarantees of latch-free algorithms are extremely valuable because a preempted context will never block or delay the execution of other contexts in the system (Section 2).

因爲在 latch-based 做法裏面, 當核數比 thread 數多的時候, 有可能當前持有 latch 的 thread 被 CPU 調度出去, 而其他線程被調度執行, 但是因爲在等鎖, 也無法執行, 持有 latch 的 thread 又得不到 cpu, 陷入了死鎖.

在這種場景裏面. latch free 算法有優勢, 因爲 latch free 並沒有一個 thread 持有 latch, 所有 thread 都嘗試樂觀獲得 old value, 然後嘗試更新, 最後再 commit, 如果 commit 之前被 cpu 調度出去, 那麼切回來以後可能 old value 已經被修改了, 僅僅是 commit 失敗而已, 不會影響其他 thread. 所以 cpu 的調度對 latch free 的影響是不大的.

當然這裏的本質原因是操作系統的調度不感知用戶層的信息, 也不可能感知. 持有 Latch thread 和 waiting latch thread 在操作系統眼裏是一樣的.

現在一些新的 im-memory database 一般都採取 latch based 的方法, 儘可能不依賴操作系統的調度.

而 MySQL 正好屬於這種場景, 在大量的併發場景下, 活躍連接遠遠高於 cpu 核數. 所以 latch free 是有意義的.

但是現在新的 Database 比如 in-memory database 都是和 core 綁定, 比如 redis 這種單線程的. 包括 polarstore 也是這樣的設計, 那麼這種場景下, 由於衝突不明顯, 本身設計就考慮了儘可能減少 contention, 所以 latch-based 就更好了. 因爲 latch-based 更簡單, lock-free 需要一些複雜的內存管理解決 ABA, garbage collect 等等問題.

所以作者不建議 database 裏面建議使用 latch-free algorithm, 更建議好好優化 Latch-based algorithm.

最後強調 multi-core 上的 scalability 重點在於減少在 single shared meomry 上面的頻繁操作, 也就是 contention. 而不是在於選擇 latch-free 和 latch-based 的算法. 其實這個觀點也是能理解的, 本質是能通過業務邏輯的設計避免 contention 肯定是最好的.

但是 MySQL 內部其實有一些邏輯避免不了 contention, 比如 lock_sys->mutex, trx_sys->mutx 等等.

另外可以看到實現一個 bw-tree, blink-tree 在學術界的論文裏面是非常簡單的一個事情, 但是 InnoDB 裏面 Page 裏面結合了事務鎖, 併發控制, undo log 等等一系列內容, 所以將 InnoDB 的 btree 修改並穩定到線上其實是比較大工程量的事情, 比如爲了推動 Blink-tree 上線, 筆者就寫了 Inno_space 這樣的工具, 用於如果真的有數據損壞的情況, 對數據進行修復, 爲了前期的灰度, blink-tree 先上線到二級索引等等這樣的工作.

那麼 PolarDB 是如何處理這個問題呢?

References:

[1] Z. Wang, et al., Building A Bw-Tree Takes More Than Just Buzz Words, in SIGMOD, 2018

[2] S.K. Cha, et al., Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems, in VLDB, 2001 (Optional)

[3] G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010 (Optional)

[4] J. Faleiro, et al., Latch-free Synchronization in Database Systems: Silver Bullet or Fool’s Gold?, in CIDR, 2017 (Optional)

[5] J. Levandoski, et al., The Bw-Tree: A B-tree for New Hardware, in ICDE, 2013 (Optional)

[6] V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016 (Optional)

[7] V. Leis, et al., The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, in ICDE, 2013 (Optional)

[8] https://15721.courses.cs.cmu.edu/spring2020/schedule.html

[9] https://zhuanlan.zhihu.com/p/374000358

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UXG9xWCjZ8TWVAd7IZxICQ

背景

OLFIT(Optimistic, Latch-Free Index Traversal CC)

ART Tree

Bw-tree

結論

猜你喜歡