Redis 的內存淘汰策略和過期刪除策略的區別

Posted on by

前言

Redis 是可以對 key 設置過期時間的，因此需要有相應的機制將已過期的鍵值對刪除，而做這個工作的就是過期鍵值刪除策略。

Redis 的「內存淘汰策略」和「過期刪除策略」，很多小夥伴容易混淆，這兩個機制雖然都是做刪除的操作，但是觸發的條件和使用的策略都是不同的。

今天就跟大傢理一理，「內存淘汰策略」和「過期刪除策略」。

過期刪除策略

Redis 是可以對 key 設置過期時間的，因此需要有相應的機制將已過期的鍵值對刪除，而做這個工作的就是過期鍵值刪除策略。

如何設置過期時間？

先說一下對 key 設置過期時間的命令。設置 key 過期時間的命令一共有 4 個：

  • expire <key> <n>：設置 key 在 n 秒後過期，比如 expire key 100 表示設置 key 在 100 秒後過期；
  • pexpire <key> <n>：設置 key 在 n 毫秒後過期，比如 pexpire key2 100000 表示設置 key2 在 100000 毫秒（100 秒）後過期。
  • expireat <key> <n>：設置 key 在某個時間戳（精確到秒）之後過期，比如 expireat key3 1655654400 表示 key3 在時間戳 1655654400 後過期（精確到秒）；
  • pexpireat <key> <n>：設置 key 在某個時間戳（精確到毫秒）之後過期，比如 pexpireat key4 1655654400000 表示 key4 在時間戳 1655654400000 後過期（精確到毫秒）

當然，在設置字符串時，也可以同時對 key 設置過期時間，共有 3 種命令：

  • set <key> <value> ex <n> ：設置鍵值對的時候，同時指定過期時間（精確到秒）；
  • set <key> <value> px <n> ：設置鍵值對的時候，同時指定過期時間（精確到毫秒）；
  • setex <key> <n> <valule>   ：設置鍵值對的時候，同時指定過期時間（精確到秒）。

如果你想查看某個 key 剩餘的存活時間，可以使用 TTL <key> 命令。

# 設置鍵值對的時候，同時指定過期時間位 60 秒
> setex key1 60 value1
OK
# 查看 key1 過期時間還剩多少
> ttl key1
(integer) 56
> ttl key1
(integer) 52

如果突然反悔，取消 key 的過期時間，則可以使用 PERSIST <key> 命令。

# 取消 key1 的過期時間
> persist key1
(integer) 1

# 使用完 persist 命令之後，
# 查下 key1 的存活時間結果是 -1，表明 key1 永不過期 
> ttl key1 
(integer) -1

如何判定 key 已過期瞭？

每當我們對一個 key 設置瞭過期時間時，Redis  會把該 key 帶上過期時間存儲到一個過期字典（expires dict）中，也就是說「過期字典」保存瞭數據庫中所有 key 的過期時間。

過期字典存儲在 redisDb 結構中，如下：

typedef struct redisDb {
    dict *dict;    /* 數據庫鍵空間，存放著所有的鍵值對 */
    dict *expires; /* 鍵的過期時間 */
    ....
} redisDb;

過期字典數據結構結構如下：

  • 過期字典的 key 是一個指針，指向某個鍵對象；
  • 過期字典的 value 是一個 long long 類型的整數，這個整數保存瞭 key 的過期時間；

過期字典的數據結構如下圖所示：

字典實際上是哈希表，哈希表的最大好處就是讓我們可以用 O(1) 的時間復雜度來快速查找。當我們查詢一個 key 時，Redis 首先檢查該 key 是否存在於過期字典中：

  • 如果不在，則正常讀取鍵值；
  • 如果存在，則會獲取該 key 的過期時間，然後與當前系統時間進行比對，如果比系統時間大，那就沒有過期，否則判定該 key 已過期。

過期鍵判斷流程如下圖所示：

過期刪除策略有哪些？

在說 Redis 過期刪除策略之前，先跟大傢介紹下，常見的三種過期刪除策略：

  • 定時刪除；
  • 惰性刪除；
  • 定期刪除；

接下來，分別分析它們的優缺點。

定時刪除策略是怎麼樣的？

定時刪除策略的做法是，在設置 key 的過期時間時，同時創建一個定時事件，當時間到達時，由事件處理器自動執行 key 的刪除操作。

定時刪除策略的優點：可以保證過期 key 會被盡快刪除，也就是內存可以被盡快地釋放。因此，定時刪除對內存是最友好的。

定時刪除策略的缺點：在過期 key 比較多的情況下，刪除過期 key 可能會占用相當一部分 CPU 時間，在內存不緊張但 CPU 時間緊張的情況下，將 CPU 時間用於刪除和當前任務無關的過期鍵上，無疑會對服務器的響應時間和吞吐量造成影響。所以，定時刪除策略對 CPU 不友好。

惰性刪除策略是怎麼樣的？惰性刪除策略的做法是，不主動刪除過期鍵，每次從數據庫訪問 key 時，都檢測 key 是否過期，如果過期則刪除該 key。

惰性刪除策略的優點：因為每次訪問時，才會檢查 key 是否過期，所以此策略隻會使用很少的系統資源，因此，惰性刪除策略對 CPU 時間最友好。

惰性刪除策略的缺點：如果一個 key 已經過期，而這個 key 又仍然保留在數據庫中，那麼隻要這個過期 key 一直沒有被訪問，它所占用的內存就不會釋放，造成瞭一定的內存空間浪費。所以，惰性刪除策略對內存不友好。

定期刪除策略是怎麼樣的？定期刪除策略的做法是，每隔一段時間「隨機」從數據庫中取出一定數量的 key 進行檢查，並刪除其中的過期key。

定期刪除策略的優點：通過限制刪除操作執行的時長和頻率，來減少刪除操作對 CPU 的影響，同時也能刪除一部分過期的數據減少瞭過期鍵對空間的無效占用。

定期刪除策略的缺點：

  • 內存清理方面沒有定時刪除效果好，同時沒有惰性刪除使用的系統資源少。
  • 難以確定刪除操作執行的時長和頻率。如果執行的太頻繁，定期刪除策略變得和定時刪除策略一樣，對CPU不友好；如果執行的太少，那又和惰性刪除一樣瞭，過期 key 占用的內存不會及時得到釋放。

Redis 過期刪除策略是什麼？

前面介紹瞭三種過期刪除策略，每一種都有優缺點，僅使用某一個策略都不能滿足實際需求。

所以， Redis 選擇「惰性刪除+定期刪除」這兩種策略配和使用，以求在合理使用 CPU 時間和避免內存浪費之間取得平衡。

Redis 是怎麼實現惰性刪除的？

Redis 的惰性刪除策略由 db.c 文件中的 expireIfNeeded 函數實現，代碼如下：

int expireIfNeeded(redisDb *db, robj *key) {
    // 判斷 key 是否過期
    if (!keyIsExpired(db,key)) return 0;
    ....
    /* 刪除過期鍵 */
    ....
    // 如果 server.lazyfree_lazy_expire 為 1 表示異步刪除，反之同步刪除；
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

Redis 在訪問或者修改 key 之前，都會調用 expireIfNeeded 函數對其進行檢查，檢查 key 是否過期：

  • 如果過期，則刪除該 key，至於選擇異步刪除，還是選擇同步刪除，根據lazyfree_lazy_expire 參數配置決定（Redis 4.0版本開始提供參數），然後返回 null 給客服端；
  • 如果沒有過期，不做任何處理，然後返回正常的鍵值對給客戶端；

惰性刪除的流程圖如下：

Redis 是怎麼實現定期刪除的？

再回憶一下，定期刪除策略的做法：每隔一段時間「隨機」從數據庫中取出一定數量的 key 進行檢查，並刪除其中的過期key。

1.這個間隔檢查的時間是多長呢？

在 Redis 中，默認每秒進行 10 次過期檢查一次數據庫，此配置可通過 Redis 的配置文件 redis.conf 進行配置，配置鍵為 hz 它的默認值是 hz 10。

特別強調下，每次檢查數據庫並不是遍歷過期字典中的所有 key，而是從數據庫中隨機抽取一定數量的 key 進行過期檢查。

2.隨機抽查的數量是多少呢？

我查瞭下源碼，定期刪除的實現在 expire.c 文件下的 activeExpireCycle 函數中，其中隨機抽查的數量由 ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 定義的，它是寫死在代碼中的，數值是 20。

也就是說，數據庫每輪抽查時，會隨機選擇 20 個 key 判斷是否過期。

接下來，詳細說說 Redis 的定時刪除的流程：

  • 從過期字典中隨機抽取 20 個 key；
  • 檢查這 20 個 key 是否過期，並刪除已過期的 key；
  • 如果本輪檢查的已過期 key 的數量，超過 5 個（20/4），也就是「已過期 key 的數量」占比「隨機抽取 key 的數量」大於 25%，則繼續重復步驟 1；如果已過期的 key 比例小於 25%，則停止繼續刪除過期 key，然後等待下一輪再檢查。

可以看到，定時刪除是一個循環的流程。

那 Redis 為瞭保證定時刪除不會出現循環過度，導致線程卡死現象，為此增加瞭定時刪除循環流程的時間上限，默認不會超過 25ms。

針對定時刪除的流程，我寫瞭個偽代碼：

do {
    //已過期的數量
    expired = 0；
    //隨機抽取的數量
    num = 20;
    while (num--) {
        //1. 從過期字典中隨機抽取 1 個 key
        //2. 判斷該 key 是否過期，如果已過期則進行刪除，同時對 expired++
    }

    // 超過時間限制則退出
    if (timelimit_exit) return;

  /* 如果本輪檢查的已過期 key 的數量，超過 25%，則繼續隨機抽查，否則退出本輪檢查 */
} while (expired > 20/4);

定時刪除的流程如下：

內存淘汰策略

前面說的過期刪除策略，是刪除已過期的 key，而當 Redis 的運行內存已經超過 Redis 設置的最大內存之後，則會使用內存淘汰策略刪除符合條件的 key，以此來保障 Redis 高效的運行。

如何設置 Redis 最大運行內存？

在配置文件 redis.conf 中，可以通過參數 maxmemory <bytes> 來設定最大運行內存，隻有在 Redis 的運行內存達到瞭我們設置的最大運行內存，才會觸發內存淘汰策略。

不同位數的操作系統，maxmemory 的默認值是不同的：

  • 在 64 位操作系統中，maxmemory 的默認值是 0，表示沒有內存大小限制，那麼不管用戶存放多少數據到 Redis 中，Redis 也不會對可用內存進行檢查，直到 Redis 實例因內存不足而崩潰也無作為。
  • 在 32 位操作系統中，maxmemory 的默認值是 3G，因為 32 位的機器最大隻支持 4GB 的內存，而系統本身就需要一定的內存資源來支持運行，所以 32 位操作系統限制最大 3 GB 的可用內存是非常合理的，這樣可以避免因為內存不足而導致 Redis 實例崩潰。

Redis 內存淘汰策略有哪些？

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

1.不進行數據淘汰的策略

noeviction（Redis3.0之後，默認的內存淘汰策略） ：它表示當運行內存超過最大設置內存時，不淘汰任何數據，而是不再提供服務，直接返回錯誤。

2.進行數據淘汰的策略

針對「進行數據淘汰」這一類策略，又可以細分為「在設置瞭過期時間的數據中進行淘汰」和「在所有數據范圍內進行淘汰」這兩類策略。

在設置瞭過期時間的數據中進行淘汰：

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

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

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

如何查看當前 Redis 使用的內存淘汰策略？

可以使用 config get maxmemory-policy 命令，來查看當前 Redis 的內存淘汰策略，命令如下：

127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"

可以看出，當前 Redis 使用的是 noeviction 類型的內存淘汰策略，它是 Redis 3.0 之後默認使用的內存淘汰策略，表示當運行內存超過最大設置內存時，不淘汰任何數據，但新增操作會報錯。

如何修改 Redis 內存淘汰策略？

設置內存淘汰策略有兩種方法：

  • 方式一：通過“config set maxmemory-policy <策略>”命令設置。它的優點是設置之後立即生效，不需要重啟 Redis 服務，缺點是重啟 Redis 之後，設置就會失效。
  • 方式二：通過修改 Redis 配置文件修改，設置“maxmemory-policy <策略>”，它的優點是重啟 Redis 服務後配置不會丟失，缺點是必須重啟 Redis 服務，設置才能生效。

LRU 算法和 LFU 算法有什麼區別？

LFU 內存淘汰算法是 Redis  4.0 之後新增內存淘汰策略，那為什麼要新增這個算法？那肯定是為瞭解決 LRU 算法的問題。

接下來，就看看這兩個算法有什麼區別？Redis 又是如何實現這兩個算法的？

什麼是 LRU 算法？

LRU 全稱是 Least Recently Used 翻譯為最近最少使用，會選擇淘汰最近最少使用的數據。

傳統 LRU 算法的實現是基於「鏈表」結構，鏈表中的元素按照操作順序從前往後排列，最新操作的鍵會被移動到表頭，當需要內存淘汰時，隻需要刪除鏈表尾部的元素即可，因為鏈表尾部的元素就代表最久未被使用的元素。

Redis 並沒有使用這樣的方式實現 LRU 算法，因為傳統的 LRU 算法存在兩個問題：

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

Redis 是如何實現 LRU 算法的？

Redis 實現的是一種近似 LRU 算法，目的是為瞭更好的節約內存，它的實現方式是在 Redis 的對象結構體中添加一個額外的字段，用於記錄此數據的最後一次訪問時間。

當 Redis 進行內存淘汰時，會使用隨機采樣的方式來淘汰數據，它是隨機取 5 個值（此值可配置），然後淘汰最久沒有使用的那個。

Redis 實現的 LRU 算法的優點：

  • 不用為所有的數據維護一個大鏈表，節省瞭空間占用；
  • 不用在每次數據訪問時都移動鏈表項，提升瞭緩存的性能；

但是 LRU 算法有一個問題，無法解決緩存污染問題，比如應用一次讀取瞭大量的數據，而這些數據隻會被讀取這一次，那麼這些數據會留存在 Redis 緩存中很長一段時間，造成緩存污染。

因此，在 Redis 4.0 之後引入瞭 LFU 算法來解決這個問題。

什麼是 LFU 算法？

LFU 全稱是 Least Frequently Used 翻譯為最近最不常用的，LFU 算法是根據數據訪問次數來淘汰數據的，它的核心思想是“如果數據過去被訪問多次，那麼將來被訪問的頻率也更高”。

所以， LFU 算法會記錄每個數據的訪問次數。當一個數據被再次訪問時，就會增加該數據的訪問次數。這樣就解決瞭偶爾被訪問一次之後，數據留存在緩存中很長一段時間的問題，相比於 LRU 算法也更合理一些。

Redis 是如何實現 LFU 算法的？

LFU 算法相比於  LRU 算法的實現，多記錄瞭「數據的訪問頻次」的信息。Redis 對象的結構如下：

typedef struct redisObject {
    ...

    // 24 bits，用於記錄對象的訪問信息
    unsigned lru:24;
    ...
} robj;

Redis 對象頭中的 lru 字段，在 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。

註意，logc 並不是單純的訪問次數，而是訪問頻次（訪問頻率），因為 logc  會隨時間推移而衰減的。

在每次 key 被訪問時，會先對 logc 做一個衰減操作，衰減的值跟前後訪問時間的差距有關系，如果上一次訪問的時間與這一次訪問的時間差距很大，那麼衰減的值就越大，這樣實現的 LFU 算法是根據訪問頻率來淘汰數據的，而不隻是訪問次數。訪問頻率需要考慮 key 的訪問是多長時間段內發生的。key 的先前訪問距離當前時間越長，那麼這個 key 的訪問頻率相應地也就會降低，這樣被淘汰的概率也會更大。

對 logc 做完衰減操作後，就開始對 logc  進行增加操作，增加操作並不是單純直接 + 1，而是根據概率增加，如果 logc 越大的 key，它的 logc 就越難再增加。

所以，Redis 在訪問 key 時，對於 logc  是這樣變化的：

  • 先按照上次訪問距離當前的時長，來對 logc 進行衰減；
  • 然後，再按照一定概率增加 logc 的值

redis.conf 提供瞭兩個配置項，用於調整 LFU 算法從而控制 logc 的增長和衰減：

  • lfu-decay-time 用於調整 logc 的衰減速度，它是一個以分鐘為單位的數值，默認值為1，lfu-decay-time 值越大，衰減越慢；
  • lfu-log-factor 用於調整 logc 的增長速度，lfu-log-factor 值越大，logc 增長越慢。

總結

Redis 使用的過期刪除策略是「惰性刪除+定期刪除」，刪除的對象是已過期的 key。

內存淘汰策略是解決內存過大的問題，當 Redis 的運行內存超過最大運行內存時，就會觸發內存淘汰策略，Redis 4.0 之後共實現瞭 8 種內存淘汰策略，我也對這 8 種的策略進行分類，如下：

到此這篇關於Redis 的內存淘汰策略和過期刪除策略的區別的文章就介紹到這瞭,更多相關Redis 內存淘汰策略和過期刪除策略內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：