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開關（btr_search_enabled）是否打開，以及`index->diable_ahi`是否為false。第二個條件是MySQL5.7對臨時表的優化，避免臨時表操作對全局對象的影響，針對臨時表不做AHI構建。我們看看函數btr_search_info_update的邏輯： 1. 對`info->hash_analysis++`，當`info->hash_analysis`值超過`BTR_SEARCH_HASH_ANALYSIS`（17）時，也就是說對該索引尋路到葉子節點17次后，才會去做AHI分析（進入步驟2） 2. 進入函數`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。 Tip1：在５.7之前的版本中，還支持索引中的字符串前綴作為構建AHI的鍵值的一部分，但上游認為帶來的好處并不明顯，因此將`btr_search_t::n_bytes`?移除了(參見commit?[6f5f19b338543277a108a97710de8dd59b9dbb60](https://github.com/mysql/mysql-server/commit/6f5f19b338543277a108a97710de8dd59b9dbb60 "Bug#16852278 SIMPLIFY RECORD COMPARISONS"),?[42499d9394bf103a27d63cd38b0c3c6bd738a7c7](https://github.com/mysql/mysql-server/commit/42499d9394bf103a27d63cd38b0c3c6bd738a7c7 "Remove support for byte-level prefix granularity in searches.")）。 Tip2：然而上游在測試中發現，如果把n_bytes移除，可能在諸如順序插入這樣的場景存在性能退化(參閱commit?[00ec81a9efc1108376813f15935b52c451a268cf](https://github.com/mysql/mysql-server/commit/00ec81a9efc1108376813f15935b52c451a268cf "Bug#21198396 REINTRODUCE ADAPTIVE HASH INDEX FIELD PREFIXES"))，因此在新發布的MySQL5.7.8版本中又重新引入，本文分析代碼時統一基于MySQL5.7.7版本。兩種情況需要構建建議的前綴索引列： 1. 當前是第一次為該索引做AHI分析，`btr_search_t::n_hash_potential`值為0，需要構建建議的前綴索引列； 2. 新的記錄匹配模式發生了變化`(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的索引列數的來進行設置，但不超過唯一確定索引記錄值的列的個數： 1. 當low_match小于up_match時，left_side設置為true，表示相同前綴索引的記錄只緩存最左記錄； 2. 當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`?最近一次成功(或可能成功)使用AHI； `buf_block_t::n_hash_helps`?計數值，如果使用當前推薦的前綴索引列構建AHI可能命中的次數，用于啟發構建／重新構建數據頁上的AHI記錄項； `buf_block_t::n_fields`?推薦在block上構建AHI的前綴索引列數； `buf_block_t::left_side`?和search_info上對應字段含義相同。函數主要流程包括： 1. 首先設置`btr_search_info::last_hash_succ`?為FALSE 這會導致在分析過程中無法使用AHI進行檢索，感覺這里的設置不是很合理。這意味著每次分析一個新的block，都會導致AHI短暫不可用。 2. 初始化或更新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。 3. 在初始化或更新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` 分為三個階段： 1. 檢查階段：加btr_search_latch的S鎖，判斷AHI開關是否打開；如果block上已經構建了老的AHI但前綴索引列和當前推薦的不同，則清空Block對應的AHI記錄項（`btr_search_drop_page_hash_index`）；檢查n_fields和page上的記錄數；然后釋放btr_search_latch的S鎖； 2. 搜集階段：根據推薦的索引列數計算記錄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) 3. 插入階段：加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 1. 關閉選項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` 2. `index->search_info`的ref_count不為0時，無法從數據集詞典cache中將對應的表驅逐，workaround的方式是臨時關閉AHI開關；參考函數：`dict_table_can_be_evicted`、`dict_index_remove_from_cache_low` 3. 刪除索引頁上的記錄，或者更新的是二級索引、或者更新了主鍵且影響了排序鍵值，則需要從AHI上將對應的索引記錄刪除；參考函數：`btr_search_update_hash_on_delete` 4. 插入新的記錄時，如果本次插入未產生頁面重組、操作的page為葉子節點，且本次插入操作使用過AHI定位成功，則先嘗試更新再嘗試插入，否則直接插入對應的AHI記錄項；參考函數：`btr_search_update_hash_node_on_insert`、`btr_search_update_hash_on_insert` 5. 涉及索引樹分裂或者節點合并，或從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](https://bugs.launchpad.net/percona-server/+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可以避免額外的維護開銷。當然這取決于你針對具體負載的性能測試。