之前看到過一道面試題：Redis 的過期策略都有哪些?內(nèi)存淘汰機制都有哪些?手寫一下 LRU 代碼實現(xiàn)?

[[278052]] 

圖片來自 Pexels

筆者結(jié)合在工作上遇到的問題學(xué)習(xí)分析，希望看完這篇文章能對大家有所幫助。

從一次不可描述的故障說起

問題描述：一個依賴于定時器任務(wù)的生成的接口列表數(shù)據(jù)，時而有，時而沒有。

懷疑是 Redis 過期刪除策略

排查過程長，因為手動執(zhí)行定時器，Set 數(shù)據(jù)沒有報錯，但是 Set 數(shù)據(jù)之后不生效。

Set 沒報錯，但是 Set 完再查的情況下沒數(shù)據(jù)，開始懷疑 Redis 的過期刪除策略(準(zhǔn)確來說應(yīng)該是 Redis 的內(nèi)存回收機制中的數(shù)據(jù)淘汰策略觸發(fā)內(nèi)存上限淘汰數(shù)據(jù))，導(dǎo)致新加入 Redis 的數(shù)據(jù)都被丟棄了。

最終發(fā)現(xiàn)故障的原因是因為配置錯了，導(dǎo)致數(shù)據(jù)寫錯地方，并不是 Redis 的內(nèi)存回收機制引起。

通過這次故障后思考總結(jié)，如果下一次遇到類似的問題，在懷疑 Redis 的內(nèi)存回收之后，如何有效地證明它的正確性?如何快速證明猜測的正確與否?以及什么情況下懷疑內(nèi)存回收才是合理的呢?

下一次如果再次遇到類似問題，就能夠更快更準(zhǔn)地定位問題的原因。另外，Redis 的內(nèi)存回收機制原理也需要掌握，明白是什么，為什么。

花了點時間查閱資料研究 Redis 的內(nèi)存回收機制，并閱讀了內(nèi)存回收的實現(xiàn)代碼，通過代碼結(jié)合理論，給大家分享一下 Redis 的內(nèi)存回收機制。

為什么需要內(nèi)存回收?

原因有如下兩點：

• 在 Redis 中，Set 指令可以指定 Key 的過期時間，當(dāng)過期時間到達以后，Key 就失效了。
• Redis 是基于內(nèi)存操作的，所有的數(shù)據(jù)都是保存在內(nèi)存中，一臺機器的內(nèi)存是有限且很寶貴的。

基于以上兩點，為了保證 Redis 能繼續(xù)提供可靠的服務(wù)，Redis 需要一種機制清理掉不常用的、無效的、多余的數(shù)據(jù)，失效后的數(shù)據(jù)需要及時清理，這就需要內(nèi)存回收了。

Redis 的內(nèi)存回收機制

Redis 的內(nèi)存回收主要分為過期刪除策略和內(nèi)存淘汰策略兩部分。

過期刪除策略

刪除達到過期時間的 Key。

①定時刪除

對于每一個設(shè)置了過期時間的 Key 都會創(chuàng)建一個定時器，一旦到達過期時間就立即刪除。

該策略可以立即清除過期的數(shù)據(jù)，對內(nèi)存較友好，但是缺點是占用了大量的 CPU 資源去處理過期的數(shù)據(jù)，會影響 Redis 的吞吐量和響應(yīng)時間。

②惰性刪除

當(dāng)訪問一個 Key 時，才判斷該 Key 是否過期，過期則刪除。該策略能最大限度地節(jié)省 CPU 資源，但是對內(nèi)存卻十分不友好。

有一種極端的情況是可能出現(xiàn)大量的過期 Key 沒有被再次訪問，因此不會被清除，導(dǎo)致占用了大量的內(nèi)存。

在計算機科學(xué)中，懶惰刪除(英文：lazy deletion)指的是從一個散列表(也稱哈希表)中刪除元素的一種方法。

在這個方法中，刪除僅僅是指標(biāo)記一個元素被刪除，而不是整個清除它。被刪除的位點在插入時被當(dāng)作空元素，在搜索之時被當(dāng)作已占據(jù)。

③定期刪除

每隔一段時間，掃描 Redis 中過期 Key 字典，并清除部分過期的 Key。該策略是前兩者的一個折中方案，還可以通過調(diào)整定時掃描的時間間隔和每次掃描的限定耗時，在不同情況下使得 CPU 和內(nèi)存資源達到最優(yōu)的平衡效果。

在 Redis 中，同時使用了定期刪除和惰性刪除。

過期刪除策略原理

為了大家聽起來不會覺得疑惑，在正式介紹過期刪除策略原理之前，先給大家介紹一點可能會用到的相關(guān) Redis 基礎(chǔ)知識。

①RedisDB 結(jié)構(gòu)體定義

我們知道，Redis 是一個鍵值對數(shù)據(jù)庫，對于每一個 Redis 數(shù)據(jù)庫，Redis 使用一個 RedisDB 的結(jié)構(gòu)體來保存，它的結(jié)構(gòu)如下：

typedef struct redisDb { 
        dict *dict;                 /* 數(shù)據(jù)庫的鍵空間，保存數(shù)據(jù)庫中的所有鍵值對 */ 
        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;                     /* 數(shù)據(jù)庫ID字段，代表不同的數(shù)據(jù)庫 */ 
        long long avg_ttl;          /* Average TTL, just for stats */ 
} redisDb; 

從結(jié)構(gòu)定義中我們可以發(fā)現(xiàn)，對于每一個 Redis 數(shù)據(jù)庫，都會使用一個字典的數(shù)據(jù)結(jié)構(gòu)來保存每一個鍵值對，dict 的結(jié)構(gòu)圖如下：

 

以上就是過期策略實現(xiàn)時用到比較核心的數(shù)據(jù)結(jié)構(gòu)。程序=數(shù)據(jù)結(jié)構(gòu)+算法，介紹完數(shù)據(jù)結(jié)構(gòu)以后，接下來繼續(xù)看看處理的算法是怎樣的。

②expires 屬性

RedisDB 定義的第二個屬性是 expires，它的類型也是字典，Redis 會把所有過期的鍵值對加入到 expires，之后再通過定期刪除來清理 expires 里面的值。

加入 expires 的場景有：

• Set 指定過期時間 expire，如果設(shè)置 Key 的時候指定了過期時間，Redis 會將這個 Key 直接加入到 expires 字典中，并將超時時間設(shè)置到該字典元素。
• 調(diào)用 expire 命令，顯式指定某個 Key 的過期時間。
• 恢復(fù)或修改數(shù)據(jù)，從 Redis 持久化文件中恢復(fù)文件或者修改 Key，如果數(shù)據(jù)中的 Key 已經(jīng)設(shè)置了過期時間，就將這個 Key 加入到 expires 字典中。

以上這些操作都會將過期的 Key 保存到 expires。Redis 會定期從 expires 字典中清理過期的 Key。

③Redis 清理過期 Key 的時機

Redis 在啟動的時候，會注冊兩種事件，一種是時間事件，另一種是文件事件。時間事件主要是 Redis 處理后臺操作的一類事件，比如客戶端超時、刪除過期 Key;文件事件是處理請求。

在時間事件中，Redis 注冊的回調(diào)函數(shù)是 serverCron，在定時任務(wù)回調(diào)函數(shù)中，通過調(diào)用 databasesCron 清理部分過期 Key。(這是定期刪除的實現(xiàn)。)

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) 
{ 
    … 
    /* Handle background operations on Redis databases. */ 
    databasesCron(); 
    ... 
} 

每次訪問 Key 的時候，都會調(diào)用 expireIfNeeded 函數(shù)判斷 Key 是否過期，如果是，清理 Key。(這是惰性刪除的實現(xiàn))

robj *lookupKeyRead(redisDb *db, robj *key) { 
    robj *val; 
    expireIfNeeded(db,key); 
    val = lookupKey(db,key); 
     ... 
    return val; 
} 

每次事件循環(huán)執(zhí)行時，主動清理部分過期 Key。(這也是惰性刪除的實現(xiàn))

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); 
       ... 
   } 

④過期策略的實現(xiàn)

我們知道，Redis 是以單線程運行的，在清理 Key 時不能占用過多的時間和 CPU，需要在盡量不影響正常的服務(wù)情況下，進行過期 Key 的清理。

過期清理的算法如下：

• server.hz 配置了 serverCron 任務(wù)的執(zhí)行周期，默認是 10，即 CPU 空閑時每秒執(zhí)行十次。
• 每次清理過期 Key 的時間不能超過 CPU 時間的 25%：timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100。
• 比如，如果 hz=1，一次清理的最大時間為 250ms，hz=10，一次清理的最大時間為 25ms。
• 如果是快速清理模式(在 beforeSleep 函數(shù)調(diào)用)，則一次清理的最大時間是 1ms。
• 依次遍歷所有的 DB。
• 從 DB 的過期列表中隨機取 20 個 Key，判斷是否過期，如果過期，則清理。
• 如果有 5 個以上的 Key 過期，則重復(fù)步驟 5，否則繼續(xù)處理下一個 DB。
• 在清理過程中，如果達到 CPU 的 25% 時間，退出清理過程。

從實現(xiàn)的算法中可以看出，這只是基于概率的簡單算法，且是隨機的抽取，因此是無法刪除所有的過期 Key，通過調(diào)高 hz 參數(shù)可以提升清理的頻率，過期 Key 可以更及時的被刪除，但 hz 太高會增加 CPU 時間的消耗。

⑤刪除 Key

Redis 4.0 以前，刪除指令是 del，del 會直接釋放對象的內(nèi)存，大部分情況下，這個指令非?？?，沒有任何延遲的感覺。

但是，如果刪除的 Key 是一個非常大的對象，比如一個包含了千萬元素的 Hash，那么刪除操作就會導(dǎo)致單線程卡頓，Redis 的響應(yīng)就慢了。

為了解決這個問題，在 Redis 4.0 版本引入了 unlink 指令，能對刪除操作進行“懶”處理，將刪除操作丟給后臺線程，由后臺線程來異步回收內(nèi)存。

實際上，在判斷 Key 需要過期之后，真正刪除 Key 的過程是先廣播 expire 事件到從庫和 AOF 文件中，然后在根據(jù) Redis 的配置決定立即刪除還是異步刪除。

如果是立即刪除，Redis 會立即釋放 Key 和 Value 占用的內(nèi)存空間，否則，Redis 會在另一個 BIO 線程中釋放需要延遲刪除的空間。

小結(jié)：總的來說，Redis 的過期刪除策略是在啟動時注冊了 serverCron 函數(shù)，每一個時間時鐘周期，都會抽取 expires 字典中的部分 Key 進行清理，從而實現(xiàn)定期刪除。

另外，Redis 會在訪問 Key 時判斷 Key 是否過期，如果過期了，就刪除，以及每一次 Redis 訪問事件到來時，beforeSleep 都會調(diào)用 activeExpireCycle 函數(shù)，在 1ms 時間內(nèi)主動清理部分 Key，這是惰性刪除的實現(xiàn)。

Redis 結(jié)合了定期刪除和惰性刪除，基本上能很好的處理過期數(shù)據(jù)的清理，但是實際上還是有點問題的。

如果過期 Key 較多，定期刪除漏掉了一部分，而且也沒有及時去查，即沒有走惰性刪除，那么就會有大量的過期 Key 堆積在內(nèi)存中，導(dǎo)致 Redis 內(nèi)存耗盡。

當(dāng)內(nèi)存耗盡之后，有新的 Key 到來會發(fā)生什么事呢?是直接拋棄還是其他措施呢?有什么辦法可以接受更多的 Key?

內(nèi)存淘汰策略

Redis 的內(nèi)存淘汰策略，是指內(nèi)存達到 maxmemory 極限時，使用某種算法來決定清理掉哪些數(shù)據(jù)，以保證新數(shù)據(jù)的存入。

Redis 的內(nèi)存淘汰機制如下：

• noeviction：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，新寫入操作會報錯。
• allkeys-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，在鍵空間(server.db[i].dict)中，移除最近最少使用的 Key(這個是最常用的)。
• allkeys-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，在鍵空間(server.db[i].dict)中，隨機移除某個 Key。
• volatile-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設(shè)置了過期時間的鍵空間(server.db[i].expires)中，移除最近最少使用的 Key。
• volatile-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設(shè)置了過期時間的鍵空間(server.db[i].expires)中，隨機移除某個 Key。
• volatile-ttl：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設(shè)置了過期時間的鍵空間(server.db[i].expires)中，有更早過期時間的 Key 優(yōu)先移除。

在配置文件中，通過 maxmemory-policy 可以配置要使用哪一個淘汰機制。

①什么時候會進行淘汰?

Redis 會在每一次處理命令的時候(processCommand 函數(shù)調(diào)用 freeMemoryIfNeeded)判斷當(dāng)前 Redis 是否達到了內(nèi)存的最大限制，如果達到限制，則使用對應(yīng)的算法去處理需要刪除的 Key。

偽代碼如下：

int processCommand(client *c) 
{ 
    ... 
    if (server.maxmemory) { 
        int retval = freeMemoryIfNeeded();   
    } 
    ... 
} 

②LRU 實現(xiàn)原理

在淘汰 Key 時，Redis 默認最常用的是 LRU 算法(Latest Recently Used)。

Redis 通過在每一個 redisObject 保存 lRU 屬性來保存 Key 最近的訪問時間，在實現(xiàn) LRU 算法時直接讀取 Key 的 lRU 屬性。

具體實現(xiàn)時，Redis 遍歷每一個 DB，從每一個 DB 中隨機抽取一批樣本 Key，默認是 3 個 Key，再從這 3 個 Key 中，刪除最近最少使用的 Key。

實現(xiàn)偽代碼如下：

keys = getSomeKeys(dict, sample) 
key = findSmallestIdle(keys) 
remove(key) 

3 這個數(shù)字是配置文件中的 maxmeory-samples 字段，也是可以設(shè)置采樣的大小，如果設(shè)置為 10，那么效果會更好，不過也會耗費更多的 CPU 資源。

以上就是 Redis 內(nèi)存回收機制的原理介紹，了解了上面的原理介紹后，回到一開始的問題，在懷疑 Redis 內(nèi)存回收機制的時候能不能及時判斷故障是不是因為 Redis 的內(nèi)存回收機制導(dǎo)致的呢?

回到問題原點

如何證明故障是不是由內(nèi)存回收機制引起的?根據(jù)前面分析的內(nèi)容，如果 Set 沒有報錯，但是不生效，只有兩種情況：

• 設(shè)置的過期時間過短，比如，1s。
• 內(nèi)存超過了最大限制，且設(shè)置的是 noeviction 或者 allkeys-random。

因此，在遇到這種情況，首先看 Set 的時候是否加了過期時間，且過期時間是否合理，如果過期時間較短，那么應(yīng)該檢查一下設(shè)計是否合理。

如果過期時間沒問題，那就需要查看 Redis 的內(nèi)存使用率，查看 Redis 的配置文件或者在 Redis 中使用 Info 命令查看 Redis 的狀態(tài)，maxmemory 屬性查看最大內(nèi)存值。

如果是 0，則沒有限制，此時是通過 total_system_memory 限制，對比 used_memory 與 Redis 最大內(nèi)存，查看內(nèi)存使用率。

如果當(dāng)前的內(nèi)存使用率較大，那么就需要查看是否有配置最大內(nèi)存，如果有且內(nèi)存超了，那么就可以初步判定是內(nèi)存回收機制導(dǎo)致 Key 設(shè)置不成功。

還需要查看內(nèi)存淘汰算法是否 noeviction 或者 allkeys-random，如果是，則可以確認是 Redis 的內(nèi)存回收機制導(dǎo)致。

如果內(nèi)存沒有超，或者內(nèi)存淘汰算法不是上面的兩者，則還需要看看 Key 是否已經(jīng)過期，通過 TTL 查看 Key 的存活時間。

 

如果運行了程序，Set 沒有報錯，則 TTL 應(yīng)該馬上更新，否則說明 Set 失敗，如果 Set 失敗了那么就應(yīng)該查看操作的程序代碼是否正確了。

總結(jié)

Redis 對于內(nèi)存的回收有兩種方式，一種是過期 Key 的回收，另一種是超過 Redis 的最大內(nèi)存后的內(nèi)存釋放。

對于第一種情況，Redis 會在：

• 每一次訪問的時候判斷 Key 的過期時間是否到達，如果到達，就刪除 Key。
• Redis 啟動時會創(chuàng)建一個定時事件，會定期清理部分過期的 Key，默認是每秒執(zhí)行十次檢查，每次過期 Key 清理的時間不超過 CPU 時間的 25%。

即若 hz=1，則一次清理時間最大為 250ms，若 hz=10，則一次清理時間最大為 25ms。

對于第二種情況，Redis 會在每次處理 Redis 命令的時候判斷當(dāng)前 Redis 是否達到了內(nèi)存的最大限制，如果達到限制，則使用對應(yīng)的算法去處理需要刪除的 Key。

看完這篇文章后，你能回答文章開頭的面試題了嗎?