前言：
之前看到過一道面試題：redis的過期策略都有哪些？內(nèi)存淘汰機(jī)制都有哪些？手寫一下LRU代碼實現(xiàn)？筆者結(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)存回收機(jī)制中的數(shù)據(jù)淘汰策略觸發(fā)內(nèi)存上限淘汰數(shù)據(jù)。），導(dǎo)致新加入Redis的數(shù)據(jù)都被丟棄了。最終發(fā)現(xiàn)故障的原因是因為配置錯了，導(dǎo)致數(shù)據(jù)寫錯地方，并不是Redis的內(nèi)存回收機(jī)制引起。
通過這次故障后思考總結(jié)，如果下一次遇到類似的問題，在懷疑Redis的內(nèi)存回收之后，如何有效地證明它的正確性？如何快速證明猜測的正確與否？以及什么情況下懷疑內(nèi)存回收才是合理的呢？下一次如果再次遇到類似問題，就能夠更快更準(zhǔn)地定位問題的原因。另外，Redis的內(nèi)存回收機(jī)制原理也需要掌握，明白是什么，為什么。
花了點時間查閱資料研究Redis的內(nèi)存回收機(jī)制，并閱讀了內(nèi)存回收的實現(xiàn)代碼，通過代碼結(jié)合理論，給大家分享一下Redis的內(nèi)存回收機(jī)制。
為什么需要內(nèi)存回收？
- 1、在Redis中，set指令可以指定key的過期時間，當(dāng)過期時間到達(dá)以后，key就失效了；
- 2、Redis是基于內(nèi)存操作的，所有的數(shù)據(jù)都是保存在內(nèi)存中，一臺機(jī)器的內(nèi)存是有限且很寶貴的。
基于以上兩點，為了保證Redis能繼續(xù)提供可靠的服務(wù)，Redis需要一種機(jī)制清理掉不常用的、無效的、多余的數(shù)據(jù)，失效后的數(shù)據(jù)需要及時清理，這就需要內(nèi)存回收了。
Redis的內(nèi)存回收機(jī)制
Redis的內(nèi)存回收主要分為過期刪除策略和內(nèi)存淘汰策略兩部分。
過期刪除策略
刪除達(dá)到過期時間的key。
1、定時刪除
對于每一個設(shè)置了過期時間的key都會創(chuàng)建一個定時器，一旦到達(dá)過期時間就立即刪除。該策略可以立即清除過期的數(shù)據(jù)，對內(nèi)存較友好，但是缺點是占用了大量的CPU資源去處理過期的數(shù)據(jù)，會影響Redis的吞吐量和響應(yīng)時間。
2、惰性刪除
當(dāng)訪問一個key時，才判斷該key是否過期，過期則刪除。該策略能最大限度地節(jié)省CPU資源，但是對內(nèi)存卻十分不友好。有一種極端的情況是可能出現(xiàn)大量的過期key沒有被再次訪問，因此不會被清除，導(dǎo)致占用了大量的內(nèi)存。
在計算機(jī)科學(xué)中，懶惰刪除（英文：lazy deletion）指的是從一個散列表（也稱哈希表）中刪除元素的一種方法。在這個方法中，刪除僅僅是指標(biāo)記一個元素被刪除，而不是整個清除它。被刪除的位點在插入時被當(dāng)作空元素，在搜索之時被當(dāng)作已占據(jù)。
3、定期刪除
每隔一段時間，掃描Redis中過期key字典，并清除部分過期的key。該策略是前兩者的一個折中方案，還可以通過調(diào)整定時掃描的時間間隔和每次掃描的限定耗時，在不同情況下使得CPU和內(nèi)存資源達(dá)到最優(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的場景有：
1、set指定過期時間expire
如果設(shè)置key的時候指定了過期時間，Redis會將這個key直接加入到expires字典中，并將超時時間設(shè)置到該字典元素。
2、調(diào)用expire命令
顯式指定某個key的過期時間
3、恢復(fù)或修改數(shù)據(jù)
從Redis持久化文件中恢復(fù)文件或者修改key，如果數(shù)據(jù)中的key已經(jīng)設(shè)置了過期時間，就將這個key加入到expires字典中
以上這些操作都會將過期的key保存到expires。redis會定期從expires字典中清理過期的key。
Redis清理過期key的時機(jī)
1、Redis在啟動的時候，會注冊兩種事件，一種是時間事件，另一種是文件事件。（可參考 啟動Redis的時候，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();
...
}
2、每次訪問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;
}
3、每次事件循環(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ù)情況下，進(jìn)行過期key的清理。過期清理的算法如下：
1、server.hz配置了serverCron任務(wù)的執(zhí)行周期，默認(rèn)是10，即CPU空閑時每秒執(zhí)行十次。 2、每次清理過期key的時間不能超過CPU時間的25%：timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100; 比如，如果hz=1，一次清理的最大時間為250ms，hz=10，一次清理的最大時間為25ms。 3、如果是快速清理模式（在beforeSleep函數(shù)調(diào)用），則一次清理的最大時間是1ms。 4、依次遍歷所有的DB。 5、從db的過期列表中隨機(jī)取20個key，判斷是否過期，如果過期，則清理。 6、如果有5個以上的key過期，則重復(fù)步驟5，否則繼續(xù)處理下一個db 7、在清理過程中，如果達(dá)到CPU的25%時間，退出清理過程。
從實現(xiàn)的算法中可以看出，這只是基于概率的簡單算法，且是隨機(jī)的抽取，因此是無法刪除所有的過期key，通過調(diào)高h(yuǎn)z參數(shù)可以提升清理的頻率，過期key可以更及時的被刪除，但hz太高會增加CPU時間的消耗。
刪除key
Redis4.0以前，刪除指令是del，del會直接釋放對象的內(nèi)存，大部分情況下，這個指令非常快，沒有任何延遲的感覺。但是，如果刪除的key是一個非常大的對象，比如一個包含了千萬元素的hash，那么刪除操作就會導(dǎo)致單線程卡頓，Redis的響應(yīng)就慢了。為了解決這個問題，在Redis4.0版本引入了unlink指令，能對刪除操作進(jìn)行“懶”處理，將刪除操作丟給后臺線程，由后臺線程來異步回收內(nèi)存。
實際上，在判斷key需要過期之后，真正刪除key的過程是先廣播expire事件到從庫和AOF文件中，然后在根據(jù)redis的配置決定立即刪除還是異步刪除。
如果是立即刪除，Redis會立即釋放key和value占用的內(nèi)存空間，否則，Redis會在另一個bio線程中釋放需要延遲刪除的空間。
小結(jié)
總的來說，Redis的過期刪除策略是在啟動時注冊了serverCron函數(shù)，每一個時間時鐘周期，都會抽取expires字典中的部分key進(jìn)行清理，從而實現(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)存達(dá)到maxmemory極限時，使用某種算法來決定清理掉哪些數(shù)據(jù)，以保證新數(shù)據(jù)的存入。
Redis的內(nèi)存淘汰機(jī)制
server.db[i].dict server.db[i].dict server.db[i].expires server.db[i].expires server.db[i].expires
在配置文件中，通過maxmemory-policy可以配置要使用哪一個淘汰機(jī)制。
什么時候會進(jìn)行淘汰？
Redis會在每一次處理命令的時候（processCommand函數(shù)調(diào)用freeMemoryIfNeeded）判斷當(dāng)前redis是否達(dá)到了內(nèi)存的最大限制，如果達(dá)到限制，則使用對應(yīng)的算法去處理需要刪除的key。偽代碼如下：
int processCommand(client *c)
{
...
if (server.maxmemory) {
int retval = freeMemoryIfNeeded();
}
...
}
LRU實現(xiàn)原理
在淘汰key時，Redis默認(rèn)最常用的是LRU算法（Latest Recently Used）。Redis通過在每一個redisObject保存lru屬性來保存key最近的訪問時間，在實現(xiàn)LRU算法時直接讀取key的lru屬性。
具體實現(xiàn)時，Redis遍歷每一個db，從每一個db中隨機(jī)抽取一批樣本key，默認(rèn)是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)存回收機(jī)制的原理介紹，了解了上面的原理介紹后，回到一開始的問題，在懷疑Redis內(nèi)存回收機(jī)制的時候能不能及時判斷故障是不是因為Redis的內(nèi)存回收機(jī)制導(dǎo)致的呢？
回到問題原點
如何證明故障是不是由內(nèi)存回收機(jī)制引起的？
根據(jù)前面分析的內(nèi)容，如果set沒有報錯，但是不生效，只有兩種情況：
- 1、設(shè)置的過期時間過短，比如，1s？
- 2、內(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)存回收機(jī)制導(dǎo)致key設(shè)置不成功，還需要查看內(nèi)存淘汰算法是否noeviction或者allkeys-random，如果是，則可以確認(rèn)是redis的內(nèi)存回收機(jī)制導(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會在：
1、每一次訪問的時候判斷key的過期時間是否到達(dá)，如果到達(dá)，就刪除key
2、redis啟動時會創(chuàng)建一個定時事件，會定期清理部分過期的key，默認(rèn)是每秒執(zhí)行十次檢查，每次過期key清理的時間不超過CPU時間的25%，即若hz=1，則一次清理時間最大為250ms，若hz=10，則一次清理時間最大為25ms。
對于第二種情況，redis會在每次處理redis命令的時候判斷當(dāng)前redis是否達(dá)到了內(nèi)存的最大限制，如果達(dá)到限制，則使用對應(yīng)的算法去處理需要刪除的key。
看完這篇文章后，你能回答文章開頭的面試題了嗎？
