你知道MySQL的LRU鏈表嗎？

2020 年 11 月 16 日
筆記
MySQL

相信大家對LRU鏈表是不陌生的，算是一種基礎的數據結構！

LRU：Least Recently Used

一、簡述傳統的LRU鏈表

LRU：Least Recently Used

相信大家對LRU鏈表是不陌生的，它算是一種基礎的數據結構吧，而且想必面試時也被問到過什麼是LRU鏈表，甚至是讓你手寫一個LRU鏈表。

如果你讀了上一篇：你有沒有搞混查詢緩存和BufferPool？談談看！

想必你已經知道了MySQL的Buffer Pool機制以及MySQL組織數據的最小單位是數據頁。並且你也知道了數據頁在Buffer Pool中是以LRU鏈表的數據結構組織在一起的。

其實所謂的LRU鏈表本質上就是一個雙向循環鏈表，如下圖：

下面我們結合LRU鏈表和數據頁機制描述一下MySQL加載數據的機制：

我們將從磁盤中讀取的數據頁稱為young page，young page會被直接放在鏈表的頭部。已經存在於LRU鏈表中數據頁如果被使用到了，那麼該數據頁也被認為是young page而被移動到鏈表頭部。這樣鏈表尾部的數據就是最近最少使用的數據了，當Buffer Pool容量不足，或者後台線程主動刷新數據頁時，就會優先刷新鏈表尾部的數據頁。

二、傳統LRU鏈表的不足

相信你之前肯定聽說過操作系統級別的空間局部性原理：

spatial locality（空間局部性）：也就是說讀取一個數據，在它周圍內存地址存儲的數據也很有可能被讀取到，於是操作系統會幫你預讀一部分數據。

MySQL也是存在存在預讀機制的！

當Buffer Pool中存儲着一個區中13個連續的數據頁時，你再去這個區裏面讀取，MySQL就會將這個區裏面所有的數據頁都加載進Buffer Pool中的LRU鏈表中。（然後可能你根本不會使用這些被預讀的數據頁）
當你順序的訪問了一個區中大於 innndb_read_ahead_threshold=56個數據頁時，MySQL會自動幫你將下一個相鄰區中的數據頁讀入LRU鏈表中。（這個機制默認是被關閉的）
當你執行select * from xxx;時，如果表中的數據頁非常多，那這些數據頁就會一一將Buffer Pool中的經常使用的緩存頁擠下去，可能留在LRU鏈表中的全部是你不經常使用的數據。

綜上你可以看到，所謂的預讀機制的優勢，實際上違背了LRU去實現將最近最少使用的數據頁刷入磁盤的設計初衷。