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) 使用過也修改過，優先級第四，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/81211.html
標籤：MySQL