一、簡述傳統(tǒng)的LRU鏈表

LRU：Least Recently Used

相信大家對LRU鏈表是不陌生的，它算是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)吧，而且想必面試時也被問到過什么是LRU鏈表，甚至是讓你手寫一個LRU鏈表。

如果你讀了上一篇：你有沒有搞混查詢緩存和BufferPool？談?wù)効矗?/p>

想必你已經(jīng)知道了MySQL的Buffer Pool機制以及MySQL組織數(shù)據(jù)的最小單位是數(shù)據(jù)頁。并且你也知道了 數(shù)據(jù)頁在Buffer Pool中是以LRU鏈表的數(shù)據(jù)結(jié)構(gòu)組織在一起的。

其實所謂的LRU鏈表本質(zhì)上就是一個雙向循環(huán)鏈表，如下圖：

下面我們結(jié)合LRU鏈表和數(shù)據(jù)頁機制描述一下MySQL加載數(shù)據(jù)的機制：

我們將從磁盤中讀取的數(shù)據(jù)頁稱為young page，young page會被直接放在鏈表的頭部。已經(jīng)存在于LRU鏈表中數(shù)據(jù)頁如果被使用到了，那么該數(shù)據(jù)頁也被認為是young page而被移動到鏈表頭部。這樣鏈表尾部的數(shù)據(jù)就是最近最少使用的數(shù)據(jù)了，當Buffer Pool容量不足，或者后臺線程主動刷新數(shù)據(jù)頁時，就會優(yōu)先刷新鏈表尾部的數(shù)據(jù)頁。

二、傳統(tǒng)LRU鏈表的不足

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

spatial locality（空間局部性）：也就是說讀取一個數(shù)據(jù)，在它周圍內(nèi)存地址存儲的數(shù)據(jù)也很有可能被讀取到，于是操作系統(tǒng)會幫你預(yù)讀一部分數(shù)據(jù)。

MySQL也是存在存在預(yù)讀機制的！

當Buffer Pool中存儲著一個區(qū)中13個連續(xù)的數(shù)據(jù)頁時，你再去這個區(qū)里面讀取，MySQL就會將這個區(qū)里面所有的數(shù)據(jù)頁都加載進Buffer Pool中的LRU鏈表中。（然后可能你根本不會使用這些被預(yù)讀的數(shù)據(jù)頁） 當你順序的訪問了一個區(qū)中大于 innndb_read_ahead_threshold=56個數(shù)據(jù)頁時，MySQL會自動幫你將下一個相鄰區(qū)中的數(shù)據(jù)頁讀入LRU鏈表中。（這個機制默認是被關(guān)閉的） 當你執(zhí)行select * from xxx;時，如果表中的數(shù)據(jù)頁非常多，那這些數(shù)據(jù)頁就會一一將Buffer Pool中的經(jīng)常使用的緩存頁擠下去，可能留在LRU鏈表中的全部是你不經(jīng)常使用的數(shù)據(jù)。

綜上你可以看到，所謂的預(yù)讀機制的優(yōu)勢，實際上違背了LRU去實現(xiàn)將最近最少使用的數(shù)據(jù)頁刷入磁盤的設(shè)計初衷。

三、MySQL的LRU鏈表

接下來我們看下MySQL的Buffer Pool是如何定制LRU鏈表的，已經(jīng)LRU幫InnoDB解決了什么問題。

當業(yè)務(wù)進行大量的CRUD時，需要不斷的將數(shù)據(jù)頁讀取到buffer pool中的LRU鏈表中。

MySQL的LRU鏈表長下面這樣。

LRU鏈表被MidPoint分成了New Sublist和Old Sublist兩部分。

其中New Sublist大概占比5/8，Old Sublist占比3/8。

New Sublist存儲著young page，而Old Sublist存儲著Old Page。

我們可以通過如下的方式查看MidPoint的默認值。

用戶可以根據(jù)自己的業(yè)務(wù)動態(tài)的調(diào)整這個參數(shù)！

這其實是一種冷熱數(shù)據(jù)分離設(shè)計思想。他相對于傳統(tǒng)的LRU鏈表有很大的優(yōu)勢

四、MySQL定制LRU鏈表的優(yōu)勢而對于MySQLLRU鏈表來說，通過MidPoint將鏈表分成兩部分。

從磁盤中新讀出的數(shù)據(jù)會放在Old Sublist的頭部。這樣即使你真的使用select * from t;也不會導(dǎo)致New Sublist中的經(jīng)常被訪問的數(shù)據(jù)頁被刷入磁盤中。

正常情況下，訪問Old Sublist中的緩存頁，那么該緩存頁會被提升到New Sublist中成為熱數(shù)據(jù)。

但是當你通過 select * from t 將一大批數(shù)據(jù)加載到Old Sublist時，然后在不到1s內(nèi)你又訪問了它，那在這段時間內(nèi)被訪問的緩存頁并不會被提升為熱數(shù)據(jù)。 這個1s由參數(shù)innodb_old_blocks_time控制。

另外：New SubList也是經(jīng)過優(yōu)化的，如果你訪問的是New SubList的前1/4的數(shù)據(jù)，他是不會被移動到LRU鏈表頭部去的。

以上就是淺析MySQL的lru鏈表的詳細內(nèi)容，更多關(guān)于MySQL lru鏈表的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！