介紹

change buffer（在 MySQL 5.6 之前叫 insert buffer，簡稱 ibuf ）是 InnoDB 5.5 引入的一種優化政策，若二級索引頁不在 buffer pool 中，則将針對二級索引頁的操作暫時緩存起來，等到該頁從磁盤讀到 buffer pool 中時再批量的（batch）apply 這些操作，進而達到減少磁盤 I/O 的目的。具體一點就是：

事務 1 執行寫操作（e.g update），但針對的二級索引頁 P1 并不在 buffer pool 中
于是 client 1 将這個操作緩存到 change buffer 裡，即添加一個 entry（ibuf insert）
事務 2 需要讀操作，将 P1 讀到 buffer pool 中
将 change buffer 裡相關的緩存的操作全部合并（merge）至 P1（ibuf merge）
将 P1 傳回給使用者線程

為什麼必須是二級索引頁，不能是主鍵索引頁？很簡單，因為主鍵索引要保證唯一性的限制，如果把 insert id=1 緩存起來，再次有要 insert id=1 時再緩存起來，則等批量的 apply 時就會出錯。change buffer 緩存的操作有三種：

BTR_INSERT_OP：普通的 insert
BTR_DELMARK_OP：在使用者線程執行 update 和 delete 中，如果發生資料删除行為，會将記錄标記為 delete mark
BTR_DELETE_OP：purge 線程删除二級索引中 delete mark 的資料行

組織形式（B-tree）

change buffer 本質是一塊寫緩存，組織形式是 B-tree，存在于系統表空間中。其根節點位于系統表空間的第四頁面（FSP_IBUF_TREE_ROOT_PAGE_NO）

ibuf entry layout

其緩存的每一個操作叫做一個 entry，實體結構是（詳見 ibuf_entry_build）：

IBUF_REC_FIELD_SPACE：對應二級索引頁的 space id
IBUF_REC_FIELD_MARKER：用于區分新舊版本的 entry 格式，目前預設值為 0
IBUF_REC_FIELD_PAGE_NO：對應二級索引頁的 page no
IBUF_REC_OFFSET_COUNTER：對于同一個二級索引頁，其 entry 的遞增序号（非單調遞增，詳見下文）
IBUF_REC_OFFSET_TYPE：緩存的操作的類型，IBUF_OP_INSERT / IBUF_OP_DELETE_MARK / IBUF_OP_DELETE
IBUF_REC_OFFSET_FLAGS：待操作的使用者記錄格式，REDUNDANT / COMPACT
IBUF_REC_FIELD_USER：使用者記錄

ibuf entry counter

ibuf entry counter 的存在是為了與 space_id 和 page_no 一起構成 entry 的主鍵，在 change buffer 裡對于同一二級索引頁的 entry，其 entry counter 是遞增的

在 change buffer 中插入 entry 時，先定位到待插入的位置（btr_pcur_open）：

search tuple: （space_id, page_no, 0xFFFF）為主鍵
mode PAGE_CUR_LE（<=）模式搜尋 B-tree
latch_mode 是 BTR_MODIFY_PREV 或 BTR_MODIFY_TREE

0xFFFF 是最大的 entry counter（IBUF_REC_OFFSET_COUNTER 域為兩個位元組），是以 cursor 會定位到對應于同一二級索引頁的具有最大 counter 的 entry，記為 max_counter。max_counter+1 即為待插入 entry 的 counter。

但在每一次 ibuf merge ，清空了該二級索引頁的所有 entry 後，再插入針對該索引頁的新的 ibuf entry，counter 又從 0 開始

Change Buffer 的限制：不能引起 index SMO

需要注意的是如果一個操作可能引起二級索引頁的 SMO，則該操作不能緩存在 change buffer 中。這個限制可以了解，比如針對二級索引頁P1 緩存了三個 entry：entry1 / entry2 / entry3，在 ibuf merge 時，如果 entry2 使得 P1 發生分裂，那麼 entry3 無法正确的 merge 至分裂後的 P1。是以 change buffer 在緩存新的操作時，新的操作不能引發這兩種情況發生：

索引頁的空間被填滿（索引頁分裂）
索引頁内隻剩下一條記錄（索引頁合并）

追蹤每個頁的剩餘空間

如何得知一個操作是否會引起二級索引頁的溢出？這需要我們追蹤每個頁的剩餘空間。通過 ibuf bitmap page 來實作（Skywalker：InnoDB：Tablespace management（1）），ibuf bitmap page 用 4 bits 描述每個頁：

IBUF_BITMAP_FREE（2 bits）：描述頁的空閑空間範圍
IBUF_BITMAP_BUFFERED（1 bit）：ibuf 中是否緩存着這個頁的操作
IBUF_BITMAP_IBUF（1 bit）：該頁是否是 ibuf B-tree 的節點

IBUF_BITMAP_FREE 2 bits 的計算方式是：

UNIV_INLINE
ulint ibuf_index_page_calc_free_bits(ulint page_size, ulint max_ins_size) {
  // max_ins_size 是這個頁中目前的全部剩餘空間，IBUF_PAGE_SIZE_PER_FREE_SPACE 是 32
  // page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE 就是 512 bytes，可以看出這裡隻是粗糙
  // 的統計 max_ins_size 是 512 bytes 的幾倍，max_ins_size / 512：
  //  - 大于 3（max_ins_size > 2048）：IBUF_BITMAP_FREE 記錄 3
  //  - 3（1536 < max_ins_size < 2048）：IBUF_BITMAP_FREE 記錄 3
  //  - 2（1024 < max_ins_size < 1536）：IBUF_BITMAP_FREE 記錄 2
  //  - 1（512  < max_ins_size < 1024）：IBUF_BITMAP_FREE 記錄 1
  //  - 0（max_ins_size < 512）：IBUF_BITMAP_FREE 記錄 0
  n = max_ins_size / (page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE);


  if (n == 3) {
    n = 2;
  }


  if (n > 3) {
    n = 3;
  }


  return (n);
}

在每次 insert / update / delete 後會更新 IBUF_BITMAP_FREE（ibuf_update_free_bits_if_full / ibuf_update_free_bits_low）。

防止頁的分裂

隻有在緩存 IBUF_OP_INSERT 時才需要防止頁的分裂發生。這裡涉及到一個函數 ibuf_get_volume_buffered。該函數用于計算對于特定的二級索引頁（設為 P1 ），change buffer 裡緩存的操作 merge 完會導緻此頁增長的資料量是多少（affect the available space on the page），然後與該頁的剩餘空間做比較。因為 IBUF_BITMAP_FREE 最大就是 3，可見能緩存的操作最多隻能占用 2048 bytes。

首先把 pcur 在 ibuf B-tree 中定位到緩存的關于 P1 的最大的 ibuf record。采用的依然是 B-tree 的函數，search tuple 是（ P1 space id， P1 page no，0xFFFF），search mode 是 PAGE_CUR_LE，latch mode 是 BTR_MODIFY_PREV（x-latch 左兄弟節點和目前節點）或 BTR_MODIFY_TREE（x-latch 左兄弟節點、目前節點和右兄弟節點）。定位完成 pcur 指向之後從 pcur 開始：

首先逆向搜尋，直至得到的 ibuf entry 不再是關于 P1。若直到左兄弟節點的 infimum record 還未停止，則放棄（根據 latch order，無法再 latch 左兄弟的左兄弟）
然後正向搜尋，直至得到的 ibuf entry 不再是關于 P1。若直到右兄弟節點的 supremum record 還未停止，則放棄（認為緩存的操作足夠多了，會引起 P1 的分裂）

放棄的意思是認為 change buffer 緩存的操作已經夠多了，不能再緩存了。

ibuf_insert_low {
  ...
  /* Find out the volume of already buffered inserts for the same index
  page */
  min_n_recs = 0;
  buffered = ibuf_get_volume_buffered(&pcur,
    page_id.space(),
    page_id.page_no(),
    op == IBUF_OP_DELETE? &min_n_recs: NULL, &mtr);




  if (op == IBUF_OP_INSERT) {
    ulint  bits = ibuf_bitmap_page_get_bits(
    bitmap_page, page_id, page_size, IBUF_BITMAP_FREE,
    &bitmap_mtr);


    // 若 ibuf_get_volume_buffered 傳回 UNIV_PAGE_SIZE，那麼 if 裡一定是 TRUE
    if (buffered + entry_size + page_dir_calc_reserved_space(1) >
      // 根據 IBUF_FREE_BITS 計算 Page 内的剩餘空間，0 / 512 / 1024 / 2048 Bytes
      // change buffer 裡緩存的針對 Page X 的最大容量不能超過 2048 Bytes 
      ibuf_index_page_calc_free_from_bits(page_size, bits)) {
      /* Release the bitmap page latch early. */
      ibuf_mtr_commit(&bitmap_mtr);


      /* It may not fit */
      do_merge = TRUE;


      ibuf_get_merge_page_nos(FALSE, btr_pcur_get_rec(&pcur), &mtr,
       space_ids, page_nos, &n_stored);
      goto fail_exit;
    }
  }
}

在上述正向 / 逆向周遊的過程中，對于每一個 ibuf entry，計算其對于二級索引頁 Px 的可能占用的空間（ibuf_get_volume_buffered_count），并累加該值。計算方式依據 ibuf entry type，如果是 IBUF_OP_DELETE_MARK 則無影響，若是 IBUF_OP_INSERT 則會計算其可能占據的空間。

...
ut_ad(ibuf_op == IBUF_OP_INSERT);


get_volume_comp : {
  dtuple_t *entry;
  ulint volume;
  dict_index_t *dummy_index;
  mem_heap_t *heap = mem_heap_create(500);


  entry = ibuf_build_entry_from_ibuf_rec(mtr, rec, heap, &dummy_index);


  volume = rec_get_converted_size(dummy_index, entry, 0);


  ibuf_dummy_index_free(dummy_index);
  mem_heap_free(heap);


  return (volume + page_dir_calc_reserved_space(1));
}

防止頁的合并

這裡需要計算 apply 完 change buffer 裡的緩存，該索引頁的剩餘記錄是多少。依然通過函數 ibuf_get_volume_buffered_count，以參數 n_rec 傳遞出來。

static ulint ibuf_get_volume_buffered(
...
lint *n_recs,           /*!< in/out: minimum number of records on the
                            page after the buffered changes have been
                            applied, or NULL to disable the counting */
)

計算方式就是遇到 IBUF_OP_DELETE 就把 n_recs --，遇到 IBUF_OP_INSERT或 IBUF_OP_DELETE_MARK 要注意：

ibuf entry 中的 user data 在 hashtable 中若沒找到，說明這個 user data 是第一次遇到，插到 hashtable 中并把 n_recs ++。原因如下是：

Inserts can be done by updating a delete-marked record. Because delete-mark and insert operations can be pointing to the same records,
we must not count duplicates.

如果要緩存的操作是 IBUF_OP_DELETE 且 n_recs < 2，說明這個操作可能導緻頁面變空，則不緩存到 ibuf 中。

Change Buffer 的寫流程

當需要把一個關于二級索引頁 P1 的操作緩存在 change buffer 中時，分為四步：

構造 ibuf entry，暫時以（P1 space id, P1 page no, 0xFFFF）為主鍵，注：0xFFFF 是最大的 ibuf entry counter
以 PAGE_CUR_LE 模式搜尋 ibuf B-Tree，cursor 最終會落在關于 P1 的最有最大 ibuf entry counter 的 ibuf entry 上，把該 counter + 1 作為新的 counter
更新第一步中構造的 ibuf entry 中的 IBUF_REC_OFFSET_COUNTER 為新的 counter
調用 B-Tree 通用的 API 函數（btr_cur_optimistic_insert/btr_cur_pessimistic_insert）把 ibuf entry插入到 ibuf B-Tree 中

緩存 purge 操作的特殊性

change buffer 會緩存三種操作：insert / delete mark / delete，前兩種是使用者事務的操作，最後一種是 purge 線程的操作。

首先我們需要知道在準備 purge 一個二級索引記錄之前，均會判斷這個記錄是否可以被删除（row_purge_del_mark -> row_purge_remove_sec_if_poss）。拿到該二級索引記錄中儲存的主鍵，找到主鍵索引記錄（row_search_index_entry），如果該主鍵索引記錄存在某個 old version 滿足下述三點，則該二級索引記錄不能被删除（row_purge_poss_sec）：

old version 不是 delete mark
old version 的 ROW_TRX_ID 大于 purge view，即可能被活躍的 reader 通路
old version 與該二級索引記錄的主鍵和二級索引列均相同

這三點表示主鍵索引還存在可能還需要被通路的舊版本，并且可能通過該二級索引記錄檢索，是以不能被 purge。

但如果使用 change buffer，上述的檢查是不夠的。比如這個場景：

使用者線程：delete mark (1, A)，然後資料頁被淘汰出 buffer pool ...
purge 線程：delete (1, A) ；通過 row_purge_poss_sec 的檢查，因為新的 (1, A) 在下一步才會出現。準備把操作緩存到 change buffer
使用者線程：insert (1, A)，準備把操作緩存到 change buffer
先把 insert (1, A) 緩存到 change buffer
再把 delete (1, A) 緩存到 change buffer

在 merge 的時候 insert (1, A) 可能會重用原來被 delete mark 的記錄 (1, A)，即 "delete unmark"；導緻 purge 直接删除 (1, A) 後，相當于事務 insert (1, A) 丢失。

解決的辦法很簡單，當發現有 purge 線程準備緩存操作到 change buffer 中時，第 4 步中放棄緩存 insert。那麼怎麼發現 purge 線程準備緩存操作到 change buffer？首先在 buffer pool 中儲存着這樣一些 buf_block_t 結構體，它們不在 buffer chunk 中而是單獨的記憶體區域，即 buf_pool->watch 數組，buf_block_t::state 初始狀态是 BUF_BLOCK_POOL_WATCH。然後：

當 purge 線程從 buffer pool 中拿索引頁時，如果不在，則在 buf_pool->watch 申請一個空閑的 buf_block_t，并設定其 page_id，還有 state 為 BUF_BLOCK_ZIP_PAG，并放到 page_hash 中。

bpage->state = BUF_BLOCK_ZIP_PAGE;
bpage->id = page_id;
bpage->buf_fix_count = 1;


ut_d(bpage->in_page_hash = TRUE);
HASH_INSERT(buf_page_t, hash, buf_pool->page_hash,
    page_id.fold(), bpage);

這樣的話在第 4 步再去檢查這個頁是否被設定為 watch，即在 buf_pool->watch 數組中（buf_page_get_also_watch），如果是的話直接放棄。

作者:騰訊資料庫技術

來源:微信公衆号:騰訊資料庫技術

出處:https://mp.weixin.qq.com/s/U3MrgLil3tLkH75LGILAJA

InnoDB 的 Change Buffer

介紹

組織形式（B-tree）

ibuf entry layout

Change Buffer 的限制：不能引起 index SMO

追蹤每個頁的剩餘空間

防止頁的分裂

防止頁的合并

Change Buffer 的寫流程

緩存 purge 操作的特殊性

繼續閱讀

MySQL的varchar存儲原理：InnoDB記錄存儲結構

「資料庫」MySQL 的 varchar 存儲原理：InnoDB 記錄存儲結構

InnoDB存儲引擎的特點：行級鎖

故障分析 | innodb_thread_concurrency 導緻資料庫異常的問題分析

MyISAM 與 InnoDB 索引的差別有哪些？

基于對古羅馬複合柱曆史的研究複合柱是羅馬設計的柱式，結合了古希臘時代愛奧尼亞柱和科林斯柱的特點。複合柱具有高度裝飾的首都

mysql的innodb引擎是如何存儲資料的?

「資料庫」庖丁解InnoDB之REDO LOG

「資料庫」庖丁解InnoDB之UNDO LOG

MySQL InnoDB 行記錄存儲結構分析

「資料庫」庖丁解 InnoDB 之存儲結構

利用Inno Setup在VS編譯時自動建構安裝包

Mysql存儲-InnoDB關鍵特性

InnoDB緩沖池揭秘：MySQL中的資料緩存利器

揭秘InnoDB插入緩沖：提升非唯一輔助索引插入性能的秘密武器

InnoDB中的各種鎖及其應用