前言

用戶對數據庫的最基本要求就是能高效的讀取和存儲數據，但是讀寫數據都涉及到與低速的設備交互，為了彌補兩者之間的速度差異，所有數據庫都有緩存池，用來管理相應的數據頁，提高數據庫的效率，當然也因為引入了這一中間層，數據庫對內存的管理變得相對比較復雜。本文主要分析MySQL Buffer Pool的相關技術以及實現原理，源碼基于阿里云RDS MySQL 5.6分支，其中部分特性已經開源到AliSQL。Buffer Pool相關的源代碼在buf目錄下，主要包括LRU List，Flu List，Double write buffer, 預讀預寫，Buffer Pool預熱，壓縮頁內存管理等模塊，包括頭文件和IC文件，一共兩萬行代碼。

基礎知識

***Buffer Pool Instance: *** 大小等于innodb_buffer_pool_size/innodb_buffer_pool_instances，每個instance都有自己的鎖，信號量，物理塊(Buffer chunks)以及邏輯鏈表(下面的各種List)，即各個instance之間沒有競爭關系，可以并發讀取與寫入。所有instance的物理塊(Buffer chunks)在數據庫啟動的時候被分配，直到數據庫關閉內存才予以釋放。當innodb_buffer_pool_size小于1GB時候，innodb_buffer_pool_instances被重置為1，主要是防止有太多小的instance從而導致性能問題。每個Buffer Pool Instance有一個page hash鏈表，通過它，使用space_id和page_no就能快速找到已經被讀入內存的數據頁，而不用線性遍歷LRU List去查找。注意這個hash表不是InnoDB的自適應哈希，自適應哈希是為了減少Btree的掃描，而page hash是為了避免掃描LRU List。
數據頁： InnoDB中，數據管理的最小單位為頁，默認是16KB，頁中除了存儲用戶數據，還可以存儲控制信息的數據。InnoDB IO子系統的讀寫最小單位也是頁。如果對表進行了壓縮，則對應的數據頁稱為壓縮頁，如果需要從壓縮頁中讀取數據，則壓縮頁需要先解壓，形成解壓頁，解壓頁為16KB。壓縮頁的大小是在建表的時候指定，目前支持16K，8K，4K，2K，1K。即使壓縮頁大小設為16K，在blob/varchar/text的類型中也有一定好處。假設指定的壓縮頁大小為4K，如果有個數據頁無法被壓縮到4K以下，則需要做B-tree分裂操作，這是一個比較耗時的操作。正常情況下，Buffer Pool中會把壓縮和解壓頁都緩存起來，當Free List不夠時，按照系統當前的實際負載來決定淘汰策略。如果系統瓶頸在IO上，則只驅逐解壓頁，壓縮頁依然在Buffer Pool中，否則解壓頁和壓縮頁都被驅逐。
***Buffer Chunks: *** 包括兩部分：數據頁和數據頁對應的控制體，控制體中有指針指向數據頁。Buffer Chunks是最低層的物理塊，在啟動階段從操作系統申請，直到數據庫關閉才釋放。通過遍歷chunks可以訪問幾乎所有的數據頁，有兩種狀態的數據頁除外：沒有被解壓的壓縮頁(BUF_BLOCK_ZIP_PAGE)以及被修改過且解壓頁已經被驅逐的壓縮頁(BUF_BLOCK_ZIP_DIRTY)。此外數據頁里面不一定都存的是用戶數據，開始是控制信息，比如行鎖，自適應哈希等。
***邏輯鏈表: *** 鏈表節點是數據頁的控制體(控制體中有指針指向真正的數據頁)，鏈表中的所有節點都有同一的屬性，引入其的目的是方便管理。下面其中鏈表都是邏輯鏈表。
***Free List: *** 其上的節點都是未被使用的節點，如果需要從數據庫中分配新的數據頁，直接從上獲取即可。InnoDB需要保證Free List有足夠的節點，提供給用戶線程用，否則需要從FLU List或者LRU List淘汰一定的節點。InnoDB初始化后，Buffer Chunks中的所有數據頁都被加入到Free List，表示所有節點都可用。
***LRU List: *** 這個是InnoDB中最重要的鏈表。所有新讀取進來的數據頁都被放在上面。鏈表按照最近最少使用算法排序，最近最少使用的節點被放在鏈表末尾，如果Free List里面沒有節點了，就會從中淘汰末尾的節點。LRU List還包含沒有被解壓的壓縮頁，這些壓縮頁剛從磁盤讀取出來，還沒來的及被解壓。LRU List被分為兩部分，默認前5/8為young list，存儲經常被使用的熱點page，后3/8為old list。新讀入的page默認被加在old list頭，只有滿足一定條件后，才被移到young list上，主要是為了預讀的數據頁和全表掃描污染buffer pool。
***FLU List: *** 這個鏈表中的所有節點都是臟頁，也就是說這些數據頁都被修改過，但是還沒來得及被刷新到磁盤上。在FLU List上的頁面一定在LRU List上，但是反之則不成立。一個數據頁可能會在不同的時刻被修改多次，在數據頁上記錄了最老(也就是第一次)的一次修改的lsn，即oldest_modification。不同數據頁有不同的oldest_modification，FLU List中的節點按照oldest_modification排序，鏈表尾是最小的，也就是最早被修改的數據頁，當需要從FLU List中淘汰頁面時候，從鏈表尾部開始淘汰。加入FLU List，需要使用flush_list_mutex保護，所以能保證FLU List中節點的順序。
***Quick List: *** 這個鏈表是阿里云RDS MySQL 5.6加入的，使用帶Hint的SQL查詢語句，可以把所有這個查詢的用到的數據頁加入到Quick List中，一旦這個語句結束，就把這個數據頁淘汰，主要作用是避免LRU List被全表掃描污染。
***Unzip LRU List: *** 這個鏈表中存儲的數據頁都是解壓頁，也就是說，這個數據頁是從一個壓縮頁通過解壓而來的。
***Zip Clean List: *** 這個鏈表只在Debug模式下有，主要是存儲沒有被解壓的壓縮頁。這些壓縮頁剛剛從磁盤讀取出來，還沒來的及被解壓，一旦被解壓后，就從此鏈表中刪除，然后加入到Unzip LRU List中。
***Zip Free: *** 壓縮頁有不同的大小，比如8K，4K，InnoDB使用了類似內存管理的伙伴系統來管理壓縮頁。Zip Free可以理解為由5個鏈表構成的一個二維數組，每個鏈表分別存儲了對應大小的內存碎片，例如8K的鏈表里存儲的都是8K的碎片，如果新讀入一個8K的頁面，首先從這個鏈表中查找，如果有則直接返回，如果沒有則從16K的鏈表中分裂出兩個8K的塊，一個被使用，另外一個放入8K鏈表中。

核心數據結構

InnoDB Buffer Pool有三種核心的數據結構：buf_pool_t，buf_block_t，buf_page_t。
***but_pool_t: *** 存儲Buffer Pool Instance級別的控制信息，例如整個Buffer Pool Instance的mutex，instance_no, page_hash，old_list_pointer等。還存儲了各種邏輯鏈表的鏈表根節點。Zip Free這個二維數組也在其中。
***buf_block_t: *** 這個就是數據頁的控制體，用來描述數據頁部分的信息(大部分信息在buf_page_t中)。buf_block_t中第一字段就是buf_page_t，這個不是隨意放的，是必須放在第一字段，因為只有這樣buf_block_t和buf_page_t兩種類型的指針可以相互轉換。第二個字段是frame字段，指向真正存數據的數據頁。buf_block_t還存儲了Unzip LRU List鏈表的根節點。另外一個比較重要的字段就是block級別的mutex。
***buf_page_t: *** 這個可以理解為另外一個數據頁的控制體，大部分的數據頁信息存在其中，例如space_id, page_no, page state, newest_modification，oldest_modification，access_time以及壓縮頁的所有信息等。壓縮頁的信息包括壓縮頁的大小，壓縮頁的數據指針(真正的壓縮頁數據是存儲在由伙伴系統分配的數據頁上)。這里需要注意一點，如果某個壓縮頁被解壓了，解壓頁的數據指針是存儲在buf_block_t的frame字段里。

這里介紹一下buf_page_t中的state字段，這個字段主要用來表示當前頁的狀態。一共有八種狀態。這八種狀態對初學者可能比較難理解，尤其是前三種，如果看不懂可以先跳過。
***BUF_BLOCK_POOL_WATCH: *** 這種類型的page是提供給purge線程用的。InnoDB為了實現多版本，需要把之前的數據記錄在undo log中，如果沒有讀請求再需要它，就可以通過purge線程刪除。換句話說，purge線程需要知道某些數據頁是否被讀取，現在解法就是首先查看page hash，看看這個數據頁是否已經被讀入，如果沒有讀入，則獲取(啟動時候通過malloc分配，不在Buffer Chunks中)一個BUF_BLOCK_POOL_WATCH類型的哨兵數據頁控制體，同時加入page_hash但是沒有真正的數據(buf_blokc_t::frame為空)并把其類型置為BUF_BLOCK_ZIP_PAGE(表示已經被使用了，其他purge線程就不會用到這個控制體了)，相關函數buf_pool_watch_set，如果查看page hash后發現有這個數據頁，只需要判斷控制體在內存中的地址是否屬于Buffer Chunks即可，如果是表示對應數據頁已經被其他線程讀入了，相關函數buf_pool_watch_occurred。另一方面，如果用戶線程需要這個數據頁，先查看page hash看看是否是BUF_BLOCK_POOL_WATCH類型的數據頁，如果是則回收這個BUF_BLOCK_POOL_WATCH類型的數據頁，從Free List中(即在Buffer Chunks中)分配一個空閑的控制體，填入數據。這里的核心思想就是通過控制體在內存中的地址來確定數據頁是否還在被使用。
***BUF_BLOCK_ZIP_PAGE: ***當壓縮頁從磁盤讀取出來的時候，先通過malloc分配一個臨時的buf_page_t，然后從伙伴系統中分配出壓縮頁存儲的空間，把磁盤中讀取的壓縮數據存入，然后把這個臨時的buf_page_t標記為BUF_BLOCK_ZIP_PAGE狀態(buf_page_init_for_read)，只有當這個壓縮頁被解壓了，state字段才會被修改為BUF_BLOCK_FILE_PAGE，并加入LRU List和Unzip LRU List(buf_page_get_gen)。如果一個壓縮頁對應的解壓頁被驅逐了，但是需要保留這個壓縮頁且壓縮頁不是臟頁，則這個壓縮頁被標記為BUF_BLOCK_ZIP_PAGE(buf_LRU_free_page)。所以正常情況下，處于BUF_BLOCK_ZIP_PAGE狀態的不會很多。前述兩種被標記為BUF_BLOCK_ZIP_PAGE的壓縮頁都在LRU List中。另外一個用法是，從BUF_BLOCK_POOL_WATCH類型節點中，如果被某個purge線程使用了，也會被標記為BUF_BLOCK_ZIP_PAGE。
***BUF_BLOCK_ZIP_DIRTY: *** 如果一個壓縮頁對應的解壓頁被驅逐了，但是需要保留這個壓縮頁且壓縮頁是臟頁，則被標記為BUF_BLOCK_ZIP_DIRTY(buf_LRU_free_page)，如果該壓縮頁又被解壓了，則狀態會變為BUF_BLOCK_FILE_PAGE。因此BUF_BLOCK_ZIP_DIRTY也是一個比較短暫的狀態。這種類型的數據頁都在Flush List中。
***BUF_BLOCK_NOT_USED: *** 當鏈表處于Free List中，狀態就為此狀態。是一個能長期存在的狀態。
***BUF_BLOCK_READY_FOR_USE: *** 當從Free List中，獲取一個空閑的數據頁時，狀態會從BUF_BLOCK_NOT_USED變為BUF_BLOCK_READY_FOR_USE(buf_LRU_get_free_block)，也是一個比較短暫的狀態。處于這個狀態的數據頁不處于任何邏輯鏈表中。
***BUF_BLOCK_FILE_PAGE: *** 正常被使用的數據頁都是這種狀態。LRU List中，大部分數據頁都是這種狀態。壓縮頁被解壓后，狀態也會變成BUF_BLOCK_FILE_PAGE。
***BUF_BLOCK_MEMORY: *** Buffer Pool中的數據頁不僅可以存儲用戶數據，也可以存儲一些系統信息，例如InnoDB行鎖，自適應哈希索引以及壓縮頁的數據等，這些數據頁被標記為BUF_BLOCK_MEMORY。處于這個狀態的數據頁不處于任何邏輯鏈表中
***BUF_BLOCK_REMOVE_HASH: *** 當加入Free List之前，需要先把page hash移除。因此這種狀態就表示此頁面page hash已經被移除，但是還沒被加入到Free List中，是一個比較短暫的狀態。
總體來說，大部分數據頁都處于BUF_BLOCK_NOT_USED(全部在Free List中)和BUF_BLOCK_FILE_PAGE(大部分處于LRU List中，LRU List中還包含除被purge線程標記的BUF_BLOCK_ZIP_PAGE狀態的數據頁)狀態，少部分處于BUF_BLOCK_MEMORY狀態，極少處于其他狀態。前三種狀態的數據頁都不在Buffer Chunks上，對應的控制體都是臨時分配的，InnoDB把他們列為invalid state(buf_block_state_valid)。
如果理解了這八種狀態以及其之間的轉換關系，那么閱讀Buffer pool的代碼細節就會更加游刃有余。

接下來，簡單介紹一下buf_page_t中buf_fix_count和io_fix兩個變量，這兩個變量主要用來做并發控制，減少mutex加鎖的范圍。當從buffer pool讀取一個數據頁時候，會其加讀鎖，然后遞增buf_page_t::buf_fix_count，同時設置buf_page_t::io_fix為BUF_IO_READ，然后即可以釋放讀鎖。后續如果其他線程在驅逐數據頁(或者刷臟)的時候，需要先檢查一下這兩個變量，如果buf_page_t::buf_fix_count不為零且buf_page_t::io_fix不為BUF_IO_NONE，則不允許驅逐(buf_page_can_relocate)。這里的技巧主要是為了減少數據頁控制體上mutex的爭搶，而對數據頁的內容，讀取的時候依然要加讀鎖，修改時加寫鎖。

Buffer Pool內存初始化

Buffer Pool的內存初始化，主要是Buffer Chunks的內存初始化，buffer pool instance一個一個輪流初始化。核心函數為buf_chunk_init和os_mem_alloc_large
。閱讀代碼可以發現，目前從操作系統分配內存有兩種方式，一種是通過HugeTLB的方式來分配，另外一種使用傳統的mmap來分配。
*HugeTLB: *** 這是一種大內存塊的分配管理技術。類似數據庫對數據的管理，內存也按照頁來管理，默認的頁大小為4KB，HugeTLB就是把頁大小提高到2M或者更加多。程序傳送給cpu都是虛擬內存地址，cpu必須通過快表來映射到真正的物理內存地址。快表的全集放在內存中，部分熱點內存頁可以放在cpu cache中，從而提高內存訪問效率。假設cpu cache為100KB，每條快表占用1KB，頁大小為4KB，則熱點內存頁為100KB/1KB=100條，覆蓋1004KB=400KB的內存數據，但是如果也默認頁大小為2M，則同樣大小的cpu cache，可以覆蓋1002M=200MB的內存數據，也就是說，訪問200MB的數據只需要一次讀取內存即可(如果映射關系沒有在cache中找到，則需要先把映射關系從內存中讀到cache，然后查找，最后再去讀內存中需要的數據，會造成兩次訪問物理內存)。也就是說，使用HugeTLB這種大內存技術，可以提高快表的命中率，從而提高訪問內存的性能。當然這個技術也不是銀彈，內存頁變大了也必定會導致更多的頁內的碎片。如果需要從swap分區中加載虛擬內存，也會變慢。當然最終要的理由是，4KB大小的內存頁已經被業界穩定使用很多年了，如果沒有特殊的需求不需要冒這個風險。在InnoDB中，如果需要用到這項技術可以使用super-large-pages參數啟動MySQL。
mmap分配： 在Linux下，多個進程需要共享一片內存，可以使用mmap來分配和綁定，所以只提供給一個MySQL進程使用也是可以的。用mmap分配的內存都是虛存，在top命令中占用VIRT這一列，而不是RES這一列，只有相應的內存被真正使用到了，才會被統計到RES中，提高內存使用率。這樣是為什么常常看到MySQL一啟動就被分配了很多的VIRT，而RES卻是慢慢漲上來的原因。這里大家可能有個疑問，為啥不用malloc。其實查閱malloc文檔，可以發現，當請求的內存數量大于MMAP_THRESHOLD(默認為128KB)時候，malloc底層就是調用了mmap。在InnoDB中，默認使用mmap來分配。
分配完了內存，buf_chunk_init函數中，把這片內存劃分為兩個部分，前一部分是數據頁控制體(buf_block_t)，在阿里云RDS MySQL 5.6 release版本中，每個buf_block_t是424字節，一共有innodb_buffer_pool_size/UNIV_PAGE_SIZE個。后一部分是真正的數據頁，按照UNIV_PAGE_SIZE分隔。假設page大小為16KB，則數據頁控制體占的內存:數據頁約等于1:38.6，也就是說如果innodb_buffer_pool_size被配置為40G，則需要額外的1G多空間來存數據頁的控制體。
劃分完空間后，遍歷數據頁控制體，設置buf_block_t::frame指針，指向真正的數據頁，然后把這些數據頁加入到Free List中即可。初始化完Buffer Chunks的內存，還需要初始化BUF_BLOCK_POOL_WATCH類型的數據頁控制塊，page hash的結構體，zip hash的結構體(所有被壓縮頁的伙伴系統分配走的數據頁面會加入到這個哈希表中)。注意這些內存是額外分配的，不包含在Buffer Chunks中。
除了buf_pool_init外，建議讀者參考一下but_pool_free這個內存釋放函數，加深對Buffer Pool相關內存的理解。

Buf_page_get函數解析

這個函數極其重要，是其他模塊獲取數據頁的外部接口函數。如果請求的數據頁已經在Buffer Pool中了，修改相應信息后，就直接返回對應數據頁指針，如果Buffer Pool中沒有相關數據頁，則從磁盤中讀取。Buf_page_get是一個宏定義，真正的函數為buf_page_get_gen，參數主要為space_id, page_no, lock_type, mode以及mtr。這里主要介紹一個mode這個參數，其表示讀取的方式，目前支持六種，前三種用的比較多。
***BUF_GET: *** 默認獲取數據頁的方式，如果數據頁不在Buffer Pool中，則從磁盤讀取，如果已經在Buffer Pool中，需要判斷是否要把他加入到young list中以及判斷是否需要進行線性預讀。如果是讀取則加讀鎖，修改則加寫鎖。
***BUF_GET_IF_IN_POOL: *** 只在Buffer Pool中查找這個數據頁，如果在則判斷是否要把它加入到young list中以及判斷是否需要進行線性預讀。如果不在則直接返回空。加鎖方式與BUF_GET類似。
***BUF_PEEK_IF_IN_POOL: *** 與BUF_GET_IF_IN_POOL類似，只是即使條件滿足也不把它加入到young list中也不進行線性預讀。加鎖方式與BUF_GET類似。
***BUF_GET_NO_LATCH: *** 不管對數據頁是讀取還是修改，都不加鎖。其他方面與BUF_GET類似。
***BUF_GET_IF_IN_POOL_OR_WATCH: *** 只在Buffer Pool中查找這個數據頁，如果在則判斷是否要把它加入到young list中以及判斷是否需要進行線性預讀。如果不在則設置watch。加鎖方式與BUF_GET類似。這個是要是給purge線程用。
***BUF_GET_POSSIBLY_FREED: *** 這個mode與BUF_GET類似，只是允許相應的數據頁在函數執行過程中被釋放，主要用在估算Btree兩個slot之前的數據行數。
接下來，我們簡要分析一下這個函數的主要邏輯。

• 首先通過buf_pool_get函數依據space_id和page_no查找指定的數據頁在那個Buffer Pool Instance里面。算法很簡單instance_no = (space_id << 20 + space_id + page_no >> 6) % instance_num，也就是說先通過space_id和page_no算出一個fold value然后按照instance的個數取余數即可。這里有個小細節，page_no的第六位被砍掉，這是為了保證一個extent的數據能被緩存到同一個Buffer Pool Instance中，便于后面的預讀操作。
• 接著，調用buf_page_hash_get_low函數在page hash中查找這個數據頁是否已經被加載到對應的Buffer Pool Instance中，如果沒有找到這個數據頁且mode為BUF_GET_IF_IN_POOL_OR_WATCH則設置watch數據頁(buf_pool_watch_set)，接下來，如果沒有找到數據頁且mode為BUF_GET_IF_IN_POOL、BUF_PEEK_IF_IN_POOL或者BUF_GET_IF_IN_POOL_OR_WATCH函數直接返回空，表示沒有找到數據頁。如果沒有找到數據但是mode為其他，就從磁盤中同步讀取(buf_read_page)。在讀取磁盤數據之前，我們如果發現需要讀取的是非壓縮頁，則先從Free List中獲取空閑的數據頁，如果Free List中已經沒有了，則需要通過刷臟來釋放數據頁，這里的一些細節我們后續在LRU模塊再分析，獲取到空閑的數據頁后，加入到LRU List中(buf_page_init_for_read)。在讀取磁盤數據之前，我們如果發現需要讀取的是壓縮頁，則臨時分配一個buf_page_t用來做控制體，通過伙伴系統分配到壓縮頁存數據的空間，最后同樣加入到LRU List中(buf_page_init_for_read)。做完這些后，我們就調用IO子系統的接口同步讀取頁面數據，如果讀取數據失敗，我們重試100次(BUF_PAGE_READ_MAX_RETRIES)然后觸發斷言，如果成功則判斷是否要進行隨機預讀(隨機預讀相關的細節我們也在預讀預寫模塊分析)。
• 接著，讀取數據成功后，我們需要判斷讀取的數據頁是不是壓縮頁，如果是的話，因為從磁盤中讀取的壓縮頁的控制體是臨時分配的，所以需要重新分配block(buf_LRU_get_free_block)，把臨時分配的buf_page_t給釋放掉，用buf_relocate函數替換掉，接著進行解壓，解壓成功后，設置state為BUF_BLOCK_FILE_PAGE，最后加入Unzip LRU List中。
• 接著，我們判斷這個頁是否是第一次訪問，如果是則設置buf_page_t::access_time，如果不是，我們則判斷其是不是在Quick List中，如果在Quick List中且當前事務不是加過Hint語句的事務，則需要把這個數據頁從Quick List刪除，因為這個頁面被其他的語句訪問到了，不應該在Quick List中了。
• 接著，如果mode不為BUF_PEEK_IF_IN_POOL，我們需要判斷是否把這個數據頁移到young list中，具體細節在后面LRU模塊中分析。
• 接著，如果mode不為BUF_GET_NO_LATCH，我們給數據頁加上讀寫鎖。
• 最后，如果mode不為BUF_PEEK_IF_IN_POOL且這個數據頁是第一次訪問，則判斷是否需要進行線性預讀(線性預讀相關的細節我們也在預讀預寫模塊分析)。

LRU List中young list和old list的維護

當LRU List鏈表大于512(BUF_LRU_OLD_MIN_LEN)時，在邏輯上被分為兩部分，前面部分存儲最熱的數據頁，這部分鏈表稱作young list，后面部分則存儲冷數據頁，這部分稱作old list，一旦Free List中沒有頁面了，就會從冷頁面中驅逐。兩部分的長度由參數innodb_old_blocks_pct控制。每次加入或者驅逐一個數據頁后，都要調整young list和old list的長度(buf_LRU_old_adjust_len)，同時引入BUF_LRU_OLD_TOLERANCE來防止鏈表調整過頻繁。當LRU List鏈表小于512，則只有old list。
新讀取進來的頁面默認被放在old list頭，在經過innodb_old_blocks_time后，如果再次被訪問了，就挪到young list頭上。一個數據頁被讀入Buffer Pool后，在小于innodb_old_blocks_time的時間內被訪問了很多次，之后就不再被訪問了，這樣的數據頁也很快被驅逐。這個設計認為這種數據頁是不健康的，應該被驅逐。
此外，如果一個數據頁已經處于young list，當它再次被訪問的時候，不會無條件的移動到young list頭上，只有當其處于young list長度的1/4(大約值)之后，才會被移動到young list頭部，這樣做的目的是減少對LRU List的修改，否則每訪問一個數據頁就要修改鏈表一次，效率會很低，因為LRU List的根本目的是保證經常被訪問的數據頁不會被驅逐出去，因此只需要保證這些熱點數據頁在頭部一個可控的范圍內即可。相關邏輯可以參考函數buf_page_peek_if_too_old。

buf_LRU_get_free_block函數解析

這個函數以及其調用的函數可以說是整個LRU模塊最重要的函數，在整個Buffer Pool模塊中也有舉足輕重的作用。如果能把這幾個函數吃透，相信其他函數很容易就能讀懂。

• 首先，如果是使用ENGINE_NO_CACHE發送過來的SQL需要讀取數據，則優先從Quick List中獲取(buf_quick_lru_get_free)。
• 接著，統計Free List和LRU List的長度，如果發現他們再Buffer Chunks占用太少的空間，則表示太多的空間被行鎖，自使用哈希等內部結構給占用了，一般這些都是大事務導致的。這時候會給出報警。
• 接著，查看Free List中是否還有空閑的數據頁(buf_LRU_get_free_only)，如果有則直接返回，否則進入下一步。大多數情況下，這一步都能找到空閑的數據頁。
• 如果Free List中已經沒有空閑的數據頁了，則會嘗試驅逐LRU List末尾的數據頁。如果系統有壓縮頁，情況就有點復雜，InnoDB會調用buf_LRU_evict_from_unzip_LRU來決定是否驅逐壓縮頁，如果Unzip LRU List大于LRU List的十分之一或者當前InnoDB IO壓力比較大，則會優先從Unzip LRU List中把解壓頁給驅逐，否則會從LRU List中把解壓頁和壓縮頁同時驅逐。不管走哪條路徑，最后都調用了函數buf_LRU_free_page來執行驅逐操作，這個函數由于要處理壓縮頁解壓頁各種情況，極其復雜。大致的流程：首先判斷是否是臟頁，如果是則不驅逐，否則從LRU List中把鏈表刪除，必要的話還從Unzip LRU List移走這個數據頁(buf_LRU_block_remove_hashed)，接著如果我們選擇保留壓縮頁，則需要重新創建一個壓縮頁控制體，插入LRU List中，如果是臟的壓縮頁還要插入到Flush List中，最后才把刪除的數據頁插入到Free List中(buf_LRU_block_free_hashed_page)。
• 如果在上一步中沒有找到空閑的數據頁，則需要刷臟了(buf_flush_single_page_from_LRU)，由于buf_LRU_get_free_block這個函數是在用戶線程中調用的，所以即使要刷臟，這里也是刷一個臟頁，防止刷過多的臟頁阻塞用戶線程。
• 如果上一步的刷臟因為數據頁被其他線程讀取而不能刷臟，則重新跳轉到上述第二步。進行第二輪迭代，與第一輪迭代的區別是，第一輪迭代在掃描LRU List時，最多只掃描innodb_lru_scan_depth個，而在第二輪迭代開始，掃描整個LRU List。如果很不幸，這一輪還是沒有找到空閑的數據頁，從三輪迭代開始，在刷臟前等待10ms。
• 最終找到一個空閑頁后，page的state為BUF_BLOCK_READY_FOR_USE。

控制全表掃描不增加cache數據到Buffer Pool

全表掃描對Buffer Pool的影響比較大，即使有old list作用，但是old list默認也占Buffer Pool的3/8。因此，阿里云RDS引入新的語法ENGINE_NO_CACHE(例如：SELECT ENGINE_NO_CACHE count(*) FROM t1)。如果一個SQL語句中帶了ENGINE_NO_CACHE這個關鍵字，則由它讀入內存的數取據頁都放入Quick List中，當這個語句結束時，會刪除它獨占的數據頁。同時引入兩個參數。innodb_rds_trx_own_block_max這個參數控制使用Hint的每個事物最多能擁有多少個數據頁，如果超過這個數據就開始驅逐自己已有的數據頁，防止大事務占用過多的數據頁。innodb_rds_quick_lru_limit_per_instance這個參數控制每個Buffer Pool Instance中Quick List的長度，如果超過這個長度，后續的請求都從Quick List中驅逐數據頁，進而獲取空閑數據頁。

刪除指定表空間所有的數據頁

函數(buf_LRU_remove_pages)提供了三種模式，第一種(BUF_REMOVE_ALL_NO_WRITE)，刪除Buffer Pool中所有這個類型的數據頁(LRU List和Flush List)同時Flush List中的數據頁也不寫回數據文件，這種適合rename table和5.6表空間傳輸新特性，因為space_id可能會被復用，所以需要清除內存中的一切，防止后續讀取到錯誤的數據。第二種(BUF_REMOVE_FLUSH_NO_WRITE)，僅僅刪除Flush List中的數據頁同時Flush List中的數據頁也不寫回數據文件，這種適合drop table，即使LRU List中還有數據頁，但由于不會被訪問到，所以會隨著時間的推移而被驅逐出去。第三種(BUF_REMOVE_FLUSH_WRITE)，不刪除任何鏈表中的數據僅僅把Flush List中的臟頁都刷回磁盤，這種適合表空間關閉，例如數據庫正常關閉的時候調用。這里還有一點值得一提的是，由于對邏輯鏈表的變動需要加鎖且刪除指定表空間數據頁這個操作是一個大操作，容易造成其他請求被餓死，所以InnoDB做了一個小小的優化，每刪除BUF_LRU_DROP_SEARCH_SIZE個數據頁(默認為1024)就會釋放一下Buffer Pool Instance的mutex，便于其他線程執行。

LRU_Manager_Thread

這是一個系統線程，隨著InnoDB啟動而啟動，作用是定期清理出空閑的數據頁(數量為innodb_LRU_scan_depth)并加入到Free List中，防止用戶線程去做同步刷臟影響效率。線程每隔一定時間去做BUF_FLUSH_LRU，即首先嘗試從LRU中驅逐部分數據頁，如果不夠則進行刷臟，從Flush List中驅逐(buf_flush_LRU_tail)。線程執行的頻率通過以下策略計算：我們設定max_free_len = innodb_LRU_scan_depth * innodb_buf_pool_instances，如果Free List中的數量小于max_free_len的1%，則sleep time為零，表示這個時候空閑頁太少了，需要一直執行buf_flush_LRU_tail從而騰出空閑的數據頁。如果Free List中的數量介于max_free_len的1%-5%，則sleep time減少50ms(默認為1000ms)，如果Free List中的數量介于max_free_len的5%-20%，則sleep time不變，如果Free List中的數量大于max_free_len的20%，則sleep time增加50ms，但是最大值不超過rds_cleaner_max_lru_time。這是一個自適應的算法，保證在大壓力下有足夠用的空閑數據頁(lru_manager_adapt_sleep_time)。

Hazard Pointer

在學術上，Hazard Pointer是一個指針，如果這個指針被一個線程所占有，在它釋放之前，其他線程不能對他進行修改，但是在InnoDB里面，概念剛好相反，一個線程可以隨時訪問Hazard Pointer，但是在訪問后，他需要調整指針到一個有效的值，便于其他線程使用。我們用Hazard Pointer來加速逆向的邏輯鏈表遍歷。
先來說一下這個問題的背景，我們知道InnoDB中可能有多個線程同時作用在Flush List上進行刷臟，例如LRU_Manager_Thread和Page_Cleaner_Thread。同時，為了減少鎖占用的時間，InnoDB在進行寫盤的時候都會把之前占用的鎖給釋放掉。這兩個因素疊加在一起導致同一個刷臟線程刷完一個數據頁A，就需要回到Flush List末尾(因為A之前的臟頁可能被其他線程給刷走了，之前的臟頁可能已經不在Flush list中了)，重新掃描新的可刷盤的臟頁。另一方面，數據頁刷盤是異步操作，在刷盤的過程中，我們會把對應的數據頁IO_FIX住，防止其他線程對這個數據頁進行操作。我們假設某臺機器使用了非常緩慢的機械硬盤，當前Flush List中所有頁面都可以被刷盤(buf_flush_ready_for_replace返回true)。我們的某一個刷臟線程拿到隊尾最后一個數據頁，IO fixed，發送給IO線程，最后再從隊尾掃描尋找可刷盤的臟頁。在這次掃描中，它發現最后一個數據頁(也就是剛剛發送到IO線程中的數據頁)狀態為IO fixed(磁盤很慢，還沒處理完)所以不能刷，跳過，開始刷倒數第二個數據頁，同樣IO fixed，發送給IO線程，然后再次重新掃描Flush List。它又發現尾部的兩個數據頁都不能刷新(因為磁盤很慢，可能還沒刷完)，直到掃描到倒數第三個數據頁。所以，存在一種極端的情況，如果磁盤比較緩慢，刷臟算法性能會從O(N)退化成O(N*N)。
要解決這個問題，最本質的方法就是當刷完一個臟頁的時候不要每次都從隊尾重新掃描。我們可以使用Hazard Pointer來解決，方法如下：遍歷找到一個可刷盤的數據頁，在鎖釋放之前，調整Hazard Pointer使之指向Flush List中下一個節點，注意一定要在持有鎖的情況下修改。然后釋放鎖，進行刷盤，刷完盤后，重新獲取鎖，讀取Hazard Pointer并設置下一個節點，然后釋放鎖，進行刷盤，如此重復。當這個線程在刷盤的時候，另外一個線程需要刷盤，也是通過Hazard Pointer來獲取可靠的節點，并重置下一個有效的節點。通過這種機制，保證每次讀到的Hazard Pointer是一個有效的Flush List節點，即使磁盤再慢，刷臟算法效率依然是O(N)。
這個解法同樣可以用到LRU List驅逐算法上，提高驅逐的效率。相應的Patch是在MySQL 5.7上首次提出的，阿里云RDS把其Port到了我們5.6的版本上，保證在大并發情況下刷臟算法的效率。

Page_Cleaner_Thread

這也是一個InnoDB的后臺線程，主要負責Flush List的刷臟，避免用戶線程同步刷臟頁。與LRU_Manager_Thread線程相似，其也是每隔一定時間去刷一次臟頁。其sleep time也是自適應的(page_cleaner_adapt_sleep_time)，主要由三個因素影響：當前的lsn，Flush list中的oldest_modification以及當前的同步刷臟點(log_sys->max_modified_age_sync，有redo log的大小和數量決定)。簡單的來說，lsn - oldest_modification的差值與同步刷臟點差距越大，sleep time就越長，反之sleep time越短。此外，可以通過rds_page_cleaner_adaptive_sleep變量關閉自適應sleep time，這是sleep time固定為1秒。
與LRU_Manager_Thread每次固定執行清理innodb_LRU_scan_depth個數據頁不同，Page_Cleaner_Thread每次執行刷的臟頁數量也是自適應的，計算過程有點復雜(page_cleaner_flush_pages_if_needed)。其依賴當前系統中臟頁的比率，日志產生的速度以及幾個參數。innodb_io_capacity和innodb_max_io_capacity控制每秒刷臟頁的數量，前者可以理解為一個soft limit，后者則為hard limit。innodb_max_dirty_pages_pct_lwm和innodb_max_dirty_pages_pct_lwm控制臟頁比率，即InnoDB什么臟頁到達多少才算多了，需要加快刷臟頻率了。innodb_adaptive_flushing_lwm控制需要刷新到哪個lsn。innodb_flushing_avg_loops控制系統的反應效率，如果這個變量配置的比較大，則系統刷臟速度反應比較遲鈍，表現為系統中來了很多臟頁，但是刷臟依然很慢，如果這個變量配置很小，當系統中來了很多臟頁后，刷臟速度在很短的時間內就可以提升上去。這個變量是為了讓系統運行更加平穩，起到削峰填谷的作用。相關函數，af_get_pct_for_dirty和af_get_pct_for_lsn。

預讀和預寫

如果一個數據頁被讀入Buffer Pool，其周圍的數據頁也有很大的概率被讀入內存，與其分開多次讀取，還不如一次都讀入內存，從而減少磁盤尋道時間。在官方的InnoDB中，預讀分兩種，隨機預讀和線性預讀。
***隨機預讀: *** 這種預讀發生在一個數據頁成功讀入Buffer Pool的時候(buf_read_ahead_random)。在一個Extent范圍(1M，如果數據頁大小為16KB，則為連續的64個數據頁)內，如果熱點數據頁大于一定數量，就把整個Extend的其他所有數據頁(依據page_no從低到高遍歷讀入)讀入Buffer Pool。這里有兩個問題，首先數量是多少，默認情況下，是13個數據頁。接著，怎么樣的頁面算是熱點數據頁，閱讀代碼發現，只有在young list前1/4的數據頁才算是熱點數據頁。讀取數據時候，使用了異步IO，結合使用OS_AIO_SIMULATED_WAKE_LATER和os_aio_simulated_wake_handler_threads便于IO合并。隨機預讀可以通過參數innodb_random_read_ahead來控制開關。此外，buf_page_get_gen函數的mode參數不影響隨機預讀。
***線性預讀: *** 這中預讀只發生在一個邊界的數據頁(Extend中第一個數據頁或者最后一個數據頁)上(buf_read_ahead_linear)。在一個Extend范圍內，如果大于一定數量(通過參數innodb_read_ahead_threshold控制，默認為56)的數據頁是被順序訪問(通過判斷數據頁access time是否為升序或者逆序來確定)的，則把下一個Extend的所有數據頁都讀入Buffer Pool。讀取的時候依然采用異步IO和IO合并策略。線性預讀觸發的條件比較苛刻，觸發操作的是邊界數據頁同時要求其他數據頁嚴格按照順序訪問，主要是為了解決全表掃描時的性能問題。線性預讀可以通過參數innodb_read_ahead_threshold來控制開關。此外，當buf_page_get_gen函數的mode為BUF_PEEK_IF_IN_POOL時，不觸發線性預讀。
InnoDB中除了有預讀功能，在刷臟頁的時候，也能進行預寫(buf_flush_try_neighbors)。當一個數據頁需要被寫入磁盤的時候，查找其前面或者后面鄰居數據頁是否也是臟頁且可以被刷盤(沒有被IOFix且在old list中)，如果可以的話，一起刷入磁盤，減少磁盤尋道時間。預寫功能可以通過innodb_flush_neighbors參數來控制。不過在現在的SSD磁盤下，這個功能可以關閉。

Double Write Buffer(dblwr)

服務器突然斷電，這個時候如果數據頁被寫壞了(例如數據頁中的目錄信息被損壞)，由于InnoDB的redolog日志不是完全的物理日志，有部分是邏輯日志，因此即使奔潰恢復也無法恢復到一致的狀態，只能依靠Double Write Buffer先恢復完整的數據頁。Double Write Buffer主要是解決數據頁半寫的問題，如果文件系統能保證寫數據頁是一個原子操作，那么可以把這個功能關閉，這個時候每個寫請求直接寫到對應的表空間中。
Double Write Buffer大小默認為2M，即128個數據頁。其中分為兩部分，一部分留給batch write，另一部分是single page write。前者主要提供給批量刷臟的操作，后者留給用戶線程發起的單頁刷臟操作。batch write的大小可以由參數innodb_doublewrite_batch_size控制，例如假設innodb_doublewrite_batch_size配置為120，則剩下8個數據頁留給single page write。
假設我們要進行批量刷臟操作，我們會首先寫到內存中的Double Write Buffer(也是2M，在系統初始化中分配，不使用Buffer Chunks空間)，如果dblwr寫滿了，一次將其中的數據刷盤到系統表空間指定位置，注意這里是同步IO操作，在確保寫入成功后，然后使用異步IO把各個數據頁寫回自己的表空間，由于是異步操作，所有請求下發后，函數就返回，表示寫成功了(buf_dblwr_add_to_batch)。不過這個時候后續的寫請求依然會阻塞，知道這些異步操作都成功，才清空系統表空間上的內容，后續請求才能被繼續執行。這樣做的目的就是，如果在異步寫回數據頁的時候，系統斷電，發生了數據頁半寫，這個時候由于系統表空間中的數據頁是完整的，只要從中拷貝過來就行(buf_dblwr_init_or_load_pages)。
異步IO請求完成后，會檢查數據頁的完整性以及完成change buffer相關操作，接著IO helper線程會調用buf_flush_write_complete函數，把數據頁從Flush List刪除，如果發現batch write中所有的數據頁都寫成了，則釋放dblwr的空間。

Buddy伙伴系統

與內存分配管理算法類似，InnoDB中的伙伴系統也是用來管理不規則大小內存分配的，主要用在壓縮頁的數據上。前文提到過，InnoDB中的壓縮頁可以有16K，8K，4K，2K，1K這五種大小，壓縮頁大小的單位是表，也就是說系統中可能存在很多壓縮頁大小不同的表。使用伙伴體統來分配和回收，能提高系統的效率。
申請空間的函數是buf_buddy_alloc，其首先在zip free鏈表中查看指定大小的塊是否還存在，如果不存在則從更大的鏈表中分配，這回導致一些列的分裂操作。例如需要一塊4K大小的內存，則先從4K鏈表中查找，如果有則直接返回，沒有則從8K鏈表中查找，如果8K中還有空閑的，則把8K分成兩部分，低地址的4K提供給用戶，高地址的4K插入到4K的鏈表中，便與后續使用。如果8K中也沒有空閑的了，就從16K中分配，16K首先分裂成2個8K，高地址的插入到8K鏈表中，低地址的8K繼續分裂成2個4K，低地址的4K返回給用戶，高地址的4K插入到4K的鏈表中。假設16K的鏈表中也沒有空閑的了，則調用buf_LRU_get_free_block獲取新的數據頁，然后把這個數據頁加入到zip hash中，同時設置state狀態為BUF_BLOCK_MEMORY，表示這個數據頁存儲了壓縮頁的數據。
釋放空間的函數是buf_buddy_free，相比于分配空間的函數，有點復雜。假設釋放一個4K大小的數據塊，其先把4K放回4K對應的鏈表，接著會查看其伙伴(釋放塊是低地址，則伙伴是高地址，釋放塊是高地址，則伙伴是低地址)是否也被釋放了，如果也被釋放了則合并成8K的數據塊，然后繼續尋找這個8K數據塊的伙伴，試圖合并成16K的數據塊。如果發現伙伴沒有被釋放，函數并不會直接退出而是把這個伙伴給挪走(buf_buddy_relocate)，例如8K數據塊的伙伴沒有被釋放，系統會查看8K的鏈表，如果有空閑的8K塊，則把這個伙伴挪到這個空閑的8K上，這樣就能合并成16K的數據塊了，如果沒有，函數才放棄合并并返回。通過這種relocate操作，內存碎片會比較少，但是涉及到內存拷貝，效率會比較低。

Buffer Pool預熱

這個也是官方5.6提供的新功能，可以把當前Buffer Pool中的數據頁按照space_id和page_no dump到外部文件，當數據庫重啟的時候，Buffer Pool就可以直接恢復到關閉前的狀態。
***Buffer Pool Dump: *** 遍歷所有Buffer Pool Instance的LRU List，對于其中的每個數據頁，按照space_id和page_no組成一個64位的數字，寫到外部文件中即可(buf_dump)。
***Buffer Pool Load: *** 讀取指定的外部文件，把所有的數據讀入內存后，使用歸并排序對數據排序，以64個數據頁為單位進行IO合并，然后發起一次真正的讀取操作。排序的作用就是便于IO合并(buf_load)。

總結

InnoDB的Buffer Pool可以認為很簡單，就是LRU List和Flush List，但是InnoDB對其做了很多性能上的優化，例如減少加鎖范圍，page hash加速查找等，導致具體的實現細節相對比較復雜，尤其是引入壓縮頁這個特性后，有些核心代碼變得晦澀難懂，需要讀者細細琢磨。