MySQL8.0 存儲引擎（InnoDB ）buffer pool的實現(xiàn)原理

小強實驗室

數(shù)據(jù)庫為了高效讀取和存儲物理數(shù)據(jù)，通常都會采用緩存的方式來彌補磁盤IO與CPU運算速度差。InnoDB 作為一個具有高可靠性和高性能的通用存儲引擎也不例外，Buffer Pool就是其用來在內(nèi)存中緩存數(shù)據(jù)頁面的結(jié)構(gòu)。本文將基于MySQL-8.0.22源碼，從buffer pool結(jié)構(gòu)、buffer pool初始化、buffer pool管理、頁面讀取過程、頁面淘汰過程、buffer pool加速等方面介紹buffer pool的實現(xiàn)原理。
第一部分、Buffer pool結(jié)構(gòu)

Buffer pool不僅僅緩存了磁盤的數(shù)據(jù)頁，也存儲了鎖信息、change buffer信息、adaptive hash index、double write buffer等信息。本文將從物理與邏輯兩方面介紹buffer pool的結(jié)構(gòu)。
1.1  Buffer pool的物理結(jié)構(gòu)

Buffer pool的物理結(jié)構(gòu)自上而下分instance、chunk和page三層，如下圖所示：

登錄/注冊后可看大圖

• Buffer pool instance
  

Buffer pool instance對應的結(jié)構(gòu)體是buf_pool_t。整個buffer pool由多個instance組成，個數(shù)等于innodb_buffer_pool_size/innodb_buffer_pool_instances。instances是為并發(fā)讀取與寫入而設計，各instance之間沒有鎖競爭關系。當 innodb_buffer_pool_size小于1GB時為防止instances太小而出現(xiàn)性能問題，innodb_buffer_pool_instances會被重置為1。instance之內(nèi)包含完整鎖、信號量、chunks、為方便數(shù)據(jù)頁管理而設計的邏輯鏈表（lru list、free list、flush list）以及一個用于快速找到指定space_id和page_no的數(shù)據(jù)頁的的page hash鏈表。

• Buffer pool chunk
  

Buffer pool chunk對應的結(jié)構(gòu)體是buf_chunk_t。每個buffer pool instance被均勻劃分為多個chunk，buffer pool resize以chunk為粒度。chunk分為數(shù)據(jù)頁和數(shù)據(jù)頁對應的控制體，控制體中有指針指向數(shù)據(jù)頁。遍歷所有instance的chunk可以幾乎訪問innodb所有緩存的數(shù)據(jù)，只有部分諸如尚未解壓的壓縮頁等除外。

• Buffer pool page
  

Buffer pool page對應的結(jié)構(gòu)體包括塊描述符buf_block_t和頁面描述符buf_page_t。Buffer pool page大小為16KB，默認與磁盤上數(shù)據(jù)頁的大小相同（innodb的文件結(jié)構(gòu)的介紹，請參考淺析InnoDB文件結(jié)構(gòu)），其緩存的不僅僅是數(shù)據(jù)頁，緩存的對象還包括：undo log頁面、change buffer（插入緩存信息）、AHI（自適應哈希）、SDI（結(jié)構(gòu)化字典信息）、行鎖等。所有緩存對象在buffer pool中都是以頁面為單位存儲。
Innodb支持數(shù)據(jù)頁壓縮，壓縮頁的大小在建表的時候指定，目前支持的范圍包括16K，8K，4K，2K，1K等（由于壓縮頁的管理方式與普通頁面不同，即使指定16K的壓縮頁，也能對數(shù)據(jù)量大的類型有一定益處）。壓縮頁面在buffer pool中使用伙伴系統(tǒng)管理，不論壓縮頁面在磁盤上的大小是多少，解壓后都為16K。當buffer pool空閑頁面不足時，innodb會優(yōu)先淘汰壓縮頁面的解壓頁（buf_LRU_free_from_unzip_LRU_list），當前者操作后仍不能為innodb提供足夠的空閑頁面時，會接著淘汰LRU list上的正常頁面和壓縮頁面（buf_LRU_free_from_common_LRU_list）。
1.1.1 Buffer pool page結(jié)構(gòu)

buf_block_t主要包含以下信息：

• 描述頁所屬space ID、文件內(nèi)偏移的page no、頁面大小、IO狀態(tài)、最新修改的LSN、最老修改的LSN、zip壓縮頁面原始數(shù)據(jù)、用于鏈接到page hash節(jié)點等信息的結(jié)構(gòu)buf_page_t。buf_page_t處于buf_block_t的第一項，方便二者之間靈活轉(zhuǎn)化。
  
• 指向存儲頁面數(shù)據(jù)的內(nèi)存地址frame。
  
• 頁面mutex，用于保護buf_fix_count、io_fix等頁面狀態(tài)等。
  
• 是否處于unzip LRU list、withdraw list、unzip CLOCK_list等信息，這些鏈表的含義將在1.2節(jié)中介紹。
  
• 其他信息。
  

每個buffer pool page的buf_block_t和frame等信息于buf_chunk_init函數(shù)中被初始化。在使用allocate_chunk分配到chunk的空間后，chunk內(nèi)所有頁面的buf_block_t連在一起從內(nèi)存前向后初始化，chunk內(nèi)所有frame連在一起，從內(nèi)存后向前初始化，最左側(cè)的buf_block_t控制最左側(cè)的frame，如下圖所示：

登錄/注冊后可看大圖

1.1.2 Buffer pool page分類

所有buffer pool page分為以下類別：

• BUF_BLOCK_POOL_WATCH：用于purge操作異步讀取磁盤頁面的一種類型。每個buf_pool_t結(jié)構(gòu)體中都有一個名為watch的數(shù)組，元素類型為buf_page_t，大小為purge線程數(shù)+1。當purge操作需要讀取一個不在buffer pool中的頁面時，會將watch數(shù)組中一個BUF_BLOCK_POOL_WATCH狀態(tài)的頁面設置為BUF_BLOCK_ZIP_PAGE，設置對應space id，page id，設置buf_fix_count設置為1防止其被淘汰出buffer pool，并將其加入page hash中（buf_pool_watch_set）。當磁盤數(shù)據(jù)被讀取進入buffer pool時，會將watch數(shù)組對應的頁面狀態(tài)恢復為BUF_BLOCK_POOL_WATCH，將watch頁面從page hash中刪除（buf_pool_watch_remove），后續(xù)會將新頁面加入page hash中。通過較為tricky地判斷存在于page hash的page地址是否在watch數(shù)組范圍內(nèi)，可以巧妙地判斷目標頁面是否成功讀入buffer pool。
  
• BUF_BLOCK_ZIP_PAGE：壓縮頁未解壓的對應狀態(tài)。從磁盤讀取壓縮頁時，用buf_page_alloc_descriptor分配一個臨時頁面描述符buf_page_t，再調(diào)用buf_buddy_alloc從伙伴系統(tǒng)中分配一個空間存放壓縮頁原始數(shù)據(jù)，臨時的bpage會被加入LRU list和page hash（buf_page_init_for_read）。這個臨時buf_page_t等到頁面被解壓時，innodb會使用從free_list中申請到的狀態(tài)為BUF_BLOCK_FILE_PAGE的buf_page_t替換掉臨時buf_page_t，放在LRU list相同的位置，并把解壓頁面的塊描述符buf_block_t放入unzip LRU list中；刪除page hash中的臨時buf_page_t，在其中加入新的buf_page_t；最后通過buf_zip_decompress解壓頁面（zip_page_handler）。如果解壓頁被淘汰，而壓縮頁本身未被淘汰，并且頁面未被修改，則此頁面會再次被標記為BUF_BLOCK_ZIP_PAGE。關于BUF_BLOCK_ZIP_PAGE的另一個用法如前所述，為在watch操作中被用來標記尚未讀入的頁面，不再復述。
  
• BUF_BLOCK_ZIP_DIRTY：壓縮頁的解壓頁被釋放時，如果頁面被修改過（oldest_modification非0），則頁面從BUF_BLOCK_FILE_PAGE狀態(tài)變?yōu)锽UF_BLOCK_ZIP_DIRTY狀態(tài)，未被修改過則為BUF_BLOCK_ZIP_PAGE（buf_LRU_free_page/buf_CLOCK_free_page）。解壓頁被釋放后，BUF_BLOCK_ZIP_PAGE/BUF_BLOCK_ZIP_DIRTY壓縮頁的頁面描述符也會在buf_LRU_free_page/buf_CLOCK_free_page臨時分配。BUF_BLOCK_ZIP_DIRTY狀態(tài)的頁面無法從LRU/CLOCK list中淘汰，只能在flush_list中等待刷盤。在flush_list中，也只存在BUF_BLOCK_FILE_PAGE和BUF_BLOCK_ZIP_DIRTY這兩種頁面。
  
• BUF_BLOCK_NOT_USED：頁面在free_list中時的狀態(tài)，此類頁面較為常見。
  
• BUF_BLOCK_READY_FOR_USE：當頁面從free list取下，準備放入LRU/CLOCK list（buf_LRU_get_free_block/buf_CLOCK_get_free_block）時處于的臨時狀態(tài)。
  
• BUF_BLOCK_FILE_PAGE：非壓縮頁面的頁面狀態(tài)，壓縮頁解壓頁的頁面狀態(tài)。最常見的頁面狀態(tài)。
  
• BUF_BLOCK_MEMORY：用于存儲內(nèi)存對象，包括innodb行鎖、AHI（自適應哈希）、壓縮頁伙伴系統(tǒng)等。此類頁面不存在任何邏輯鏈表中。
  
• BUF_BLOCK_REMOVE_HASH：頁面從page hash刪除后，被放入free_list前處于的臨時狀態(tài)。
  

1.1.3 頁面讀取方法

頁面讀取方法包括：NORMAL、SCAN、IF_IN_POOL、PEEK_IF_IN_POOL、NO_LATCH、IF_IN_POOL_OR_WATCH、POSSIBLY_FREED。在詳細介紹頁面讀取方法之前，先介紹隨機預讀、make young、線性預讀等概念：

• 隨機預讀（buf_read_ahead_random）：發(fā)生在磁盤頁面讀取函數(shù)buf_read_page_low之后，所有非SCAN的頁面讀取模式都會嘗試隨機預讀。隨機預讀的作用是當一個extent（通常為1M，64個連續(xù)的物理頁面）內(nèi)處于LRU list前1/4的熱點頁面（buf_page_peek_if_young返回為true）個數(shù)超過13時（BUF_READ_AHEAD_RANDOM_THRESHOLD）時，會采用異步IO和IO合并的方式將該extent內(nèi)所有頁面都讀入buffer pool。隨機預讀是可選的，可以使用innodb_random_read_ahead參數(shù)關閉。
  
• make young（buf_page_make_young_if_needed）：用于修改頁面的位置，除SCAN和PEEK_IF_IN_POOL之外的所有模式都會嘗試make young。對于LRU list中的頁面，如果頁面處于LRU末尾，并且距離上一次讀取超過一定時長（buf_LRU_old_threshold_ms），則將頁面放入LRU list的頭部。對于CLOCK list頁面，如果頁面被沒有independent標記的正常流量訪問，則需按innodb_independent_buffer_pool_list_move_action的配置決定是否移動到LRU list中。
  
• 線性預讀（buf_read_ahead_linear）：發(fā)生在buf_page_make_young_if_needed之后，除SCAN和PEEK_IF_IN_POOL之外的模式中，第一次讀取頁面（access_time為0）時才會嘗試線性預讀。線性預讀條件比較苛刻，只有extent的數(shù)據(jù)邊界頁面，即extent的第一個頁面或者最后一個頁面讀取結(jié)束后才可能觸發(fā)，并且要求在extent范圍內(nèi)超過innodb_read_ahead_threshold（默認值為56）個頁面被順序訪問（判定方法是檢查頁面的訪問時間access_time），滿足條件后會采用異步IO和IO合并的方式將下一個extent的數(shù)據(jù)都讀入buffer pool。
  

下面來了解各種頁面讀取方法的具體作用：

• NORMAL：默認獲取數(shù)據(jù)頁的方式，如果數(shù)據(jù)頁不在 buffer pool中，則從磁盤讀取，如果已經(jīng)在buffer pool中，則直接返回。會嘗試進行隨機預讀、make young和線性預讀。正常加讀寫鎖。
  
• SCAN：用于掃描類的頁面讀取。掃描類的特點為大批量讀取頁面，但短時間不再需要此類頁面，因此頁面讀取應盡可能不影響buffer pool的狀態(tài)。所以SCAN不會進行隨機預讀、make young和線性預讀。正常加讀寫鎖。
  
• IF_IN_POOL：只在buffer pool查找目標數(shù)據(jù)頁，如果不在則直接返回為空。隨機預讀發(fā)生在磁盤頁面讀取之后，因此不會嘗試隨機預讀。會嘗試make young和線性預讀。正常加讀寫鎖。
  
• PEEK_IF_IN_POOL：與IF_IN_POOL模式相似，但只是窺探頁面是否在buffer pool中，不會修改頁面的位置和干擾buffer pool狀態(tài)，因此不會隨機預讀、make young和線性預讀。正常加讀寫鎖。
  
• NO_LATCH：除了不加讀寫鎖之外，其他與NORMAL模式相似，從磁盤或者buffer pool讀取頁面。會嘗試進行隨機預讀、make young和線性預讀。
  
• IF_IN_POOL_OR_WATCH：用于purge操作，與IF_IN_POOL模式相似，頁面在buffer pool則直接返回，但如果頁面不在buffer pool，則會設置page watch，等待目標頁面被其他線程異步讀入buffer pool。會嘗試make young和線性預讀。正常加讀寫鎖。
  
• POSSIBLY_FREED：用于數(shù)據(jù)統(tǒng)計操作，與NORMAL模式相似，但不在乎頁面是否被freed。從磁盤或者buffer pool讀取頁面。會嘗試進行隨機預讀、make young和線性預讀。正常加讀寫鎖。
  

1.1.4 Page hash

innodb為加速buffer pool中頁面的查找，在每個buffer pool instance（buf_pool_t）中提供了page hash。page hash對應的結(jié)構(gòu)體為hash_table_t。page hash中只存儲對應到物理文件的頁面（buf_page_in_file() == TRUE），類型包括BUF_BLOCK_ZIP_PAGE、BUF_BLOCK_ZIP_DIRTY、BUF_BLOCK_FILE_PAGE三類。page hash的key為(m_space << 20) + m_space + m_page_no，value為頁面描述符buf_page_t*。page hash為了提高性能，提供了鎖分區(qū)的功能，即采用一系列鎖來保護page hash的單元（hash_cell_t），不同鎖保護不同分區(qū)。分區(qū)個數(shù)為默認16個，只有在debug模式下才能通過innodb_page_hash_locks參數(shù)更改。
1.1.5 Zip hash

innodb的壓縮頁存儲空間由伙伴系統(tǒng)管理。為加速伙伴系統(tǒng)所有頁面的查找，其頁面都會存入zip hash中。
1.2 Buffer Pool的邏輯結(jié)構(gòu)

為方便管理buffer pool page，innodb用多個邏輯鏈表將相同屬性的buffer pool頁面描述符（通常都是buf_page_t）串聯(lián)在一起。
1.2.1 Free list

free list對應暫時沒有被使用的節(jié)點，對應結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) free，如前所述，其頁面的類型為BUF_BLOCK_NOT_USED。LRU list、CLOCK list等鏈表需要新頁面時就會向free list申請，當后者空閑頁面不足時（buf_get_free_only返回為空），則需要通過掃描CLOCK list（buf_CLOCK_scan_and_free_block）或者LRU list（buf_LRU_scan_and_free_block），淘汰合適的節(jié)點以騰出空間頁面。
1.2.2 LRU list

LRU list是buffer pool最重要的鏈表，對應的結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) LRU，除被independent標記的頁面外，所有讀進來的頁面都放在LRU list上。LRU list頁面被用改良后的LRU算法管理，除LRU算法的基本特點之外，還包括以下特點：

• 所有新頁面被插入距離隊尾3/8 LRU list長度的位置，此位置稱為midpoint，前5/8稱為young list，瀕臨淘汰的3/8稱為old list。
  
• 處于midpoint的頁面在超過一定時間間隔（buf_LRU_old_threshold_ms）后再次被讀取時才會被移入LRU list的頭部。
  
• 處于LRU list前1/4的的頁面屬于熱點頁面，不會被移動到LRU list的頭部（buf_page_peek_if_young）。
  

如上方式管理LRU list的主要原因是擔心buffer pool中經(jīng)常被使用的頁面被預讀的頁面以及全表掃描類操作淘汰，影響數(shù)據(jù)庫的性能。
1.2.3 Unzip LRU list

unzip LRU list是用于存儲LRU list中壓縮頁的解壓頁的鏈表，對應結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_block_t) unzip_LRU，存儲單元是塊描述符buf_block_t。讀取磁盤中的壓縮頁時，會調(diào)用buf_page_alloc_descriptor臨時分配一個頁面描述符buf_page_t，再調(diào)用buf_buddy_alloc從伙伴系統(tǒng)中分配一個空間存放壓縮頁原始數(shù)據(jù)，臨時的buf_page_t會被加入LRU list和page hash（buf_page_init_for_read），如果是debug模式，還會將未解壓的壓縮頁放入zip clean list。
壓縮頁在被用戶請求的過程中，在壓縮頁面獲取之后，innodb會在zip_page_handler函數(shù)內(nèi)，先通過buf_relocate從free list申請新的空閑頁面替換掉臨時的buf_page_t，放在LRU list相同的位置，并把解壓頁面的塊描述符buf_block_t放入unzip LRU list中（unzip LRU list中頁面的前后順序與LRU list相同），并且刪除page hash中的臨時buf_page_t，在其中加入新的buf_page_t；后通過buf_zip_decompress對壓縮數(shù)據(jù)進行解壓。由于解壓頁既以buf_page_t存在于LRU list，又以buf_block_t存在于unzip LRU list，buf_page_t和buf_block_t又能互相轉(zhuǎn)化，因此unzip LRU list實際上是LRU list的子集。
當free list空間不足時，innodb會優(yōu)先淘汰unzip LRU list，并且只淘汰解壓頁而不淘汰壓縮頁。如果從unzip LRU list中沒能淘汰出頁面，則會嘗試從LRU list中淘汰，此時如果遇到解壓頁，則會連同壓縮頁本身一起淘汰（buf_LRU_scan_and_free_block）。當解壓頁被淘汰，而壓縮頁未被淘汰時，innodb會重新為壓縮頁分配臨時頁面描述符buf_page_t，將其插入LRU list中與解壓頁相同的位置，并且從page hash中刪除解壓頁，將臨時buf_page_t加入page hash（buf_LRU_free_page）。
1.2.4 CLOCK list

雖然innodb小心翼翼地設計了midpoint的buffer pool page讀取方案，8.0還引入了SCAN讀取模式盡可能減少全表掃描與正常query的數(shù)據(jù)頁面間的沖突，但并未根除。假設buffer pool有限，正常query需要的頁面可以恰好完整緩存到buffer pool或者還無法緩存到buffer pool，若此時發(fā)起類似全表掃描的操作，全表掃描需要的頁面不論需要多少，都會導致以下問題：

• LRU list隊尾中正常query的舊頁面會快速被全表掃描淘汰。
  
• 全表掃描頁面和正確query競爭free buffer pool page，正常query讀取新頁面速度受影響。
  
• 正常query讀入的新頁面放在midpoint處，全表掃描讀入的頁面也是如此，如果正常query沒及時讀取新頁面，新頁面會被全表掃描流量快速推向隊尾并淘汰。
  

上述問題的根本原因在于全表掃描頁面與正常query頁面存在耦合，能夠互相影響。CLOCK list是CDB為接觸全表掃描頁面與正常query頁面耦合而引入的新鏈表結(jié)構(gòu)，對應結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) CLOCK。所有用independent hint標記過的頁面都會存入CLOCK list，而非LRU list。CLOCK list采用類似優(yōu)化過的CLOCK算法進行管理：

• buf_page_t新增use_times參數(shù)，記錄頁面被訪問的次數(shù)，每次被讀取時use_times加1。
  
• CLOCK list上限用innodb_txsql_independent_buffer_pool_size_pct配置，其表示CLOCK list能使用的BP最大比例。
  
• CLOCK list未達到上限時，需要新數(shù)據(jù)頁時直接從free list申請。CLOCK list達到上限時，掃描CLOCK list，被掃描的頁面use_times減1，直至找到use_times為0的能順利淘汰的頁面為止（buf_CLOCK_scan_and_free_block）。
  
• 新增后臺線程buf_independent_buffer_pool_evict_thread，每隔innodb_txsql_independent_buffer_pool_evict_interval時長，對CLOCK list進行掃描，將每個頁面的use_times減1，主動淘汰CLOCK list頁面
  
• 淘汰的CLOCK list頁面歸還給free list，沒有全表掃描時，可以給正常query使用。
  

使用CLOCK list的方法很簡單，只需要在INSERT、DELETE、UPDATE等DML關鍵詞后添加名為independent的hint即可，例如select /*+ independent */ id from t。CLOCK list的長度、頁面被使用次數(shù)分布等信息可以使用show engine innodb status命令觀察。如下圖所示：

登錄/注冊后可看大圖

1.2.5 Unzip CLOCK list

unzip CLOCK list與unzip LRU list類似，都是用于存儲解壓的壓縮頁，對應的結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_block_t) unzip_CLOCK。CLOCK list對壓縮頁的讀取，解壓過程都與LRU list相似，都是先用臨時buf_page_t讀取原始壓縮數(shù)據(jù)，將臨時buf_page_t加入CLOCK list和page hash，如果是debug模式，還會將未解壓的壓縮頁放入zip clean list。之后在zip_page_handler函數(shù)內(nèi)，再用從free list申請的新頁面替換臨時buf_page_t，存放到CLOCK list和unzip CLOCK list對應的位置中，最后用buf_zip_decompress進行數(shù)據(jù)解壓。與unzip LRU list相似，unzip CLOCK list也是CLOCK list的子集。
unzip CLOCK list的淘汰分兩種，一種與unzip LRU list相似：當independent hint訪問需要的頁面不足時，先掃描unzip CLOCK list，后掃CLOCK list，直至找到use_times為0的頁面并淘汰復用（buf_CLOCK_scan_and_free_block）。淘汰頁面時如果只有解壓頁被淘汰而壓縮頁未被淘汰，處理細節(jié)與unzip LRU list相同。另一種是后臺線程buf_independent_buffer_pool_evict_thread主動掃描unzip CLOCK list和CLOCK list，將每個頁面的use_times減1，遇到解壓頁會連同壓縮頁一起釋放，需要的話還會進行刷臟，從而避免全表掃描頁面長時間駐留在unzip CLOCK list和CLOCK list中。
1.2.6 Flush list

flush list用來存儲buffer pool中所有修改過的頁面，對應結(jié)構(gòu)是buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) flush_list。如前所述，flush list中只有BUF_BLOCK_FILE_PAGE和BUF_BLOCK_ZIP_DIRTY這兩種頁面。flush list是LRU list + CLOCK list的子集。flush list中的頁面按照最老修改的LSN（即第一次修改頁面的LSN）排序，鏈表尾是LSN最小的頁面，優(yōu)先被刷入磁盤。多次修改不影響頁面在flush list中的位置，如果刷盤的時候，頁面存在多個LSN，那么這些修改將合并刷入磁盤。
1.2.7 Zip clean list

zip clean list僅存在于debug模式下，用于調(diào)試buffer pool的頁壓縮功能，對應結(jié)構(gòu)是buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) zip_clean。zip clean list用于存儲還沒解壓的，類型為BUF_BLOCK_ZIP_PAGE的干凈壓縮頁。從源碼中觀察，zip clean list中的頁面來源以下三類：

• 從磁盤讀取壓縮頁時（buf_page_init_for_read）
  
• 解壓頁淘汰時，壓縮頁沒有一起淘汰并且壓縮頁未被修改時（buf_LRU_free_page和buf_CLOCK_free_page）
  
• flush list中類型的頁面完成刷盤，壓縮頁重新處于干凈狀態(tài)時（buf_flush_remove）
  

壓縮頁完成解壓后，就會從zip clean鏈表中刪除，然后根據(jù)請求是否帶有independent hint來判斷，解壓頁是加入unzip LRU list還是unzip CLOCK list。
1.2.8 Zip free list

zip free list是用來管理壓縮頁伙伴系統(tǒng)的鏈表，對應結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_buddy_free_t) zip_free[BUF_BUDDY_SIZES_MAX]。buf_buddy_free_t由三部分組成分別記錄了狀態(tài)、頁面描述符和下一節(jié)點指針，鏈表的第一個buf_buddy_free_t會記錄鏈表中節(jié)點頁面大小。從zip free list對應結(jié)構(gòu)可以看出，其由多個對應page size不同大?。?6K、8K、4K、2K、1K）的鏈表組成。構(gòu)成zip free list的所有page的類似為BUF_BLOCK_MEMORY，所有頁面存入zip hash中。
壓縮頁讀取時，需要從zip free list中申請空間到block→page.zip.data，用于存儲壓縮頁原始數(shù)據(jù)（buf_buddy_alloc），下面舉例說明其申請過程，假設申請2K的空間：

• 如果沒有在size為2K的鏈表上找到空閑空間，則去4K鏈表上尋找；找到則會進行伙伴分裂，高地址2K空間插入到2K鏈表中，低地址的2K空間返回。
  
• 如果沒有在size為4K的鏈表上找到空閑空間，則去8K鏈表上尋找；找到則對8K空間進行2次伙伴分裂，將高地址空間的4K和2K分別插入對應鏈表，將最低地址的2K返回。
  
• 如果沒有在size為8K的鏈表上找到空閑空間，則去16K鏈表上尋找；找到則對16K空間進行3次伙伴分裂，將高地址空間的8K、4K和2K分別插入對應鏈表，將最低地址的2K返回。
  
• 如果沒有size為16K的鏈表，則通過buf_LRU_get_free_block從free list上申請新的頁面，通過buf_buddy_block_register函數(shù)將頁面設置為BUF_BLOCK_MEMORY，插入zip hash。之后進行4次伙伴分裂，將高地址空間的8K、4K和2K分別插入對應鏈表，將最低地址的2K返回。
  

伙伴系統(tǒng)調(diào)用buf_buddy_alloc釋放空間。對于size為16K的空間回收，則直接清空后掛回到16K鏈表即可。對于size低于16K的空間回收，會先遞歸尋找其伙伴空間，如果伙伴空間也處于空閑狀態(tài)，則合并至更大的size；如果合并失敗，則將釋放的空間掛至zip free對應鏈表中。通過這樣的方式，盡可能減少伙伴系統(tǒng)中的內(nèi)存碎片。
1.2.9 Withdraw list

withdraw list僅僅用于buffer pool縮小過程（bp resize），對應的結(jié)構(gòu)為buf_pool_t中的UT_LIST_BASE_NODE_T(buf_page_t) withdraw。下面介紹buffer pool resize的過程：

• 用戶設置innodb_buffer_pool_size參數(shù)會觸發(fā)buffer pool size的更新函數(shù)innodb_buffer_pool_size_update，該函數(shù)設置srv_buf_resize_event，借此方式通知buffer pool更新事件。
  
• 專門用于處理buffer pool resize的后臺線程buf_resize_thread接到srv_buf_resize_event事件，調(diào)用buf_pool_resize開啟resize實際過程。
  
• 如果開啟adaptive hash index（AHI），則暫時關閉并清空。
  
• 如果目標空間小于當前空間，則計算withdraw_target。當前buffer pool instance的最后部分多余的chunks將被回收。接下來借用withdraw list匯總收縮空間的頁面（buf_pool_withdraw_blocks），buf_pool_withdraw_blocks詳細邏輯如下：
  

• 合并伙伴系統(tǒng)（zip free list）中空閑的頁面（buf_buddy_condense_free）。
  
• 掃描free list，將待收縮空間的頁面從free list摘下，存入withdraw list。先處理free list的原因是避免后續(xù)LRU/CLOCK list重新分配頁面的時候使用收縮空間的頁面。
  
• 將LRU list進行一次刷盤，flush LRU長度受innodb_lru_scan_depth，innodb_buffer_pool_size變化量，當前LRU list長度、當前CLOCK list長度等因素影響。
  
• 掃描LRU list，將處于收縮空間的壓縮頁在伙伴系統(tǒng)中重新分配空間（buf_buddy_realloc），處于收縮空間的普通頁在free list重新申請頁面（buf_page_realloc）。
  
• 掃描CLOCK list，將處于收縮空間的壓縮頁在伙伴系統(tǒng)中重新分配空間（buf_buddy_realloc），處于收縮空間的普通頁在free list重新申請頁面（buf_page_realloc）。
  
• 如果withdraw list的長度未達到withdraw_target，則循環(huán)掃描buffer pool，單次循環(huán)10次沒有達成目標，返回true表示本次回收不成功。
  
• withdraw list的長度達到withdraw_targe后，逐一校驗所有收縮空間的頁面是否都在withdraw list中（檢查block→in_withdraw_list狀態(tài)）。
  

• 停止正在進行的buffer pool load（頁面預熱的一種方式，后續(xù)將詳細介紹）。
  
• 如果上一次buf_pool_withdraw_blocks回收失敗，則打印所有非尚未啟動狀態(tài)的事務（trx_sys→mysql_trx_list）到錯誤日志告警，然后休眠一段時間后再次進入buf_pool_withdraw_blocks掃描buffer pool。休息時間規(guī)則為：重試次數(shù)5次及以內(nèi)，休眠時間為重試次數(shù)*2s，重試次數(shù)大于5次，則只休眠10s。
  
• 上述所有過程允許并發(fā)負載，接下來將獲取buffer pool所有mutex，鎖定整個buffer pool，不再允許任何并發(fā)。
  
• 刪除或者新增chunks：如果是收縮buffer pool，使用deallocate_chunk將多余的chunk，釋放withdraw list；如果是擴展buffer pool，使用ut_zalloc_nokey_nofatal分配新內(nèi)存，使用buf_pool_register_chunk初始化新chunk。
  
• 根據(jù)調(diào)整的結(jié)果，將buf_pool→curr_size調(diào)整到chunks的倍數(shù)，再重新設置innodb_buffer_pool_size。
  
• 如果新的buffer pool size是舊size的2倍或者不到1/2，將重新設置page hash和zip hash（buf_pool_resize_hash）。
  
• 釋放buffer pool所有鎖，允許并發(fā)負載。
  
• 如果新的buffer pool size是舊size的2倍或者不到1/2，進行l(wèi)ock_sys_resize和dict_resize，重新設置lock_sys->rec_hash、lock_sys->prdt_hash、lock_sys->prdt_page_hash、dict_sys->table_hash和dict_sys→table_id_hash等結(jié)構(gòu)的大小。
  
• 重新開啟AHI。
  

1.2.10 Hazard point

hazard point是用來避免逆向掃描鏈表過程的迭代器。hazard point與普通迭代器不同，當掃描過程的下一節(jié)點被其他操作移除或替換了時，hazard point能調(diào)整位置并指向被移除或替換的節(jié)點的下一有效節(jié)點，避免逆向掃描過程失敗。使用hazard point逆向掃描鏈表的時間復雜度為O(N)，可以避免逆向掃描失敗時從頭開始掃描而導致的最高 O(N*N)的時間復雜度。因此hazard point廣泛應用于flush list、LRU list、CLOCK list等鏈表的批量操作中的鏈表掃描中。
hazard point的實現(xiàn)也不復雜，對應的基類為HazardPointer，包括get、set、is_hp、adjust、move等方法。使用于不同的鏈表時，基于基類派生出不同的子類，并添加定制化的方法。當逆向掃描鏈表時，每次循環(huán)通過get函數(shù)獲取下一個節(jié)點，并將節(jié)點的下一節(jié)點設置為hazard point。并發(fā)的負載如果修改了鏈表，并且節(jié)點是hazard point（is_hp返回為true），則使用adjust函數(shù)將被修改的節(jié)點的下一節(jié)點設置為hazard point。
1.2.11 總結(jié)

上述介紹的鏈表都是用于管理需要持久化的頁面的緩存。從內(nèi)存來源來看，除未解壓的壓縮頁的buf_page_t存儲于臨時分配空間，其他所有頁面都存儲于buf_pool→chunks中。從頁面分布來看，通常而言，LRU list和CLOCK list描述了所有在buffer pool中的頁面，unzip LRU list、unzip CLOCK list、flush list都是LRU list + CLOCK list的子集。從用途來看，LRU/unzip LRU list、CLOCK/unzip CLOCK list、free list、zip free list、flush list屬于常規(guī)鏈表，服務于數(shù)據(jù)庫正常服務，zip clean list和withdraw list屬于特殊用途的list，zip clean list用于debug模式下壓縮頁面的調(diào)試，withdraw list僅僅服務于buffer pool resize。
第二部分、Buffer pool快速讀寫優(yōu)化

2.1 Buffer pool初始化

Buffer pool初始化入口是buf_pool_init。在buf_pool_init中先通過ut_zalloc_nokey分配管理所有buffer pool instance的結(jié)構(gòu)體（buf_pool_t）的buf_pool_ptr，接著為每個instance創(chuàng)建buf_pool_create線程來初始化instance中的鏈表、chunks、mutex、page_hash、zip_hash、hazard_point、用于purge異步讀取頁面的watch結(jié)構(gòu)體等。chunks初始化結(jié)束后，逐一對每個block調(diào)用buf_block_init，對block的io、是否在邏輯鏈表、是否在page hash、zip hash等信息進行初始化，并添加到buf_pool->free鏈表中。
Buffer pool初始化過程中，內(nèi)存申請比較常見的是使用減少了用戶空間與內(nèi)核空間地址拷貝（零拷貝）的mmap。在chunks初始化時，也會調(diào)用os_mem_alloc_large分配內(nèi)存，嘗試在Linux支持的情況下采用HUGETLB的方式分配內(nèi)存。
2.2 單機buffer pool預熱

MySQL官方為了讓實例能夠在重啟后快速恢復到重啟前的狀態(tài)，在MySQL 5.6版本開始支持了buffer pool單機預熱的功能。單機預熱功能分為dump和load兩個步驟。
dump將實例重啟前的所有buffer pool instance的LRU list中每個頁面的space_id和page_no記錄到本地innodb_buffer_pool_filename文件中。（space_id是數(shù)據(jù)文件的編號，page_no數(shù)據(jù)文件內(nèi)的偏移。space_id與page_no可以唯一確定一個頁面，詳見淺析InnoDB文件結(jié)構(gòu)）。為了盡可能避免掃描過程對buffer pool正常工作的影響，dump先將LRU list掃描過程中的頁面信息記錄在臨時的數(shù)組中，掃描LRU list后立刻釋放LRU_list_mutex鎖，再在無鎖的情況下將LRU list的信息寫入innodb_buffer_pool_filename文件中。
load在實例重啟后將本地innodb_buffer_pool_filename文件中記錄的所有頁面加載到buffer pool中，從而完成數(shù)據(jù)預熱，將實例快速恢復成重啟前的狀態(tài)。load操作會遍歷innodb_buffer_pool_filename文件兩次（由于每個頁面的信息只包括space_id和page_no，一共只占8個字節(jié)，正常情況下文件只有幾百K到幾G的級別，兩次掃描帶來的IO量尚可接受）。第一次遍歷整個文件以確定其中總共包含的page記錄數(shù)，如果page記錄數(shù)超過當前buffer pool size，調(diào)整待讀入的page總數(shù)。第二遍掃描文件時，先按照第一遍得到的page數(shù)量，創(chuàng)建好page數(shù)組，再依次讀入innodb_buffer_pool_filename文件中所有的page記錄。為提高IO效率，對page數(shù)組進行按照space_id和page_no排序。最后才使用buf_read_page_background函數(shù)在后臺將所有頁面加載到LRU list中的midpoint中。
官方數(shù)據(jù)預熱的特點如下：

• 能夠精準高效地恢復實例重啟前的狀態(tài)。
  
• 應用場景比較有限，只能用于單機預熱，無法解決主從切換、跨機遷移場景的預熱需求。
  

2.3 主從buffer pool同步

MySQL官方提供的dump和load操作只能用于單機預熱的根本原因是：MySQL的主從復制是邏輯復制，非物理復制。數(shù)據(jù)雖然是一致的，但是主從數(shù)據(jù)的分布是不一樣的。InnoDB的所有數(shù)據(jù)都存儲于B+樹中，也可簡單理解為主從所對應數(shù)據(jù)的B+樹的結(jié)構(gòu)是不一樣的，在從庫按部就班加載B+樹相同位置的頁面無法解決主從切換、跨機遷移等多場景的預熱問題。
主從緩存同步是CDB針對主從多場景下快速buffer pool預熱的解決方案，其從邏輯復制的思路出發(fā)，通過主從邏輯數(shù)據(jù)一致的角度解決了多場景的預熱問題。主從緩存同步分為snapshot、transmit、recover三個步驟：
snapshot將主庫buffer pool狀態(tài)邏輯導出到主庫本地的ib_bp_info文件中，具體過程如下（buf_snapshot）：

• 逐一掃描每個所有buffer pool instance的LRU list和CLOCK list中的每個頁面，將頁面的space_id和page_no匯總到以space_id為key，unordered_set為value的lru_maps中。掃描結(jié)束后，所有頁面按照space_id進行了初步歸類。
  
• 逐一處理每個space_id下的頁面。通過頁面的前后節(jié)點指針，將相鄰的頁面串聯(lián)成頁面鏈表，并用最左頁面、最左頁面的第一條用戶記錄、最右頁面、最右頁面最后一條用戶記錄代表該頁面鏈表，存入multi_ranges中（link_page）。
  
• 將multi_ranges中所有record range按照一定格式落盤到本地ib_bp_info文件中。
  

針對如何傳輸ib_bp_info文件，有很多備選方案：采用scp來傳輸文件誤操作的可能性比較高，并且經(jīng)常修改傳輸腳本；采用binlog傳輸會加重binlog的負擔，加大主從延遲的風險，方案復雜，風險大；采用內(nèi)建表的方式同步文件又擔心引入兼容性的問題。主從緩存通過最終選擇了transmit方案，即在slave新創(chuàng)建一種與IO線程相似，需要與master建立tcp連接的transmit線程（handle_slave_transmit），該線程負責向master發(fā)送ib_bp_info文件傳輸申請，并負責接收ib_bp_info文件。transmit方案不侵入主從復制的原有邏輯，對于不支持transmit的主庫，也僅僅是無法從主庫獲取ib_bp_info文件，不存在兼容問題。
recover將ib_bp_info文件中代表的數(shù)據(jù)加載到從庫buffer pool中。recover可以在跨機遷移前、版本升級前、主從切換前或切換過程中進行，也可以定期將主庫的buffer pool同步到從庫，隨時做好切換準備。recover具體過程如下（buf_recover）：

• 按固定格式識別ib_bp_info中的record_range信息。
  
• 在從庫通過B+樹搜索record_range最左頁面的第一條用戶記錄和最右頁面的最后一條用戶記錄對應的兩個頁面。
  
• 將上述兩個頁面之間的所有頁面加載到buffer pool中。為了避免新加載的頁面互相淘汰，recover操作還支持將新頁面直接加載到LRU list的頭部而不是midpoint。
  
• 重復1-3步驟，直至ib_bp_info中所有recored_range被處理完成。
  

2.4 Change buffer優(yōu)化

2.4.1 原理

innodb的二級索引與cluster index相同，也存儲在B+樹中。cluster index與二級索引的B+樹節(jié)點散落在數(shù)據(jù)文件中。在此架構(gòu)下，一條普通的DML都可能因為需要修改多個二級索引，而帶來大量隨機IO，對innodb的性能帶來巨大挑戰(zhàn)。
change buffer就是為了解決二級索引隨機IO問題而引入的緩存。當待插入、刪除、修改的記錄所在的二級索引頁面不在buffer pool中時，修改內(nèi)容會以記錄的形式緩存到change buffer中。當二級索引頁面最終被讀入buffer pool中時，需要檢查change buffer中是否有該頁面的修改記錄，如果存在需要將修改記錄合并到新讀入的二級索引頁面上，再返回。change buffer適用于buffer pool大小有限，無法將所有數(shù)據(jù)緩存到buffer pool，并且有大量二級索引需要更新的場景。但如果buffer pool足夠大到能緩存所有索引頁面，或者隨機IO的速度和順序IO的速度所差無幾，也可以考慮關閉change buffer。
2.4.2 實現(xiàn)

innodb在Mysql-5.5版本之前的版本中只支持了二級索引的insert buffer，后續(xù)才支持了update和delete，名稱改為了change buffer。而在代碼層面上，很多以ibuf為前綴的參數(shù)、函數(shù)、文件沿襲了下來，沒有做修改。
change buffer本身也是一顆B+樹，它位于系統(tǒng)表空間（space_id為0），根結(jié)點的page_no固定為4（FSP_IBUF_TREE_ROOT_PAGE_NO），所有innodb用戶表的二級索引變更都緩存在同一顆B+樹上。一條change buffer record中的信息包括：

• IBUF_REC_FIELD_SPACE：二級索引的space_id。
  
• IBUF_REC_FIELD_MARKER：用于以4.1.x版本為界區(qū)分新舊版本，新版本該值為0。
  
• IBUF_REC_FIELD_PAGE：二級索引的 page_no。
  
• IBUF_REC_FIELD_METADATA分為以下三項信息：
  
  
  
  • IBUF_REC_OFFSET_COUNTER：相同space_id和page_no頁面內(nèi)的操作序號，單調(diào)遞增。
    
  • IBUF_REC_OFFSET_TYPE：緩存的操作的類型，IBUF_OP_INSERT（插入）；IBUF_OP_DELETE_MARK （用戶刪除，二級索引的刪除都是delete_mark + insert）；IBUF_OP_DELETE（purge操作）。
    
  • IBUF_REC_OFFSET_FLAGS：待操作的用戶記錄格式，REDUNDANT / COMPACT。
    
  
  

• IBUF_REC_FIELD_USER：用戶列數(shù)據(jù)。
  

change buffer的B+樹以（space_id、page_no、counter）為主鍵，來確保記錄的唯一性以及apply時的順序。change buffer在正常運行過程中必須保證緩存合并到二級索引后，二級索引不能發(fā)生分裂或合并操作，否則緩存到主鍵將對應到未知的頁面而失效。為此需要實時獲取目標二級索引頁面的剩余空間，innodb的方案是在數(shù)據(jù)文件中（ibdata或ibd）。page_size是默認大小16KB的情況下，page_no為1、1+16384*N的頁面都是FIL_PAGE_IBUF_BITMAP類型，用于記錄其后16384個頁面change buffer的信息。FIL_PAGE_IBUF_BITMAP頁面用4個bit來描述一個頁面：

• IBUF_BITMAP_FREE占2個bit，表示頁面空閑的空間范圍。其值是頁面當前剩余空間max_ins_size/512字節(jié)的結(jié)果。0表示max_ins_size處于[0,512)字節(jié)中間，1表示max_ins_size處于[512,1024)字節(jié)中間，2表示max_ins_size處于[1024,2048)字節(jié)中間，3表示max_ins_size大于2048字節(jié)（ibuf_index_page_calc_free_bits）。
  
• IBUF_BITMAP_BUFFERED占1個bit：表示頁面是否有操作緩存，準備向change buffer B+tree插入前會將對應二級索引頁面的IBUF_BITMAP_BUFFERED設置為true（ibuf_insert_low）。二級索引頁面物理頁面被讀入buffer pool時會根據(jù)該標記判斷是否需要進行change buffer 合并操作（buf_page_io_complete）。
  
• IBUF_BITMAP_IBUF占1個bit：表示頁面是否為change buffer B+tree 的節(jié)點。
  

DML運行過程中會實時將二級索引信息變化更新到FIL_PAGE_IBUF_BITMAP頁面中。在change buffer插入過程中，如果發(fā)現(xiàn)準備插入的change buffer record可能會導致二級索引頁面分裂，則插入失敗并調(diào)用ibuf_get_merge_page_nos觸發(fā)一次從當前cursor位置附近開始的異步的change buffer 合并操作，目的是盡量將當前頁面的緩存操作做一次合并（ibuf_insert_low）。此外為避免出現(xiàn)空頁面，需要在purge線程真正刪除記錄時使用ibuf_get_volume_buffered預估合并完頁面所有change buffer record之后的記錄數(shù)，如果二級索引頁面上記錄等于1（加上purge線程這次緩存的刪除操作將變?yōu)榭枕撁妫?，則索引插入失敗，改走正常讀入物理頁面邏輯。
二級索引記錄沒有trx_id這一系統(tǒng)列，這為緩存purge線程刪除記錄操作帶來了困難，難以區(qū)分真正要刪除掉的記錄。為避免purge線程刪除操作誤刪用戶reinsert的二級索引記錄，如果purge操作先進入ibuf_insert，則用戶后續(xù)的insert操作將放棄緩存插入，轉(zhuǎn)而讀取物理頁面；如果insert操作先進入ibuf_insert，則purge操作也放棄緩存刪除。
change buffer頁面的與普通索引頁面相同，其修改也是先記錄redo日志后刷盤，在crash recover時，同樣需要redo來保證一致性。change buffer可以理解為記錄在index page上的二級索引更改日志。
2.4.3 緩存條件

只有滿足一定條件時，二級索引變更才會被change buffer緩存，判斷條件如下（ibuf_should_try）：

• 用戶設置了innodb_change_buffering，innodb_change_buffer_max_size非0。
  
• 非數(shù)據(jù)字典表空間，非聚簇索引，非空間索引。
  
• 對IBUF_OP_INSERT操作要求二級索引為非unique類型，對于其他操作不限制二級索引是否為unique類型。
  
• 只緩存二級索引葉子結(jié)點（不包括B+樹只有一層時的根節(jié)點）。
  
• 表上沒有flush 操作，例如執(zhí)行flush table for export時，不允許對表進行緩存 （通過dict_table_t::quiesce進行標識）。
  
• 二級索引不能只包含降序列。
  

2.4.4 合并時機

有以下幾種場景會觸發(fā)change buffer合并操作：

• 用戶線程觸發(fā)二級索引頁面的讀取時，例如用戶通過二級索引查詢數(shù)據(jù)（buf_page_io_complete）。
  
• 嘗試將緩存插入change buffer，但預估二級索引頁面空間不足，可能導致頁面分裂時，會調(diào)用ibuf_get_merge_page_nos從當前cursor位置附近開始的異步的change buffer merge（ibuf_insert_low）。
  
• change buffer B+tree size空間變化（ibuf_contract_after_insert）：
  
  
  
  • size小于innodb_change_buffer_max_size配置大小時，不做處理。
    
  • size介于innodb_change_buffer_max_size配置大小與innodb_change_buffer_max_size配置大小 + 5之間，執(zhí)行一次異步change buffer merge，位置隨機。
    
  • size大于innodb_change_buffer_max_size配置大小 + 5 （IBUF_CONTRACT_ON_INSERT_SYNC）時，執(zhí)行一次同步change buffer merge（ibuf_contract），位置隨機。
    
  • size大于innodb_change_buffer_max_size配置大小 + 10（IBUF_CONTRACT_DO_NOT_INSERT）時，執(zhí)行一次同步change buffer merge（ibuf_contract），不再允許change buffer插入。
    
  
  

• innodb master線程調(diào)用ibuf_merge_in_background 合并change buffer。master線程較為空閑時，會以100%的io capacity合并change buffer（srv_master_do_idle_tasks），系統(tǒng)活躍時則根據(jù)change buffer size來控制io capacity，size越大io capacity比例越高（srv_master_do_active_tasks）。
  
• slow shutdown時，會調(diào)用ibuf_merge_in_background全量合并change buffer（srv_master_do_shutdown_tasks）。
  
• 對某個表執(zhí)行flush table for export操作時，會調(diào)用ibuf_merge_space強制合并change buffer（row_quiesce_table_start）。合并change buffer是為flush for export準備的，避免準備拷貝的ibd文件對change buffer有依賴。
  

2.5 Adaptive hash index優(yōu)化

2.5.1 原理

innodb的數(shù)據(jù)存儲于B+樹中，B+樹通常不會太高，通常只有3到5層。從根節(jié)點到葉節(jié)點的尋路涉及到多層頁面內(nèi)記錄的比較，即使所有路徑上的頁面都在內(nèi)存中，也是比較消耗CPU的操作。
對尋路到CPU開銷優(yōu)化分兩部分，第一部分為盡可能避免尋路次數(shù)，innodb為此設計了多個優(yōu)化，例如一次尋路多緩存幾條記錄到fetch_cache中；尋路結(jié)束將cursor緩存到row_prebuilt_t::pcur，方便下次查詢復用。第二部分為盡可能避免單詞尋路的開銷。Adaptive hash index（AHI）便是為此而設計。AHI可以理解為建立在B+樹上的索引，它采用自適應的方式管理，為B+樹尋路建立以查詢條件為key，B+樹record地址為value的hash index。
AHI的大小為buffer pool size的1/64，在buf_pool_init中調(diào)用btr_search_sys_create初始化。為了避免AHI的鎖競爭壓力，innodb支持AHI分區(qū)，可以使用innodb_adaptive_hash_index_parts參數(shù)配置分區(qū)個數(shù)，默認為8。當buffer pool size動態(tài)調(diào)整大小為原大小的2倍以上或者1/2以下時，AHI也隨之調(diào)用btr_search_sys_resize調(diào)整大小（buf_pool_resize）。
2.5.2 創(chuàng)建過程

當innodb_adaptive_hash_index參數(shù)打開，非臨時表、非空間類型的索引會累加索引被使用的次數(shù)，當使用次數(shù)小于17（BTR_SEARCH_HASH_ANALYSIS），當前索引被認為不夠熱，被自動忽略（btr_search_info_update）。索引次數(shù)達標后，進入下一步驟。
AHI的key與用戶的查詢條件相關，每個索引（dict_index_t）都包含用于存儲查詢條件的search_info（btr_search_t）。search_info主要用三項信息描述查詢條件：完整匹配的匹配列數(shù)n_fields，不完整匹配的列的前綴字節(jié)數(shù)n_bytes，是否為左側(cè)匹配left_side。如果查詢條件與上一次緩存的相同，則將search_info->n_hash_potential加1。否則清空search_info，重新設定index的查詢條件（btr_search_info_update_hash）。
即使索引通過了篩選，查詢條件通過了考核，AHI也不會對索引的每個頁面都建立hash index。對于需要創(chuàng)建AHI的頁面還需要經(jīng)過一輪篩選：某頁如果能通過當前search_info命中，則對頁面的n_hash_helps加1（當前search_info首次命中到頁面，還會將search_info信息記錄在頁面buf_block_t中）。如果頁面的n_hash_helps大于記錄數(shù)/16（BTR_SEARCH_PAGE_BUILD_LIMIT）并且search_info->n_hash_potential大于100（BTR_SEARCH_BUILD_LIMIT），則對該頁面創(chuàng)建AHI。對于已經(jīng)創(chuàng)建過AHI的頁面，只有頁面的n_hash_helps大于記錄數(shù)的兩倍，或者search_info發(fā)生改變了才會重新創(chuàng)建AHI（btr_search_update_block_hash_info）。
創(chuàng)建AHI之前，會先檢查AHI鎖的狀態(tài)，如果其他線程正在持有AHI的X鎖，則先跳過本次AHI的創(chuàng)建。原因是當前處于B+樹搜索的關鍵路徑，在此處等鎖會拖累其他B+樹的搜索效率，而本次search_info→n_hash_potential和頁面的n_hash_helps狀態(tài)并未清空，下一次該頁面被讀取時會再次觸發(fā)AHI創(chuàng)建流程。AHI的創(chuàng)建過程分為5步（btr_search_build_page_hash_index）：

• 再次判斷innodb_adaptive_hash_index參數(shù)打開，并且當前索引非臨時表索引。
  
• 加AHI的S鎖，如果當前頁面已經(jīng)創(chuàng)建AHI并且與當前search_info不同，則解鎖后調(diào)用btr_search_drop_page_hash_index刪除舊AHI索引，否則直接解開S鎖。
  
• 根據(jù)當前search_info挑選出具有代表性的記錄，計算hash fold值，并記錄在folds和recs兩個數(shù)組中。舉例，假設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)
  

• 重新加上AHI的X鎖，檢查block上的search_info，如果發(fā)生變化則放棄本次AHI構(gòu)建，否則插入上一步準備好的folds和recs兩個數(shù)組，插入AHI中。
  
• 解開AHI的X鎖，釋放folds和recs兩個數(shù)組的內(nèi)存。
  

2.5.3 使用條件

AHI的使用在B+樹搜索的關鍵路徑上，使用AHI的幾個條件如下（btr_cur_search_to_nth_level）：

• AHI處于非X鎖狀態(tài)。AHI查詢過程中要加AHI的S鎖，等鎖會導致AHI得不償失。
  
• 加鎖模式為BTR_SEARCH_LEAF或BTR_MODIFY_LEAF，即本次查詢不變更B+樹結(jié)構(gòu)，只在葉子節(jié)點查詢或者修改頁面內(nèi)的單條記錄。
  
• 索引上的search_info顯示上一次AHI使用成功。
  
• 當前索引非空間索引。
  

滿足上述條件后，在正式搜索AHI之前，會再次對比索引的最新search_info是否已經(jīng)被重置了，即search_info→n_hash_potential是否等于0，以及當前查詢條件的列數(shù)相比search_info是否完整。前者等于0意味著當前舊AHI記錄已經(jīng)被刪除；后者查詢條件不足意味著當前查詢條件不足以構(gòu)建AHI的key值進行查詢，兩種情況都只能放棄AHI查詢，轉(zhuǎn)而使用正常的B+樹搜索（btr_search_guess_on_hash）。接下來，將查詢條件轉(zhuǎn)化為AHI的key值，加AHI的S鎖從AHI中讀取數(shù)據(jù)（ha_search_and_get_data）。如果查詢失敗了，并且頁面上的search_info信息依舊與索引上的search_info相同，則會將新的記錄插入AHI中（btr_search_update_hash_ref）。
從上述AHI創(chuàng)建過程中可以看到，只有較為查詢模式較為固定的業(yè)務才能經(jīng)過層層篩選，創(chuàng)建出AHI，從該功能中受益。
2.5.4 自適應維護

• 自動插入與更新：葉節(jié)點的新記錄如果未產(chǎn)生頁面重組，則新記錄插入或更新到AHI中（btr_search_update_hash_on_insert、btr_search_update_hash_node_on_insert）。
  
• 自動記錄刪除：記錄刪除時，如果記錄的fold存在于AHI中，則將其刪除（btr_search_update_hash_on_delete）。
  
• 自動全頁面記錄刪除：AHI作用是加速內(nèi)存中B+數(shù)的搜索。當頁面從內(nèi)存淘汰（buf_LRU_free_page或buf_CLOCK_free_page）時，AHI會自動刪除。此外，頁面發(fā)生合并、分裂時記錄地址發(fā)生變更，調(diào)整后的頁面相當于新讀入內(nèi)存的頁面，舊AHI信息會刪除（btr_search_drop_page_hash_index）。刪除方法為找到頁面所有具有代表性的folds，調(diào)用ha_remove_all_nodes_to_page刪除。
  
• 自動全索引AHI刪除：當索引被刪除時則需要所有此索引相關AHI刪除。刪除方法為遍歷LRU list和CLOCK list上的所有頁面，將該索引的頁面存入數(shù)組中。最后注意刪除每個頁面的AHI記錄（btr_drop_ahi_for_index）。
  
• 自動全表記錄AHI刪除：當表被刪除時，觸發(fā)全表記錄的AHI刪除。刪除方法為逐一刪除每個索引的AHI記錄（btr_drop_ahi_for_table）。不過當表非常大時，全表記錄的AHI刪除非常緩慢，刪表過程持有dict_sys->mutex，將長時間阻塞此實例其他DDL操作，其他DDL操作也會長期持有更多資源，進而阻塞整個系統(tǒng)。一種tradeoff的做法是當改表的AHI記錄數(shù)量足夠多或者比例足夠大時將整個AHI都清空。AHI的清空不影響數(shù)據(jù)查詢的正確性，而AHI最終還能再次創(chuàng)建。上述方法可以用此暫時的效率降低換來系統(tǒng)的穩(wěn)定。
  

第三部分、頁面讀取過程解讀

3.1 頁面讀取堆棧

buf_page_get_gen  Buf_fetch<T>::single_page    Buf_fetch_normal::get      lookup      read_page        buf_read_page_low          buf_page_init_for_read            buf_LRU_get_free_block              buf_LRU_get_free_only              buf_LRU_scan_and_free_block                buf_LRU_free_from_unzip_LRU_list                  buf_LRU_free_page                    buf_LRU_block_remove_hashed                buf_LRU_free_from_common_LRU_list              buf_flush_single_page_from_LRU            buf_LRU_add_block              buf_LRU_add_block_low          fil_io          buf_page_io_complete
復制
3.2 核心函數(shù)概述
buf_page_get_gen

• 檢查頁面獲取mode是否是7類獲取模式之一，不是則報錯。
  
• 如果頁面獲取類型是NORMAL并且頁面不是系統(tǒng)臨時系統(tǒng)表，則使用Buf_fetch_normal的single_page函數(shù)獲取頁面；否則頁面采用Buf_fetch_other的single_page函數(shù)獲取頁面。
  

Buf_fetch<T>::single_page

• 調(diào)用Buf_fetch子類的的get函數(shù)（例如Buf_fetch_normal::get、Buf_fetch_other::get）獲取頁面，如果get函數(shù)結(jié)果為DB_NOT_FOUND，則向上返回nullptr，否則繼續(xù)往下。
  
• 檢查頁面獲取類型是否為樂觀類型（IF_IN_POOL或PEEK_IF_IN_POOL），持鎖獲取block的io_fix（表示IO操作狀態(tài)）的狀態(tài)，如果是BUF_IO_READ狀態(tài)，說明頁面正在讀到BP的過程中，不繼續(xù)等待其完成，將block的buf_fix_count（表示當前對該頁面操作的次數(shù)）減1，返回nullptr。
  
• 用check_state和debug_check檢查block的狀態(tài)，如果狀態(tài)是DB_NOT_FOUND，則返回nullptr；如果狀態(tài)是DB_FAIL則從1重新開始。
  
• 調(diào)用buf_page_is_accessed獲取block的第一次讀取時間access_time，如果access_time=0，表示這是block第一次被讀取。
  
• 如果頁面獲取模式非scan類型，則為access_time為0的頁面設置access_time，假設頁面獲取模式非scan且非PEEK_IF_IN_POOL，則調(diào)用buf_page_make_young_if_needed在需要的時候make young，即將頁面移入lru的young list頭部，避免其快速被淘汰。
  
• 使用buf_wait_for_read函數(shù)等待頁面完成讀入。
  
• 如果讀取模式不是PEEK_IF_IN_POOL或者SCAN，并且是第一次讀入的話調(diào)用buf_read_ahead_linear進行線性預讀。結(jié)束后向上一層函數(shù)返回block。
  

Buf_fetch_normal::get

• 使用normal模式讀取頁面。先調(diào)用look_up函數(shù)page_hash中查找，找到則用buf_block_fix對page的buf_fix_count++，表示增加了一個線程在讀取這個頁面，解鎖page_hash分區(qū)鎖。
  
• lookup失敗則使用read_page函數(shù)在磁盤中讀取該頁面。失敗則再次回到1嘗試（異步IO的緣故），讀取成功后返回block。
  

Buf_fetch_other::get

• 使用非normal模式讀取頁面。先調(diào)用look_up函數(shù)page_hash中查找。調(diào)用buf_block_fix對buf_fix_count++，表示增加了一個線程在讀取這個頁面，解鎖page_hash分區(qū)鎖。（臨時表空間使用block->mutex在用戶線程和刷盤線程之間同步，需要額外加block->mutex）
  
• 如果讀取模式是IF_IN_POOL_OR_WATCH，調(diào)用is_on_watch等待block被讀取并得到block。
  
• 如果block此時非空，從循環(huán)中退出并返回找到block。
  
• 如果頁面獲取類型是樂觀類型（IF_IN_POOL或PEEK_IF_IN_POOL）或者為IF_IN_POOL_OR_WATCH，返回nullptr。
  
• 使用read_page函數(shù)在磁盤中讀取該頁面。失敗則再次回到1嘗試（異步IO的緣故），讀取成功后返回block。
  

Buf_fetch<T>::lookup

• 在hash_scan中查找頁面。先獲取分區(qū)鎖。
  
• 加鎖后，擔心page_hash情況有變，用buf_page_hash_lock_s_confirm再次確認，如果確認鎖變化了，則在循環(huán)中釋放舊鎖加上新鎖，再次檢測，直到變化結(jié)束。
  
• 如果guess block不在bp中，或者不屬于BUF_BLOCK_FILE_PAGE類型說明猜測失敗。嘗試用buf_page_hash_get_low從page_hash中讀取頁面，如果還是讀取失敗則解鎖page_hash的分區(qū)鎖然后返回nullptr，如果從buf_page_hash_get_low讀到頁面，從buf_pool->watch檢查這個頁面是否是被watch的頁面，是的話解鎖page_hash的分區(qū)鎖然后返回nullptr，否的話返回頁面。
  

Buf_fetch<T>::read_page

• scan模式異步調(diào)用buf_read_page_low異步讀取頁面。其他模式調(diào)用buf_read_page同步讀取頁面，buf_read_page底層也是調(diào)用buf_read_page_low，但是輸入的是同步讀取參數(shù)。讀取失敗則最多重試BUF_PAGE_READ_MAX_RETRIES次，直至成功。
  
• 同步讀取的話還會嘗試隨機預讀，隨機預讀為：一個extent中超過一定數(shù)量的頁面被讀取則將整個extent全部讀取到內(nèi)存。
  

buf_read_page_low

此函數(shù)的第四參數(shù)mode并非Page_fetch，而是BUF_READ_IBUF_PAGES_ONLY和BUF_READ_ANY_PAGE二選一，前者是指讀取ibuf頁面。

• 支?持同步和異步讀取，如果是ibuf_bitmap或者系統(tǒng)表空間事務頭頁面（0，5）則直接不論傳入的參數(shù)是同步讀取還是異步讀取，都改為同步讀取。
  
• 使用buf_page_init_for_read準備一個空block，函數(shù)邏輯后續(xù)有詳細介紹。
  
• 如果是同步模式，調(diào)用thd_wait_begin，準備同步等待io完成。
  
• 如果是壓縮頁面的話，讀入的內(nèi)存位置是bpage->zip.data，否則是((buf_block_t *)bpage)->frame。調(diào)用fil_io讀取頁面。
  
• 如果是同步模式，調(diào)用thd_wait_end，表示同步io結(jié)束。
  
• 如果出現(xiàn)表空間不存在等情況導致io不成功，調(diào)用buf_read_page_handle_error報錯。
  
• 如果是同步模式，調(diào)用buf_page_io_complete。buf_page_io_complete簡單分兩類BUF_IO_READ、BUF_IO_WRITE。對于BUF_IO_READ，通過頁面前后的checksum檢查頁面是否損壞，損壞的話，得看srv_force_recovery的級別，如果低于SRV_FORCE_IGNORE_CORRUPT，則使用報錯。沒有報錯則修改頁面狀態(tài)為BUF_IO_NONE，更新統(tǒng)計信息；對于BUF_IO_WRITE則是加鎖后調(diào)用buf_flush_write_complete將頁面移除flush_list，更新相應統(tǒng)計信息。
  
• 返回。
  

buf_page_init_for_read

• BUF_READ_IBUF_PAGES_ONLY是ibuf的預讀路徑。該類型下，recv_no_ibuf_operations為false（沒有進行crash recovery），并且目標頁面不是ibuf的層次結(jié)構(gòu)中的2層或者3層頁面（ibuf_page函數(shù)范圍false），則返回nullptr。
  
• 如果page_size是壓縮頁面，而請求的是非壓縮頁面，并且沒有進行crash recovery時，將block設置為nullptr。否則使用buf_LRU_get_free_block獲取一個free_block。buf_LRU_get_free_block邏輯后續(xù)有詳細介紹，大概內(nèi)容為從LRU list中找到合適的block，如果沒有從LRU list獲取到則嘗試刷盤。
  
• 如果block為nullptr，說明準備讀取的是一個壓縮頁，用buf_page_alloc_descriptor分配一個臨時頁面描述符bpage，再調(diào)用buf_buddy_alloc從伙伴系統(tǒng)中分配一個空間存放壓縮頁原始數(shù)據(jù)。這個臨時bpage會等到頁面被解壓成功，使用buf_relocate函數(shù)從free_list中申請到的bpage替換掉臨時bpage，放在LRU list相同的位置。
  
• 調(diào)用buf_page_hash_get_low嘗試從page_hash中讀取該block。如果讀到頁面，并且該block不是被watch的頁面，說明這個頁面已經(jīng)在buffer pool中了。釋放臨時資源：釋放臨時分配的描述符（如果分配了）、釋放伙伴系統(tǒng)中分配的空間（如果申請了）、將空閑block插入free_list（如果block不為空），跳到函數(shù)結(jié)束處準備返回。
  
• block不為空，則調(diào)用buf_page_init：初始化該block，并調(diào)用HASH_INSERT該頁面插入page_hash。調(diào)用buf_LRU_add_block將block插入LRU。參數(shù)is_old為true的話，插入old_list頭部，參數(shù)is_old為false的話，插入young list頭部。如果LRU_list很短，LRU_list將不再劃分young、old，新block將直接被插入LRU_list頭部。如果頁面是壓縮頁面的解壓頁，還會先設置block->page.zip.data，然后將該頁面加入unzip_LRU_list中。如果頁面是臨時表頁面并且開啟了srv_temp_tablespace_fast_cleanup，還會調(diào)用temp_tablespace_pages_map_add，將頁面插入buf_pool->temp_tablespace_pages。
  
• 如果block為空，說明是壓縮頁。將從伙伴系統(tǒng)申請到的空間設置到bpage->zip.data中。調(diào)用buf_page_init_low初始化臨時頁面描述符bpage。調(diào)用buf_LRU_add_block將block插入LRU。參數(shù)is_old為true的話，插入old_list頭部，參數(shù)is_old為false的話，插入young list頭部。如果LRU_list很短，LRU_list將不再劃分young、old，新block將直接被插入LRU_list頭部。DEBUG模式下，將臨時描述符bpage加入通過buf_LRU_insert_zip_clean函數(shù)加入zip_clean鏈表中。將bpage狀態(tài)設置為BUF_IO_READ。
  
• 如果是BUF_READ_IBUF_PAGES_ONLY類型，調(diào)用ibuf_mtr_commit提交mtr。否則返回頁面。
  

buf_LRU_get_free_block

• ?調(diào)用buf_LRU_get_free_only：如果free_list有空閑的block則將block->page.zip設置為空后返回。
  
• 如果沒有從free_list得到空閑的block，則判斷多次從lru_list中淘汰block并獲取。如果設置了try_LRU_scan，則調(diào)用buf_LRU_scan_and_free_block開始第一輪掃描LRU list，最多從LRU list尾部掃描srv_LRU_scan_depth個block，如果還沒成功的話調(diào)用buf_flush_single_page_from_LRU將flush list中最尾部的頁面刷入磁盤。如果還是沒有獲取到空閑block則跳轉(zhuǎn)到步驟2重新開始第二輪掃描。
  
• 第二輪掃描，即使沒有設置try_LRU_scan，也會掃描整個lru list。沒有獲取到空閑block則再調(diào)用buf_flush_single_page_from_LRU將flush list中最尾部的頁面刷入磁盤。還是沒獲取空閑頁面則進入第三輪。
  
• 第三輪掃描開始，每輪中間間隔10ms，其他和第二輪掃描相同。如果超過20輪都沒找到合適的block，則向用戶告警：調(diào)大BP或升級操作系統(tǒng)版本。
  

?buf_LRU_get_free_only

• 負責從buffer_pool的free_list中獲取一個空閑的block。獲取的方法是用封裝好的list操作接口：UT_LIST_GET_FIRST。
  
• 獲取不到空閑block直接返回nullptr。如果順利獲取的空閑的block，需要判斷此block是否準備被resize buffer pool操作回收：使用buf_block_will_withdrawn判斷當前頁面是否準備回收的頁面（最后一個chunk的block），使用buf_get_withdraw_depth判斷withdraw list的頁面是否達到釋放目標大小。如果經(jīng)上述判斷頁面不需要被resize回收則返回block，否則將block插入withdraw list中，循環(huán)使用UT_LIST_GET_FIRST從free_list嘗試再獲取一個block，循環(huán)判斷是否有空閑block，以及block是否恰好需要被回收。
  

buf_LRU_scan_and_free_block

• 如果是用了壓縮頁（use_unzip_list為true），則調(diào)用buf_LRU_free_from_unzip_LRU_list從unzip_LRU_list中淘汰空閑block。這一步只釋放壓縮頁的解壓頁，壓縮頁本身并不需要釋放。
  
• 如果上一步?jīng)]有成功釋放空閑block，則再調(diào)用buf_LRU_free_from_common_LRU_list從lru_list中淘汰空閑block。
  
• 如果前兩步驟沒有成功釋放空閑block，則釋放LRU_list_mutex鎖，否則退出時不釋放buf_pool->LRU_list_mutex鎖。
  

buf_LRU_free_from_unzip_LRU_list

• 調(diào)用buf_LRU_evict_from_unzip_LRU判斷是需要從unzip_LRU_list中淘汰頁面。如果unzip_LRU_list是空或者unzip_LRU_list的空間小于LRU_list空間的10%，則拒絕從unzip_LRU_list淘汰。此外，通過公式判斷當前業(yè)務類型，如果是IO bound類型，則只淘汰解壓頁，不淘汰壓縮頁；CPU bound類型則連壓縮頁也淘汰。
  
• 使用for循環(huán)從尾到頭掃描（或者最多掃描srv_LRU_scan_depth個頁面）unzip_LRU_list，逐一調(diào)用buf_LRU_free_page嘗試釋放頁面，釋放解壓的壓縮頁不會釋放壓縮頁原數(shù)據(jù)，最后返回釋放狀態(tài)freed。成功釋放為true。
  

buf_LRU_free_from_common_LRU_list

從buf_pool->lru_scan_itr.start()開始掃描LRU_list，如果掃描個數(shù)沒達到BUF_LRU_SEARCH_SCAN_THRESHOLD或者是全表掃描則一直向下掃描。使用buf_flush_ready_for_replace判斷頁面是否能立即替換：先使用buf_page_in_file判斷頁面是否為文件頁面類型之一：BUF_BLOCK_FILE_PAGE、BUF_BLOCK_ZIP_DIRTY、BUF_BLOCK_ZIP_PAGE；再調(diào)用buf_LRU_free_page判斷頁面是否能淘汰成功。此輪淘汰將淘汰壓縮頁原數(shù)據(jù)。
buf_LRU_free_page

嘗試從LRU list中釋放一個頁面，中間有臨時釋放鎖再加鎖的邏輯，實現(xiàn)比較復雜。

• 先調(diào)用buf_page_can_relocate判斷頁面是否正在被讀取，判斷方法是查看頁面是否正在被其他頁面讀取，如果在被讀取則直接返回釋放失敗。
  
• 查看當前頁面是否為被修改過的壓縮頁面，是的話頁返回失敗。
  
• 調(diào)用buf_LRU_block_remove_hashed將頁面從page_hash表中刪除。
  
• 如果是壓縮頁面的解壓頁，則再將壓縮頁面插入LRU_list（如果前一個頁面不為空，則調(diào)用UT_LIST_INSERT_AFTER插入，如果前一個頁面為空，則調(diào)用buf_LRU_add_block_low插入midpoint或者young_list頭部），page_hash（使用HASH_INSERT），如果有必要的話還需要插入flush_list。
  
• 如果不是BUF_BLOCK_ZIP_PAGE類型，說明是臟頁(BUF_BLOCK_ZIP_DIRTY)，使用buf_flush_relocate_on_flush_list插入放入flush_list合適的位置。
  
• 檢查頁面是否有自適應hash（adaptive hash index），有的話則刪除，對應函數(shù)為btr_search_drop_page_hash_index。
  
• 調(diào)用buf_LRU_block_free_hashed_page將釋放成功的，不再被page_hash索引的頁面，放回free_list上。
  

buf_LRU_free_page有一個參數(shù)配置是否釋放解壓頁的原壓縮數(shù)據(jù)。buf_LRU_free_from_unzip_LRU_list中這個參數(shù)是false，即默認不刪除壓縮頁的原數(shù)據(jù)。buf_LRU_free_from_common_LRU_list中這個參數(shù)是true，即將壓縮頁原數(shù)據(jù)刪除。
buf_LRU_add_block_low

• 如果old參數(shù)為false，或者LRU_list的總長度小于BUF_LRU_OLD_MIN_LEN，將頁面插入young_list的開頭。否則插入old_list的頭部之后。
  
• 調(diào)整 LRU_list長度，old_list頭部位置等。如果LRU_list現(xiàn)在長于BUF_LRU_OLD_MIN_LEN，則將其初始化為young_list和old_list兩部分。
  
• 用buf_page_belongs_to_unzip_LRU判斷：如果當前頁面是一個解壓縮頁面，則也同時將此頁面插入unzip_LRU_list（buf_unzip_LRU_add_block）。
  

buf_flush_single_page_from_LRU

用來淘汰一個頁面，將其刷盤。并將頁面從page_hash和LRU_list中刪除，放入free_list。

• 加LRU_list鎖進入for循環(huán)
  
• 從尾巴逐一先用buf_flush_ready_for_replace判斷頁面當前頁面是否可以直接釋放（檢查oldest_modification==0，buf_fix_count==0，處于BUF_IO_NONE狀態(tài)），是則調(diào)用buf_LRU_free_page將頁面釋放。
  
• 上一步驟沒有成功，則調(diào)用buf_flush_ready_for_flush來將一個可以被刷盤的頁面刷入磁盤（檢查oldest_modification是否不等于0，頁面是否在被讀取，刷盤模式是否正確等）。是則調(diào)用buf_flush_page將頁面單獨同步刷盤。
  
• 上述兩個步驟成功一個即可退出循環(huán)，釋放鎖，返回刷盤是否成功。
  

buf_relocate

將壓縮頁的bpage從LRU中刪除，重新分配block，把bpage中的內(nèi)容拷貝到block->page中，把dpage （block->page）插入bpage的位置。
注意：
       目前騰訊云數(shù)據(jù)庫 MySQL 8.0特惠活動，不限新老用戶，最低5折起

-----------------------------