讓我們一起聊聊如何改進(jìn) LRU 算法

作者：小林coding 2022-08-30 13:48:16

Linux 的 Page Cache 和 MySQL 的 Buffer Pool 的大小是有限的，并不能無(wú)限的緩存數(shù)據(jù)，對(duì)于一些頻繁訪問的數(shù)據(jù)我們希望可以一直留在內(nèi)存中，而一些很少訪問的數(shù)據(jù)希望可以在某些時(shí)機(jī)可以淘汰掉，從而保證內(nèi)存不會(huì)因?yàn)闈M了而導(dǎo)致無(wú)法再緩存新的數(shù)據(jù)，同時(shí)還能保證常用數(shù)據(jù)留在內(nèi)存中。

大家好，我是小林。

上周群里看到有位小伙伴面試時(shí)，被問到這兩個(gè)問題：

咋一看，以為是在問操作系統(tǒng)的問題，其實(shí)這兩個(gè)題目都是在問如何改進(jìn) LRU 算法。

因?yàn)閭鹘y(tǒng)的 LRU 算法存在這兩個(gè)問題：

「預(yù)讀失效」導(dǎo)致緩存命中率下降（對(duì)應(yīng)第一個(gè)問題）
「緩存污染」導(dǎo)致緩存命中率下降（對(duì)應(yīng)第二個(gè)問題）

Redis 的緩存淘汰算法則是通過實(shí)現(xiàn) LFU 算法來避免「緩存污染」而導(dǎo)致緩存命中率下降的問題（Redis 沒有預(yù)讀機(jī)制）。

MySQL 和 Linux 操作系統(tǒng)是通過改進(jìn) LRU 算法來避免「預(yù)讀失效和緩存污染」而導(dǎo)致緩存命中率下降的問題。

這次，就重點(diǎn)講講 MySQL 和 Linux 操作系統(tǒng)是如何改進(jìn) LRU 算法的？

好了，開始發(fā)車，坐穩(wěn)了！

Linux 和 MySQL 的緩存

Linux 操作系統(tǒng)的緩存

在應(yīng)用程序讀取文件的數(shù)據(jù)的時(shí)候，Linux 操作系統(tǒng)是會(huì)對(duì)讀取的文件數(shù)據(jù)進(jìn)行緩存的，會(huì)緩存在文件系統(tǒng)中的 Page Cache（如下圖中的頁(yè)緩存）。

Page Cache 屬于內(nèi)存空間里的數(shù)據(jù)，由于內(nèi)存訪問比磁盤訪問快很多，在下一次訪問相同的數(shù)據(jù)就不需要通過磁盤 I/O 了，命中緩存就直接返回?cái)?shù)據(jù)即可。

因此，Page Cache 起到了加速訪問數(shù)據(jù)的作用。

MySQL 的緩存

MySQL 的數(shù)據(jù)是存儲(chǔ)在磁盤里的，為了提升數(shù)據(jù)庫(kù)的讀寫性能，Innodb 存儲(chǔ)引擎設(shè)計(jì)了一個(gè)緩沖池（Buffer Pool），Buffer Pool 屬于內(nèi)存空間里的數(shù)據(jù)。

有了緩沖池后：

當(dāng)讀取數(shù)據(jù)時(shí)，如果數(shù)據(jù)存在于 Buffer Pool 中，客戶端就會(huì)直接讀取 Buffer Pool 中的數(shù)據(jù)，否則再去磁盤中讀取。
當(dāng)修改數(shù)據(jù)時(shí)，首先是修改 Buffer Pool 中數(shù)據(jù)所在的頁(yè)，然后將其頁(yè)設(shè)置為臟頁(yè)，最后由后臺(tái)線程將臟頁(yè)寫入到磁盤。

傳統(tǒng) LRU 是如何管理內(nèi)存數(shù)據(jù)的？

要實(shí)現(xiàn)這個(gè)，最容易想到的就是 LRU（Least recently used）算法。

LRU 算法一般是用「鏈表」作為數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，鏈表頭部的數(shù)據(jù)是最近使用的，而鏈表末尾的數(shù)據(jù)是最久沒被使用的。那么，當(dāng)空間不夠了，就淘汰最久沒被使用的節(jié)點(diǎn)，也就是鏈表末尾的數(shù)據(jù)，從而騰出內(nèi)存空間。

因?yàn)?Linux 的 Page Cache 和 MySQL 的 Buffer Pool 緩存的基本數(shù)據(jù)單位都是頁(yè)（Page）單位，所以后續(xù)以「頁(yè)」名稱代替「數(shù)據(jù)」。

傳統(tǒng)的 LRU 算法的實(shí)現(xiàn)思路是這樣的：

當(dāng)訪問的頁(yè)在內(nèi)存里，就直接把該頁(yè)對(duì)應(yīng)的 LRU 鏈表節(jié)點(diǎn)移動(dòng)到鏈表的頭部。
當(dāng)訪問的頁(yè)不在內(nèi)存里，除了要把該頁(yè)放入到 LRU 鏈表的頭部，還要淘汰 LRU 鏈表末尾的頁(yè)。

比如下圖，假設(shè) LRU 鏈表長(zhǎng)度為 5，LRU 鏈表從左到右有編號(hào)為 1，2，3，4，5 的頁(yè)。

如果訪問了 3 號(hào)頁(yè)，因?yàn)?3 號(hào)頁(yè)已經(jīng)在內(nèi)存了，所以把 3 號(hào)頁(yè)移動(dòng)到鏈表頭部即可，表示最近被訪問了。

而如果接下來，訪問了 8 號(hào)頁(yè)，因?yàn)?8 號(hào)頁(yè)不在內(nèi)存里，且 LRU 鏈表長(zhǎng)度為 5，所以必須要淘汰數(shù)據(jù)，以騰出內(nèi)存空間來緩存 8 號(hào)頁(yè)，于是就會(huì)淘汰末尾的 5 號(hào)頁(yè)，然后再將 8 號(hào)頁(yè)加入到頭部。

傳統(tǒng)的 LRU 算法并沒有被 Linux 和 MySQL 使用，因?yàn)閭鹘y(tǒng)的 LRU 算法無(wú)法避免下面這兩個(gè)問題：

預(yù)讀失效導(dǎo)致緩存命中率下降；
緩存污染導(dǎo)致緩存命中率下降；

預(yù)讀失效，怎么辦？

什么是預(yù)讀機(jī)制？

Linux 操作系統(tǒng)為基于 Page Cache 的讀緩存機(jī)制提供預(yù)讀機(jī)制，一個(gè)例子是：

應(yīng)用程序只想讀取磁盤上文件 A 的 offset 為 0-3KB 范圍內(nèi)的數(shù)據(jù)，由于磁盤的基本讀寫單位為 block（4KB），于是操作系統(tǒng)至少會(huì)讀 0-4KB 的內(nèi)容，這恰好可以在一個(gè) page 中裝下。
但是操作系統(tǒng)出于空間局部性原理（靠近當(dāng)前被訪問數(shù)據(jù)的數(shù)據(jù)，在未來很大概率會(huì)被訪問到），會(huì)選擇將磁盤塊 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加載到內(nèi)存，于是額外在內(nèi)存中申請(qǐng)了 3 個(gè) page；

下圖代表了操作系統(tǒng)的預(yù)讀機(jī)制：

上圖中，應(yīng)用程序利用 read 系統(tǒng)調(diào)動(dòng)讀取 4KB 數(shù)據(jù)，實(shí)際上內(nèi)核使用預(yù)讀機(jī)制（ReadaHead）機(jī)制完成了 16KB 數(shù)據(jù)的讀取，也就是通過一次磁盤順序讀將多個(gè) Page 數(shù)據(jù)裝入 Page Cache。

這樣下次讀取 4KB 數(shù)據(jù)后面的數(shù)據(jù)的時(shí)候，就不用從磁盤讀取了，直接在 Page Cache 即可命中數(shù)據(jù)。因此，預(yù)讀機(jī)制帶來的好處就是減少了磁盤 I/O 次數(shù)，提高系統(tǒng)磁盤 I/O 吞吐量。

MySQL Innodb 存儲(chǔ)引擎的 Buffer Pool 也有類似的預(yù)讀機(jī)制，MySQL 從磁盤加載頁(yè)時(shí)，會(huì)提前把它相鄰的頁(yè)一并加載進(jìn)來，目的是為了減少磁盤 IO。

預(yù)讀失效會(huì)帶來什么問題？

如果這些被提前加載進(jìn)來的頁(yè)，并沒有被訪問，相當(dāng)于這個(gè)預(yù)讀工作是白做了，這個(gè)就是預(yù)讀失效。

如果使用傳統(tǒng)的 LRU 算法，就會(huì)把「預(yù)讀頁(yè)」放到 LRU 鏈表頭部，而當(dāng)內(nèi)存空間不夠的時(shí)候，還需要把末尾的頁(yè)淘汰掉。

如果這些「預(yù)讀頁(yè)」如果一直不會(huì)被訪問到，就會(huì)出現(xiàn)一個(gè)很奇怪的問題，不會(huì)被訪問的預(yù)讀頁(yè)卻占用了 LRU 鏈表前排的位置，而末尾淘汰的頁(yè)，可能是熱點(diǎn)數(shù)據(jù)，這樣就大大降低了緩存命中率。

如何避免預(yù)讀失效造成的影響？

我們不能因?yàn)楹ε骂A(yù)讀失效，而將預(yù)讀機(jī)制去掉，大部分情況下，空間局部性原理還是成立的。

要避免預(yù)讀失效帶來影響，最好就是讓預(yù)讀頁(yè)停留在內(nèi)存里的時(shí)間要盡可能的短，讓真正被訪問的頁(yè)才移動(dòng)到 LRU 鏈表的頭部，從而保證真正被讀取的熱數(shù)據(jù)留在內(nèi)存里的時(shí)間盡可能長(zhǎng)。

那到底怎么才能避免呢？

Linux 操作系統(tǒng)和 MySQL Innodb 通過改進(jìn)傳統(tǒng) LRU 鏈表來避免預(yù)讀失效帶來的影響，具體的改進(jìn)分別如下：
Linux 操作系統(tǒng)實(shí)現(xiàn)兩個(gè)了 LRU 鏈表：活躍 LRU 鏈表（active_list）和非活躍 LRU 鏈表（inactive_list）；

MySQL 的 Innodb 存儲(chǔ)引擎是在一個(gè) LRU 鏈表上劃分來 2 個(gè)區(qū)域：young 區(qū)域和 old 區(qū)域。

這兩個(gè)改進(jìn)方式，設(shè)計(jì)思想都是類似的，都是將數(shù)據(jù)分為了冷數(shù)據(jù)和熱數(shù)據(jù)，然后分別進(jìn)行 LRU 算法。不再像傳統(tǒng)的 LRU 算法那樣，所有數(shù)據(jù)都只用一個(gè) LRU 算法管理。

接下來，具體聊聊 Linux 和 MySQL 是如何避免預(yù)讀失效帶來的影響？

Linux 是如何避免預(yù)讀失效帶來的影響？

Linux 操作系統(tǒng)實(shí)現(xiàn)兩個(gè)了 LRU 鏈表：活躍 LRU 鏈表（active_list）和非活躍 LRU 鏈表（inactive_list）。

active list活躍內(nèi)存頁(yè)鏈表，這里存放的是最近被訪問過（活躍）的內(nèi)存頁(yè)；
inactive list不活躍內(nèi)存頁(yè)鏈表，這里存放的是很少被訪問（非活躍）的內(nèi)存頁(yè)；

有了這兩個(gè) LRU 鏈表后，預(yù)讀頁(yè)就只需要加入到 inactive list 區(qū)域的頭部，當(dāng)頁(yè)被真正訪問的時(shí)候，才將頁(yè)插入 active list 的頭部。如果預(yù)讀的頁(yè)一直沒有被訪問，就會(huì)從 inactive list 移除，這樣就不會(huì)影響 active list 中的熱點(diǎn)數(shù)據(jù)。

接下來，給大家舉個(gè)例子。

假設(shè) active list 和 inactive list 的長(zhǎng)度為 5，目前內(nèi)存中已經(jīng)有如下 10 個(gè)頁(yè)：

現(xiàn)在有個(gè)編號(hào)為 20 的頁(yè)被預(yù)讀了，這個(gè)頁(yè)只會(huì)被插入到 inactive list 的頭部，而 inactive list 末尾的頁(yè)（10號(hào)）會(huì)被淘汰掉。

即使編號(hào)為 20 的預(yù)讀頁(yè)一直不會(huì)被訪問，它也沒有占用到 active list 的位置，而且還會(huì)比 active list 中的頁(yè)更早被淘汰出去。

如果 20 號(hào)頁(yè)被預(yù)讀后，立刻被訪問了，那么就會(huì)將它插入到 active list 的頭部， active list 末尾的頁(yè)（5號(hào)），會(huì)被降級(jí)到 inactive list ，作為 inactive list 的頭部，這個(gè)過程并不會(huì)有數(shù)據(jù)被淘汰。

MySQL 是如何避免預(yù)讀失效帶來的影響？

MySQL 的 Innodb 存儲(chǔ)引擎是在一個(gè) LRU 鏈表上劃分來 2 個(gè)區(qū)域，young 區(qū)域和 old 區(qū)域。

young 區(qū)域在 LRU 鏈表的前半部分，old 區(qū)域則是在后半部分，這兩個(gè)區(qū)域都有各自的頭和尾節(jié)點(diǎn)，如下圖：

young 區(qū)域與 old 區(qū)域在 LRU 鏈表中的占比關(guān)系并不是一比一的關(guān)系，而是是 7 比 3 （默認(rèn)比例）的關(guān)系。

劃分這兩個(gè)區(qū)域后，預(yù)讀的頁(yè)就只需要加入到 old 區(qū)域的頭部，當(dāng)頁(yè)被真正訪問的時(shí)候，才將頁(yè)插入 young 區(qū)域的頭部。如果預(yù)讀的頁(yè)一直沒有被訪問，就會(huì)從 old 區(qū)域移除，這樣就不會(huì)影響 young 區(qū)域中的熱點(diǎn)數(shù)據(jù)。

接下來，給大家舉個(gè)例子。

假設(shè)有一個(gè)長(zhǎng)度為 10 的 LRU 鏈表，其中 young 區(qū)域占比 70 %，old 區(qū)域占比 30 %。

現(xiàn)在有個(gè)編號(hào)為 20 的頁(yè)被預(yù)讀了，這個(gè)頁(yè)只會(huì)被插入到 old 區(qū)域頭部，而 old 區(qū)域末尾的頁(yè)（10號(hào)）會(huì)被淘汰掉。

如果 20 號(hào)頁(yè)一直不會(huì)被訪問，它也沒有占用到 young 區(qū)域的位置，而且還會(huì)比 young 區(qū)域的數(shù)據(jù)更早被淘汰出去。

如果 20 號(hào)頁(yè)被預(yù)讀后，立刻被訪問了，那么就會(huì)將它插入到 young 區(qū)域的頭部，young 區(qū)域末尾的頁(yè)（7號(hào)），會(huì)被擠到 old 區(qū)域，作為 old 區(qū)域的頭部，這個(gè)過程并不會(huì)有頁(yè)被淘汰。

緩存污染，怎么辦？

什么是緩存污染？

雖然 Linux （實(shí)現(xiàn)兩個(gè) LRU 鏈表）和 MySQL （劃分兩個(gè)區(qū)域）通過改進(jìn)傳統(tǒng)的 LRU 數(shù)據(jù)結(jié)構(gòu)，避免了預(yù)讀失效帶來的影響。

但是如果還是使用「只要數(shù)據(jù)被訪問一次，就將數(shù)據(jù)加入到活躍 LRU 鏈表頭部（或者 young 區(qū)域）」這種方式的話，那么還存在緩存污染的問題。

當(dāng)我們?cè)谂孔x取數(shù)據(jù)的時(shí)候，由于數(shù)據(jù)被訪問了一次，這些大量數(shù)據(jù)都會(huì)被加入到「活躍 LRU 鏈表」里，然后之前緩存在活躍 LRU 鏈表（或者 young 區(qū)域）里的熱點(diǎn)數(shù)據(jù)全部都被淘汰了，如果這些大量的數(shù)據(jù)在很長(zhǎng)一段時(shí)間都不會(huì)被訪問的話，那么整個(gè)活躍 LRU 鏈表（或者 young 區(qū)域）就被污染了。

緩存污染會(huì)帶來什么問題？

緩存污染帶來的影響就是很致命的，等這些熱數(shù)據(jù)又被再次訪問的時(shí)候，由于緩存未命中，就會(huì)產(chǎn)生大量的磁盤 I/O，系統(tǒng)性能就會(huì)急劇下降。

我以 MySQL 舉例子，Linux 發(fā)生緩存污染的現(xiàn)象也是類似。

當(dāng)某一個(gè) SQL 語(yǔ)句掃描了大量的數(shù)據(jù)時(shí)，在 Buffer Pool 空間比較有限的情況下，可能會(huì)將 Buffer Pool 里的所有頁(yè)都替換出去，導(dǎo)致大量熱數(shù)據(jù)被淘汰了，等這些熱數(shù)據(jù)又被再次訪問的時(shí)候，由于緩存未命中，就會(huì)產(chǎn)生大量的磁盤 I/O，MySQL 性能就會(huì)急劇下降。

注意，緩存污染并不只是查詢語(yǔ)句查詢出了大量的數(shù)據(jù)才出現(xiàn)的問題，即使查詢出來的結(jié)果集很小，也會(huì)造成緩存污染。

比如，在一個(gè)數(shù)據(jù)量非常大的表，執(zhí)行了這條語(yǔ)句：

select * from t_user where name like "%xiaolin%";

可能這個(gè)查詢出來的結(jié)果就幾條記錄，但是由于這條語(yǔ)句會(huì)發(fā)生索引失效，所以這個(gè)查詢過程是全表掃描的，接著會(huì)發(fā)生如下的過程：

從磁盤讀到的頁(yè)加入到 LRU 鏈表的 old 區(qū)域頭部；
當(dāng)從頁(yè)里讀取行記錄時(shí)，也就是頁(yè)被訪問的時(shí)候，就要將該頁(yè)放到 young 區(qū)域頭部；
接下來拿行記錄的 name 字段和字符串 xiaolin 進(jìn)行模糊匹配，如果符合條件，就加入到結(jié)果集里；
如此往復(fù)，直到掃描完表中的所有記錄。

經(jīng)過這一番折騰，由于這條 SQL 語(yǔ)句訪問的頁(yè)非常多，每訪問一個(gè)頁(yè)，都會(huì)將其加入 young 區(qū)域頭部，那么原本 young 區(qū)域的熱點(diǎn)數(shù)據(jù)都會(huì)被替換掉，導(dǎo)致緩存命中率下降。那些在批量掃描時(shí)，而被加入到 young 區(qū)域的頁(yè)，如果在很長(zhǎng)一段時(shí)間都不會(huì)再被訪問的話，那么就污染了 young 區(qū)域。

舉個(gè)例子，假設(shè)需要批量掃描：21，22，23，24，25 這五個(gè)頁(yè)，這些頁(yè)都會(huì)被逐一訪問（讀取頁(yè)里的記錄）。

在批量訪問這些頁(yè)的時(shí)候，會(huì)被逐一插入到 young 區(qū)域頭部。

可以看到，原本在 young 區(qū)域的 6 和 7 號(hào)頁(yè)都被淘汰了，而批量掃描的頁(yè)基本占滿了 young 區(qū)域，如果這些頁(yè)在很長(zhǎng)一段時(shí)間都不會(huì)被訪問，那么就對(duì) young 區(qū)域造成了污染。

如果 6 和 7 號(hào)頁(yè)是熱點(diǎn)數(shù)據(jù)，那么在被淘汰后，后續(xù)有 SQL 再次讀取 6 和 7 號(hào)頁(yè)時(shí)，由于緩存未命中，就要從磁盤中讀取了，降低了 MySQL 的性能，這就是緩存污染帶來的影響。

怎么避免緩存污染造成的影響？

前面的 LRU 算法只要數(shù)據(jù)被訪問一次，就將數(shù)據(jù)加入活躍 LRU 鏈表（或者 young 區(qū)域），這種 LRU 算法進(jìn)入活躍 LRU 鏈表的門檻太低了！正式因?yàn)殚T檻太低，才導(dǎo)致在發(fā)生緩存污染的時(shí)候，很容就將原本在活躍 LRU 鏈表里的熱點(diǎn)數(shù)據(jù)淘汰了。

所以，只要我們提高進(jìn)入到活躍 LRU 鏈表（或者 young 區(qū)域）的門檻，就能有效地保證活躍 LRU 鏈表（或者 young 區(qū)域）里的熱點(diǎn)數(shù)據(jù)不會(huì)被輕易替換掉。

Linux 操作系統(tǒng)和 MySQL Innodb 存儲(chǔ)引擎分別是這樣提高門檻的：

Linux 操作系統(tǒng)：在內(nèi)存頁(yè)被訪問第二次的時(shí)候，才將頁(yè)從 inactive list 升級(jí)到 active list 里。
MySQL Innodb：在內(nèi)存頁(yè)被訪問第二次的時(shí)候，并不會(huì)馬上將該頁(yè)從 old 區(qū)域升級(jí)到 young 區(qū)域，因?yàn)檫€要進(jìn)行停留在 old 區(qū)域的時(shí)間判斷：

如果第二次的訪問時(shí)間與第一次訪問的時(shí)間在 1 秒內(nèi)（默認(rèn)值），那么該頁(yè)就不會(huì)被從 old 區(qū)域升級(jí)到 young 區(qū)域；

如果第二次的訪問時(shí)間與第一次訪問的時(shí)間超過 1 秒，那么該頁(yè)就會(huì)從 old 區(qū)域升級(jí)到 young 區(qū)域；

提高了進(jìn)入活躍 LRU 鏈表（或者 young 區(qū)域）的門檻后，就很好了避免緩存污染帶來的影響。

在批量讀取數(shù)據(jù)時(shí)候，如果這些大量數(shù)據(jù)只會(huì)被訪問一次，那么它們就不會(huì)進(jìn)入到活躍 LRU 鏈表（或者 young 區(qū)域），也就不會(huì)把熱點(diǎn)數(shù)據(jù)淘汰，只會(huì)待在非活躍 LRU 鏈表（或者 old 區(qū)域）中，后續(xù)很快也會(huì)被淘汰。

總結(jié)

傳統(tǒng)的 LRU 算法法無(wú)法避免下面這兩個(gè)問題：

預(yù)讀失效導(dǎo)致緩存命中率下降；
緩存污染導(dǎo)致緩存命中率下降；

為了避免「預(yù)讀失效」造成的影響，Linux 和 MySQL 對(duì)傳統(tǒng)的 LRU 鏈表做了改進(jìn)：

Linux 操作系統(tǒng)實(shí)現(xiàn)兩個(gè)了 LRU 鏈表：活躍 LRU 鏈表（active list）和非活躍 LRU 鏈表（inactive list）。
MySQL Innodb 存儲(chǔ)引擎是在一個(gè) LRU 鏈表上劃分來 2 個(gè)區(qū)域：young 區(qū)域和 old 區(qū)域。

為了避免「緩存污染」造成的影響，Linux 操作系統(tǒng)和 MySQL Innodb 存儲(chǔ)引擎分別提高了升級(jí)為熱點(diǎn)數(shù)據(jù)的門檻：

Linux 操作系統(tǒng)：在內(nèi)存頁(yè)被訪問第二次的時(shí)候，才將頁(yè)從 inactive list 升級(jí)到 active list 里。
MySQL Innodb：在內(nèi)存頁(yè)被訪問第二次的時(shí)候，并不會(huì)馬上將該頁(yè)從 old 區(qū)域升級(jí)到 young 區(qū)域，因?yàn)檫€要進(jìn)行停留在 old 區(qū)域的時(shí)間判斷：

如果第二次的訪問時(shí)間與第一次訪問的時(shí)間超過 1 秒，那么該頁(yè)就會(huì)從 old 區(qū)域升級(jí)到 young 區(qū)域；

通過提高了進(jìn)入 active list （或者 young 區(qū)域）的門檻后，就很好了避免緩存污染帶來的影響。

責(zé)任編輯：武曉燕來源：小林coding