在學習【作業系統】 【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鏈表：為了方便確認哪些頁還沒有讀入資料，
由三個鏈表的功能可以知道，最開始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)，
- ldt 是用來記錄 key 的訪問時間戳；
- logc 是用來記錄 key 的訪問頻次，它的值越小表示使用頻率越低，越容易淘汰，每個新加入的 key 的logc 初始值為 5， ---注意是訪問評次，而不是簡單的訪問次數，
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/549289.html
標籤：其他
上一篇：萬字詳解 | Java 流式編程
下一篇：生產事故-記一次特殊的OOM排查