面試中的兩個問題：

【資料圖】

操作系統(tǒng)在讀磁盤的時候會額外多讀一些數(shù)據(jù)到內(nèi)存中，最后也沒有用到，如何改善？批量讀取數(shù)據(jù)的時候，可能會熱點(diǎn)數(shù)據(jù)擠出去，如何改善?Linux 和 MySQL 的緩存Linux 操作系統(tǒng)的緩存

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

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

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

MySQL 的緩存

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

有了緩沖池后：

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

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

要實(shí)現(xiàn)這個，最容易想到的就是 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ù)單位都是頁（Page）單位，所以后續(xù)以「頁」名稱代替「數(shù)據(jù)」。

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

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

存在的問題：

如果一條數(shù)據(jù)僅僅是突然被訪問（有可能后續(xù)將不再訪問），在 LRU 算法下，此數(shù)據(jù)將被定義為熱數(shù)據(jù)，最晚被淘汰。但實(shí)際生產(chǎn)環(huán)境下，我們很多時候需要計算的是一段時間下key的訪問頻率，淘汰此時間段內(nèi)的冷數(shù)據(jù)。

預(yù)讀失效，怎么辦？什么是預(yù)讀機(jī)制？

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

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

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

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

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

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

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

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

如果把「預(yù)讀頁」放到了 LRU 鏈表頭部，而當(dāng)內(nèi)存空間不夠的時候，還需要把末尾的頁淘汰掉。而末尾淘汰的頁，可能是熱點(diǎn)數(shù)據(jù)，這樣就大大降低了緩存命中率。

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

我們不能因?yàn)楹ε骂A(yù)讀失效，而將預(yù)讀機(jī)制去掉，大部分情況下，空間局部性原理還是成立的。要避免預(yù)讀失效帶來影響，可以從兩個方面考慮

讓預(yù)讀頁停留在內(nèi)存里的時間要盡可能的短，讓真正被訪問的頁移動到 LRU 鏈表的頭部，從而保證熱數(shù)據(jù)留在內(nèi)存里的時間盡可能長。

那到底怎么才能避免呢？

Linux 操作系統(tǒng)和 MySQL Innodb 通過改進(jìn)傳統(tǒng) LRU 鏈表來避免預(yù)讀失效帶來的影響，具體的改進(jìn)分別如下：

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

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

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

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

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

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

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

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

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

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

young 區(qū)域與 old 區(qū)域在 LRU 鏈表中的占比關(guān)系并不是一比一的關(guān)系，而是 63:37（默認(rèn)比例）的關(guān)系。劃分這兩個區(qū)域后，預(yù)讀的頁就只需要加入到 old 區(qū)域的頭部，當(dāng)頁被真正訪問的時候，才將頁插入 young 區(qū)域的頭部。如果預(yù)讀的頁一直沒有被訪問，就會從 old 區(qū)域移除，這樣就不會影響 young 區(qū)域中的熱點(diǎn)數(shù)據(jù)。

緩存污染，怎么辦？什么是緩存污染？

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

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

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

緩存污染帶來的問題

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

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

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

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

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

Linux 操作系統(tǒng)：在內(nèi)存頁被訪問第二次的時候，才將頁從 inactive list 升級到 active list 里。MySQL Innodb：在內(nèi)存頁被訪問第二次的時候，并不會馬上將該頁從 old 區(qū)域升級到 young 區(qū)域，因?yàn)檫€要進(jìn)行停留在 old 區(qū)域的時間判斷：如果第二次的訪問時間與第一次訪問的時間在 1 秒內(nèi)（默認(rèn)值），那么該頁就不會被從 old 區(qū)域升級到 young 區(qū)域；如果第二次的訪問時間與第一次訪問的時間超過 1 秒，那么該頁就會從 old 區(qū)域升級到 young 區(qū)域；

關(guān)鍵詞：