MySQL🐬 InnoDB 教我的事： 最近最少使用 LRU 串列的優化
筆者曾任職 Yahoo，現在區塊鏈產業打滾，《軟體需求溝通 ─ 從外商公司學跨部門協作開發》線上課程講師，紛絲團《程式猿吃香蕉🍌》
LRU (Least Recently Used) 串列在中文翻譯為「最近最少使用串列」 ，是一種常見的資料結構，白話來說，就是把每一筆資料排排站，把最近使用的資料爬排在前面，把最少使用的資料排在後面，通常是使用鏈結串列 (Linked List) 的形式來實作。LRU 串列的應用場景很廣，目的是為了要「降低讀取資料的操作成本」，具體的做法是：將資料從磁碟取出後，放到快取 (Cache) 當中，快取中的資料以 LRU 的形式排序，把常用的資料排在前面，以方便我們多次取用。
舉例來說，Yahoo 熱門搜尋關鍵字排行榜，就可以應用 LRU 的思想來多次取用資料。因為，前幾個小時熱門的關鍵字，可能在下一個小時依然很熱門，也就是說，前幾名的關鍵字，有很高的機率會不斷被程式取出來顯示在頁面上，如果我們在快取中保留這些常用的字，就可以方便程式多次讀取，降低讀取的操作成本。
以生活化的例子比喻，快取 (Cache) 就像我們的書桌桌面，我們會將常用的物品擺在離手邊近一點的地方，而不常用的物品擺在遠一點的地方。這也是 LRU 思想的體現，目的同樣是降低我們取用物品的「操作成本」。
InnoDB 是 MySQL 預設的儲存引擎，它有許多軟體設計的思想值得我們借鑑。很多人總會開玩笑地說，寫程式不外乎是處理「新增、讀取、修改、刪除」 (簡稱 CRUD)
而 InnoDB 儲存引擎裡面正好就有大量關於 CRUD 的設計，跟我們日常的程式開發工作息息相關。
這些設計都是具體而微的，因此，看看前人的設計，可以啟發我們更多的思考，打造更好的軟體。以下，我將會分享 InnoDB 對 LRU 串列的使用以及優化思路。
▍InnoDB 會用到 LRU 串列？
MySQL InnoDB 為了優化讀取的效能，做了兩件事情：
- 在記憶體裡快取資料
- 記憶體內的資料以鏈結串列 (Linked List) 構造
如上圖所示，在記憶體裡快取資料，可以減少對磁盤的存取，讀取速度更快，而以鏈結串列構造資料，可以方便我們對快取的內容做調整。然而，為什麼需要「做調整」呢？因為 InnoDB 要把常用的資料排在鏈結串列的前面，少用的放在後面，而這些順序是會隨著時間變化的，因此，鏈結串列的特性就很契合需求，它對於插入、刪除節點較方便。可能有些讀者發現了，這裡 InnoDB 就是採用 LRU 的思想對快取的資料進行排序。
MySQL InnoDB 在存取資料的最小單位稱為「頁」(Page)，因此鏈結串列的每一個節點存放的便是一個又一個的頁。而這個快取的記憶體空間，InnoDB 稱為 Buffer Pool，如下圖所示。
▍LRU 演算法
已知要以頁 (Page) 為節點，建立鏈結串列，那麼排序就成為了一個問題，該怎麼判斷哪個節點要在前面，哪個節點要在後面？此外，記憶體空間是有限的，不能把所有頁都快取到記憶體裡面，因此便需要設計一個演算法，來回答以下問題：
- 每個節點排序的邏輯是什麼？
- 什麼時候可以新增節點？
- 什麼時候可以淘汰/移除節點？
傳統的 LRU 演算法，會先定義好鏈結串列的總節點個數，不得超過。當有一筆資料頁(Page) 被讀取到，會將這一筆資料視為「最常用」，而將它插入到最前面，而此時，如果節點超過總節點個數限制，排在最後的資料頁會被淘汰，如下圖所示。
如果是鏈結串列當中已有的資料頁被讀取，該資料會從原本的位置被移出，插入到最前面的位置。保持排在前面的節點，都是最近用到的，如下圖所示。
這個做法看起來很完美，然而， InnoDB 並不是這樣做的。
因為，如果 InnoDB 每一次都把最近用到的資料插在最前面，那麼前半部「最常用」的資料會變動得太頻繁，失去快取資料頁的意義。
怎麼說呢？因為在資料庫的讀取情境下，一口氣讀取一大批資料頁 (Page) 是很常見的，尤其是觸發全表掃描 (table scan) 或索引掃描 (index scan) 的時候。這些資料頁有很高機率就只讀這麼一次，下次也不會被重複讀取，這些「不會再被讀取」的資料頁，在傳統的 LRU 演算法下，會被大批地塞到鏈結串列的前半部，被誤認為「最常用」的資料頁。因為大部分的快取空間被佔滿，反而真正常用的資料頁不再快取裡面，要從磁碟當中去讀，這也就失去了對資料頁做快取的意義。
▍InnoDB 對 LRU 演算法的優化
有鑒於這個情況， InnoDO 不採用傳統的 LRU 演算法，而是針對自己的使用情境進行優化。調整了「最常用」的認定標準，主要為以下兩點：
❶ 次數認定
最近使用到的資料頁 (Page) 從磁碟中被讀到時，不再直接插入在鏈結串列的前端，而是插入在中間。當在快取中再次被讀取到時，才會被認定為「最常用」的資料，放到鏈結串列的最前端。這樣不同的插入做法，也稱為中點插入策略 (Midpoint Insertion Strategy)。
以生活化的例子來說：你想看的書，不再是直接放到書桌上最靠近你的手邊，因為你可能只是興致來了取下書翻一翻，不是真的要看。因此，把書從書架取下 (磁碟取出) 翻閱後，必須先放在書桌的中間 (鏈結串列的中間)，當你再次把它拿起來看時，才可以放在你的手邊 (鏈結串列最前端)。
InnoDB 的作法如下圖所示，將鏈結串列分成兩段，稱為新串列 (New Sub List) 以及舊串列 (Old Sub List) ，中間的分隔約在倒數 3/8 的位置，從磁碟中讀取的資料會先放在舊串列的頭部 (Head)，即倒數 3/8 的位置，等到在 Buffer Pool 中的資料頁再次被讀取時，才會插入到新串列的頭部，當插入後，導致節點滿了的時候，舊串列中最後一個節點會被淘汰(Evict)。由參數 innodb_old_blocks_pct可以設定舊串列所佔的比例，在 MySQL 8.0 中預設值為 37 ，即 37% 的意思，約為 3/8。
這項優化是由「次數」來認定是否要移動到鏈結串列的最前面，當在快取 Buffer Pool 中「再一次」被讀取時，才會被認定為「最常用」，這樣就可以避免當全表掃描 (table scan) 或索引掃描 (index scan) 的時候，大量的資料被塞到快取的前半部。
❷ 時間認定
除了次數認定之外，innoDB 還提供 innodb_old_blocks_time 參數，設定至少資料頁 (Page) 要待在舊串列多久，才可以被移動到新串列的頭部。這個參數的單位是毫秒，在 MySQL 8.0 的預設值是 1000。透過這個參數來避免鏈結串列被頻繁地刷新。
InnoDB 透過這些優化，來讓真正該被快取的內容，可以排在前面，有效地提升讀取的效能。衡量快取是否有效的重要指標為「命中率」 (Hit rate)，舉例來說，如果快取一堆無用的資料，讀資料時都還要從磁碟裡面找，這樣快取的命中率就很低，它也就失去用處了。InnoDB 提供了 INNODB_BUFFER_POOL_STATS 這張表，讓我們可以查看 Buffer Pool 快取的命中率。
▍小結
在設計快取的時候，命中率 (Hit rate) 是很重要的考量，從 InnoDB 的設計理念我們可以發現，它透過調整「次數」以及「時間」來改良 LRU 的算法，重新定義「最常用」的資料是什麼，讓快取的命中率提高。
讀取資料的快取設計是在開發系統時很常見的情境，無論是在分散式環境或是單體運行的架構都會遇到。參考 InnoDB 的設計思想，當我們在設計自己系統的快取時，也可以用次數以及時間的維度來調整資料順序，採用鏈結串列的資料結構特性提升效率，並且設計命中率統計資訊來幫助我們持續優化。設計見得愈多，解法的工具箱也就愈豐富。當然，InnoDB 的作法不一定最好，但至少 It just works，在遇到類似的問題時，可以作為參考。
讀這些設計是很有趣的，站在前人的肩膀上，將他們做法抽象化並提煉成自己的思考，來幫助我們自己做得更好，走得更遠。希望這些分享也對你有所啟發。
若是喜歡我分享的內容，可以訂閱我的粉絲團《程式猿吃香蕉🍌》，在軟體開發的路上，一起分享交流，一起成長。
