歡迎光臨
每天分享高質量文章

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

來自:孤獨煙(微信號:zrj_guduyan)

引言

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

面試官:”懂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 0not 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少,看起來像是一個閑人
  • 註釋多,代碼清晰,任何人可以接手,看起來就是誰都可以替代
  • 代碼寫的爛,每天驚動各大領導提流程改生產代碼,解決生產問題,就是公司亮眼人才
  • 代碼寫的爛,只有自己看得懂,就是公司不可替代的重要人才

心累,社會呀~

    已同步到看一看
    赞(0)

    分享創造快樂