347
MySQL · 引擎特性 · InnoDB Adaptive hash index介紹
前言
我們知道InnoDB的索引組織結構為Btree。通常情況下，我們需要根據查詢條件，從根節點開始尋路到葉子節點，找到滿足條件的記錄。為了減少尋路開銷，InnoDB本身做了幾點優化。
首先，對於連續記錄掃描，InnoDB在滿足比較嚴格的條件時采用row cache的方式連續讀取8條記錄（並將記錄格式轉換成MySQL Format），存儲在線程私有的row_prebuilt_t::fetch_cache中；這樣一次尋路就可以獲取多條記錄，在server層處理完一條記錄後，可以直接從cache中取數據而無需再次尋路，直到cache中數據取完，再進行下一輪。
另一種方式是，當一次進入InnoDB層獲得數據後，在返回server層前，當前在btree上的cursor會被暫時存儲到row_prebuilt_t::pcur中，當再次返回Innodb層撈數據時，如果對應的Block沒有發生任何修改，則可以繼續沿用之前存儲的cursor，無需重新定位。
上麵這兩種方式都是為了減少了重新尋路的次數，而對於一次尋路的開銷，則使用Adaptive hash index來解決。AHI是一個內存結構，嚴格來說不是傳統意義上的索引，可以把它理解為建立在BTREE索引上的“索引”。
本文代碼分析基於MySQL 5.7.7-rc，描述的邏輯適用於5.7.7之前及5.6版本。但在即將發布的MySQL-5.7.8版本中， InnoDB根據索引id對AHI進行了分區處理，以此來降低btr_search_latch讀寫鎖競爭，由於尚未發布，本文暫不覆蓋相關內容。
我們以一個幹淨啟動的實例作為起點，分析下如何進行AHI構建的過程。
初始化
AHI在內存中表現就是一個普通的哈希表對象，存儲在btr_search_sys_t::hash_index中，對AHI的查刪改操作都是通過一個全局讀寫鎖btr_search_latch來保護。
在實例啟動，完成buffer pool初始化後，會初始化AHI子係統相關對象，並分配AHI內存，大小為buffer pool的1/64。
參考函數：btr_search_sys_create
Tips：由於MySQL 5.7已經開始支持InnoDB buffer pool的動態調整，其策略是buffer pool的大小改變超過1倍 ，就重新分配AHI Hash內存（btr_search_sys_resize）
觸發AHI信息統計
在係統剛啟動時，索引對象上沒有足夠的信息來啟發是否適合進行AHI緩存，因此開始有個信息搜集的階段，在索引對象上維護了dict_index_t::search_info，類型為btr_search_t，用於跟蹤當前索引使用AHI的關鍵信息。
在第一次執行SQL時，需要從btree的root節點開始，當尋址到匹配的葉子節點時，會走如下邏輯：
btr_cur_search_to_nth_level：
if (btr_search_enabled && !index->disable_ahi) {
btr_search_info_update(index, cursor);
}
這裏髒讀AHI開關，並判斷index->diable_ahi是否為false。第二個條件是MySQL5.7對臨時表的優化，避免臨時表操作對全局對象的影響，針對臨時表不做AHI構建。
我們看看函數btr_search_info_update的邏輯：
a. 對info->hash_analysis++，當info->hash_analysis值超過BTR_SEARCH_HASH_ANALYSIS（17）時，也就是說對該索引尋路到葉子節點17次後，才會去做AHI分析（進入步驟b）
b. 進入函數btr_search_info_update_slow
在連續執行17次對相同索引的操作後，滿足info->hash_analysis大於等於BTR_SEARCH_HASH_ANALYSIS的條件，就會調用函數btr_search_info_update_slow來更新search_info， 這主要是為了避免頻繁的索引查詢分析產生的過多CPU開銷。
InnoDB通過索引條件構建一個可用於查詢的tuple，而AHI需要根據tuple定位到葉子節點上記錄的位置，既然AHI是構建在btree索引上的索引，它的鍵值就是通過索引的前N列的值計算的來，所有的信息搜集統計都是為了確定一個合適的"Ｎ" ，這個值也是個動態的值，會跟隨應用的負載自適應調整並觸發block上的AHI重構建。
btr_search_info_update_slow包含三個部分：更新索引查詢信息、block上的查詢信息以及為當前block構建AHI，下麵幾小節分別介紹。
更新索引上的查詢信息
參考函數：btr_search_info_update_hash
這裏涉及到的幾個search_info變量包括：
btr_search_t::n_hash_potential 表示如果使用AHI構建索引，潛在的可能成功的次數btr_search_t::hash_analysis 若設置了新的建議前綴索引模式，則重置為0，隨後的17次查詢分析可以忽略更新search_info
下麵兩個字段表示推薦的前綴索引模式btr_search_t::n_fields 推薦構建AHI的索引列數btr_search_t::left_side 表示是否在相同索引前綴的最左索引記錄構建AHI；值為true時，則對於相同前綴索引的記錄，隻存儲最右的那個記錄。
通過n_fields和left_side可以指導選擇哪些列作為索引前綴來構建（fold, rec）哈希記錄。如果用戶的SQL的索引前綴列的個數大於等於構建AHI時的前綴索引，就可以用上AHI。
Tips：在５.7之前的版本中，還支持索引中的字符串前綴作為構建AHI的鍵值的一部分，但上遊認為帶來的好處並不明顯，因此將btr_search_t::n_bytes 移除了。(參見commit 6f5f19b338543277a108a97710de8dd59b9dbb60, 42499d9394bf103a27d63cd38b0c3c6bd738a7c7）
Tips2：然而上遊在測試中發現，如果把n_bytes移除，可能在諸如順序插入這樣的場景存在性能退化*(參閱commit 00ec81a9efc1108376813f15935b52c451a268cf)，因此在MySQL5.7.8版本中又重新引入，本文分析代碼時統一基於MySQL5.7.7版本。
兩種情況需要構建建議的前綴索引列：
第一種. 當前是第一次為該索引做AHI分析，btr_search_t::n_hash_potential值為0，需要構建建議的前綴索引列；
第二種. 新的記錄匹配模式發生了變化(info->left_side == (info->n_fields <= cursor->low_match))，需要重新設置前綴索引列。
相關代碼段：
if (cursor->up_match == cursor->low_match) {
info->n_hash_potential = 0;
/* For extra safety, we set some sensible values here */
info->n_fields = 1;
info->left_side = TRUE;
} else if (cursor->up_match > cursor->low_match) {
info->n_hash_potential = 1;
if (cursor->up_match >= n_unique) {
info->n_fields = n_unique;
} else if (cursor->low_match < cursor->up_match) {
info->n_fields = cursor->low_match + 1;
} else {
info->n_fields = cursor->low_match;
}
info->left_side = TRUE;
} else {
info->n_hash_potential = 1;
if (cursor->low_match >= n_unique) {
info->n_fields = n_unique;
} else if (cursor->low_match > cursor->up_match) {
info->n_fields = cursor->up_match + 1;
} else {
info->n_fields = cursor->up_match;
}
info->left_side = FALSE;
}
從上述代碼可以看到，在low_match和up_match之間，選擇小一點match的索引列數的來進行設置，但不超過唯一確定索引記錄值的列的個數：
當low_match小於up_match時，left_side設置為true，表示相同前綴索引的記錄隻緩存最左記錄；
當low_match大於up_match時，left_side設置為false，表示相同前綴索引的記錄隻緩存最右記錄。
如果不是第一次進入seach_info分析，有兩種情況會遞增btr_search_t::n_hash_potential：
- 本次查詢的up_match和當前推薦的前綴索引都能唯一決定一條索引記錄(例如唯一索引)，則根據search_info推薦的前綴索引列構建AHI肯定能命中，遞增 info->n_hash_potential
if (info->n_fields >= n_unique && cursor->up_match >= n_unique) {
increment_potential:
info->n_hash_potential++;
return;
}
- 本次查詢的tuple可以通過建議的前綴索引列構建的ahi定位到。
if (info->left_side == (info->n_fields <= cursor->up_match)) {
goto increment_potential;
}
很顯然，如果對同一個索引的查詢交替使用不同的查詢模式，可能上次更新的search_info很快就會被重新設置，具有固定模式的索引查詢將會受益於AHI索引。
更新block上的查詢信息
參考函數：btr_search_update_block_hash_info
更新數據頁block上的查詢信息，涉及到修改的變量包括：
btr_search_info::last_hash_succ 最近一次成功(或可能成功)使用AHIbuf_block_t::n_hash_helps 計數值，如果使用當前推薦的前綴索引列構建AHI可能命中的次數，用於啟發構建／重新構建數據頁上的AHIi記錄項buf_block_t::n_fields 推薦在block上構建AHI的前綴索引列數buf_block_t::left_side 和search_info上對應字段含義相同
函數主要流程包括：
a.首先設置btr_search_info::last_hash_succ 為FALSE
這會導致在分析過程中無法使用AHI進行檢索，感覺這裏的設置不是很合理。這意味著每次分析一個新的block，都會導致AHI短暫不可用。
b. 初始化或更新block上的查詢信息
if ((block->n_hash_helps > 0)
&& (info->n_hash_potential > 0)
&& (block->n_fields == info->n_fields)
&& (block->left_side == info->left_side)) {
if ((block->index)
&& (block->curr_n_fields == info->n_fields)
&& (block->curr_left_side == info->left_side)) {
/* The search would presumably have succeeded using
the hash index */
info->last_hash_succ = TRUE;
}
block->n_hash_helps++;
} else {
block->n_hash_helps = 1;
block->n_fields = info->n_fields;
block->left_side = info->left_side;
}
當block第一次被touch到並進入該函數時，設置block上的建議索引列值；以後再進入時，如果和索引上的全局search_info相匹配，則遞增block->n_hash_helps，啟發後續的創建或重構建AHI。
如果當前數據頁block上已經構建了AHI記錄項，且buf_block_t::curr_n_fields等字段和btr_search_info上對應字段值相同時，則認為當前SQL如果使用AHI索引能夠命中，因此將btr_search_info::last_hash_succ設置為true，下次再使用相同索引檢索btree時就會嚐試使用AHI。
c. 在初始化或更新block上的變量後，需要判斷是否為整個page構建AHI索引：
if ((block->n_hash_helps > page_get_n_recs(block->frame)
/ BTR_SEARCH_PAGE_BUILD_LIMIT)
&& (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT)) {
if ((!block->index)
|| (block->n_hash_helps
> 2 * page_get_n_recs(block->frame))
|| (block->n_fields != block->curr_n_fields)
|| (block->left_side != block->curr_left_side)) {
/* Build a new hash index on the page */
return(TRUE);
}
}
簡單來說，當滿足下麵三個條件時，就會去為整個block上構建AHI記錄項：
- 分析使用AHI可以成功查詢的次數(
buf_block_t::n_hash_helps)超過block上記錄數的16(BTR_SEARCH_PAGE_BUILD_LIMIT)分之一 -
btr_search_info::n_hash_potential大於等於BTR_SEARCH_BUILD_LIMIT（100），表示連續100次潛在的成功使用AHI可能性 - 尚未為當前block構造過索引、或者當前block上已經構建了AHI索引且
block->n_hash_helps大於page上記錄數的兩倍、或者當前block上推薦的前綴索引列發生了變化 。
為數據頁構建AHI索引
如果在上一階段判斷認為可以為當前page構建AHI索引（函數btr_search_update_block_hash_info返回值為TRUE），則根據當前推薦的索引前綴進行AHI構建。
參考函數：btr_search_build_page_hash_index
分為三個階段：
檢查階段：加btr_search_latch的S鎖，判斷AHI開關是否打開；如果block上已經構建了老的AHI但前綴索引列和當前推薦的不同，則清空Block對應的AHI記錄項（btr_search_drop_page_hash_index）；檢查n_fields和page上的記錄數；然後釋放btr_search_latch的S鎖；
搜集階段：根據推薦的索引列數計算記錄fold值，將對應的數據頁記錄內存地址到數組裏；
根據left_mode值，相同的前綴索引列值會有不同的行為，舉個簡單的例子，假設page上記錄為 (2,1), (2,2), (5, 3), (5, 4), (7, 5), (8, 6)，n_fields＝１
- 若left_most為true，則hash存儲的記錄為(2,1) , (5, 3), (7, 5), (8,6)
- 若left_most為false，則hash存儲的記錄為(2, 2), (5, 4), (7,5), (8, 6)
插入階段：加btr_search_latch的X鎖，將第二階段搜集的(fold, rec)插入到AHI中，並更新：
if (!block->index) {
index->search_info->ref_count++;
}
block->n_hash_helps = 0;
block->curr_n_fields = n_fields;
block->curr_left_side = left_side;
block->index = index;
PS：由於第二階段釋放了btr_search_latch鎖，這裏還得判斷block上的AHI信息是否發生了變化，如果block上已經構建了AHI且block->curr_*幾個變量和當前嚐試構建的檢索模式不同，則放棄本次構建。
使用AHI
AHI的目的是根據用戶提供的查詢條件加速定位到葉子節點，一般如果有固定的查詢pattern，都可以通過AHI受益，尤其是btree高度比較大的時候。
入口函數：btr_cur_search_to_nth_level
相關代碼：
/* Use of AHI is disabled for intrinsic table as these tables re-use
the index-id and AHI validation is based on index-id. */
if (rw_lock_get_writer(&btr_search_latch) == RW_LOCK_NOT_LOCKED
&& latch_mode <= BTR_MODIFY_LEAF
&& info->last_hash_succ
&& !index->disable_ahi
&& !estimate
# ifdef PAGE_CUR_LE_OR_EXTENDS
&& mode != PAGE_CUR_LE_OR_EXTENDS
# endif /* PAGE_CUR_LE_OR_EXTENDS */
&& !dict_index_is_spatial(index)
/* If !has_search_latch, we do a dirty read of
btr_search_enabled below, and btr_search_guess_on_hash()
will have to check it again. */
&& UNIV_LIKELY(btr_search_enabled)
&& !modify_external
&& btr_search_guess_on_hash(index, info, tuple, mode,
latch_mode, cursor,
has_search_latch, mtr)) {
從代碼段可以看出，需要滿足如下條件才能夠使用AHI：
** 沒有加btr_search_latch寫鎖。如果加了寫鎖，可能操作時間比較耗時，走AHI檢索記錄就得不償失了；
- latch_mode <= BTR_MODIFY_LEAF，表明本次隻是一次不變更BTREE結構的DML或查詢（包括等值、RANGE等查詢）操作；
- btr_search_info::last_hash_succ為true表示最近一次使用AHI成功（或可能成功）了；
- 打開AHI開關；
- 查詢優化階段的估值操作，例如計算range範圍等 ，典型的堆棧包括：handler::multi_range_read_info_const --> ha_innobase::records_in_range --> btr_estimate_n_rows_in_range --> btr_cur_search_to_nth_level；
- 不是spatial索引；
- 調用者無需分配外部存儲頁(BTR_MODIFY_EXTERNAL，主要用於輔助寫入大的blob數據，參考struct btr_blob_log_check_t)。
當滿足上述條件時，進入函數btr_search_guess_on_hash，根據當前的查詢tuple對象計算fold，並查詢AHI；隻有當前檢索使用的tuple列的個數大於等於構建AHI的列的個數時，才能夠使用AHI索引。
btr_search_guess_on_hash：
- 首先用戶提供的前綴索引查詢條件必須大於等於構建AHI時的前綴索引列數，這裏存在一種可能性：索引上的search_info的n_fields 和block上構建AHI時的cur_n_fields值已經不相同了，但是我們並不知道本次查詢到底落在哪個block上，這裏一致以search_info上的n_fields為準來計算fold，去查詢AHI。
- 在檢索AHI時需要加&btr_search_latch的S鎖
- 如果本次無法命中AHI，就會將btr_search_info::last_hash_succ設置為false，這意味著隨後的查詢都不會去使用AHI了，隻能等待下一路查詢信息分析後才可能再次啟動。（
btr_search_failure） - 對於從ahi中獲得的記錄指針，還需要根據當前的查詢模式檢查是否是正確的記錄位置（
btr_search_check_guess）
如果本次查詢使用了AHI，但查詢失敗了（cursor->flag == BTR_CUR_HASH_FAIL），並且當前block構建AHI索引的curr_n_fields等字段和btr_search_info上的相符合，則根據當前cursor定位到的記錄插入AHI。參考函數：btr_search_update_hash_ref
從上述分析可見，AHI如其名，完全是自適應的， 如果檢索模式不固定，很容易就出現無法用上AHI或者AHI失效的情況。
維護AHI
a.關閉選項innodb_adaptive_hash_index
- 持有dict_sys->mutex和btr_search_latch的x鎖;
- 遍曆dict_sys->table_LRU和dict_sys->table_non_LRU鏈表，將每個表上的所有索引的index->search_info->ref_count設置為0;
- 釋放dict_sys->mutex;
- 遍曆buffer pool，將block上的index標記(buf_block_t::index)清空為NULL
- 清空AHI中的哈希項，並釋放為記錄項分配的Heap
- 釋放btr_search_latch
參考函數：btr_search_disable
b. index->search_info的ref_count不為0時，無法從數據集詞典cache中將對應的表驅逐。workaround的方式是臨時關閉AHI開關
參考函數：dict_table_can_be_evicted、dict_index_remove_from_cache_low
c. 刪除索引頁上的記錄，或者更新的是二級索引、或者更新了主鍵且影響了排序鍵值，則需要從AHI上將對應的索引記錄刪除
參考函數：btr_search_update_hash_on_delete
d. 插入新的記錄時，如果本次插入未產生頁麵重組、操作的page為葉子節點，且本次插入操作使用過AHI定位成功，則先嚐試更新再嚐試插入，否則直接插入對應的AHI記錄項；
參考函數：btr_search_update_hash_node_on_insert、btr_search_update_hash_on_insert
e. 涉及索引樹分裂或者節點合並，或從LRU中驅逐page（buf_LRU_free_page）時，需要清空AHI對應的page。
參考函數：btr_search_drop_page_hash_index
shortcut查詢模式
在row_search_mvcc函數中，首先會去判斷在滿足一定條件時，使用shortcut模式，利用AHI索引來進行檢索。
隻有滿足嚴苛的條件時（例如需要唯一鍵查詢、使用聚集索引、長度不超過八分之一的page size、隔離級別在RC及RC之上、活躍的Read view等等條件，具體的參閱代碼），才能使用shortcut：
- 加
btr_search_latch的S鎖； - 然後通過
row_sel_try_search_shortcut_for_mysql檢索記錄；如果找到滿足條件的記錄，本次查詢可以不釋放 btr_search_latch，這意味著innodb/server層交互期間可能持有AHI鎖，但最多在10000次（BTR_SEA_TIMEOUT）交互後釋放AHI latch。 一旦發現有別的線程在等待AHI X 鎖，也會主動釋放其擁有的S鎖。
然而， Percona的開發Alexey Kopytov認為這種長時間擁有的btr_search_latch的方式是沒有必要的，這種設計方式出現在很久之前加鎖、解鎖非常昂貴的時代，然而現在的CPU已經很先進了，完全沒有必要，在Percona的版本中，一次shortcut的查詢操作後都直接釋放掉btr_search_latch(參閱 bug#1218347
AHI監控項
我們可以通過information_schema.innodb_metrics來監控AHI模塊的運行狀態
首先打開監控：
mysql> set global innodb_monitor_enable = module_adaptive_hash;
Query OK, 0 rows affected (0.00 sec)
mysql> select status, name, subsystem from INNODB_METRICS where subsystem like '%adaptive_hash%';
+---------+------------------------------------------+---------------------+
| status | name | subsystem |
+---------+------------------------------------------+---------------------+
| enabled | adaptive_hash_searches | adaptive_hash_index |
| enabled | adaptive_hash_searches_btree | adaptive_hash_index |
| enabled | adaptive_hash_pages_added | adaptive_hash_index |
| enabled | adaptive_hash_pages_removed | adaptive_hash_index |
| enabled | adaptive_hash_rows_added | adaptive_hash_index |
| enabled | adaptive_hash_rows_removed | adaptive_hash_index |
| enabled | adaptive_hash_rows_deleted_no_hash_entry | adaptive_hash_index |
| enabled | adaptive_hash_rows_updated | adaptive_hash_index |
+---------+------------------------------------------+---------------------+
8 rows in set (0.00 sec)
重置所有的計數
mysql> set global innodb_monitor_reset_all = 'adaptive_hash%';
Query OK, 0 rows affected (0.00 sec)
該表搜集了AHI子係統諸如ahi查詢次數，更新次數等信息，可以很好的監控其運行狀態，在某些負載下，AHI並不適合打開，關閉AHI可以避免額外的維護開銷。當然這取決於你針對具體負載的性能測試。
最後更新：2017-04-01 13:44:35