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

引言

某日，煙哥前去面試(純屬瞎編)，有瞭如下對話

面試官:”懂mysql吧，知道CPU在讀硬碟上資料的時候，是怎麼解決CPU和硬碟速度不一致問題麼?”
煙哥:”懂啊，mysql先把資料頁載入到記憶體裡，然後讀記憶體中的資料啊！“
面試官:”你們用的是哪個儲存引擎?”
煙哥:”嗯，innodb，因為需要用事務功能！“
面試官:”嗯，好。那既然需要把資料頁載入到記憶體裡，這裡必然涉及到LRU演演算法，當這塊區域滿了後，將一些不常用的資料頁淘汰掉，innodb具體怎麼做的？“
煙哥尷尬的笑了笑，回答道:”我只知道redis中LRU怎麼做的..balabala”
面試官:”停，我只想知道innodb怎麼做的？“
煙哥:”我還是回去等通知吧~”

接下來煙哥回去

於是就有了本文誕生

正文

什麼是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的表邏輯結構如下圖所示

從 InnoDB儲存引擎的邏輯儲存結構看,所有資料都被邏輯地存放在一個空間中,稱之為表空間( tablespace)。表空間又由段(segment)、區( extent)、頁(page)組成。頁在一些檔案中有時也稱為塊( block), 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 statusG
……
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少，看起來像是一個閑人
• 註釋多，程式碼清晰，任何人可以接手，看起來就是誰都可以替代
• 程式碼寫的爛，每天驚動各大領導提流程改生產程式碼，解決生產問題，就是公司亮眼人才
• 程式碼寫的爛，只有自己看得懂，就是公司不可替代的重要人才

心累，社會呀～