記憶體淘汰策略|頁面置換演算法對比總結

在學習【操作系統】【MySQL】【Redis】後，發現其都有一些緩存淘汰的策略，因此一篇小文章總結一下。目前還沒著筆，初略一想MySQL和操作系統應該都是使用的年輕代和老生代的改進策略，而Redis使用的是隨機抽的策略。 MySQL MySQL中存在一個記憶體緩存池，Buffer Pool。裡面存 ...

在學習【操作系統】【MySQL】【Redis】後，發現其都有一些緩存淘汰的策略，因此一篇小文章總結一下。

目前還沒著筆，初略一想MySQL和操作系統應該都是使用的年輕代和老生代的改進策略，而Redis使用的是隨機抽的策略。

MySQL

MySQL中存在一個記憶體緩存池，Buffer Pool。裡面存在著控制塊和緩存的數據頁（當然還有些其他緩存，比如：鎖信息、undo頁等）。

下麵的LRU限制在緩存的數據頁當中（控制塊等應該也是不會淘汰的）

有了緩存池之後

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

即MySQL會直接操作緩存池中的數據，然後再刷新到磁碟中。
在Buffer Pool中MySQL還會維護三個鏈表，分別為：LRU鏈表，dirty page 鏈表與free page鏈表。三個鏈表存在分別的意義為：

LRU鏈表：記憶體是有限的，不能無限讀入數據，此LRU鏈表key方便決定要淘汰哪些頁面。---也正是本文的核心，記憶體淘汰策略。
dirty page 鏈表：為了方便確認哪些數據頁是臟頁，要刷新入磁碟。
free page鏈表：為了方便確認哪些頁還沒有讀入數據。

Pasted image 20230404203815.png

由三個鏈表的功能可以知道，最開始free list是滿的（數據還沒有讀入），隨後會越來越少。

Buffer Pool 的大小是有限的，對於一些頻繁訪問的數據我們希望可以一直留在 Buffer Pool 中，而一些很少訪問的數據希望可以在某些時機可以淘汰掉，從而保證 Buffer Pool 不會因為滿了而導致無法再緩存新的數據，同時還能保證常用數據留在 Buffer Pool 中。
要實現這個，最容易想到的就是 LRU（Least recently used）演算法。
該演算法的思路是，鏈表頭部的節點是最近使用的，而鏈表末尾的節點是最久沒被使用的。那麼，當空間不夠了，就淘汰最久沒被使用的節點，從而騰出空間。
簡單的 LRU 演算法的實現思路是這樣的：

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

簡單的LRU演算法會有兩個問題：預讀失效和緩存污染。

MySQL解決這兩個問題的基本思路：

解決預讀失效：將緩存區分為新生代和老生代。預讀的數據讀入老生代（優先淘汰），如果真正使用了才會加入新生代。

解決緩存污染：由於預讀的數據只要使用了就加入新生代，即使用一次就加入新生代，後面就算不用了新生代也全部被這些只用了一次的數據污染了。因此解決方案就是提高進入新生代的代價。

具體來說，為瞭解決緩存污染：MySQL 是這樣做的，進入到 young 區域條件增加了一個停留在 **old** 區域的時間判斷。
具體是這樣做的，在對某個處在 old 區域的緩存頁進行第一次訪問時，就在它對應的控制塊中記錄下來這個訪問時間：

如果後續的訪問時間與第一次訪問的時間在某個時間間隔內，那麼該緩存頁就不會被從 old 區域移動到 young 區域的頭部；
如果後續的訪問時間與第一次訪問的時間不在某個時間間隔內，那麼該緩存頁移動到 young 區域的頭部；

這個間隔時間是由 innodb_old_blocks_time 控制的，預設是 1000 ms。
也就說，只有同時滿足「被訪問」與「在 old 區域停留時間超過 1 秒」兩個條件，才會被插入到 young 區域頭部，這樣就解決了 Buffer Pool 污染的問題。
另外，MySQL 針對 young 區域其實做了一個優化，為了防止 young 區域節點頻繁移動到頭部。young 區域前面 1/4 被訪問不會移動到鏈表頭部，只有後面的 3/4被訪問了才會。

這個優化非常有意思，因為越靠前的區域就是越熱點的數據，可能來回訪問就是那幾個熱點數據，因此特別熱點的數據訪問就不用來回移動了hhh。

操作系統

參考：

當 CPU 訪問的頁面不在物理記憶體時，便會產生一個缺頁中斷，請求操作系統將所缺頁調入到物理記憶體。
這個將所缺頁調入到物理記憶體的過程也會涉及到記憶體淘汰策略。

不同的是操作系統淘汰的是頁表，而MySQL淘汰的是數據頁。其實本質上都是一樣的hhh。
所缺頁調入到物理記憶體的步驟大概為：

首先查找頁表，找對應的頁表項，如果頁表項中的狀態位為「無效的」，就觸發缺頁中斷。

去磁碟找對應頁面在磁碟中的位置，讀取出來。

準備換入：物理記憶體中找空閑頁，有就換入。沒有就自然涉及了記憶體頁面置換的一些策略了。

將頁表項中的狀態位設置為[有效的]，重新執行對應的觸發缺頁中斷的代碼。

記憶體淘汰策略演算法目標則是，儘可能減少頁面的換入換出的次數，常見的頁面置換演算法有如下幾種：

最佳頁面置換演算法（OPT）：這是理論上的最優演算法，因為未來不可知，所以是理論上的。它是一個頁面置換演算法的上限。
先進先出置換演算法（FIFO）：思想就是先入先出隊列，效果差。
最近最久未使用的置換演算法（LRU）：近似最優置換演算法，最優置換演算法是通過「未來」的使用情況來推測要淘汰的頁面，而 LRU 則是通過「歷史」的使用情況來推測要淘汰的頁面。使用LRU就要維護一個LRU鏈表（後面這幾句都可以在MySQL的記憶體淘汰策略中有所體現），在每次訪問記憶體時都必須要更新「整個鏈表」。LRU 雖然看上去不錯，但是由於開銷比較大，實際應用中比較少使用。

MySQL用的是LRU，效果好，但是代價也是比較大的。

時鐘頁面置換演算法（Lock）：優化置換的次數，也能方便實現兩者兼得，它跟 LRU 近似，又是對 FIFO 的一種改進。

演算法思想為：把所有的頁面都保存在一個類似鐘面的「環形鏈表」中，一個表針指向最老的頁面。
當發生缺頁中斷時，演算法首先檢查表針指向的頁面：遇到1則變為0，然後繼續往下，知道遇到0就替換掉這個頁面。

感覺是相對於FIFO演算法，每個頁面多了一次的選擇機會。

最不常用置換演算法（LFU）：當發生缺頁中斷時，選擇「訪問次數」最少的那個頁面，並將其淘汰。(感覺演算法名字不太貼切)。具體實現：對每個頁面設置一個「訪問計數器」，每當一個頁面被訪問時，該頁面的訪問計數器就累加 1。在發生缺頁中斷時，淘汰計數器值最小的那個頁面。

要增加一個計數器來實現，這個硬體成本是比較高的，另外如果要對這個計數器查找哪個頁面訪問次數最小，查找鏈表本身，如果鏈表長度很大，是非常耗時的，效率不高。
但還有個問題，LFU 演算法只考慮了頻率問題，沒考慮時間的問題，比如有些頁面在過去時間里訪問的頻率很高，但是現在已經沒有訪問了，而當前頻繁訪問的頁面由於沒有這些頁面訪問的次數高，在發生缺頁中斷時，就會可能會誤傷當前剛開始頻繁訪問，但訪問次數還不高的頁面。
那這個問題的解決的辦法還是有的，可以定期減少訪問的次數，比如當發生時間中斷時，把過去時間訪問的頁面的訪問次數除以 2，也就說，隨著時間的流失，以前的高訪問次數的頁面會慢慢減少，相當於加大了被置換的概率。

Redis

參考：

Redis 記憶體淘汰策略共有八種，這八種策略大體分為「不進行數據淘汰」和「進行數據淘汰」兩類策略。

1、不進行數據淘汰的策略
noeviction（Redis3.0之後，預設的記憶體淘汰策略) ：它表示當運行記憶體超過最大設置記憶體時，不淘汰任何數據，這時如果有新的數據寫入，則會觸發 OOM，但是如果沒用數據寫入的話，只是單純的查詢或者刪除操作的話，還是可以正常工作。
2、進行數據淘汰的策略
針對「進行數據淘汰」這一類策略，又可以細分為「在設置了過期時間的數據中進行淘汰」和「在所有數據範圍內進行淘汰」這兩類策略。
在設置了過期時間的數據中進行淘汰：

volatile-random：隨機淘汰設置了過期時間的任意鍵值；
volatile-ttl：優先淘汰更早過期的鍵值。
volatile-lru（Redis3.0 之前，預設的記憶體淘汰策略）：淘汰所有設置了過期時間的鍵值中，最久未使用的鍵值；
volatile-lfu（Redis 4.0 後新增的記憶體淘汰策略）：淘汰所有設置了過期時間的鍵值中，最少使用的鍵值；

在所有數據範圍內進行淘汰：

allkeys-random：隨機淘汰任意鍵值;
allkeys-lru：淘汰整個鍵值中最久未使用的鍵值；
allkeys-lfu（Redis 4.0 後新增的記憶體淘汰策略）：淘汰整個鍵值中最少使用的鍵值

說白了就是LRU和LFU演算法。

Redis 是如何實現 LRU 演算法的？

簡單的LRU演算法存在什麼問題？

MySQL中考慮的是LRU演算法帶來的預讀失效和Buffer Pool污染的問題（簡單LRU演算法效果不好），而Redis是從LRU演算法維護成本來考慮的。

需要用鏈表管理所有的緩存數據，這會帶來額外的空間開銷；
當有數據被訪問時，需要在鏈表上把該數據移動到頭端，如果有大量數據被訪問，就會帶來很多鏈表移動操作，會很耗時，進而會降低 Redis 緩存性能。

Redis 實現的是一種近似 LRU 演算法，目的是為了更好的節約記憶體，它的實現方式是在 Redis 的對象結構體中添加一個額外的欄位，用於記錄此數據的最後一次訪問時間。
當 Redis 進行記憶體淘汰時，會使用隨機採樣的方式來淘汰數據，它是隨機取 5 個值（此值可配置），然後淘汰最久沒有使用的那個。

這樣實現就自然沒有了鏈表的開銷和移動鏈表節點的開銷了。但是多了一個額外欄位（記錄最後一次訪問時間）的開銷。

Redis 是如何實現 LFU 演算法的？

可以在上文中看到操作系統實現LFU演算法的問題有：1.加一個訪問計數器有硬體成本 2.雖叫LFU，但是只考慮了次數，而沒有考慮時間（頻率）。

在LFU演算法中，Redis實現相比於操作系統實現更好，真正的考慮了訪問頻率這個問題。
可以思考一下，為了考慮訪問頻率，我們至少需要哪些值。

當前的訪問頻率的值肯定是要記錄的。logc(Logistic Counter)
上一次的訪問時間，因為訪問時間間隔不同，訪問頻率的更新值就不同。ldt(Last Decrement Time)

在實現LRU演算法的時候，不是多了一個維護上一次訪問時間的欄位嗎？在LFU演算法中肯定不能浪費呀，也是重新用到了這個欄位。具體為：
在 LRU 演算法中，Redis 對象頭的 24 bits 的 lru 欄位是用來記錄 key 的訪問時間戳，因此在 LRU 模式下，Redis可以根據對象頭中的 lru 欄位記錄的值，來比較最後一次 key 的訪問時間長，從而淘汰最久未被使用的 key。
在 LFU 演算法中，Redis對象頭的 24 bits 的 lru 欄位被分成兩段來存儲，高 16bit 存儲 ldt(Last Decrement Time)，低 8bit 存儲 logc(Logistic Counter)。