過期刪除策略

過期刪除策略： 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 的增長和衰減：

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