資料組織存儲

我們知道innodb使用btree來進行資料組織存儲，當發生insert/update/delete時，有可能會産生資料空洞，不能有效的利用page的空間。而這些空洞在未來甚至有可能不再被使用到。本文主要記錄了相關的代碼，現有的處理方式，最後介紹了facebook mysql對page碎片的處理方式.

以下簡述下三種操作類型對頁面空間的影響

即時是順序的insert，也可能産生空間浪費，為了保證以後對相同page的更新不會産生page分裂，innodb總是為其保留一部分的剩餘空間.

簡單說一下，對于insert也分兩種情況，直接insert 以及通過更改已有記錄的方式來insert；第一種方式大家可能比較了解；對于第二種方式，假設這種場景：

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.

扯遠了，這裡我們隻讨論第一種方式，在插入記錄時，對于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

假定page最多插入6條記錄

子節點p1有資料(1,2,3,4,5,6)

插入記錄（10），産生分裂新子節點p2(10)

插入記錄（8），尋址到p1，page_last_insert是6，滿足順序插入條件，但p1已滿，産生新子節點p3(8)。

分裂選擇： btr_page_get_split_rec_to_right  btr_page_get_split_rec_to_left

順序插入優化：page_cur_search_with_match.

對于更新操作，有兩種方式，一種是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空間使用率依然會有所降低。

row_upd_clust_step  //更新聚集索引非pk列

row_upd_sec_step   //更新二級索引

btr_cur_del_mark_set_clust_rec

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

row_upd_del_mark_clust_rec

row_upd_sec_index_entry->btr_cur_del_mark_set_sec_rec

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

btr_page_reorganize

當一個page内的記錄數過少時，有可能觸發page合并，當發生悲觀删除一條記錄後，page的記錄數小于1/2 page size時（btr_cur_page_compress_limit）, 可能觸發。

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

btr_cur_compress_if_useful

btr_compress

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鎖的時間。

其大概流程為：

使用者通過alter table tbname defragement [async_commit]發起請求

innodb層(defragment_table)将使用者請求加入一個任務隊列（隊列項為一個已經定位到leaf page的persistent cursor，初始化在第一個葉子節點頁）.對于async_commit，直接傳回，否則進入condition wait.

獨立線程btr_defragment_thread讀取任務隊列，然後開始操作n個page，總是将記錄盡量往左邊的葉子節點頁轉移，當出現空page時，直接從btree删除。

做完一次操作後，如果達到索引末尾，則從任務隊列删除，喚醒等待的使用者線程，否則将item更新後，sleep一段時間，下一輪繼續。