MySQL🐬 InnoDB 教我的事: 最近最少使用 LRU 串列的優化

筆者曾任職 Yahoo ,《軟體需求溝通 ─ 從外商公司學跨部門協作開發》線上課程講師,紛絲團《程式猿吃香蕉🍌》

(圖片來源:kunalsharda.com)

LRU (Least Recently Used) 串列在中文翻譯為「最近最少使用串列」 ,是一種常見的資料結構,白話來說,就是把每一筆資料排排站,把最近使用的資料爬排在前面,把最少使用的資料排在後面,通常是使用鏈結串列 (Linked List) 的形式來實作。LRU 串列的應用場景很廣,目的是為了要「降低讀取資料的操作成本」,具體的做法是:將資料從磁碟取出後,放到快取 (Cache) 當中,快取中的資料以 LRU 的形式排序,把常用的資料排在前面,以方便我們多次取用。

舉例來說,Yahoo 熱門搜尋關鍵字排行榜,就可以應用 LRU 的思想來多次取用資料。因為,前幾個小時熱門的關鍵字,可能在下一個小時依然很熱門,也就是說,前幾名的關鍵字,有很高的機率會不斷被程式取出來顯示在頁面上,如果我們在快取中保留這些常用的字,就可以方便程式多次讀取,降低讀取的操作成本。

(Yahoo 熱門搜尋關鍵字排行榜)

以生活化的例子比喻,快取 (Cache) 就像我們的書桌桌面,我們會將常用的物品擺在離手邊近一點的地方,而不常用的物品擺在遠一點的地方。這也是 LRU 思想的體現,目的同樣是降低我們取用物品的「操作成本」。

InnoDB 是 MySQL 預設的儲存引擎,它有許多軟體設計的思想值得我們借鑑。很多人總會開玩笑地說,寫程式不外乎是處理「新增、讀取、修改、刪除」 (簡稱 CRUD)

而 InnoDB 儲存引擎裡面正好就有大量關於 CRUD 的設計,跟我們日常的程式開發工作息息相關。

這些設計都是具體而微的,因此,看看前人的設計,可以啟發我們更多的思考,打造更好的軟體。以下,我將會分享 InnoDB 對 LRU 串列的使用以及優化思路。

▍InnoDB 會用到 LRU 串列?

MySQL InnoDB 為了優化讀取的效能,做了兩件事情:

  1. 在記憶體裡快取資料
  2. 記憶體內的資料以鏈結串列 (Linked List) 構造

如上圖所示,在記憶體裡快取資料,可以減少對磁盤的存取,讀取速度更快,而以鏈結串列構造資料,可以方便我們對快取的內容做調整。然而,為什麼需要「做調整」呢?因為 InnoDB 要把常用的資料排在鏈結串列的前面,少用的放在後面,而這些順序是會隨著時間變化的,因此,鏈結串列的特性就很契合需求,它對於插入、刪除節點較方便。可能有些讀者發現了,這裡 InnoDB 就是採用 LRU 的思想對快取的資料進行排序。

MySQL InnoDB 在存取資料的最小單位稱為「頁」(Page),因此鏈結串列的每一個節點存放的便是一個又一個的頁。而這個快取的記憶體空間,InnoDB 稱為 Buffer Pool,如下圖所示。

▍LRU 演算法

已知要以頁 (Page) 為節點,建立鏈結串列,那麼排序就成為了一個問題,該怎麼判斷哪個節點要在前面,哪個節點要在後面?此外,記憶體空間是有限的,不能把所有頁都快取到記憶體裡面,因此便需要設計一個演算法,來回答以下問題:

  1. 每個節點排序的邏輯是什麼?
  2. 什麼時候可以新增節點?
  3. 什麼時候可以淘汰/移除節點?

傳統的 LRU 演算法,會先定義好鏈結串列的總節點個數,不得超過。當有一筆資料頁(Page) 被讀取到,會將這一筆資料視為「最常用」,而將它插入到最前面,而此時,如果節點超過總節點個數限制,排在最後的資料頁會被淘汰,如下圖所示。

(示例:傳統 LRU 算法,innoDB 並非這樣做)

如果是鏈結串列當中已有的資料頁被讀取,該資料會從原本的位置被移出,插入到最前面的位置。保持排在前面的節點,都是最近用到的,如下圖所示。

(示例:傳統 LRU 算法,innoDB 並非這樣做)

這個做法看起來很完美,然而, 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。

(圖片來源:MySQL 8.0 doc)

這項優化是由「次數」來認定是否要移動到鏈結串列的最前面,當在快取 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,在遇到類似的問題時,可以作為參考。

讀這些設計是很有趣的,站在前人的肩膀上,將他們做法抽象化並提煉成自己的思考,來幫助我們自己做得更好,走得更遠。希望這些分享也對你有所啟發。

若是喜歡我分享的內容,可以訂閱我的粉絲團《程式猿吃香蕉🍌》,在軟體開發的路上,一起分享交流,一起成長。

--

--

我們是一群軟體開發愛好者,喜歡將軟體知識以簡單生動的方式講給你聽,順口好消化,營養又健康!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jayden Lin

Jayden Lin

Yahoo 擔任 Lead Engineer,負責廣告系統,帶團隊做跨國開發。也是《程式猿吃香蕉》團隊創辦人,喜歡將實用的軟體知識以簡單生動的方式講給大家聽 😄😄😄