Facebook MySQL: 索引線上碎片整理特性

我們知道innodb使用btree來進行資料組織存儲，當發生insert/update/delete時，有可能會産生資料s碎片，不能有效的利用page空間。而這些空洞在未來甚至有可能不再被使用到。即使是順序的insert，也可能産生空間浪費：為了保證以後對相同page的更新不會産生page分裂，innodb總是為其保留一部分的剩餘空間。

本文是對之前寫的這篇部落格的整理和補充（http://mysqllover.com/?p=1014）

對于insert也分兩種情況，直接insert 以及通過更改已有記錄的方式來insert；第一種方式大家可能比較了解；

對于第一種方式，在插入記錄時，對于page 内資料大小是有個硬限制的：

從btr_cur_optimistic_insert函數截取的代碼：

1399         /* if there have been many consecutive inserts to the 1400         clustered index leaf page of an uncompressed table, check if 1401         we have to split the page to reserve enough free space for 1402         future updates of records. */ 1403 1404         if (leaf && !zip_size && dict_index_is_clust(index) 1405             && page_get_n_recs(page) >= 2 1406             && dict_index_get_space_reserve() + rec_size > max_size 1407             && (btr_page_get_split_rec_to_right(cursor, &dummy) 1408                 || btr_page_get_split_rec_to_left(cursor, &dummy))) { 1409                 goto fail; 1410         }

dict_index_get_space_reserve函數的傳回值是十六分之一的page size，也就是說插入新記錄後，留餘的空閑空間不能小于這個1/16 *page size，預設16k配置下，就是1k。

說到insert，就不得不提一個bug#67718，以主鍵逆序的方式插入記錄可能導緻索引分裂非常頻繁。感興趣的可以看看 bug傳送門： http://bugs.mysql.com/bug.php?id=67718：

假定page最多插入6條記錄 子節點p1有資料(1,2,3,4,5,6) 插入記錄（10），産生分裂新子節點p2(10) 插入記錄（8），尋址到p1，page_last_insert是6，滿足順序插入條件，但p1已滿，産生新子節點p3(8)。

這個bug已經在最新版本中被fix掉了（5.6.21 及5.7.5）。

對于第二種插入方式，假設這種場景：

create table t1 (a int, b int, c int, primary key(a,b)); insert into t1 (1,2,3); delete from t1; insert into t1 (1,2,6);

mysql使用标記删除的方式來删除記錄，如果delete和再次insert中間的間隔足夠小，purge線程還沒來得及清理該記錄時，新插入的(1,2,6)就會沿用之前的記錄，因為他們主鍵是相同的。

參考函數：row_ins_must_modify_rec、row_ins_clust_index_entry_by_modify

insert by modify的方式是，先将原記錄的delete标記清楚，然後再對該記錄做update。

對于更新操作，有兩種方式，一種是in-place更新，另一種是先标記删除再插入新記錄的方式。更新的順序是總是先更新聚集索引，再更新二級索引。

對于二級索引記錄更新，總是先标記删除再插入新記錄。對于聚集索引，這兩種情況都存在。例如如果沒有改變記錄大小（row_upd_changes_field_size_or_external），就直接in-place更新了（btr_cur_update_in_place），否則在代碼邏輯上，總是先删除（page_cur_delete_rec）再插入記錄（btr_cur_insert_if_possible），如果主鍵未變，則沿用其之前的聚集索引記錄所在的位置，注意盡管主鍵不變，但如果記錄長度變小了，依然會在page内産生碎片

如果更新的是聚集索引記錄，引起索引順序發生變化，則采用标記删除+插入（row_upd_clust_rec_by_insert）

很顯然頻繁的update可能會導緻空間膨脹，尤其是當二級索引比較多的時候。當然purge線程可以去回收被标記删除的空間，但page空間使用率依然會有所降低。

實際上删除操作和update操作走類似的接口函數row_update_for_mysql，隻是将prebuilt->upd_node->is_delete設定為true來進行區分。使用标記删除的方式。

innodb在特定情況下會主動去嘗試合并page，主要包含以下幾個調用棧

btr_compress btr_node_ptr_delete btr_cur_pessimistic_update btr_cur_pessimistic_delete             |—->btr_cur_compress_if_useful                        |—->btr_compress

上述調用棧，都是在做完悲觀delete或update後嘗試合并page。在滿足如下條件時會去嘗試合并(函數btr_cur_compress_recommendation)：

# 非root page

# page内的資料小于page size的二分之一（btr_cur_page_compress_limit）；

# 如果是目前level唯一的一個page，需要上提到父節點(btr_lift_page_up)

早期有個bug#68501，innodb在确定合并的page是左節點還是右節點時，總是先嘗試左節點，如果左節點是可用的，但是合并失敗時，沒有去再次嘗試右節點頁。在做逆序删除操作時，可能導緻大量btr_compress失敗，引起ibd空間無法有效收縮。

oracle mysql 在5.6.13版本fix了這個問題，當合并左節點失敗時，會再次嘗試右節點，具體可以浏覽更新檔rev:4384

當page内的最大可用空間不滿足記錄插入時，可能會觸發page内的資料重組（btr_page_reorganize）。即使空閑空間滿足插入記錄，還有一個硬限制來進行重組，即page大小的32分之一(btr_cur_page_reorganize_limit)。

相關堆棧：

btr_can_merge_with_page |—->btr_page_reorganize_block          |—->btr_page_reorganize_low btr_page_split_and_insert btr_cur_insert_if_possible btr_cur_optimistic_insert btr_cur_update_alloc_zip_func ibuf_insert_to_index_page_low |—->btr_page_reorganize page_cur_insert_rec_zip |—–>btr_page_reorganize_low

頁内重組的流程大概如下：

從bufferpool重配置設定一個新的block，并将page内的資料都拷貝進去。

重新初始化頁面 （page整個frame被寫redo了，是以可以崩潰恢複)

從step 1産生的臨時block中将記錄一個個拷貝到重初始化過後的page

對于壓縮表，會做一次重壓縮

從代碼來看，拷貝過程中并沒有去移除标記删除的記錄。是以這個重組織做的并不徹底。

optimize table、alter table tbname engine=innodb (mysql 5.6.17及之後已經開始支援online)

dump/restore 資料集

fb的實作中，引入了一個獨立的線程(btr_defragment_thread)來專門做碎片整理，每次從葉子節點開始，持有索引x鎖，每整理n個page後釋放鎖，然後再繼續執行。可以指定做defragement操作的索引是聚集索引還是二級索引。一次處理最多不超過32個page，以降低持有索引x鎖的時間。

以下基于webscalesql-5.6.21.55分析

defragment:           defragment_sym index_defragmentation opt_async_commit           {             thd *thd= yythd;             lex->m_sql_cmd= new (thd->mem_root)               sql_cmd_defragment_table();             if (lex->m_sql_cmd == null)               mysql_yyabort;           }

從文法可以看到，支援對特定索引做defragement操作，支援異步/同步傳回

sql_cmd_defragment_table類：

class sql_cmd_defragment_table : public sql_cmd_common_alter_table { public:   sql_cmd_defragment_table()   {}   ~sql_cmd_defragment_table()   bool execute(thd *thd); };

bool sql_cmd_defragment_table::execute(thd *thd) : 436   int ret = handler->ha_defragment_table(path, index.str, 437                                          thd->lex->async_commit);

在完成必要的mdl加鎖後，調用存儲引擎接口，也就是ha_innobase::defragment_table

根據要做defragment的表名和索引名，首先檢查是否已經在工作隊列(btr_defragment_wq)中（btr_defragment_find_index(index)），如果不在，則傳回錯誤，否則加入工作隊列中（btr_defragment_add_index(index, async)）

如果sql指定的async操作，則直接傳回，否則需要等待defragment操作完成。如果在等待的過程中線程被kill了，就将這個任務标記為removed，然後傳回。

将item加入工作隊列時，初始化一個cursor，定位在b-tree 葉子節點的第一個page的第一個記錄:

        btr_pcur_t* pcur = btr_pcur_create_for_mysql();         os_event_t event = null;         if (!async) {                 event = os_event_create();         }         btr_pcur_open_at_index_side(true, index, btr_search_leaf, pcur,                                     true, 0, &mtr);         btr_pcur_move_to_next(pcur, &mtr);         btr_pcur_store_position(pcur, &mtr);         mtr_commit(&mtr);

背景開啟一個線程，專門做defragment操作，入口函數為btr_defragment_thread.

defragement 線程的設計大概如下：

1. defragment線程負責清理工作隊列中被标記為removed的item，或者在item工作完成時移除，使用者線程隻負責插入。

2. 可配置做defragment的操作頻度，避免給系統帶來太大的負載

3. 因為每次defragment操作都需要鎖索引鎖，是以為了平衡負載，對每個item（對應一個索引）的操作也不是一次完成的，而是一次完成srv_defragment_n_pages（可配置）個page後，記錄下目前的cursor ,下一輪繼續，但一輪最多不超過32個page：

      儲存cursor

                        page_t* last_page = buf_block_get_frame(last_block);                         rec_t* rec = page_rec_get_prev(                                 page_get_supremum_rec(last_page));                         ut_a(page_rec_is_user_rec(rec));                         page_cur_position(rec, last_block,                                           btr_cur_get_page_cur(cursor));                         btr_pcur_store_position(pcur, &mtr);                        mtr_commit(&mtr);

大概流程如下：

1. 讀入這n個page；并計算這些page中存儲的總的資料長度(total_data_size)和記錄數(total_n_recs)

如果目前level隻有一個page的話，上提到父節點(btr_lift_page_up(index, block, mtr))

2. 計算可縮減的空間量

data_size_per_rec = total_data_size / total_n_recs; optimal_page_size = page_get_free_space_of_empty(page_is_comp(first_page)); （對于壓縮表，optimal_page_size是根據壓縮失敗時的page使用率來估算，索引對象上維持了一個stat_defrag_data_size_sample數組，用于記錄采樣值） reserved_space = min((ulint)(optimal_page_size                               * (1 – srv_defragment_fill_factor)),                              (data_size_per_rec                               * srv_defragment_fill_factor_n_recs));  //每個page的保留白間

有兩個factor可以用于控制保留白間數，按照記錄數保留或按照page百分比保留；srv_defragment_fill_factor預設為20；srv_defragment_fill_factor_n_recs預設為20;

optimal_page_size -= reserved_space; n_new_slots = (total_data_size + optimal_page_size – 1)                       / optimal_page_size;  //優化後需要的page數 如果計算後的n_new_slots 比目前的page數還多，則無需整理，直接傳回。

從第二個page開始，向前面的page中開始merge記錄。

        for (uint i = 1; i < n_pages; i ++) {                 buf_block_t* new_block = btr_defragment_merge_pages(                         index, blocks[i], current_block, zip_size,                         reserved_space, &max_data_size, heap, mtr);                 if (new_block != current_block) {                         n_defragmented ++;                         current_block = new_block;                 }

btr_defragment_merge_pages函數處理page間的記錄合并:

a. 計算能裝載的空間大小，并據此記錄可移動的記錄數；

b. 如果可用空間可能不足，會嘗試做一次頁面重組(btr_page_reorganize_block)；

c. 然後開始一個記錄，一個記錄的轉移 （page_copy_rec_list_start）

d. 如果整個page都搬空了，則釋放該page，加入到空閑連結清單中：

470                 lock_update_merge_left(to_block, orig_pred, 471                                        from_block); 472                 btr_search_drop_page_hash_index(from_block); 473                 btr_level_list_remove(space, zip_size, from_page, 474                                       index, mtr); 475                 btr_node_ptr_delete(index, from_block, mtr); 476                 btr_blob_dbg_remove(from_page, index, 477                                     “btr_defragment_n_pages”); 478                 btr_page_free(index, from_block, mtr);

e. 否則，删除page中已被merge到目标page的記錄，更新行鎖，ibuf，父節點指針。同時目前page作為下一輪merge的目标塊。

這中間也有很多特殊處理，比如對壓縮表的處理，感興趣的自行翻代碼。

該特性的好處是：能夠實作線上defragment，提升innodb索引的使用率，被釋放出來的空間将會被重用，進而降低碎片化，提升空間使用率，最終達到節約存儲空間的目的。