Redis記憶體兜底策略——記憶體淘汰及回識訓制

Redis記憶體淘汰及回收策略都是Redis記憶體優化兜底的策略，那它們是如何進行兜底的呢？先來說明一下什么是記憶體淘汰和記憶體回收策略：

• Redis記憶體淘汰：當Redis的記憶體使用超過配置的限制時，根據一定的策略洗掉一些鍵，以釋放記憶體空間
• Redis記憶體回收：Redis通過定期洗掉和惰性洗掉兩種方式來清除過期的鍵，以保證資料的時效性和減少記憶體占用

記憶體淘汰策略

Redis記憶體淘汰策略是指當Redis的記憶體使用超過配置的最大值時，如何選擇一些鍵進行洗掉，以釋放空間給新的資料，Redis提供了八種記憶體淘汰策略，分別是：

• noeviction：不會淘汰任何鍵，達到記憶體限制后回傳錯誤
• allkeys-random：在所有鍵中，隨機洗掉鍵
• volatile-random：在設定了過期時間的鍵中，隨機洗掉鍵
• allkeys-lru：通過LRU演算法淘汰最近最少使用的鍵，保留最近使用的鍵
• volatile-lru：從設定了過期時間的鍵中，通過LRU演算法淘汰最近最少使用的鍵
• allkeys-lfu：從所有鍵中淘汰使用頻率最少的鍵，從所有鍵中驅逐使用頻率最少的鍵
• volatile-lfu：從設定了過期時間的鍵中，通過LFU演算法淘汰使用頻率最少的鍵
• volatile-ttl：從設定了過期時間的鍵中，淘汰馬上就要過期的鍵

LRU和LFU

LRU（least frequently used）演算法為最近最少使用演算法，根據資料的歷史訪問記錄來進行淘汰資料，優先移除最近最少使用的資料，這種演算法認為最近使用的資料很大概率將會再次被使用

LFU（least frequently used）演算法為最少頻率使用演算法，優先移除使用頻率最少的資料，這種演算法認為使用頻率高的資料很大概率將會再次被使用

LRU和Redis的近似LRU

LRU（least frequently used）演算法為最近最少使用演算法，根據資料的歷史訪問記錄來進行淘汰資料，優先移除最近最少使用的資料，這種演算法認為最近使用的資料很大概率將會再次被使用

什么是LRU

在演算法的選擇上，Redis需要能夠快速地查詢、添加、洗掉資料，也就是說查詢、添加、洗掉的時間復雜讀需為O(1)，哈希表能保證查詢資料的時間復雜度為O(1)，而雙向鏈表能保證添加、洗掉資料的時間復雜度為O(1)，如下：

Redis的近似LRU

如前文所述，真實的 LRU 演算法需要用鏈表管理所有的資料，每次訪問一個資料就要移動鏈表節點，這樣會占用額外的空間和時間，而Redis通過近似 LRU 演算法，隨機抽樣一些鍵，然后比較它們的訪問時間戳，這樣可以節省記憶體和提高性能，而Redis 的近似 LRU 演算法的具體實作如下：

• 每個鍵值對物件（redisObject）中有一個 24 位的 lru 欄位，用于記錄每個資料最近一次被訪問的時間戳
• 每次按鍵獲取一個值的時候，都會呼叫 lookupKey 函式，如果配置使用了 LRU 模式，該函式會更新 value 中的 lru 欄位為當前秒級別的時間戳
• 當記憶體達到限制時，Redis 會維護一個候選集合（pool），大小為 16
• Redis 會隨機從字典中取出 N 個鍵（N 可以通過 maxmemory-samples 引數設定，默認為 5），將 lru 欄位值最小的鍵放入候選集合中，并按照 lru 大小排序
• 如果候選集合已滿，那么新加入的鍵必須有比集合中最大的 lru 值更小的 lru 值，才能替換掉原來的鍵
• 當需要淘汰資料時，直接從候選集合中選擇一個 lru 最小的鍵進行淘汰

舉個例子，假設我們按照下面的順序訪問快取中的資料：h,e,l,l,o,w,o,r,l,d且記憶體中只能存盤3個字符，下面是每次訪問或插入后快取的狀態，其中括號內是lru欄位的值，假設初始時間戳為0

LFU

LFU（Least Frequently Used）是最不經常使用演算法，它的思想是淘汰訪問頻率最低的資料，Redis在3.0版本之后引入了LFU演算法，并對lru欄位進行了拆分，

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

我們看lru:LRU_BITS這個欄位，這個欄位在LRU演算法中的意義是時間戳，精確到秒，而在LFU 演算法中，將它拆為兩部分前16bits為時間戳，精確到分；后8為則表示該物件在一定時間段內被訪問的次數，如下：

當Redis需要淘汰資料時，它會從記憶體中隨機抽取一定數量（默認為5個，可以通過 maxmemory-samples 引數設定）的鍵值對物件，然后比較它們的訪問次數和訪問時間戳，找出其中最小的那個，也就是最不經常使用且最早被訪問的那個，將其從記憶體中洗掉，

例如，假設我們有以下鍵值對和頻率計數器：

如果我們要添加一個新的鍵值對（E,5），并且快取已經滿了，那么我們就需要淘汰一個舊的鍵值對，我們可以隨機選擇A,B,C中的一個，并且發現C的頻率最低，為1，所以我們就淘汰C，并且添加E到快取中，并且將E的頻率設為1，這樣，快取中的資料就變成了：

如何選擇

在選擇上，需要根據不同的適用場景選擇不同策略，如下：

根據8種策略的特性，也從資料完整性、快取命中率及淘汰效率這三個方面詳細對比了，如下：

• 資料完整性（是否會洗掉永久有效的資料)
  • noeviction 、 volatile-lru、volatile-lfu和volatile-random 都可以保證資料完整性，因為它們不會洗掉永久有效的資料
  • allkeys-lru、allkeys-lfu和allkeys-random系列的策略則會影響資料完整性，因為它們會無差別地洗掉所有型別的資料
• 快取命中率（是否能夠盡可能保留最有價值的資料）
  • allkeys-lru 和 volatile-lru 策略可以提高快取命中率，因為它們會根據資料的訪問時間來淘汰資料
  • allkeys-random 和 volatile-random 策略則會降低快取命中率，因為它們會隨機淘汰資料
  • allkeys-lfu 和 volatile-lfu 策略也可以提高快取命中率，因為它們會根據資料的訪問頻率來淘汰資料
  • volatile-ttl 策略則會降低快取命中率，因為它會根據資料的剩余生命周期來淘汰資料
• 淘汰效率（是否能夠快速地找到并洗掉目標資料）
  • allkeys-random 和 volatile-random 策略可以提高執行效率，因為它們只需要隨機選擇一些資料進行洗掉
  • allkeys-lru 和 volatile-lru 策略則會降低執行效率，因為它們需要對所有或部分資料進行排序
  • allkeys-lfu 和 volatile-lfu 策略也會降低執行效率，因為它們需要對所有或部分資料進行計數和排序
  • volatile-ttl 策略則會提高執行效率，因為它只需要對設定了過期時間的資料進行排序

記憶體回收策略

Redis的過期鍵洗掉有兩種方式，一種是定期洗掉，一種是惰性洗掉

惰性洗掉

Redis惰性洗掉是指當一個鍵過期后，它并不會立即被洗掉，而是在客戶端嘗試訪問這個鍵時，Redis會檢查這個鍵是否過期，如果過期了，就會洗掉這個鍵，惰性洗掉由db.c/expireIfNeeded函式實作，

惰性洗掉的優點是節約CPU性能，發現必須洗掉的時候才洗掉，缺點是記憶體壓力很大，出現長期占用記憶體的資料，惰性洗掉是Redis的默認策略，它不需要額外的配置，

惰性洗掉的缺點是可能會導致過期鍵長時間占用記憶體，如果訪問頻率較低的鍵過期了，但沒有被訪問到，那么它們就不會被惰性洗掉，從而浪費記憶體空間，

為了解決這個問題，Redis還采用了定期洗掉和記憶體淘汰機制來配合惰性洗掉，以達到更好的清理效果

定期洗掉

Redis會將設定了過期時間的鍵放到一個獨立的字典中，稱為過期字典，Redis會對這個字典進行每秒10次（由組態檔中的hz引數控制）的過期掃描，過期掃描不會遍歷字典中所有的鍵，而是采用了一種簡單的貪心策略，該策略的洗掉邏輯如下：

• 從過期字典中隨機選擇20個鍵
• 洗掉其中已經過期的鍵
• 如果超過25%的鍵被洗掉，則重復步驟1
• 如果本次掃描耗時超過1毫秒，則停止掃描

這種策略可以在一定程度上保證過期鍵能夠及時被洗掉，同時也避免了對CPU時間的過度占用，但是它也有一些缺點，比如可能會誤刪一些有效的鍵（因為隨機性），或者漏刪一些無效的鍵（因為限制了掃描時間）

因此，Redis還結合了惰性洗掉策略，即在每次訪問一個鍵之前，都會檢查這個鍵是否過期，如果過期就洗掉，然后回傳空值，這樣可以保證不回傳過期的資料，也可以節省CPU時間，但是它可能會導致一些過期的鍵長期占用記憶體，如果這些鍵很少被訪問或者一直不被訪問，那么它們就永遠不會被洗掉

組態檔說明

Redis記憶體淘汰、記憶體回收策略相關的組態檔如下：

# 記憶體淘汰策略
maxmemory-policy noeviction
# 抽取數量
maxmemory-samples 5
# 最大記憶體
maxmemory 100mb
# 記憶體淘汰韌性
maxmemory-eviction-tenacity 10
# 后臺任務執行間隔
hz 10
# 是否開啟動態間隔
dynamic-hz yes

組態檔說明:

• maxmemory-policy：記憶體淘汰策略，可選值為noeviction、allkeys-random、volatile-random、allkeys-lru、volatile-lru、allkeys-lfu、volatile-lfu、volatile-ttl其中的一個
• maxmemory：默認值為0，也就是不限制記憶體的使用，
• maxmemory-samples：抽取數量，默認為5，如果設為10將非常接近真實的LRU，但需要更多CPU資源，如果設為3將非常快，但是非常不準確，
• maxmemory-eviction-tenacity：記憶體淘汰韌性，默認為10
  • maxmemory-eviction-tenacity為0時，表示不進行任何淘汰，相當于noeviction策略
  • maxmemory-eviction-tenacity為10時，表示每次淘汰鍵的數量為記憶體使用量的0.1%，每秒最多淘汰10次
• hz：Redis后臺任務執行間隔，如超時關閉客戶端連接、定期洗掉等，默認值為10，范圍在 1 到 500 之間，官方建議不要超過100，大多數應使用默認值，并且只有在極低延遲的環境中才能設為 100
• dynamic-hz：此配置用于動態調整hz的值，默認開啟，如果有大量客戶端連接進來時，會以hz的配置值將作為基線，將hz的實際值設定為hz的配置值的整數倍，用來節省CPU資源，

總結

總結如下：

• Redis記憶體淘汰機制是指在Redis的用于快取的記憶體不足時，怎么處理需要新寫入且需要申請額外空間的資料
• Redis提供了八種記憶體淘汰策略，分別是：
  • noeviction：不會淘汰任何鍵，達到記憶體限制后回傳錯誤
  • allkeys-random：在所有鍵中，隨機洗掉鍵
  • volatile-random：在設定了過期時間的鍵中，隨機洗掉鍵
  • allkeys-lru：通過LRU演算法淘汰最近最少使用的鍵，保留最近使用的鍵
  • volatile-lru：從設定了過期時間的鍵中，通過LRU演算法淘汰最近最少使用的鍵
  • allkeys-lfu：從所有鍵中淘汰使用頻率最少的鍵，從所有鍵中驅逐使用頻率最少的鍵
  • volatile-lfu：從設定了過期時間的鍵中，通過LFU演算法淘汰使用頻率最少的鍵
  • volatile-ttl：從設定了過期時間的鍵中，淘汰馬上就要過期的鍵
• Redis記憶體回識訓制是指在Redis中如何洗掉已經過期或者被淘汰的資料，釋放記憶體空間
• Redis提供了兩種記憶體回收策略，分別是：
  • 定期洗掉：Redis會每隔一定時間（默認100ms）隨機抽取一些設定了過期時間的鍵，檢查它們是否過期，如果過期就洗掉，這種策略可以減少CPU開銷，但可能會導致一些過期鍵占用記憶體
  • 惰性洗掉：Redis在客戶端訪問一個鍵時，會檢查這個鍵是否過期，如果過期就洗掉，這種策略可以及時釋放記憶體空間，但可能會增加CPU開銷和延遲

標籤：其他

上一篇：Redis記憶體兜底策略——記憶體淘汰及回識訓制

下一篇：返回列表