當(dāng)Buffer Pool中的緩存頁不夠的時候，如何基于LRU算法淘汰部分緩存？

1、如果Buffer Pool中的緩存頁不夠了怎么辦？

之前我們已經(jīng)給大家講解了Buffer Pool中的緩存頁的劃分，包括free鏈表的使用，然后磁盤上的數(shù)據(jù)頁是如何加載到緩存頁里去的，包括對緩存頁修改之后，flush鏈表是如何用來記載臟數(shù)據(jù)頁的。

今天我們接著來分析Buffer Pool的工作原理，我們來思考一個問題，當(dāng)你要執(zhí)行CRUD操作的時候，無論是查詢數(shù)據(jù)，還是修改數(shù)據(jù)，實際上都會把磁盤上的數(shù)據(jù)頁加載到緩存頁里來，這個大家都是沒有問題的吧？

那么在加載數(shù)據(jù)到緩存頁的時候，必然是要加載到空閑的緩存頁里去的，所以必須要從free鏈表中找一個空閑的緩存頁，然后把磁盤上的數(shù)據(jù)頁加載到那個空閑的緩存頁里去，我們看下圖的紅色箭頭的示意。

? ? ? ? ? ?

? ? ? ? ? ? ?

那么大家通過之前的學(xué)習(xí)肯定都知道了，隨著你不停的把磁盤上的數(shù)據(jù)頁加載到空閑的緩存頁里去，free鏈表中的空閑緩存頁是不是會越來越少？因為只要你把一個數(shù)據(jù)頁加載到一個空閑緩存頁里去，free鏈表中就會減少一個空閑緩存頁。

所以，當(dāng)你不停的把磁盤上的數(shù)據(jù)頁加載到空閑緩存頁里去，free鏈表中不停的移除空閑緩存頁，遲早有那么一瞬間，你會發(fā)現(xiàn)free鏈表中已經(jīng)沒有空閑緩存頁了

這個時候，當(dāng)你還要加載數(shù)據(jù)頁到一個空閑緩存頁的時候，怎么辦呢？如下圖。

? ? ? ? ? ?

? ? ? ? ? ? ?

2、如果要淘汰掉一些緩存數(shù)據(jù)，淘汰誰？

針對上述的問題，大家來思考下一個問題，如果所有的緩存頁都被塞了數(shù)據(jù)了，此時無法從磁盤上加載新的數(shù)據(jù)頁到緩存頁里去了，那么此時你只有一個辦法，就是淘汰掉一些緩存頁。

那什么叫淘汰緩存頁呢？

顧名思義，你必須把一個緩存頁里被修改過的數(shù)據(jù)，給他刷到磁盤上的數(shù)據(jù)頁里去，然后這個緩存頁就可以清空了，讓他重新變成一個空閑的緩存頁。

接著你再把磁盤上你需要的新的數(shù)據(jù)頁加載到這個騰出來的空閑緩存頁中去，如下圖。

? ? ? ? ? ?

? ? ? ? ? ? ?

那么下一個問題來了，如果要把一個緩存頁里的數(shù)據(jù)刷入磁盤，騰出來一個空閑緩存頁，那么應(yīng)該把哪個緩存頁的數(shù)據(jù)給刷入磁盤呢？

3、緩存命中率概念的引入

要解答這個問題，我們就得引入一個緩存命中率的概念。

假設(shè)現(xiàn)在有兩個緩存頁，一個緩存頁的數(shù)據(jù)，經(jīng)常會被修改和查詢，比如在100次請求中，有30次都是在查詢和修改這個緩存頁里的數(shù)據(jù)。那么此時我們可以說這種情況下，緩存命中率很高

為什么呢？因為100次請求中，30次都可以操作緩存，不需要從磁盤加載數(shù)據(jù)，這個緩存命中率就比較高了。

另外一個緩存頁里的數(shù)據(jù)，就是剛從磁盤加載到緩存頁之后，被修改和查詢過1次，之后100次請求中沒有一次是修改和查詢這個緩存頁的數(shù)據(jù)的，那么此時我們就說緩存命中率有點低，因為大部分請求可能還需要走磁盤查詢數(shù)據(jù)，他們要操作的數(shù)據(jù)不在緩存中。

所以針對上述兩個緩存頁，假設(shè)此時讓你做一個抉擇，要把其中緩存頁的數(shù)據(jù)刷入到磁盤去，騰出來一個空閑的緩存頁，此時你會選擇誰？

那還用想么，當(dāng)然是選擇第二個緩存頁刷入磁盤中了！

因為第二個緩存頁，壓根兒就沒什么人來使用他里面的數(shù)據(jù)，結(jié)果這些數(shù)據(jù)還空占據(jù)了一個緩存頁，這不是占著茅坑不拉屎么？

4、引入LRU鏈表來判斷哪些緩存頁是不常用的

接著我們就要解決下一個問題了，就是你怎么知道哪些緩存頁經(jīng)常被訪問，哪些緩存頁很少被訪問？

此時就要引入一個新的LRU鏈表了，這個所謂的LRU就是Least Recently Used，最近最少使用的意思。

通過這個LRU鏈表，我們可以知道哪些緩存頁是最近最少被使用的，那么當(dāng)你緩存頁需要騰出來一個刷入磁盤的時候，不就可以選擇那個LRU鏈表中最近最少被使用的緩存頁了么？

這個LRU鏈表大致是怎么個工作原理呢？

簡單來說，我們看下圖，假設(shè)我們從磁盤加載一個數(shù)據(jù)頁到緩存頁的時候，就把這個緩存頁的描述數(shù)據(jù)塊放到LRU鏈表頭部去，那么只要有數(shù)據(jù)的緩存頁，他都會在LRU里了，而且最近被加載數(shù)據(jù)的緩存頁，都會放到LRU鏈表的頭部去。

? ? ? ? ? ?

? ? ? ? ? ? ?

然后假設(shè)某個緩存頁的描述數(shù)據(jù)塊本來在LRU鏈表的尾部，后續(xù)你只要查詢或者修改了這個緩存頁的數(shù)據(jù)，也要把這個緩存頁挪動到LRU鏈表的頭部去，也就是說最近被訪問過的緩存頁，一定在LRU鏈表的頭部，如下圖。

? ? ? ? ? ?

? ? ? ? ? ? ?

那么這樣的話，當(dāng)你的緩存頁沒有一個空閑的時候，你是不是要找出來那個最近最少被訪問的緩存頁去刷入磁盤？此時你就直接在LRU鏈表的尾部找到一個緩存頁，他一定是最近最少被訪問的那個緩存頁！

然后你就把LRU鏈表尾部的那個緩存頁刷入磁盤中，然后把你需要的磁盤數(shù)據(jù)頁加載到騰出來的空閑緩存頁中就可以了！

5、上次思考題解答

今天我們在末尾解答一下上次留的那個思考題，就是說，我們在SQL語句里都是用到的是表和行的概念，但是之前我們提到的表空間、數(shù)據(jù)頁，他們之間的關(guān)系是什么呢？

其實簡單來講，一個是邏輯概念，一個是物理概念。

表、列和行，都是邏輯概念，我們只知道數(shù)據(jù)庫里有一個表，表里有幾個字段，有多少行，但是這些表里的數(shù)據(jù)，在數(shù)據(jù)庫的磁盤上如何存儲的，你知道嗎？我們是不關(guān)注的，所以他們都是邏輯上的概念。

表空間、數(shù)據(jù)頁，這些東西，都是物理上的概念，實際上在物理層面，你的表里的數(shù)據(jù)都放在一個表空間中，表空間是由一堆磁盤上的數(shù)據(jù)文件組成的，這些數(shù)據(jù)文件里都存放了你表里的數(shù)據(jù)，這些數(shù)據(jù)是由一個一個的數(shù)據(jù)頁組織起來的，這些都是物理層面的概念，這就是他們之間的區(qū)別。

End

專欄版權(quán)歸公眾號儒猿技術(shù)窩所有

未經(jīng)許可不得傳播，如有侵權(quán)將追究法律責(zé)任