1.前言 緩衝池是資料庫最終的概念，資料庫可以將一部分數據頁放在記憶體中形成緩衝池，當需要一個數據頁時，首先檢查記憶體中的緩衝池是否有這個頁面，如果有則直接命中返回，沒有則從磁碟中讀取這一頁，然後緩存到記憶體並返回。 但是記憶體的價值較高，一般來說伺服器的記憶體總是小於磁碟大小的，而且記憶體不能完全分配給資料庫 ...
1.前言
緩衝池是資料庫最終的概念，資料庫可以將一部分數據頁放在記憶體中形成緩衝池，當需要一個數據頁時，首先檢查記憶體中的緩衝池是否有這個頁面，如果有則直接命中返回，沒有則從磁碟中讀取這一頁，然後緩存到記憶體並返回。
但是記憶體的價值較高，一般來說伺服器的記憶體總是小於磁碟大小的，而且記憶體不能完全分配給資料庫作為緩衝池。這就意味著資料庫基本上無法將所有的數據都緩衝到記憶體中。
當緩衝池滿後，如果還有新的頁面要被緩衝到池中，就要設計一種頁面置換的演算法，將一個舊的頁面替換成新的頁面。
一般來說我們熟悉的演算法有下麵幾種：
下麵逐一介紹各種演算法。
2. 最佳置換演算法
如果被替換掉的頁是以後再也不會使用的，那麼這種演算法無疑是最優秀的。因為不管什麼演算法，替換掉的頁也有可能再次被緩存，替換掉其它的頁。
但是這種演算法是無法實現的，我們不可能知道哪個頁面以後也在不會被使用。
或者我們退一步，將這個演算法改成被替換掉的頁是以後很長一段時間都不會再次被使用的，那麼這種演算法無疑也是最優秀的。
但是還是會面對一個無法實現的問題，我們還是不知道哪些頁面會在未來多長一段時間內不會被再次訪問。頁面無法確認，時間也無法確定。
雖然這種演算法無法被實現，但是可以作為一種度量，如果有一種演算法其效率最接近OPT，那麼這種演算法無疑是優秀的演算法。
3. 先進先出演算法
先進先出演算法是一種很簡單的演算法，其基本思想是形成一個隊列，最先入隊的頁面最先被逐出。我們用示意圖來模擬一下FIFO演算法：
我們的記憶體假設只能保存4個頁面，此時的訪問請求按照時間順序是1->2->3->4->5，那麼按照時間順序，當訪問到4號頁面時隊列正好填滿，當要訪問5號頁面時，會將最先入隊的1號頁面逐出。
這種演算法實現起來很簡單，但是從實現上來看，性能和OPT演算法差距最大。因為被替換出去的頁面很有可能是最常使用的頁面，因此這個演算法很少見出現在資料庫緩衝池管理中的。
FIFO演算法會出現一個叫做Belay異常的現象，就這個現象我們解釋如下。
我們首先定義一個4個頁面長度的隊列作為緩衝池，然後按照下麵的順序訪問：1->2->3->4->5->3->9->1->4->2->7->4->7。那麼我們按照剛纔描述的FIFO來看看訪問的過程：
| 訪問順序 | 訪問頁 | 記憶體隊列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1,2 | 否 |
| 3 | 3 | 1,2,3 | 否 |
| 4 | 4 | 1,2,3,4 | 否 |
| 5 | 5 | 2,3,4,5 | 否 |
| 6 | 3 | 2,3,4,5 | 是 |
| 7 | 9 | 3,4,5,9 | 否 |
| 8 | 1 | 4,5,9,1 | 否 |
| 9 | 4 | 4,5,9,1 | 是 |
| 10 | 2 | 5,9,1,2 | 否 |
| 11 | 7 | 9,1,2,7 | 是 |
| 12 | 4 | 1,2,7,4 | 否 |
| 13 | 7 | 1,2,7,4 | 是 |
從這個表格上看到，非命中次數有9次，那麼我們將這個隊列的容量增加到5，然後再次重覆這個訪問序列，看看效果：
| 訪問順序 | 訪問頁 | 記憶體隊列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1,2 | 否 |
| 3 | 3 | 1,2,3 | 否 |
| 4 | 4 | 1,2,3,4 | 否 |
| 5 | 5 | 1,2,3,4,5 | 否 |
| 6 | 3 | 1,2,3,4,5 | 是 |
| 7 | 9 | 2,3,4,5,9 | 否 |
| 8 | 1 | 3,4,5,9,1 | 是 |
| 9 | 4 | 3,4,5,9,1 | 是 |
| 10 | 2 | 4,5,9,1,2 | 否 |
| 11 | 7 | 5,9,1,2,7 | 否 |
| 12 | 4 | 9,1,2,7,4 | 否 |
| 13 | 7 | 9,1,2,7,4 | 否 |
這樣的話，非命中的次數是10次，奇怪的是增加了緩衝池的容量，非命中緩衝的數量還增加了，這種現象就叫做Belay異常。
這種演算法不應該被考慮。
4. 最近最少使用演算法
LRU演算法的思想也很簡單，實現一個鏈表（雙向鏈表），每次要緩衝新的頁面時，遍歷鏈表，選擇最近最少使用的頁面進行逐出操作。
這種演算法要求每個頁面上記錄一個上次使用時間t，程式決定逐出時，以這個時間t為準，t距離當前時間最大的，就是要被逐出的頁面。
下圖中按照1->5->2->2->6->5->4的順序訪問，記憶體和訪問示意圖如下：
其中最接近頂端的頁面我們認為其t最小，最接近底部，我們認為其t最大。
訪問6號頁面的時候，記憶體被填滿，下一次訪問5號頁面的時候，會將5號頁面提升到頂部，也就是t最小，之後訪問4號頁面，因為原先記憶體中沒有4號頁面，因此會選擇逐出一個頁面。此時1號頁面在底部，其t最大，因此被逐出。
那麼LRU演算法是否解決了Belay異常呢？
還是按照上一節的實驗順序，測試容量為4和5的記憶體，左側到右側，t逐漸增大：
| 訪問順序 | 訪問頁 | 記憶體隊列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1，2 | 否 |
| 3 | 3 | 1，2，3 | 否 |
| 4 | 4 | 1，2，3，4 | 否 |
| 5 | 5 | 2，3，4，5 | 否 |
| 6 | 3 | 2，4，5，3 | 是 |
| 7 | 9 | 4，5，3，9 | 否 |
| 8 | 1 | 5，3，9，1 | 否 |
| 9 | 4 | 3，9，1，4 | 否 |
| 10 | 2 | 9，1，4，2 | 否 |
| 11 | 7 | 1，4，2，7 | 否 |
| 12 | 4 | 1，2，7，4 | 是 |
| 13 | 7 | 1，2，4，7 | 是 |
一共有10次未命中。增加容量到5，看一下新的情況：
| 訪問順序 | 訪問頁 | 記憶體隊列 | 是否命中 |
|---|---|---|---|
| 1 | 1 | 1 | 否 |
| 2 | 2 | 1，2 | 否 |
| 3 | 3 | 1，2，3 | 否 |
| 4 | 4 | 1，2，3，4 | 否 |
| 5 | 5 | 1，2，3，4，5 | 否 |
| 6 | 3 | 1，2，4，5，3 | 是 |
| 7 | 9 | 2，4，5，3，9 | 否 |
| 8 | 1 | 4，5，3，9，1 | 否 |
| 9 | 4 | 5，3，9，1，4 | 是 |
| 10 | 2 | 3，9，1，4，2 | 否 |
| 11 | 7 | 9，1，4，2，7 | 否 |
| 12 | 4 | 9，1，2，7，4 | 是 |
| 13 | 7 | 9，1，2，4，7 | 是 |
未命中的次數已經變成了9次，減少了一次，如果我設計的隊列中有大量的重覆，那麼這個改進應該更加明顯。
LRU演算法在InnoDB的實現中是被改進的，每次新添加進去的頁面會被放在隊列的3/8處。
無論如何，LRU演算法都被認為是最接近OPT的演算法。
5. 時鐘置換演算法
時鐘置換演算法可以認為是一種最近未使用演算法，即逐出的頁面都是最近沒有使用的那個。我們給每一個頁面設置一個標記位u，u=1表示最近有使用u=0則表示該頁面最近沒有被使用，應該被逐出。
按照1-2-3-4的順序訪問頁面，則緩衝池會以這樣的一種順序被填滿：
註意中間的指針，就像是時鐘的指針一樣在移動，這樣的訪問結束後，緩衝池裡現在已經被填滿了，此時如果要按照1-5的順序訪問，那麼在訪問1的時候是可以直接命中緩存返回的，但是訪問5的時候，因為緩衝池已經滿了，所以要進行一次逐出操作，其操作示意圖如下：
最初要經過一輪遍歷，每次遍歷到一個節點發現u=1的，將該標記位置為0，然後遍歷下一個頁面，一輪遍歷完後，發現沒有可以被逐出的頁面，則進行下一輪遍歷，這次遍歷之後發現原先1號頁面的標記位u=0，則將該頁面逐出，置換為頁面5，並將指針指向下一個頁面。
假設我們接下來會訪問2號頁面，那麼可以直接命中指針指向的頁面，並將這個頁面的標記為u置為1。
但是考慮一個問題，資料庫里逐出的頁面是要寫回磁碟的，這是一個很昂貴的操作，因此我們應該優先考慮逐出那些沒有被修改的頁面，這樣可以降低IO。
因此在時鐘置換演算法的基礎上可以做一個改進，就是增加一個標記為m，修改過標記為1，沒有修改過則標記為0。那麼u和m組成了一個元組，有四種可能，其被逐出的優先順序也不一樣：
- (u=0, m=0) 沒有使用也沒有修改，被逐出的優先順序最高；
- (u=1, m=0) 使用過，但是沒有修改過，優先順序第二；
- (u=0, m=1) 沒有使用過，但是修改過，優先順序第三；
- (u=1, m=1) 使用過也修改過，優先順序第四。
