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

前言

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!

推薦閱讀: