庖丁解 InnoDB 之 Buffer Pool

Buffer Pool 是 InnoDB 中非常重要的組成部分，也是數據庫用戶最關心的組件之一。Buffer Pool 的基本功能並不複雜，設計實現也比較清晰，但作爲一個有幾十年歷史的工業級數據庫產品，不可避免的在代碼上融合了越來越多的功能，以及很多細節的優化，從而顯得有些臃腫和晦澀。本文希望聚焦在 Buffer Pool 的本職功能上，從其提供的接口、內存組織方式、Page 獲取、刷髒等方面進行介紹，其中會穿插一些重要的優化手段，之後用單獨的一節介紹其中稍顯複雜的併發控制，也就是各種 mutex 的設計及實現。而除此之外，像 Change Buffer、壓縮 Page、Double Write Buffer 等功能雖然大量的穿插在 Buffer Pool 的實現之中，但其本身並不屬於 Buffer Pool 的核心邏輯，本文並不會包括這部分內容，本文代碼相關內容基於 MySQL 8.0[1]。

背景

傳統數據庫中的數據是完整的保存在磁盤上的，但計算卻只能發生在內存中，因此需要有良好的機制來協調內存及磁盤的數據交互，這就是 Buffer Pool 存在的意義。也因此 Buffer Pool 通常按固定長度的 Page 來管理內存，從而方便的進行跟磁盤的數據換入換出。除此之外，磁盤和內存在訪問性能上有着巨大的差距，如何最小化磁盤的 IO 就成了 Buffer Pool 的設計核心目標。《數據庫故障恢復的前世今生》[2] 一文中介紹過，主流的數據庫會採用 REDO LOG 加 UNDO LOG，而不是限制刷髒順序的方式，來保證數據庫 ACID 特性。這種做法也保證了 Buffer Pool 可以更專注地實現高效的 Cache 策略。
Buffer Pool 作爲一個整體，其對外部使用者提供的其實是非常簡單的接口，我們稱之爲 FIX-UNFIX 接口 [3]，之所以需要 FIX 和 UNFIX，是因爲對 Buffer Pool 來說，上層對 Page 的使用時長是未知的，這個過程中需要保證 Page 被正確的維護在 Buffer Pool 中：

上層調用者先通過索引獲得要訪問的 Page Number；
之後用這個 Page Number 調用 Buffer Pool 的 FIX 接口，獲得 Page 並對其進行訪問或修改，被 FIX 的 Page 不會被換出 Buffer Pool；
之後調用者通過 UNFIX 釋放 Page 的鎖定狀態。

不同事務、不同線程併發的調用 Buffer Pool 的 FIX-UNFIX 接口的序列，我們稱爲 Page 訪問序列（Page Reference String），這個序列本身是 Buffer Pool 無關的，只取決於數據庫上面的負載類型、負載併發度、上層的索引實現以及數據模型。而通用數據庫的 Buffer Pool 設計就是希望能在大多數的 Page 訪問序列下，儘可能的實現最小化磁盤 IO 以及高效訪問的目標。
爲了實現這個目標，Buffer Pool 內部做了大量的工作，而替換算法是其中最至關重要的部分，由於內存容量通常是遠小於磁盤容量的，替換算法需要在內存容量達到上限時，選擇將現有的內存 Page 踢出，替換成新的被訪問的 Page，好的替換算法可以在給定的 Buffer Size 下儘量少的出現 Buffer Miss。理想的情況下，我們每次替換未來的訪問序列中最遠的那個 Page，這也是 OPT 算法的思路，但顯然獲得未來的 Page 序列是不切實際的，因此 _OPT 算法_只是一個理想模型，作爲評判替換算法的一個最優邊界。與之相反的是作爲最劣邊界的 Random 算法，其思路是完全隨機的替換。大多數的情況下， Page 的訪問其實是有熱度區分的，這也就給替換算法一個通過歷史序列判斷未來序列的可能，參考的指標通常有兩個：

訪問距離（Age）：

在 Page 訪問序列上，某個 Page 上一次訪問到現在的距離；
引用次數（References）：

某個 Page 歷史上或者一段時間的歷史上被訪問的次數。

只考慮訪問距離的 _FIFO（First In First Out）算法_和只考慮引用次數的 _LFU（Least Frequently Used）算法_都被證明在特定序列下會有巨大的缺陷。而好的實用的替換算法會同時考慮這兩個因素，其中有我們熟悉的 _LRU(Least Recently Used) 算法_以及 Clocks 算法。本文接下來會詳細的介紹 InnoDB 中的 LRU 替換算法的實現，除此之外，還會包括如何實現高效的 Page 查找、內存管理、刷髒策略以及 Page 的併發訪問。

使用方式

首先，我們來看在 InnoDB 中，Buffer Pool 的功能是如何被使用的。《B + 樹數據庫加鎖歷史》[4] 以及《B + 樹數據庫故障恢復概述》[5] 兩篇文章中，指出 B + 樹數據庫爲了獲得更高的事務併發度，在併發控制和故障恢復中都區分邏輯內容和物理內容。其中物理內容指的就是就是對 Page 的訪問，一個邏輯事務可以在不同時刻發起並提交多個 System Transaction，System Transaction 會在很短的時間內就提交，並且不需要回滾；通常只會涉及幾個 Page，比如發生分裂或合併的父子節點，數據節點和 Undo 節點；System Transaction 通過 Redo + No Steal 的方式保證多個 Page 的 Crash Safe；不同 System Transaction 之間會通過比 Lock 更輕量的 Latch 來保證安全的併發訪問。
簡而言之，System Transaction 需要依次獲取幾個不同的 Page，對獲取的 Page 加 Latch，使用或修改 Page，並寫 Redo Log，來保證多個 Page 訪問的原子。在 InnoDB 中這個 System Transaction 就是 MTR（Mini-Transaction）。而 Buffer Pool 提供的就是通過 Page No 獲取對應 Page 的接口。因此可以說，在 InnoDB 中 MTR（Min-Transaction）就是 Buffer Pool 的主要使用方式。

1. 上層用調用 buf_page_get_gen 獲取需要的 Page

如下是上層通過 Buffer Pool 獲取一個需要的 Page 的代碼，buf_page_get_gen接口對應上面提到的 FIX 接口：

其中 buf_block_t 是 Page 對應的內存管理結構，通過 block->frame 指針可以訪問完整的 Page 內容；第一個參數 page_id 指定需要獲取的 Page 號，這個 page_id 通常是通過上層的 BTree 搜索得到；第三個參數 rw_latch 指定需要對 Page 加的讀寫 Latch 模式；最後一個 mtr 參數就是上面提到的 Mini-Transaction，同一個 mtr 訪問多個 page 時，會將這個 mtr 結構在每次調用 buf_page_get_gen 的時候傳遞下去。

2. buf_page_get_gen 內部獲取 Page 並標記 FIX 及加鎖

在buf_page_get_gen內部首先需要獲取需要的 Page，這個過程會在後面詳細介紹，在此之後會做兩件事清，標記 page 的 FIX 狀態（page->buf_fix_count），阻止 Page 的換出，以及對 Page 加對應的 rw_latch 模式的的鎖（block->lock）

MTR 結構中會包含一個或多個已經持有鎖的 Page，最後 mtr 提交的時候，一起做 UNFIX 並放鎖：

static void memo_slot_release(mtr_memo_slot_t *slot) {  switch (slot->type) {
    buf_block_t *block;    case MTR_MEMO_BUF_FIX:    case MTR_MEMO_PAGE_S_FIX:    case MTR_MEMO_PAGE_SX_FIX:    case MTR_MEMO_PAGE_X_FIX:
      block = reinterpret_cast<buf_block_t *>(slot->object);      /* 1. 對Page UNFIX，即buf_fix_count-- */
      buf_block_unfix(block);      /* 2. 釋放Page的鎖，block->lock */
      buf_page_release_latch(block, slot->type);      break;
      ...
  }
  ...
}

通過本節的介紹，我們已經瞭解了 InnoDB 是中是如何使用 Buffer Pool 提供的接口訪問 Page 的了，在具體介紹如何維護 Page 支持高效的查找和刷髒之前，我們先從整體上了解一下 Buffer Pool 的組織結構。

組織結構

爲了減少併發訪問的衝突，InnoDB 將 Buffer Pool 劃分爲innodb_buffer_pool_instances個 Buffer Pool Instances，Instance 之間沒有鎖衝突，每個 Page 固定屬於其中一個 Instance。從結構上看每個 Instance 都是對等的，因此本文接下來的內容都以一個 Instance 來進行介紹的。

Block、Page 和 Chunk

Buffer Pool 將分配的內存大小劃分爲相等的 Block，同時爲每一個 Block 分配了一個內存管理結構 buf_block_t，用來維護 Block 相關的狀態信息、加鎖信息、內存數據結構指針等。Block 是 Page 在內存中的載體，很多場景下他就是 Page。代碼上看 buf_block_t 的開頭就是維護 Page 信息的 buf_page_t（其中包括 page_id，發生修改的 lsn 信息 oldest_modification, newest_modification 等），從而他們之間可以直接做類型強制轉換：

struct buf_block_t {
  buf_page_t page; /*!< page information; this must
                   be the first field, so that
                   buf_pool->page_hash can point
                   to buf_page_t or buf_block_t */
  ...
}

單個 buf_block_t 需要幾百個字節存儲，以 100G 的 Buffer Pool，16KB 的 Page Size 爲例，將會有 6M 個 Block，這麼多的 buf_block_t 的內存佔用也是非常可觀的。爲了方便這部分內存的分配和管理，InnoDB 將其直接拼接到 Block 數組之前，這也是爲什麼 Buffer Pool 的實際內存佔用會看到略大於配置的innodb_buffer_pool_size。後來爲了方便在線調整大小，從 5.7 開始 Buffer Pool 又將內存劃分爲默認 128MB 的 Chunk，每個 Chunk 內部都是如下的內存結構：

在啓動時，buf_chunk_init函數中通過 mmap 分配 Buffer Pool 需要的所有內存，因此 InnoDB 在啓動時並不會真正佔用這麼大的物理內存，而是隨着 Page 的分配不斷上漲的。另外，由於每個 Block 的內存地址要求按照 Page Size 對齊，而 buf_block_t 並不是一定存在 Page Size 的約數關係，在 Page 數組的之前還可能有部分不會使用的內存碎片。

Hash Map、LRU List、Free List、Flush List

從使用的角度出發，用指定的 page_id 調用接口 buf_page_get_gen 是一個統一且非常頻繁的操作，InnoDB 用一個從 page_id 到 Block 的 Hash Map 來支持高效的查詢，所有在 Buffer Pool 中的 Page 都可以在 Hash Map 中找到。這個 Hash Map 採用鏈式衝突的方式實現，通過 buf_pool_t 中的 page_hash 指針訪問。除此之外，Buffer Pool 在內存中還維護了很多的鏈表來管理 Block，其中 LRU List 承擔的就是 LRU 替換算法中的棧的功能，Block 被訪問到時會被移動到 LRU List 的 Header 上，而長期未被訪問的 Page 會逐步的被推到 LRU List 的 Tail 位置，直至被換出。Free List 中維護的是尚未被使用到的 Block，每一個 Block，在同一時刻一定存在於 LRU List 或者 Free List 上。被修改的 Page 在 InnoDB 中被稱爲髒頁，髒頁需要在合適的時候進行刷盤。爲了獲取可以 Checkpoint 的位置，推進尚未刷髒的最小髒頁位置是必要的，因此需要一個按 oldest_modification 有序的髒頁序列，這就是 Flush List 的意義，髒頁一定是在使用中的 Block，因此一定同時也在 LRU List 上。整個內存結構如下圖所示：

獲取 Page

作爲 Buffer Pool 統一的對外接口，buf_page_get_gen會首先用給定的 Page ID 從 Hash Map 中查找對應的 Page，最簡單的，該 Page 已經在 Buffer Pool，可以直接標記 FIX 加 Lock 後返回。對良好配置的 Buffer Pool，絕大多數的 Page 需求都是可以在這裏就滿足的。show engine innodb status命令結果的 Buffer Pool Section 中有專門的 hit rate 的統計。如果 Page 還不在 Buffer Pool 就需要找到一塊空閒的內存 Block，初始化內存結構，然後將磁盤對應的 Page 加載進來。

獲取 Free Block

獲取空閒 Block 的邏輯在函數buf_LRU_get_free_block中實現。Free List 中維護了所有的空閒 Block，可以通過buf_LRU_get_free_only直接摘取一個下來使用。但更常見的情況是，Free List 根本沒有 Block，所有的 Block 已經都在 LRU List 上。這個時候就需要 LRU 替換算法來踢出一個已有的 Page，將其 Block 分配給新的 Page 使用。buf_LRU_scan_and_free_block會從 LRU 的尾部向前遍歷innodb_lru_scan_depth個 Page，被選擇的 Page 必須要滿足三個條件：不是髒頁、沒有被上層 FIX 以及沒有在 IO 過程中。如果沒有找到滿足條件的 Page，第二輪的遍歷就會覆蓋整 LRU。極端條件下，到這裏仍然沒能獲得一個可以逐出的 Page，可能是因爲髒頁太多導致，這個時候就需要通過buf_flush_single_page_from_LRU來直接 Flush 一個沒有被 FIX，且沒有 IO 的 Page，之後將其變成一個上面講到的可以逐出的 Page。被選擇可以逐出的 Page 會通過buf_LRU_free_page從 LRU List 及 Page Hash 中刪除，之後加入到 Free List 中，供本次訪問的 Page 使用。

填充新的 Page 內容

獲取到的 Free Block 會先通過buf_page_init進行初始化，其中會對 buf_block_t，包括 buf_page_t 的字段進行初始化和填充，之後加入到 Hash Map 中，並通過buf_LRU_add_block加入到 LRU List。最後在通過磁盤 IO 將 Page 數據填充到 buf_block_t 的 frame 字段中。在 IO 讀取的過程中會對 Page 標記 IO FIX 狀態來阻止其他線程 buf_page_get_gen 時的換出，並且持有 buf_block_t 的 lock 來阻止其他線程對 Page 內容的訪問。
爲了更好的利用磁盤的順序讀性能，InnoDB 還支持兩種預讀方式，每當讀一個 Page 成功後都會判斷是否要將周圍 Page 一起加載進 Buffer Pool，隨機預讀會參考同一個 Extend 中最近是不是有大量 Page 被訪問，可以通過innodb_random_read_ahead配置，而順序預讀參考的是是否有大量的 Page 正在順序被訪問到，可以通過innodb_read_ahead_threshold配置

LRU 實現

嚴格的 LRU 替換算法，會在每次被訪問的時候，將對應的 Page 移動到 LRU List 的 Header，也就是提升近期剛訪問 Page 的熱度，使之更不容易被換出。但這樣的實現會存在一個問題，通常數據庫的一個 Scan 操作可能會訪問到大量的，甚至超過內存容量的 Page 數，但這些 Page 在 Scan 結束後可能並不會繼續被使用，在這個過程中，LRU List 被整個替換一遍，導致 Scan 操作結束後的一段時間內，Buffer Pool 的命中率變的很低。這當然是我們不願意看到的。InnoDB 應對這個問題的方式，是將 LRU List 分成兩段 [6]，如下圖所示[7] 是 LRU 實現的示意圖，通過一個 Midpoint 將整個 List 分爲 New Sublist 和 Old Sublist，每次需要 Page 換出的時候會從 List 的尾部選擇：

當 LRU List 的長度超過BUF_LRU_OLD_MIN_LEN(512)時，新的插入會開始維護出 Midpoint 位置，實現裏是一個叫做 LRU_old 的指針，該指針指向 LRU List 距離 Tail 大約 3/8 的位置。之後新的buf_LRU_add_block都會將 Page 插入到 LRU_old 的位置，而不是 LRU List 的 Header。每次 Page 插入或者刪除時，都需要通過buf_LRU_old_adjust_len來嘗試調整 LRU_old 位置，儘量將 LRU_old 指針保持在 3/8 的位置，之所以說盡量，是因爲 InnoDB 中爲了避免頻繁的調整 LRU_old，設置了BUF_LRU_OLD_TOLERANCE(20)的容忍區間。
那麼，什麼時候會插入到 Header 呢？每次通過buf_page_get_gen獲取一個 Page 以後，無論是直接命中還是從磁盤換入，都會通過buf_page_make_young_if_needed判斷是否移動這個 Page 到 LRU List 的 Header 位置，選擇移動的有兩種情況：

如果這個 Page 是在 LRU_old 之後的位置，那麼必須滿足距離首次訪問超過innodb_old_blocks_time參數配置的時間，如此一來，無論多大的 Scan 操作最多隻會污染大約 3/8 的 LRU List，避免了前面所說的 Buffer Pool 效率降低問題。
如果這個 Page 在 LRU_old 之前的位置，那麼需要距離 LRU List 的 Header 超過大約 1/6 的位置，這個做法是爲了避免太熱的 Page 頻繁的反覆向 LRU Header 插入。

Flush

Buffer Pool 中發生修改的 Page 被稱爲髒頁，髒頁最終是需要寫回到磁盤中的，這個就是 Buffer Pool 的 Flush 過程。髒頁除了在 LRU List 上之外，還會被插入到 Flush List，Flush List 上的 Page 大體是按照 oldest_modification 有序排列的，但實現上因爲併發的原因，其實是接受了在一個小範圍（log_sys->recent_closed 的容量大小）內存在亂序的，當然這一點需要在確認 checkpoint 位置的時候做處理 [8]。

髒頁的產生

首先，先來看髒頁產生的過程。當 DB 需要修改的 Page 的時候會在 buf_page_get_gen 獲取的 Page 的時候指定 RW_X_LATCH 的 latch 模式，來對獲得到的 Page 加 X Lock；之後修改 Page 內容的同時，將對應的 Redo Log 寫入到獨佔的 Min-transaction buffer 中；Min-transaction commit 的時候將 log 拷貝到全局的 Log Buffer 中，並通過buf_flush_note_modification函數將該 Page 加入到 Buffer Pool 的 Flush List 上面，並用 mtr 的 start_lsn 及 end_lsn 更新 Page 的 oldest_modification 及 newest_modification。

刷髒時機

髒頁最終是需要寫回到磁盤中的，而這個寫回時機，其實是數據庫的故障恢復策略決定的，InnoDB 採用了《數據庫故障恢復機制的前世今生》[9] 中介紹的 Redo + Undo 的策略，將 Page 的刷髒跟事務的提交時間完全剝離開來，使得 Buffer Pool 的刷髒策略可以更靈活。理論上講，假設 Buffer Pool 足夠大，那麼將 Page 一直緩存在 Buffer Pool 中，等所有的修改完成再寫 Page 一定是最高效的，因爲這樣最小化了相對於內存訪問很慢的磁盤 IO。但顯然，這是不現實的，主要影響因素有兩個，這兩個因素也決定了 InnoDB Buffer Pool 的刷髒時機：

髒頁總量：

由於通常 Buffer Pool 的容量都是遠小於磁盤數據總量的，當內存不足時需要通過 LRU 換出老 Page，前面也提到了髒頁是不能直接被換出的。

髒頁總量的因素傾向於優先 Flush LRU Tail 附近 Page。
Active Redo 總量：

也就是 Checkpoint LSN 之後的 Redo 總量，《庖丁解 InnoDB 之 REDO LOG》[8] 中介紹過，InnoDB 的 Redo 是在innodb_log_files_in_group配置的 redo 數量中循環使用的，落後 Checkpoint 會導 Active Redo 總量過高，致使剩餘可用的 Redo 空間不足，而最老髒頁的位置是限制 Checkpoint 推進的最直接原因。

Active Redo 總量因素傾向於優先將 oldest_modification 最小的 Page，也就是 Flush List 的 Tail 位置進行刷髒。

依據這兩個因素，InnoDB 的 Buffer Pool 提供了三種模式的 Flush，其中 Single Flush 應對的是髒頁總量過高的極端情況，由用戶線程在完全找不到可以換出的 Clean Page 時觸發，每次同步刷一個 Page；而 Sync Flush 可以認爲是應對 Active Redo 總量過高的極端情況，在可用的 Redo 空間嚴重不足或需要強制推進 Checkpoint 時觸發，Sync Flush 會盡可能的將 oldest_modification 小於制定 LSN 的 Page 全部刷髒，因此可能會涉及大量 Page，從而嚴重影響用戶請求。因此，理想情況下，這兩種刷髒模式都是應該儘量避免的。而更多的時候應該依靠的是後臺一直在運行的 Batch Flush。

Batch Flush

Batch Flush 由一個 Page Coordinator 線程和一組 Page Cleaner 線程負責，具體的個數跟 Buffer Pool 的 Instance 數綁定，所有的線程共用一個page_cleaner_t結構體來做一些統計和狀態管理。通常情況下 Page Coordinator 會週期性被喚醒，通過page_cleaner_flush_pages_recommendation計算每一輪需要刷髒的 Page 數，然後將這個需求下發給所有的 Page Cleaner 線程，並等待所有的 Page Cleaner 刷髒完畢，Page Coordinator 自己也會承擔一份刷髒任務。而page_cleaner_flush_pages_recommendation判斷刷髒量的時候，會綜合考慮當前的髒頁總量，Active Redo 總量，以及磁盤 IO 的承載能，其中磁盤能力這個可以通過參數innodb_io_capacity以及innodb_io_capacity_max指定，下面是整理過的計算公式：

  n_pages = (innodb_io_capacity * (ut_max(pct_for_dirty, pct_for_lsn)) / 100
              + avg_page_rate
              + pages_for_lsn
             ) / 3;  /* 上限被參數innodb_io_capacity_max 限制 */
  if (n_pages > srv_max_io_capacity) {
    n_pages = srv_max_io_capacity;
  }

靜態髒頁總量（pct_for_dirty）：

根據當前已有的髒頁總量計算的一個刷髒比例。

髒頁量低於innodb_max_dirty_pages_pct_lwm不刷髒，高於innodb_max_dirty_pages_pct_lwm，則按髒頁量佔innodb_max_dirty_pages_pct的百分比刷髒，也就說大於innodb_max_dirty_pages_pctpct_for_diry 就會成爲百分百。

也就是說，pct_for_dirty 是一個在 pct_lwm 到 pct 之間，從 0 到 100 按髒頁率線性增長的值。
靜態 Active Redo（pct_for_lsn）：

根據當前的 Active Redo 計算的刷髒比例。

如果 Active Redo 的量超過了一個接近 Redo 空間滿的值log_sys->max_modified_age_async，或者用戶配置了innodb_adaptive_flushing，這裏就用當前的 Active Redo 水位計算一個 pct_for_lsn，這裏實現上不是一個純線性的關係，而是隨着 Active Redo 的增加 pct_for_lsn 增長速度也在加快。
動態髒頁量變化（avg_page_rate）：

由於 n_pages 的判斷過程是一個週期的打點行爲，只考慮靜態的水位顯然是不夠的，這裏還會將這個週期內的髒頁增長速率作爲一個因素計算進來。
動態 Active Redo 變化（pages_for_lsn）：

類似的這裏也會考慮週期內的 Redo 增長速率，這裏的計算方式是將單位時間內 Redo 的增長之後的 LSN，投影到 BP 中 Page 的 oldest_modification 上，所覆蓋的 Page 數就是 pages_for_lsn 的值。

通過上面過程計算出的 n_pages 數，會平分給多個 Page Cleaner，然後將他們喚醒。每個 Page Cleaner 會負責自己獨立的 Buffer Pool Instance，因此之間沒有衝突，每個 Page Cleaner 被喚醒後，會先後從 LRU List 及 Flush List 上進行刷髒，一輪刷髒結束後纔會發起下一輪的刷髒。之所以要從 LRU List 做刷髒還是爲了保持足夠用的 Free Page，因此只有當 Free List 上的 Page 小於innodb_lru_scan_depth的時候纔會發起。如果不是髒頁可以直接用buf_LRU_free_page從 LRU 上刪除，否則還需要調用buf_flush_page_and_try_neighbors先進行刷髒，從函數名字也可以看出，刷每一個 Page 的時候都會嘗試對其周圍的其他髒頁也進行 Flush，這個主要還是爲了利用磁盤的順序寫性能，可以通過innodb_flush_neighbors配置開關。如果從 LRU List 上沒有 Flush 足夠量的 Page 就需要遍歷 Flush List，同樣調用buf_flush_page_and_try_neighbors進行刷髒。
無論哪種方式的刷髒，最終都會進入buf_flush_write_block_low寫盤，除了 Single Flush 以外，所有的 Flush 操作都是異步進行的，IO 結束後會在 IO 線程中回調buf_page_io_complete做收尾工作，包括清空 IO FIX 狀態，釋放 Page Lock，以及從 Flush List 和 LRU List 上刪除。

併發控制

InnoDB 中可能存在大量的線程同時競爭訪問 Buffer Pool，包括所有通過buf_page_get_gen獲取 Page 的用戶線程和後臺線程；上面提到的 Flush 線程；以及 IO 線程。作爲整個數據庫的數據中樞，Buffer Pool 對併發訪問的支持能力直接影響數據庫的性能，從代碼中也可以看出其中有大量鎖相關的邏輯，作爲一個工業級的數據庫實現，這些邏輯都經過了大量細節上的優化，一定程度上增加了代碼的複雜性。而鎖的優化思路，無外乎降低鎖粒度，減少鎖時間，消除鎖請求等，本節就沿着這樣的思路介紹 Buffer Pool 中鎖的設計與實現。Buffer Pool 中涉及到的鎖，按照鎖保護對象的層次，依次分爲：保護 Hash 表的 Hash Map Lock，保護 List 結構的 List Mutex，保護 buf_block_t 中結構的 Block Mutex，保護真正的 Page 內容的 Page Frame Lock。

Hash Map Lock

所有的 buf_page_get_gen 請求的第一步就是通過 Hash Map 判斷 Block 是否存在於 Buffer Pool 中，可想而知這裏的競爭是極其強烈的，InnoDB 中採用了分區鎖的辦法，分區的數量可以通過innodb_page_hash_locks（16）來配置，每個分區會維護一個獨立的讀寫鎖。每次請求會先通過 page_id 映射到一個分區上，然後請求這個分區的讀寫鎖。如此一來只有映射到同一個分區的請求才會產生所衝突。

List Mutex

上面講過 Buffer Pool 中的 Block 是按照 List 維護的，最基礎的包括維護全量使用 Block 的 LRU List，空閒頁的 Free List，以及髒頁的 Flush List。這些 List 都有自己獨立的互斥鎖 Mutex，對 List 的讀取或修改都需要持有 List 本身的 Mutex。這些鎖的目的是保護對應的 List 本身的數據結構，因此會最小化到對 List 本身數據結構訪問和修改的範圍內。

Block Mutex

每個 Page 的控制結構體 buf_block_t 上都有一個block->mutex用來保護這個 block 的一些諸如 io_fix，buf_fix_count、訪問時間等狀態信息。相對於外層無論是 Hash Map 還是 List Mutex，Block Mutex 的鎖粒度都小的很多，通過 Block Mutex 來避免更長時間的持有上層容器的鎖顯然是划算的。而 io_fix，buf_fix_count 這些信息也能顯著的減少對 Page Lock 的爭搶，比如當 Buffer Pool 需要從 LRU 上踢出一個老 Page 時，需要確定這個 Page 沒有正在被使用，以及沒有在做 IO 操作，這個是個非常常見的行爲，但他本身其實並不關心 Page 的內容。這時，短暫的持有 Block Mutex 並判斷 io_fix 狀態和 buf_fix_count 計數，顯然會比爭搶 Page Frame Lock 更輕量。

Page Frame Lock

除了 Block Mutex，buf_block_t 上還有一個讀寫鎖結構block->lock，這個讀寫鎖保護的是真正的 page 內容，也就是 block->frame。這個鎖就是《B + 樹數據庫加鎖歷史》[4] 一文中講到的保護 Page 的 Latch，在對 B+Tree 的遍歷和修改中都可能需要獲取這把鎖，除此之外，涉及到 Page 的 IO 的過程中也需要持有這把鎖，Page 讀 IO 由於需要直接修改內存 frame 內容，需要持有 X lock，而寫 IO 的過程持有的是 SX Lock，來避免有其他寫 IO 操作同時發生。

死鎖避免

當上面這些鎖中的多個需要同時獲取時，爲了避免不同線程間發生死鎖，InnoDB 規定了嚴格的加鎖順序，也就是 Latch Order，如下所示，所有對鎖的獲取必須要按照這個順序從下往上進行。這個順序跟大多數場景的使用是一致的，但也是有例外的，比如從 Flush List 上選擇 Page 進行刷髒的時候，由於 Flush List Mutex 的級別比較低，可以看到放掉 Flush List Mutex 再去獲取 Block Mutex 的情況。

enum latch_level_t {
  ...
  SYNC_BUF_FLUSH_LIST,   /* Flush List Mutex */
  SYNC_BUF_FREE_LIST,    /* Free List Mutex */
  SYNC_BUF_BLOCK,         /* Block Mutex */
  SYNC_BUF_PAGE_HASH,    /* Hash Map Lock */
  SYNC_BUF_LRU_LIST,     /* LRU List Mutex */...
}

示例場景

爲了更好的理解 Buffer Pool 的加鎖過程，我們設想這樣一種場景：一個用戶讀請求，需要通過buf_page_get_gen來獲取 Page a，首先查找 Hash Map 發現其不在內存，檢查 Free List 發現也沒有空頁，只好從 LRU 的 Tail 先踢出一個老的 Page，將其 Block A 加入 Free List，之後再從磁盤將 Page a 讀入 Block A，最後獲得這個 Page a，並持有其 Lock 及 FIX 狀態。得到一個如下表所示的加鎖過程：

這張表中可以清楚的看到：1，每種鎖都限制在真正操作其保護的數據結構的較小範圍內；2，當需要同時持有多個鎖時，嚴格遵守上面說的 Latch Order，比如從 LRU 和 Hash Map 中加入或刪除時，嚴格遵守 LRU List Mutex -> Hash Map Mutex -> Block Mutex 的順序。3，在 IO 過程中，除了 Page Frame Lock 外不持有任何鎖，同時也通過設置 io_fix，避免了諸如 LRU 算法檢查是否可以換出時，對 Page Frame Lock 加鎖。篇幅關係，這裏只介紹了這一種場景的加鎖順序，更多的內容可以見鏈接：Flush List 刷髒加鎖，LRU List 刷髒加鎖。

總結

本文聚焦於 InnoDB 中的 Buffer Pool 的核心功能，首先從宏觀上介紹其背景，包括設計目標、接口、遇到的問題及替換算法的選擇等；然後後從使用者的角度介紹了 Buffer Pool 作爲一個整體對外暴露的統一接口和調用方式；之後介紹了 Buffer Pool 內部獲取 Page 的詳細過程以及 LRU 替換算法的實現；再之後介紹了 Page 刷髒的觸發因素及過程；最後梳理了 Buffer Pool 如何安全的實現高併發高性能。

參考

[1] MySQL Source Code

[2] 數據庫故障恢復的前世今生

[3] Effelsberg, Wolfgang, and Theo Haerder. “Principles of database buffer management.” ACM Transactions on Database Systems (TODS) 9.4 (1984): 560-595.

[4] B + 樹數據庫加鎖歷史

[5] B + 樹數據庫故障恢復概述

[6] MySQL 8.0 Reference Manual 15.8.3.3 Making the Buffer Pool Scan Resistant

[7] MySQL 8.0 Reference Manual 15.5.1 Buffer Pool

[8] 庖丁解 InnoDB 之 REDO LOG

[9] 數據庫故障恢復機制的前世今生

[10] Buffer pool 併發控制

[11] Buffer Pool Performance Improvements in the InnoDB Storage Engine of MariaDB Server

[12] PolarDB 數據庫內核月報

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Q1AIYFcVz8HXiGpVHA4DtQ

背景