Redis過期刪除策略與記憶體淘汰策略

2022-09-04 18:04:07

過期刪除策略

過期刪除策略： redis可以對key設定過期時間，因此要有相應的機制將已過期的鍵值對刪除。

設定Redis中key的過期時間 (單位：秒)

1）expire key time 這是最常用的方式
2）setex key, seconds, value 字串獨有的方式

如果未設定時間，那就是永不過期。如果設定了過期時間，使用 persist key 讓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是否過期

常見的三種過期刪除策略

定時刪除：在設定key的過期時間時，同時建立一個定時事件，當時間到達時，由事件處理器自動執行key的刪除操作。
惰性刪除：不主動刪除過期鍵，每次從資料庫存取key時，都檢測key是否過期，如果過期則刪除該key。
定期刪除：每隔一段時間「隨機」從資料庫中取出一定數量的key進行檢查，並刪除其中的過期key。

Redis使用用的過期刪除策略

Redis 採用了 惰性刪除 + 定期刪除 的方式處理過期資料，以求在合理使用 CPU 時間和避免記憶體浪費之間取得平衡。

惰性刪除的使用：當我們存取一個key時，會先檢查這個key是否過期，如果過期則刪除這個key並返回給使用者端null，否則返回對應value
定期刪除的使用：定期檢查一次資料庫，此設定可通過 Redis 的組態檔 redis.conf 進行設定，設定鍵為 hz 它的預設值是 hz 10( 從資料庫中隨機抽取20個key 進行過期檢查 )

Redis的定期刪除的流程

從過期字典中隨機抽取 20 個 key（20是寫死在程式碼中的，不可修改）
檢查這 20個key是否過期，並刪除過期的 key
如果本輪檢查的已過期 key 的數量，超過 5 個(過期 key 的數量 / 20 > 25%)，則再次抽取20個檢查檢查，如果某一次該比例小於 25%，則結束檢查，然後等待下一輪再檢查

Redis 為了保證定期刪除不會出現迴圈過度，導致執行緒卡死現象，為此增加了定期刪除迴圈流程的時間上限，預設不會超過 25ms（超過就停止檢查）。

記憶體淘汰策略

記憶體淘汰策略：redis 的執行記憶體已經超過redis設定的最大記憶體後，會使用記憶體淘汰策略刪除符合條件的 key，以此來保障 Redis 高效的執行。

設定Redis最大執行記憶體

在組態檔 redis.conf 中，可以通過引數 maxmemory 來設定最大執行記憶體，只有在 Redis 的執行記憶體達到了我們設定的最大執行記憶體，才會觸發記憶體淘汰策略。

不同位數的作業系統，maxmemory 的預設值是不同的：

在 64 位元運算系統中，maxmemory 的預設值是 0，表示沒有記憶體大小限制，那麼不管使用者存放多少資料到 Redis 中，Redis 也不會對可用記憶體進行檢查，直到 Redis 範例因記憶體不足而崩潰也無作為。
在 32 位元運算系統中，maxmemory 的預設值是 3G，因為 32 位的機器最大隻支援 4GB 的記憶體，而系統本身就需要一定的記憶體資源來支援執行，所以 32 位元運算系統限制最大 3 GB 的可用記憶體是非常合理的，這樣可以避免因為記憶體不足而導致 Redis 範例崩潰

Redis 記憶體淘汰策略有哪些？

Redis 記憶體淘汰策略共有八種，這八種策略大體分為「不進行資料淘汰」和「進行資料淘汰」兩類策略

不進行資料淘汰的策略：

noeviction（Redis3.0之後，預設的記憶體淘汰策略）：它表示當執行記憶體超過最大設定記憶體時，不淘汰任何資料，而是不再提供服務，直接返回錯誤
進行資料淘汰的策略（又可以細分為在設定了過期時間的資料中進行淘汰和在所有資料範圍內進行淘汰這兩類策略）

在設定了過期時間的資料中進行淘汰：

volatile-random：隨機淘汰設定了過期時間的任意鍵值
volatile-ttl：優先淘汰更早過期的鍵值
volatile-lru（Redis3.0 之前，預設的記憶體淘汰策略）：淘汰所有設定了過期時間的鍵值中，最久未使用的鍵值
volatile-lfu（Redis 4.0 後新增的記憶體淘汰策略）：淘汰所有設定了過期時間的鍵值中，最少使用的鍵值

在所有資料範圍內進行淘汰：

allkeys-random：隨機淘汰任意鍵值
allkeys-lru：淘汰整個鍵值中最久未使用的鍵值
allkeys-lfu（Redis 4.0 後新增的記憶體淘汰策略）：淘汰整個鍵值中最少使用的鍵值

可以使用 config get maxmemory-policy 命令，來檢視當前 Redis 的記憶體淘汰策略，命令如下：

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

Redis 使用的是 noeviction 型別的記憶體淘汰策略，它是 Redis 3.0 之後預設使用的記憶體淘汰策略，表示當執行記憶體超過最大設定記憶體時，不淘汰任何資料，但新增操作會報錯。

設定記憶體淘汰策略有兩種方法：

方式一：通過config set maxmemory-policy <策略>命令設定。立即生效，不需要重啟 Redis 服務，但重啟 Redis 之後，設定就會失效
方式二：通過修改 Redis 組態檔修改，設定maxmemory-policy <策略>，重啟 Redis 服務後設定不會丟失（修改了組態檔，必須重啟Redis服務，設定才能生效）

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

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

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 {
     ...
     unsigned lru:24;  // 24 bits，用於記錄物件的存取資訊
     ...
 } 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 的增長和衰減：