InnoDB btree latch 優化曆程

(一般在資料庫裡面latch 指的是實體Lock, Lock 指的是事務的邏輯lock, 這裡混用)

在InnoDB 的實作中, btree 主要有兩種lock: index lock 和 page lock

index lock 就是整個Index 的lock, 具體在代碼裡面就是 dict_index->lock

page lock 就是我們在btree 裡面每一個page 的變量裡面都會有的 lock

當我們說btree lock的時候, 一般同時包含 index lock 和 page lock 來一起實作

在5.6 的實作裡面比較簡單,btree latch 大概是這樣的流程

1. 如果是一個查詢請求
   • 那麼首先把btree index->lock S LOCK
   • 然後直到找到 leaf node 以後, 對leaft node 也是 S LOCK, 然後把index-> lock 放開

   

2. 如果是一個修改leaf page 請求
   • 同樣把btree index-> lock S LOCK
   • 然後直到找到leaf node 以後, 對leaf node 執行 X LOCK, 因為需要修改這個page. 然後把index->lock 放開. 到這裡又分兩種場景了, 對于這個page 的修改是否會引起 btree 的變化
     • 如果不會, 那麼很好, 對leaf node 執行了X LOCK 以後, 修改完資料傳回就可以
     • 如果會, 那麼需要執行悲觀插入操作, 重新周遊btree.

     對btree inex 加X LOCK, 執行btr_cur_search_to_nth_level 到指定的page.

     因為leaft node 修改, 可能導緻整個沿着leaf node 到root node 的btree 都會随着修改, 是以必須讓其他的線程不能通路到, 是以需要整個btree 加X LOCK, 那麼其他任何的查詢請求都不能通路了, 并且加了index X LOCK 以後, 進行record 插入到page, 甚至可能導緻上一個Level 的page 也需要改變, 這裡需要從磁盤中讀取資料, 是以可能有磁盤IO, 這就導緻了加X LOCK 可能需要很長一段時間, 這段時間sread 相關的操作就都不可通路了

     這裡具體的代碼在 row_ins_clust_index_entry

     首先嘗試樂觀的插入操作

     err = row_ins_clust_index_entry_low(

     0, BTR_MODIFY_LEAF, index, n_uniq, entry, n_ext, thr,
       &page_no, &modify_clock);
                

     然後這裡如果插入失敗, 再嘗試悲觀的插入操作,

     return(row_ins_clust_index_entry_low(

     0, BTR_MODIFY_TREE, index, n_uniq, entry, n_ext, thr,
           &page_no, &modify_clock));
                

     從這裡可以看到, 唯一的差別在于這裡latch_mode = BTR_MODIFY_LEAF 或者 BTR_MODIFY_TREE. 并且由于btr_cur_search_to_nth_level 是在函數 row_ins_clust_index_entry_low 執行, 那麼也就是嘗試了樂觀操作失敗以後, 重新進行悲觀插入的時候, 需要重新周遊btree

     

從上面可以看到, 5.6 裡面隻有對整個btree 的index lock, 以及在btree 上面的leaf node page 會有lock, 但是btree 上面non-leaf node 并沒有 lock.

這樣的實作帶來的好處是代碼實作非常簡單, 但是缺點也很明顯由于在SMO 操作的過程中, 讀取操作也是無法進行的, 并且SMO 操作過程可能有IO 操作, 帶來的性能抖動非常明顯, 我們線上上也經常觀察到這樣的現象.

是以有了官方的改動, 其實這些改動在5.7 就引入, 我們這裡以8.0 為例子:

主要有這兩個改動

1. 引入了sx lock
2. 引入了non-leaf page lock

引入SX Lock 以後

首先介紹一下 SX Lock, SX Lock 在index lock 和 page lock 的時候都可能用到.

SX Lock 是和 S LOCK 不沖突, 但是和 X LOCK 沖突的, SX LOCK 和 SX LOCK 之間是沖突的.

SX LOCK 的意思我有意向要修改這個保護的範圍, 但是現在還沒開始修改, 是以還可以繼續通路, 但是要修改以後, 就無法通路了. 因為我有意向要修改, 是以不能允許其他的改動發生, 是以和 X LOCK 是沖突的.

目前主要用途是标記搜尋路徑上的page sx lock, 當确認需要修改了以後, 見這些page sx lock 轉換成x lock

SX LOCK 的引入由這個 WL 加入

WL#6363

可以認為 SX LOCK 的引入是為了對讀操作更加的優化, SX lock 是和 X lock 沖突, 但是是和 S lock 不沖突的, 将以前需要加X lock 的地方改成了SX lock, 是以對讀取更加友好了

引入non-leaf page lock

其實這也是大部分商業資料庫都是這樣, 除了leaf page 有page lock, non-leaf page 也有page lock.

主要的想法還是 Latch coupling, 在從上到下周遊btree 的過程中, 持有了子節點的page lock 以後, 再把父節點的page lock 放開, 這樣就可以盡可能的減少latch 的範圍. 這樣的實作就必須保證non-leaf page 也必須持有page lock.

不過這裡InnoDB 并未把index->lock 完全去掉, 這就導緻了現在InnoDB 同一時刻仍然隻有同時有一個 BTR_MODIFY_TREE 操作在進行, 進而在激烈并發修改btree 結構的時候, 性能下降明顯.

回到5.6 的問題

可以看到在5.6 裡面, 最差的情況是如果要修改一個btree leaf page, 這個btree leaf page 可能會觸發btree 結構的改變, 那麼這個時候就需要加一整個index X LOCK, 但是其實我們知道有可能這個改動隻影響目前以及上一個level 的btree page, 如果我們能夠縮小LOCK 的範圍, 那麼肯定對并發是有幫助的.

那麼到了8.0

1. • 然後沿着搜尋btree 路徑, 遇到的non-leaf node page 都加 S LOCK
   • 然後直到找到 leaf node 以後, 對leaft node page 也是 S LOCK, 然後把index-> lock 放開

   

2. • 同樣把btree index-> lock S LOCK, 通過對non-leaf node page 都加S LOCK
   • • 如果會, 那麼需要執行悲觀插入操作, 重新周遊btree. 這時候給index->lock 是加 SX LOCK

     因為已經給btree 加上sx lock, 那麼搜尋路徑上的btree 的page 都不需要加 lock, 但是需要把搜尋過程中的page 儲存下來, 最後階段給搜尋路徑上有可能發生結構變化的page 加x lock.

     這樣就保證了在搜尋的過程中, 對于read 操作的影響降到最低.

     隻有在最後階段确定了本次修改btree 結構的範圍, 對可能發生結構變化的page 加X lock 以後, 才會有影響.

     • 8.0 裡面, SMO 操作過程中, 拿着sx lock 的持續時間是

     持有sx lock 的時間:

     第一次btr_cur_optimistic_insert insert 失敗以後, 在 row_ins_clust_index_entry 會調用

     row_ins_clust_index_entry_low(flags, BTR_MODIFY_TREE ...) 進行插入, 在 row_ins_clust_index_entry_low 裡面, 在btr_cur_search_to_nth_level 函數裡面加上 sx lock, 到這裡btree 因為已經加了sx lock, 就已經無法進行smo 操作了, 然後接下來仍然會嘗試先樂觀插入,這個時候sx lock 依然持有, 失敗的話, 再嘗試悲觀插入操作.

     釋放sx lock 的時間:

     在悲觀插入操作裡面會一直持有sx lock, 直到在 btr_page_split_and_insert 内部, 将新的page2 已經産生, 同時page2 已經連接配接上father node 之後. 并且這次發生SMO 的page 還需要是leaf page, 否則一直持有sx lock, 直到SMO 操作完成, 并且insert 成功才會釋放

     

     具體執行SMO 操作并且insert 的函數是 btr_page_split_and_insert

     btr_page_split_and_insert 操作大概有8個流程:

     1. 從要分裂的page 中, 找到要split 的record, split 的時候要保證split 的位置是record 的邊界
     2. 配置設定一個新的索引頁
     3. 分别計算page, 和new_page 的邊界record
     4. 在上一級索引頁(父節點)添加新的索引頁的索引項, 如果上一級沒有足夠的空間, 那麼就觸發父節點的分裂操作了
     5. 連接配接目前索引頁, 目前索引頁prev_page, next_page, father_page, 新建立的 page. 目前的連接配接順序是先連接配接父節點, 然後是prev_page/next_page, 最後是 page 和 new_page (在這一步結束之後就可以放開index->sx lock)
     6. 将目前索引頁上的部分Record 移動到新的索引頁
     7. SMO 操作已經結束, 計算本次insert 要插入的page 位置
     8. 進行insert 操作, 如果insert 失敗, 通過reorgination page 重新嘗試插入

現有代碼裡面隻有一個場景會對index->lock X lock. 也就是

if (lock_intention == BTR_INTENTION_DELETE &&
      trx_sys->rseg_history_len > BTR_CUR_FINE_HISTORY_LENGTH &&
      buf_get_n_pending_read_ios()) {           

如果這次lock_intention 是BTR_INTENTION_DELETE, 并且history list 過長, 才會對 index 加 x lock

總結:

8.0 比5.6 改進的地方

在5.6 裡面, 寫入的時候, 如果有SMO 在進行, 那麼就需要把整個index->lock x lock, 那麼在SMO 期間所有的read 操作也是無法進行的.

在8.0 裡面SMO 操作的過程中是允許有read 和 樂觀寫入操作的.

但是8.0 裡面還有一個限制就是同一時刻隻能有一個SMO 正在進行, 因為SMO 的時候需要拿 sx lock. sx lock 和 sx lock 是沖突的, 這也是目前8.0 主要問題.

優化點

當然這裡還是有優化點.

1. 依然有全局的index->lock, 雖然是sx lock, 但是理論上按照8.0 的實作, 可以完全将index lock 放開, 當然很多細節需要處理
2. 在執行具體的分裂操作過程中, btr_page_split_and_insert 裡面的持有index lock 是否還可以優化?
   • 比如按照一定的順序的話, 是否将新建立page 連接配接到new_page 以後就可以放開index->lock

• 還可以考慮發生SMO 的page 持有x lock 的時間.

  目前會持有整個路徑上的page x lock 直到SMO 操作結束, 并且這次insert 完成, 同時需要一直持有fater_page, prev_page, next_page 的x lock, 是否可以減少持有page 的個數, 比如這個優化

  BUG#99948

• btr_attach_half_pages 中多次通過btr_cur_search_to_nth_level 周遊btree 操作是否可以避免?

  函數是将father link, prev link, next link 等建立好的操作

  在這裡會重新執行一次 btr_page_get_father_block 對btree 進行周遊找到父節點, 在該函數裡面有需要重新執行 btr_cur_search_to_nth_level 函數, 其實這一步操作是可以避免的.

  因為這時index已經 sx lock 了, father 肯定不會變了的, 那麼可以将上次btr_cur_search_to_nth_level 的結果保留, 就可以獲得

• 是否可以像b-link tree 類似, 給正在SMO 的page 标記狀态, 這個狀态是允許讀取的, 隻不過有可能存在要讀取的record 不在目前的page, 那麼就需要去該page->next page 去嘗試讀取, 如果能讀取到依然是可以的..

1. 每次進行btr_cur_search_to_nth_level, 搜尋路徑中遇到的page 是否可以保留? 這樣即使重複搜尋, 隻需要确定upper level page 的max trx_id, 則可以确定整個搜尋路徑都沒有改變, 那麼就不需要重新周遊.
2. 是否還需要保留先樂觀insert 再悲觀insert 的操作過程?

我了解現有的流程是因為在5.6 的實作中, 悲觀insert 操作的開銷太大, 進而盡可能的避免悲觀insert, 是以沿用到了目前的8.0 實作中.這種多次insert 需要多次周遊btree, 帶來額外開銷

talking

https://dom.as/2011/07/03/innodb-index-lock/ https://dev.mysql.com/worklog/task/?id=6326