技術文章 » 面試官：Redis 過期刪除策略和記憶體淘汰策略有什麼區別？

面試官：Redis 過期刪除策略和記憶體淘汰策略有什麼區別？

2022-07-04 12:03:01

作者：小林coding

計算機八股文網站：https://xiaolincoding.com

大家好，我是小林。

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 的定期刪除的流程：

  1. 從過期字典中隨機抽取 20 個 key；
  2. 檢查這 20 個 key 是否過期，並刪除已過期的 key；
  3. 如果本輪檢查的已過期 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 是這樣變化的：

  1. 先按照上次存取距離當前的時長，來對 logc 進行衰減；
  2. 然後，再按照一定概率增加 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》文章

資料型別篇：

持久化篇：

叢集篇：

架構篇：