面試中的兩個問題：

操作系統(tǒng)在讀磁盤的時候會額外多讀一些數(shù)據(jù)到內存中，最后也沒有用到，如何改善？

批量讀取數(shù)據(jù)的時候，可能會熱點數(shù)據(jù)擠出去，如何改善?

Linux 和 MySQL 的緩存

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

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

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

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

MySQL 的緩存

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

有了緩沖池后：

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

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

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

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

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

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

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

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

存在的問題：

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

預讀失效，怎么辦？

什么是預讀機制？

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

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

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

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

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

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

預讀失效會帶來什么問題？

如果這些被提前加載進來的頁，并沒有被訪問，相當于這個預讀工作是白做了，這個就是預讀失效。

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

如何避免預讀失效造成的影響？

我們不能因為害怕預讀失效，而將預讀機制去掉，大部分情況下，空間局部性原理還是成立的。要避免預讀失效帶來影響，可以從兩個方面考慮

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

那到底怎么才能避免呢？

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

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

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

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

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

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

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

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

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

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

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

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

緩存污染，怎么辦？

什么是緩存污染？

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

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

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

緩存污染帶來的問題

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

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

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

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

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

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

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