之前看到過一道面試題：Redis 的過期政策都有哪些?記憶體淘汰機制都有哪些?手寫一下 LRU 代碼實作?
圖檔來自 Pexels
筆者結合在工作上遇到的問題學習分析，希望看完這篇文章能對大家有所幫助。
從一次不可描述的故障說起
問題描述：一個依賴于定時器任務的生成的接口清單資料，時而有，時而沒有。
懷疑是 Redis 過期删除政策
排查過程長，因為手動執行定時器，Set 資料沒有報錯，但是 Set 資料之後不生效。
Set 沒報錯，但是 Set 完再查的情況下沒資料，開始懷疑 Redis 的過期删除政策(準确來說應該是 Redis 的記憶體回收機制中的資料淘汰政策觸發記憶體上限淘汰資料)，導緻新加入 Redis 的資料都被丢棄了。
最終發現故障的原因是因為配置錯了，導緻資料寫錯地方，并不是 Redis 的記憶體回收機制引起。
通過這次故障後思考總結，如果下一次遇到類似的問題，在懷疑 Redis 的記憶體回收之後，如何有效地證明它的正确性?如何快速證明猜測的正确與否?以及什麼情況下懷疑記憶體回收才是合理的呢?
下一次如果再次遇到類似問題，就能夠更快更準地定位問題的原因。另外，Redis 的記憶體回收機制原理也需要掌握，明白是什麼，為什麼。
花了點時間查閱資料研究 Redis 的記憶體回收機制，并閱讀了記憶體回收的實作代碼，通過代碼結合理論，給大家分享一下 Redis 的記憶體回收機制。
為什麼需要記憶體回收?
原因有如下兩點：
- 在 Redis 中，Set 指令可以指定 Key 的過期時間，當過期時間到達以後，Key 就失效了。
- Redis 是基于記憶體操作的，所有的資料都是儲存在記憶體中，一台機器的記憶體是有限且很寶貴的。
基于以上兩點，為了保證 Redis 能繼續提供可靠的服務，Redis 需要一種機制清理掉不常用的、無效的、多餘的資料，失效後的資料需要及時清理，這就需要記憶體回收了。
Redis 的記憶體回收機制
Redis 的記憶體回收主要分為過期删除政策和記憶體淘汰政策兩部分。
過期删除政策
删除達到過期時間的 Key。
①定時删除
對于每一個設定了過期時間的 Key 都會建立一個定時器，一旦到達過期時間就立即删除。
該政策可以立即清除過期的資料，對記憶體較友好，但是缺點是占用了大量的 CPU 資源去處理過期的資料，會影響 Redis 的吞吐量和響應時間。
②惰性删除
當通路一個 Key 時，才判斷該 Key 是否過期，過期則删除。該政策能最大限度地節省 CPU 資源，但是對記憶體卻十分不友好。
有一種極端的情況是可能出現大量的過期 Key 沒有被再次通路，是以不會被清除，導緻占用了大量的記憶體。
在計算機科學中，懶惰删除(英文：lazy deletion)指的是從一個散清單(也稱哈希表)中删除元素的一種方法。
在這個方法中，删除僅僅是名額記一個元素被删除，而不是整個清除它。被删除的位點在插入時被當作空元素，在搜尋之時被當作已占據。
③定期删除
每隔一段時間，掃描 Redis 中過期 Key 字典，并清除部分過期的 Key。該政策是前兩者的一個折中方案，還可以通過調整定時掃描的時間間隔和每次掃描的限定耗時，在不同情況下使得 CPU 和記憶體資源達到最優的平衡效果。
在 Redis 中，同時使用了定期删除和惰性删除。
過期删除政策原理
為了大家聽起來不會覺得疑惑，在正式介紹過期删除政策原理之前，先給大家介紹一點可能會用到的相關 Redis 基礎知識。
①RedisDB 結構體定義
我們知道，Redis 是一個鍵值對資料庫，對于每一個 Redis 資料庫，Redis 使用一個 RedisDB 的結構體來儲存，它的結構如下：
typedef struct redisDb { dict *dict; /* 資料庫的鍵空間，儲存資料庫中的所有鍵值對 */ dict *expires; /* 儲存所有過期的鍵 */ dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/ dict *ready_keys; /* Blocked keys that received a PUSH */ dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ int id; /* 資料庫ID字段，代表不同的資料庫 */ long long avg_ttl; /* Average TTL, just for stats */ } redisDb;
從結構定義中我們可以發現，對于每一個 Redis 資料庫，都會使用一個字典的資料結構來儲存每一個鍵值對，dict 的結構圖如下：
以上就是過期政策實作時用到比較核心的資料結構。程式=資料結構+算法，介紹完資料結構以後，接下來繼續看看處理的算法是怎樣的。
②expires 屬性
RedisDB 定義的第二個屬性是 expires，它的類型也是字典，Redis 會把所有過期的鍵值對加入到 expires，之後再通過定期删除來清理 expires 裡面的值。
加入 expires 的場景有：
- Set 指定過期時間 expire，如果設定 Key 的時候指定了過期時間，Redis 會将這個 Key 直接加入到 expires 字典中，并将逾時時間設定到該字典元素。
- 調用 expire 指令，顯式指定某個 Key 的過期時間。
- 恢複或修改資料，從 Redis 持久化檔案中恢複檔案或者修改 Key，如果資料中的 Key 已經設定了過期時間，就将這個 Key 加入到 expires 字典中。
以上這些操作都會将過期的 Key 儲存到 expires。Redis 會定期從 expires 字典中清理過期的 Key。
③Redis 清理過期 Key 的時機
Redis 在啟動的時候，會注冊兩種事件，一種是時間事件，另一種是檔案事件。時間事件主要是 Redis 處理背景操作的一類事件，比如用戶端逾時、删除過期 Key;檔案事件是處理請求。
在時間事件中，Redis 注冊的回調函數是 serverCron，在定時任務回調函數中，通過調用 databasesCron 清理部分過期 Key。(這是定期删除的實作。)
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { … /* Handle background operations on Redis databases. */ databasesCron(); ... }
每次通路 Key 的時候，都會調用 expireIfNeeded 函數判斷 Key 是否過期，如果是，清理 Key。(這是惰性删除的實作)
robj *lookupKeyRead(redisDb *db, robj *key) { robj *val; expireIfNeeded(db,key); val = lookupKey(db,key); ... return val; }
每次事件循環執行時，主動清理部分過期 Key。(這也是惰性删除的實作)
void aeMain(aeEventLoop *eventLoop) { eventLoop->stop = 0; while (!eventLoop->stop) { if (eventLoop->beforesleep != NULL) eventLoop->beforesleep(eventLoop); aeProcessEvents(eventLoop, AE_ALL_EVENTS); } } void beforeSleep(struct aeEventLoop *eventLoop) { ... /* Run a fast expire cycle (the called function will return - ASAP if a fast cycle is not needed). */ if (server.active_expire_enabled && server.masterhost == NULL) activeExpireCycle(ACTIVE_EXPIRE_CYCLE_FAST); ... }
④過期政策的實作
我們知道，Redis 是以單線程運作的，在清理 Key 時不能占用過多的時間和 CPU，需要在盡量不影響正常的服務情況下，進行過期 Key 的清理。
過期清理的算法如下：
- server.hz 配置了 serverCron 任務的執行周期，預設是 10，即 CPU 空閑時每秒執行十次。
- 每次清理過期 Key 的時間不能超過 CPU 時間的 25%：timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100。
- 比如，如果 hz=1，一次清理的最大時間為 250ms，hz=10，一次清理的最大時間為 25ms。
- 如果是快速清理模式(在 beforeSleep 函數調用)，則一次清理的最大時間是 1ms。
- 依次周遊所有的 DB。
- 從 DB 的過期清單中随機取 20 個 Key，判斷是否過期，如果過期，則清理。
- 如果有 5 個以上的 Key 過期，則重複步驟 5，否則繼續處理下一個 DB。
- 在清理過程中，如果達到 CPU 的 25% 時間，退出清理過程。
從實作的算法中可以看出，這隻是基于機率的簡單算法，且是随機的抽取，是以是無法删除所有的過期 Key，通過調高 hz 參數可以提升清理的頻率，過期 Key 可以更及時的被删除，但 hz 太高會增加 CPU 時間的消耗。
⑤删除 Key
Redis 4.0 以前，删除指令是 del，del 會直接釋放對象的記憶體，大部分情況下，這個指令非常快，沒有任何延遲的感覺。
但是，如果删除的 Key 是一個非常大的對象，比如一個包含了千萬元素的 Hash，那麼删除操作就會導緻單線程卡頓，Redis 的響應就慢了。
為了解決這個問題，在 Redis 4.0 版本引入了 unlink 指令，能對删除操作進行“懶”處理，将删除操作丢給背景線程，由背景線程來異步回收記憶體。
實際上，在判斷 Key 需要過期之後，真正删除 Key 的過程是先廣播 expire 事件到從庫和 AOF 檔案中，然後在根據 Redis 的配置決定立即删除還是異步删除。
如果是立即删除，Redis 會立即釋放 Key 和 Value 占用的記憶體空間，否則，Redis 會在另一個 BIO 線程中釋放需要延遲删除的空間。
小結：總的來說，Redis 的過期删除政策是在啟動時注冊了 serverCron 函數，每一個時間時鐘周期，都會抽取 expires 字典中的部分 Key 進行清理，進而實作定期删除。
另外，Redis 會在通路 Key 時判斷 Key 是否過期，如果過期了，就删除，以及每一次 Redis 通路事件到來時，beforeSleep 都會調用 activeExpireCycle 函數，在 1ms 時間内主動清理部分 Key，這是惰性删除的實作。
Redis 結合了定期删除和惰性删除，基本上能很好的處理過期資料的清理，但是實際上還是有點問題的。
如果過期 Key 較多，定期删除漏掉了一部分，而且也沒有及時去查，即沒有走惰性删除，那麼就會有大量的過期 Key 堆積在記憶體中，導緻 Redis 記憶體耗盡。
當記憶體耗盡之後，有新的 Key 到來會發生什麼事呢?是直接抛棄還是其他措施呢?有什麼辦法可以接受更多的 Key?
記憶體淘汰政策
Redis 的記憶體淘汰政策，是指記憶體達到 maxmemory 極限時，使用某種算法來決定清理掉哪些資料，以保證新資料的存入。
Redis 的記憶體淘汰機制如下：
- noeviction：當記憶體不足以容納新寫入資料時，新寫入操作會報錯。
- allkeys-lru：當記憶體不足以容納新寫入資料時，在鍵空間(server.db[i].dict)中，移除最近最少使用的 Key(這個是最常用的)。
- allkeys-random：當記憶體不足以容納新寫入資料時，在鍵空間(server.db[i].dict)中，随機移除某個 Key。
- volatile-lru：當記憶體不足以容納新寫入資料時，在設定了過期時間的鍵空間(server.db[i].expires)中，移除最近最少使用的 Key。
- volatile-random：當記憶體不足以容納新寫入資料時，在設定了過期時間的鍵空間(server.db[i].expires)中，随機移除某個 Key。
- volatile-ttl：當記憶體不足以容納新寫入資料時，在設定了過期時間的鍵空間(server.db[i].expires)中，有更早過期時間的 Key 優先移除。
在配置檔案中，通過 maxmemory-policy 可以配置要使用哪一個淘汰機制。
①什麼時候會進行淘汰?
Redis 會在每一次處理指令的時候(processCommand 函數調用 freeMemoryIfNeeded)判斷目前 Redis 是否達到了記憶體的最大限制，如果達到限制，則使用對應的算法去處理需要删除的 Key。
僞代碼如下：
int processCommand(client *c) { ... if (server.maxmemory) { int retval = freeMemoryIfNeeded(); } ... }
②LRU 實作原理
在淘汰 Key 時，Redis 預設最常用的是 LRU 算法(Latest Recently Used)。
Redis 通過在每一個 redisObject 儲存 lRU 屬性來儲存 Key 最近的通路時間，在實作 LRU 算法時直接讀取 Key 的 lRU 屬性。
具體實作時，Redis 周遊每一個 DB，從每一個 DB 中随機抽取一批樣本 Key，預設是 3 個 Key，再從這 3 個 Key 中，删除最近最少使用的 Key。
實作僞代碼如下：
keys = getSomeKeys(dict, sample) key = findSmallestIdle(keys) remove(key)
3 這個數字是配置檔案中的 maxmeory-samples 字段，也是可以設定采樣的大小，如果設定為 10，那麼效果會更好，不過也會耗費更多的 CPU 資源。
以上就是 Redis 記憶體回收機制的原理介紹，了解了上面的原理介紹後，回到一開始的問題，在懷疑 Redis 記憶體回收機制的時候能不能及時判斷故障是不是因為 Redis 的記憶體回收機制導緻的呢?
回到問題原點
如何證明故障是不是由記憶體回收機制引起的?根據前面分析的内容，如果 Set 沒有報錯，但是不生效，隻有兩種情況：
- 設定的過期時間過短，比如，1s。
- 記憶體超過了最大限制，且設定的是 noeviction 或者 allkeys-random。
是以，在遇到這種情況，首先看 Set 的時候是否加了過期時間，且過期時間是否合理，如果過期時間較短，那麼應該檢查一下設計是否合理。
如果過期時間沒問題，那就需要檢視 Redis 的記憶體使用率，檢視 Redis 的配置檔案或者在 Redis 中使用 Info 指令檢視 Redis 的狀态，maxmemory 屬性檢視最大記憶體值。
如果是 0，則沒有限制，此時是通過 total_system_memory 限制，對比 used_memory 與 Redis 最大記憶體，檢視記憶體使用率。
如果目前的記憶體使用率較大，那麼就需要檢視是否有配置最大記憶體，如果有且記憶體超了，那麼就可以初步判定是記憶體回收機制導緻 Key 設定不成功。
還需要檢視記憶體淘汰算法是否 noeviction 或者 allkeys-random，如果是，則可以确認是 Redis 的記憶體回收機制導緻。
如果記憶體沒有超，或者記憶體淘汰算法不是上面的兩者，則還需要看看 Key 是否已經過期，通過 TTL 檢視 Key 的存活時間。
如果運作了程式，Set 沒有報錯，則 TTL 應該馬上更新，否則說明 Set 失敗，如果 Set 失敗了那麼就應該檢視操作的程式代碼是否正确了。
總結
Redis 對于記憶體的回收有兩種方式，一種是過期 Key 的回收，另一種是超過 Redis 的最大記憶體後的記憶體釋放。
對于第一種情況，Redis 會在：
- 每一次通路的時候判斷 Key 的過期時間是否到達，如果到達，就删除 Key。
- Redis 啟動時會建立一個定時事件，會定期清理部分過期的 Key，預設是每秒執行十次檢查，每次過期 Key 清理的時間不超過 CPU 時間的 25%。
即若 hz=1，則一次清理時間最大為 250ms，若 hz=10，則一次清理時間最大為 25ms。
對于第二種情況，Redis 會在每次處理 Redis 指令的時候判斷目前 Redis 是否達到了記憶體的最大限制，如果達到限制，則使用對應的算法去處理需要删除的 Key。
看完這篇文章後，你能回答文章開頭的面試題了嗎?