面試官:說說Innodb中LRU怎麼做的？

引言

某日，小編去面試(純屬瞎編)，有了如下對話

接下來回去

於是就有了本文誕生

正文

什麼是BufferPool

Innodb為了解決磁盤上磁盤速度和CPU速度不一致的問題，在操作磁盤上的數據時，先將數據加載至內存中，在內存中對數據頁進行操作。

Mysql在啟動的時候，會向內存申請一塊連續的空間，這塊空間名為Bufffer Pool，也就是緩衝池，默認情況下Buffer Pool只有128M。

那緩衝池長什麼樣的呢，如下圖所示

圖片出自《Mysql運維內參》

如圖所示，有三部分組成:

• ctl: 俗稱控制體，裡頭有一個指針指向緩存頁，還有一個成員變量存儲著所謂的一些所謂的控制信息，例如該頁所屬的表空間編號、頁號
• page:緩存頁，就是磁盤上的頁加載進Bufffer Pool後的結構體
• 碎片：每個控制體都有一個緩存頁。最後內存中會有一點點的空間不足以容納一對控制體和緩存頁，於是碎片就誕生的！

這個控制體ctl在mysql源碼中長這樣的

struct buf_block_t{
 //省略
 buf_page_t page;
 byte* frame;
 //省略
}

嗯，懂C語言的自然知道，frame是一個指針啦，指向緩存頁。

而page存儲的就是該頁所屬的表空間編號、頁號等。

在BufferPool中有三大鏈表，需要重點關注，它們存儲的元素都是buf_page_t。

比如，我總要知道那些頁是可以用，是空閒的吧。

OK,這些信息在free鏈表中維護。

再比如，CPU肯定是不會去修改磁盤上的數據。那麼，CPU修改了BufferPool中的數據後，Innodb總要知道要把哪一塊信息刷到磁盤上吧。

OK，這些信息在flush鏈表中維護。

最後，當free鏈表裡沒多餘的空閒頁啦，innodb要淘汰一些緩存頁啦。怎麼淘汰？

這還用問，一定是淘汰最近最少使用的緩存頁啊。

怎麼知道這些頁是最近最少使用的呢？

嗯，那就是要藉助傳說中的LRU鏈表啦。

簡單的LRU

我們先來說一個簡單的LRU算法。LRU嘛，全稱吧啦吧啦…英文名忘了。反正就是一個淘汰最近最少使用

然後就去百度了一下，我發現百度是這麼說的

最常見的實現是使用一個鏈表保存緩存數據，詳細算法實現如下：

• 1. 新數據插入到鏈表頭部；
• 2. 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部；
• 3. 當鏈表滿的時候，將鏈表尾部的數據丟棄。

嗯，完美！很完美！反正innodb中不可能這樣設計～

那麼為什麼不能這麼設計呢？

原因一

假設有一張表叫yan_ge_hao_shuai,(請將表名多看幾遍)，回到正題，這張表什麼索引都木有，有著幾千萬數據，反正就是很多很多數據頁。然後，執行下面的語句

select * from yan_ge_hao_shuai

因為沒有任何索引嘛，那就進行全表掃描了。那麼按照上面說的算法，這些數據頁也會被全部塞入LRU鏈表，並且通通加載到BufferPool中，從而迅速清空其他查詢語句留下來的高頻的數據頁。那麼此時，你的BufferPool裡全是低頻的數據頁，就會發現緩存命中率大大滴降低了。

於是你就會覺得:"我勒個去，設計這個Innodb的人，怕不是腦袋有問題…(以下省略一萬字)"

原因二

這裡先說以下innodb的預讀機制，是這樣子滴！這個預讀細說起來可以分為線性預讀和隨機預讀。借一張姜承堯大大的圖，innodb的表邏輯結構如下圖所示

其實借這張圖，我只想說一件事。數據頁(page)是放在區(extent)裡的。

那麼

• 線性預讀:當一個區中有連續56個頁面(56為默認值)被加載到BufferPool中，會將這個區中的所有頁面都加載到BufferPool中。其實挺合理的，畢竟一個區最多才64個頁。
• 隨機預讀:當一個區中隨機13個頁面(13為默認值)被加載到BufferPool中，會將這個區中所有頁面都加載到BufferPool中。隨機預讀默認是關閉，由變量innodb_random_read_ahead控制。

好了，上面那一堆其實看不懂也沒事。我只想說一件事，預讀機制會預讀一些額外的頁到到BufferPool中。

那麼，如果這些預讀頁並不是高頻的頁呢？

OK，如果這些頁並不是高頻的頁，按照上面的算法，也會被加入LRU 鏈表，就會將鏈表末端一些高頻的數據頁給淘汰掉，從而導致命中率下降。

於是你會覺得:"唉，自己寫一個都比他強…(此處略過一萬字)"

Innodb的LRU

OK，為了解決上面的兩個缺點。Innodb將這個鏈表分為兩個部分，也就是所謂的old區和young區。

天啦嚕，這兩個區幹嘛用的？

ok，young區在鏈表的頭部，存放經常被訪問的數據頁，可以理解為熱數據！

ok，old區在鏈表的尾部，存放不經常被訪問的數據頁，可以理解為冷數據！

這兩個部分的交匯處稱為midpoint，往下看！

怎麼知道兩個區的比例？

執行下面的命令

mysql> SHOW VARIABLES LIKE 'innodb_old_blocks_pct';
+-----------------------+-------+
| Variable_name | Value |
+-----------------------+-------+
| innodb_old_blocks_pct | 37 |
+-----------------------+-------+
1 row in set (0.01 sec)

這說明了old區的比例為37%，也就是冷數據大概佔LRU鏈表的3/8。剩下的就是young區的熱數據。

於是可以得到一張大概的LRU鏈表圖，如下所示(圖片出自網絡)

ps：一般生產的機器，內存比較大。我們會把innodb_old_blocks_pct值調低，防止熱數據被刷出內存。

數據何時在old區，何時進入young區？

好，數據頁第一次被加載進BufferPool時在old區頭部。

當這個數據頁在old區，再次被訪問到，會做如下判斷

• 如果這個數據頁在LRU鏈表中old區存在的時間超過了1秒，就把它移動到young區
• 這個存在時間由innodb_old_blocks_time控制

我們來看看innodb_old_blocks_time的值，如下所示

mysql> SHOW VARIABLES LIKE 'innodb_old_blocks_time';
+------------------------+-------+
| Variable_name | Value |
+------------------------+-------+
| innodb_old_blocks_time | 1000 |
+------------------------+-------+
1 row in set (0.01 sec)

那怎麼解決這些缺點的？

針對原因一

也就是所謂的全表掃描導致Bufferpool中的高頻數據頁快速被淘汰的問題。

Innodb這麼做的:

(1)掃描過程中，需要新插入的數據頁，都被放到old區

(2)一個數據頁會有多條記錄，因此一個數據頁會被訪問多次

(3)由於是順序掃描,數據頁的第一次被訪問和最後一次被訪問的時間間隔不會超過1S，因此還是會留在old區

(4)繼續掃描，之前的數據頁再也不會被訪問到，因此也不會被移到young區，最終很快被淘汰

針對原因二

也就是預讀到的頁，可能不是高頻次的頁。

你看，你預讀到的頁，是存在old區的。如果這個頁後續不會被繼續訪問到，是會在old區逐步被淘汰的。因此不會影響young區的熱數據。

監控冷熱數據

執行下面命令即可

mysql> show engine innnodb status\G
……
Pages made young 0, not young 0
0.00 youngs/s, 0.00 non-youngs/s

1、數據頁從冷到熱，稱為young；not young就是數據在沒有成為熱數據情況下就被刷走的量(累計值)。

2、non-youngs/s，這個數值如果很高，一般情況下就是系統存在嚴重的全表掃描，自然意味著很高的物理讀。(上面分析過)

3、youngs/s，如果這個值相對較高，最好增加一個innodb_old_blocks_time，降低innodb_old_blocks_pct，保護熱數據。

總結

本文總結了Innodb中的LRU是如何做的，希望大家有所收穫。

另外，唉，最近有一番新的感慨。

• 代碼寫的好，bug少，看起來像是一個閒人
• 註釋多，代碼清晰，任何人可以接手，看起來就是誰都可以替代
• 代碼寫的爛，每天驚動各大領導提流程改生產代碼，解決生產問題，就是公司亮眼人才
• 代碼寫的爛，只有自己看得懂，就是公司不可替代的重要人才

心累，社會呀～

閱讀更多 java互聯網架構 的文章

關鍵字: 中央處理器 C語言 在讀