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

LRU：Least Recently Used

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

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

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

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

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

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

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

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

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

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

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

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

三、MySQL的LRU鏈表

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

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

MySQL的LRU鏈表長(zhǎng)下面這樣。

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

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

New Sublist存儲(chǔ)著young page，而Old Sublist存儲(chǔ)著Old Page。

我們可以通過(guò)如下的方式查看MidPoint的默認(rèn)值。

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

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

四、MySQL定制LRU鏈表的優(yōu)勢(shì)
而對(duì)于MySQLLRU鏈表來(lái)說(shuō)，通過(guò)MidPoint將鏈表分成兩部分。

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

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

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

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

以上就是淺析MySQL的lru鏈表的詳細(xì)內(nèi)容，更多關(guān)于MySQL lru鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！