redis 過期策略及內存回收機制解析

redis作為緩存的場景下，內存淘汰策略決定的redis的內存使用效率。考慮到這個很多大廠給出的“送分題”，但一般人很少能講清楚，除非你對真的對過期策略、懶惰刪除、LRU、LRU有一定的研究。

1. 過期策略

Redis 所有的數據結構都可以設置過期時間，時間一到，就會自動刪除。就像死神，時刻盯著所有設置瞭過期時間的 key，壽命一到就會立即收割。

站在死神的角度思考：會不會在同一時間太多的 key 過期（Redis 是單線程的，收割的時間也會占用線程的處理時間，如果收割的太過於繁忙），以至於忙不過來？會不會導致線上讀寫指令出現卡頓？

1.1 過期的 key 集合

redis 會將每個設置瞭過期時間的 key 放入到一個獨立的字典中，以後會定時遍歷這個字典來刪除到期的 key。

redis 采用兩種策略：

• 定時刪除是集中處理
• 惰性刪除是零散處理

1.2 定時掃描策略

Redis 默認會每秒進行十次過期掃描，過期掃描不會遍歷過期字典中所有的 key，而是采用瞭一種簡單的貪心策略。

• 從過期字典中隨機 20 個 key；
• 刪除這 20 個 key 中已經過期的 key；
• 如果過期的 key 比率超過 1/4，那就重復步驟 1；

同時，為瞭保證過期掃描不會出現循環過度，導致線程卡死現象，算法還增加瞭掃描時間的上限，默認不會超過 25ms。

如果Redis 實例中所有的 key （幾十萬個）在同一時間過期會怎樣？

Redis 會持續掃描過期字典 (循環多次)，直到過期字典中過期的 key 變得稀疏，才會停止 (循環次數明顯下降)。內存管理器需要頻繁回收內存頁，此時會產生一定的 CPU 消耗，必然導致線上讀寫請求出現明顯的卡頓現象。

當客戶端請求到來時（服務器如果正好進入過期掃描狀態），客戶端的請求將會等待至少 25ms 後才會進行處理，如果客戶端將超時時間設置的比較短，比如 10ms，那麼就會出現大量的鏈接因為超時而關閉，業務端就會出現很多異常。而且這時你還無法從 Redis 的 slowlog 中看到慢查詢記錄，因為慢查詢指的是邏輯處理過程慢，不包含等待時間。

其實這個故障在社區中時常爆出 ，業務開發人員一定要註意不宜全部在同一時間過期，可以給目標過期時間的基礎上再加一個隨機范圍（redis.expire_at(key, random.randint(86400) + expire_ts)），分散過期處理的壓力。

1.3 從庫的過期策略

從庫不會進行過期掃描，從庫對過期的處理是被動的。主庫在 key 到期時，會在 AOF 文件裡增加一條 del 指令，同步到所有的從庫，從庫通過執行這條 del 指令來刪除過期的 key。

因為指令同步是異步進行的，所以主庫過期的 key 的 del 指令沒有及時同步到從庫的話，會出現主從數據的不一致，主庫沒有的數據在從庫裡還存在，分佈式鎖的算法漏洞就是因為這個同步延遲產生的。

2. 懶惰刪除

懶惰刪除(lazy free)，在客戶端訪問key時再進行檢查如果過期瞭就立即刪除

為什麼要懶惰刪除？

Redis內部實際上並不是隻有一個主線程，它還有幾個異步線程專門用來處理一些耗時的操作。刪除指令 del 會直接釋放對象的內存，大部分情況下，這個指令非常快，沒有明顯延遲。

不過如果刪除的 key 是一個非常大的對象，那麼刪除操作就會導致單線程卡頓，怎麼破？

Redis 4.0 版本引入瞭 unlink 指令（為瞭解決這個卡頓問題），它能對刪除操作進行懶處理，丟給後臺線程來異步回收內存。

> unlink key

OK

你肯定會擔心這裡的線程安全問題，會不會出現多個線程同時並發修改數據結構的情況存在？

這裡我打個比方：可以將整個 Redis 內存裡面所有有效的數據想象成一棵大樹。當 unlink 指令發出時，它隻是把大樹中的一個樹枝別斷瞭，然後扔到旁邊的火堆裡焚燒 (異步線程池)。樹枝離開大樹的一瞬間，它就再也無法被主線程中的其它指令訪問到瞭，因為主線程隻會沿著這顆大樹來訪問。

2.1 異步線程

異步線程在 Redis 內部有一個特別的名稱，它就是BIO，全稱是Background IO，意思是在背後默默幹活的 IO 線程。不過內存回收本身並不是什麼 IO 操作，隻是 CPU 的計算消耗可能會比較大而已。

異步線程演進之路

實現懶惰刪除時，它並不是一開始就想到瞭異步線程。最初的嘗試是在主線程裡，使用類似於字典漸進式搬遷那樣來實現漸進式刪除回收。懶惰刪除是采用類似於 scan 操作的方法，通過遍歷第一維數組來逐步刪除回收第二維鏈表的內容，等到所有鏈表都回收完瞭，再一次性回收第一維數組。這樣也可以達到刪除大對象時不阻塞主線程的效果。

但是說起來容易做起來卻很難。漸進式回收需要仔細控制回收頻率，它不能回收的太猛，這會導致 CPU 資源占用過多，也不能回收的蝸牛慢，因為內存回收不及時可能導致內存持續增長。

Antirez 需要采用合適的自適應算法來控制回收頻率。他首先想到的是檢測內存增長的趨勢是增長 (+1) 還是下降 (-1) 來漸進式調整回收頻率系數，這樣的自適應算法實現也很簡單。但是測試後發現在服務繁忙的時候，QPS 會下降到正常情況下 65% 的水平，這點非常致命。

所以 Antirez 才使用瞭如今使用的方案——異步線程。異步線程這套方案就簡單多瞭，釋放內存不用為每種數據結構適配一套漸進式釋放策略，也不用搞個自適應算法來仔細控制回收頻率。

不過使用異步線程也是有代價的，主線程和異步線程之間在內存回收器 (jemalloc) 的使用上存在競爭。這點競爭消耗是可以忽略不計的，因為 Redis 的主線程在內存的分配與回收上花的時間相對整體運算時間而言是極少的。

異步線程方案相當復雜，具體可參閱引用資料。

2.2 flush

Redis 提供瞭 flushdb 和 flushall 指令，用來清空數據庫，這也是極其緩慢的操作。

Redis 4.0 同樣給這兩個指令也帶來瞭異步化，在指令後面增加 async 參數就可以將整棵大樹拔起，扔給後臺線程慢慢焚燒。

> flushall async

OK

2.3 異步隊列

Redis4.0，主線程將對象的引用從「大樹」中摘除後，會將這個 key 的內存回收操作包裝成一個任務，塞進異步任務隊列，後臺線程會從這個異步隊列中取任務。任務隊列被主線程和異步線程同時操作，所以必須是一個線程安全的隊列。

不是所有的 unlink 操作都會延後處理，如果對應 key 所占用的內存很小，延後處理就沒有必要瞭，這時候 Redis 會將對應的 key 內存立即回收，跟 del 指令一樣。

2.4 AOF Sync很慢的問題

Redis需要每秒一次（可配置）同步AOF日志到磁盤，確保消息盡量不丟失，需要調用sync函數，這個操作會比較耗時，會導致主線程的效率下降，所以Redis也將這個操作移到異步線程來完成。

執行AOF Sync操作的線程是一個獨立的異步線程，和前面的懶惰刪除線程不是一個線程，同樣它也有一個屬於自己的任務隊列，隊列裡隻用來存放AOF Sync任務。

2.5 更多異步刪除點

Redis 回收內存除瞭 del 指令和 flush 之外，還會存在於在 key 的過期、LRU 淘汰、rename 指令以及從庫全量同步時接受完 rdb 文件後會立即進行的 flush 操作。

Redis4.0 為這些刪除點也帶來瞭異步刪除機制，打開這些點需要額外的配置選項。

• slave-lazy-flush 從庫接受完 rdb 文件後的 flush 操作
• lazyfree-lazy-eviction 內存達到 maxmemory 時進行淘汰
• lazyfree-lazy-expire key 過期刪除
• lazyfree-lazy-server-del rename 指令刪除 destKey

3. 過期淘汰配置

當 Redis 已使用內存超出物理內存限制時，內存中的數據會開始和磁盤產生頻繁的交換 (swap)，交換會讓 Redis 的性能急劇下降，而此時Redis的存取效率簡直是龜速（基本上等於不可用）。在生產環境中這是不允許的，為瞭限制最大使用內存，Redis 提供瞭配置參數 maxmemory 來限制內存超出期望大小。

那如果實際內存超出 maxmemory 時該怎麼辦？

Redis提供瞭幾種可選策略 (maxmemory-policy) 來讓用戶自己決定該如何騰出新的空間以繼續提供讀寫服務。

redis.conf中配置

maxmemory <bytes> #最大內存（單位字節）

maxmemory-policy noeviction #默認

小結

• volatile-xxx 策略隻會針對帶過期時間的 key 進行淘汰
• allkeys-xxx 策略會對所有的 key 進行淘汰

那該如何抉擇呢？

如果你隻是拿 Redis 做緩存，那最好使用 allkeys-xxx，客戶端寫緩存時不必攜帶過期時間。

如果你還想同時具備持久化功能，那就使用 volatile-xxx 策略，好處就是，沒有設置過期時間的 key 不會被 LRU 算法淘汰

4. LRU 算法

實現 LRU（最近最少） 算法除瞭需要 key/value 字典外，還需要附加一個鏈表，鏈表中的元素按照一定的順序進行排列。

當空間滿的時候，會踢掉鏈表尾部的元素。當字典的某個元素被訪問時，它在鏈表中的位置會被移動到表頭。所以鏈表的元素排列順序就是元素最近被訪問的時間順序。

4.1 近似 LRU 算法

Redis 使用的是一種近似 LRU 算法，它跟 LRU 算法還不太一樣。之所以不使用 LRU 算法，是因為需要消耗大量的額外的內存，需要對現有的數據結構進行較大的改造。近似 LRU 算法則很簡單，在現有數據結構的基礎上使用隨機采樣法來淘汰元素，能達到和 LRU 算法非常近似的效果。

Redis 為實現近似 LRU 算法，它給每個 key 增加瞭一個額外的小字段，這個字段的長度是 24 個 bit，也就是最後一次被訪問的時間戳。

前面講過key 過期方式分為集中處理和懶惰處理，LRU 淘汰不一樣，它的處理方式隻有懶惰處理。當 Redis 執行寫操作時，發現內存超出 maxmemory，就會執行一次 LRU 淘汰算法。這個算法也很簡單，就是隨機采樣（可以通過maxmemory-policy配置）出 5個 key，然後淘汰掉最舊的 key，如果淘汰後內存還是超出 maxmemory，那就繼續隨機采樣淘汰，直到內存低於 maxmemory為止。

下面是隨機 LRU 算法和嚴格 LRU 算法的效果對比圖：綠色部分是新加入的 key，深灰色部分是老舊的 key，淺灰色部分是通過 LRU 算法淘汰掉的 key。可以看出采樣數量越大，近似 LRU 算法的效果越接近嚴格 LRU 算法。同時 Redis3.0 在算法中增加瞭淘汰池，進一步提升瞭近似 LRU 算法的效果。

淘汰池是一個數組，它的大小是 maxmemory_samples，在每一次淘汰循環中，新隨機出來的 key 列表會和淘汰池中的 key 列表進行融合，淘汰掉最舊的一個 key 之後，保留剩餘較舊的 key 列表放入淘汰池中留待下一個循環。

5. LRU

Redis 4.0 裡引入瞭一個新的淘汰策略 —— LFU （Least Frequently Used）模式，作者認為它比 LRU 更加優秀。它表示按最近的訪問頻率進行淘汰，它比 LRU 更加精準地表示瞭一個 key 被訪問的熱度。

它淘汰策略配置參數maxmemory-policy增加瞭 2 個選項，分別是 volatile-lfu 和 allkeys-lfu，分別是對帶過期時間的 key 進行 lfu 淘汰以及對所有的 key 執行 lfu 淘汰算法。

如果一個 key 長時間不被訪問，隻是剛剛偶然被用戶訪問瞭一下，那麼在使用 LRU 算法下它是不容易被淘汰的，因為 LRU 算法認為當前這個 key 是很熱的。而 LFU 是需要追蹤最近一段時間的訪問頻率，如果某個 key 隻是偶然被訪問一次是不足以變得很熱的，它需要在近期一段時間內被訪問很多次才有機會被認為很熱。

Redis 的所有對象結構頭中都有一個 24bit 的字段，這個字段用來記錄對象的「熱度」。

// redis 的對象頭
typedef struct redisObject {
    unsigned type:4; // 對象類型如 zset/set/hash 等等
    unsigned encoding:4; // 對象編碼如 ziplist/intset/skiplist 等等
    unsigned lru:24; // 對象的「熱度」
    int refcount; // 引用計數
    void *ptr; // 對象的 body
}robj;

5.1 LRU 模式

lru 字段存儲的是 Redis 時鐘server.lruclock，Redis 時鐘是一個 24bit 的整數，默認是 Unix 時間戳對 2^24 取模的結果，大約 97 天清零一次。當某個 key 被訪問一次，它的對象頭的 lru 字段值就會被更新為server.lruclock，該值一直是遞增的，通過這個邏輯就可以精準計算出對象多長時間沒有被訪問——對象的空閑時間。如果超過server.lruclock折返瞭。

有瞭對象的空閑時間，就可以相互之間進行比較誰新誰舊，隨機 LRU 算法靠的就是比較對象的空閑時間來決定誰該被淘汰瞭。

默認 Redis 時鐘值每毫秒更新一次，在定時任務serverCron裡主動設置，在serverCron裡面其實有很多很多定時任務，比如大型 hash 表的漸進式遷移、過期 key 的主動淘汰、觸發 bgsave、bgaofrewrite 等等。

為什麼 Redis 要緩存系統時間戳？

在java中我們使用System.currentTimeInMillis()，而Redis 不能這樣，因為每一次獲取系統時間戳都是一次系統調用，系統調用相對來說是比較費時間的，這樣的消耗對redis而言是傷不起的，所以獲取時間都直接從緩存中直接拿。

5.2 LFU 模式

lru 字段 24 個 bit 用來存儲兩個值，分別是ldt(last decrement time)和logc(logistic counter)。

logc是 8 個 bit，用來存儲訪問頻次（最大整數值為 255）。存儲頻次遠遠不夠（太小），所以這 8 個 bit 存儲的是頻次的對數值，並且這個值還會隨時間衰減。如果它的值比較小，就很容易被回收，為瞭確保新創建的對象不被回收，新對象的初始化默認是LFU_INIT_VAL=5。

ldt 是 16 個位，用來存儲上一次 logc 的更新時間（精度不可能很高），它取的是分鐘時間戳對 2^16 進行取模，大約每隔 45 天就會折返。同 LRU 模式一樣，我們也可以使用這個邏輯計算出對象的空閑時間，隻不過精度是分鐘級別的。

server.unixtime 是當前 redis 記錄的系統時間戳，和 server.lruclock 一樣，它也是每毫秒更新一次。

// nowInMinutes
// server.unixtime 為 redis 緩存的系統時間戳
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}
// idle_in_minutes
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt; // 正常比較
    return 65535-ldt+now; // 折返比較
}

ldt 的值不是在對象被訪問時更新的，它在 Redis 的淘汰邏輯進行時進行更新，淘汰邏輯隻會在內存達到 maxmemory 的設置時才會觸發，在每一個指令的執行之前都會觸發。每次淘汰都是采用隨機策略，隨機挑選若幹個 key，更新這個 key 的「熱度」，淘汰掉「熱度」最低的。因為 Redis 采用的是隨機算法，如果 key 比較多的話，那麼 ldt 更新的可能會比較慢。不過既然它是分鐘級別的精度，也沒有必要更新的過於頻繁。

ldt 更新的同時也會一同衰減 logc 的值，衰減也有特定的算法。它將現有的 logc 值減去對象的空閑時間 (分鐘數) 除以一個衰減系數，默認這個衰減系數lfu_decay_time是 1。如果這個值大於 1，那麼就會衰減的比較慢。如果它等於零，那就表示不衰減，它是可以通過配置參數lfu_decay_time進行配置。

logc 的更新和 LRU 模式的 lru 字段一樣，都會在 key 每次被訪問的時候更新，隻不過它的更新不是簡單的+1，而是采用概率法進行遞增，因為 logc 存儲的是訪問計數的對數值，不能直接+1。

總結，通過LFU 和LRU的介紹，我們知道redis的設計有多優秀，不浪費一丁點內存！

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：

• Redis 的內存淘汰策略和過期刪除策略的區別
• redis 限制內存使用大小的實現
• Redis緩存更新策略詳解
• 淺談Redis對於過期鍵的三種清除策略
• 淺談Redis中的內存淘汰策略和過期鍵刪除策略