面試中的兩個(gè)問題：

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

Linux 和 MySQL 的緩存

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

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

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

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

MySQL 的緩存

MySQL 的數(shù)據(jù)是存儲在磁盤里的，為了提升數(shù)據(jù)庫的讀寫性能，Innodb 存儲引擎設(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ù)所在的頁，然后將其頁設(shè)置為臟頁，最后由后臺線程將臟頁寫入到磁盤。

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

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

要實(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ù)單位都是頁（Page）單位，所以后續(xù)以「頁」名稱代替「數(shù)據(jù)」。

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

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

存在的問題：

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

預(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)存中申請了 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 存儲引擎的 Buffer Pool 也有類似的預(yù)讀機(jī)制，MySQL 從磁盤加載頁時(shí)，會(huì)提前把它相鄰的頁一并加載進(jìn)來，目的是為了減少磁盤 IO。

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

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

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

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

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

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

那到底怎么才能避免呢？

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 存儲引擎是在一個(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)存頁鏈表，這里存放的是最近被訪問過（活躍）的內(nèi)存頁；
• inactive list 不活躍內(nèi)存頁鏈表，這里存放的是很少被訪問（非活躍）的內(nèi)存頁；

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

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

MySQL 的 Innodb 存儲引擎是在一個(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)系，而是 63:37（默認(rèn)比例）的關(guān)系。劃分這兩個(gè)區(qū)域后，預(yù)讀的頁就只需要加入到 old 區(qū)域的頭部，當(dāng)頁被真正訪問的時(shí)候，才將頁插入 young 區(qū)域的頭部。如果預(yù)讀的頁一直沒有被訪問，就會(huì)從 old 區(qū)域移除，這樣就不會(huì)影響 young 區(qū)域中的熱點(diǎn)數(shù)據(jù)。

緩存污染，怎么辦？

什么是緩存污染？

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

緩存污染帶來的問題

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

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

前面的 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 存儲引擎分別是這樣提高門檻的：

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

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