Redis 過(guò)期 key 刪除，那些不得不說(shuō)的事情！
點(diǎn)擊上方“程序員大白”，選擇“星標(biāo)”公眾號(hào)
重磅干貨，第一時(shí)間送達(dá)
1.過(guò)期key的刪除策略
定時(shí)刪除：當(dāng)為key設(shè)置過(guò)期時(shí)間的時(shí)候，設(shè)置一個(gè)定時(shí)任務(wù)，到時(shí)間后即刻調(diào)用并刪除 定期刪除：每隔一定的時(shí)間，對(duì)某些key進(jìn)行掃描，并刪除掉其中已經(jīng)過(guò)期的key 惰性刪除：不進(jìn)行任何操作，只有訪問(wèn)到當(dāng)前key時(shí)，如果已經(jīng)過(guò)期再去刪除該key
定時(shí)刪除策略對(duì)于內(nèi)存來(lái)說(shuō)是最友好的，過(guò)期的key立刻被刪除，不會(huì)過(guò)多的占用內(nèi)存，但是會(huì)消耗大部分的時(shí)間片，對(duì)cpu很不友好。
惰性刪除平時(shí)不做任何操作，只有key被訪問(wèn)到的時(shí)候才會(huì)進(jìn)行判斷與刪除，對(duì)于cpu非常友好，但是這些已經(jīng)過(guò)期的key會(huì)占用大量的內(nèi)存，造成極大的浪費(fèi)。
定期刪除是每隔一段時(shí)間進(jìn)行一次掃描，這是一種折衷的方案，既不會(huì)對(duì)cpu造成很高的負(fù)擔(dān)，也不會(huì)讓大量過(guò)期的key未被刪除而造成浪費(fèi)，但是對(duì)于掃描的頻率和時(shí)間間隔設(shè)置較為復(fù)雜，如果設(shè)置的不科學(xué)，也會(huì)產(chǎn)生與其他方式類似的問(wèn)題。
redis使用了后面兩種方式來(lái)進(jìn)行過(guò)期key的刪除，在內(nèi)存使用和cpu使用率上做了一定的取舍。與過(guò)期key刪除策略經(jīng)常弄混的是redis的內(nèi)存逐出策略，redis的逐出策略只有在內(nèi)存容量到達(dá)上線maxmemory之后才會(huì)使用，平時(shí)狀態(tài)是不會(huì)使用的；而redis的過(guò)期key刪除策略是每次循環(huán)都會(huì)使用的。
redis的redis的內(nèi)存逐出策略有八種算法：
volatile-lru：設(shè)置了過(guò)期時(shí)間的key使用LRU算法淘汰；allkeys-lru：所有key使用LRU算法淘汰；volatile-lfu：設(shè)置了過(guò)期時(shí)間的key使用LFU算法淘汰；allkeys-lfu：所有key使用LFU算法淘汰；volatile-random：設(shè)置了過(guò)期時(shí)間的key使用隨機(jī)淘汰；allkeys-random：所有key使用隨機(jī)淘汰；volatile-ttl：設(shè)置了過(guò)期時(shí)間的key根據(jù)過(guò)期時(shí)間淘汰，越早過(guò)期越早淘汰；noeviction：默認(rèn)策略，當(dāng)內(nèi)存達(dá)到設(shè)置的最大值時(shí)，所有申請(qǐng)內(nèi)存的操作都會(huì)報(bào)錯(cuò)，只讀命令可以正常執(zhí)行；
2.redis過(guò)期key刪除詳解
2.1 reids中的字典
redis作為一種k-v數(shù)據(jù)庫(kù)，支持多種數(shù)據(jù)類型，這些數(shù)據(jù)的保存都和一個(gè)結(jié)構(gòu)體redisDB相關(guān)。
在redis中，有一個(gè)鏈表用來(lái)做數(shù)據(jù)上的邏輯區(qū)分，鏈表上的每個(gè)節(jié)點(diǎn)都是一個(gè)redisDb，編號(hào)從0到n（可以在配置文件中修改，默認(rèn)為16，通過(guò)select命令可以切換編號(hào)，編號(hào)對(duì)應(yīng)結(jié)構(gòu)體中的id字段）。
typedef?struct?redisDb?{
????dict?*dict;?????????????????/*?DB的鍵空間，保存了所有的key?*/
????dict?*expires;??????????????/*?保存了所有的過(guò)期key，dict的子集?*/
????dict?*blocking_keys;????????/*?實(shí)現(xiàn)阻塞客戶端使用該字典?*/
????dict?*ready_keys;???????????/*??喚醒阻塞客戶端使用該字典?*/
????dict?*watched_keys;?????????/*?實(shí)現(xiàn)簡(jiǎn)單事物使用該字典?*/
????int?id;?????????????????????/*?數(shù)據(jù)庫(kù)ID?*/
????long?long?avg_ttl;??????????/*?平均過(guò)期時(shí)間?*/
}
每次對(duì)數(shù)據(jù)庫(kù)進(jìn)行寫命令操作時(shí)，就會(huì)在字典dict中進(jìn)行相應(yīng)的操作（增加或者修改），如果對(duì)該key的過(guò)期時(shí)間有操作，則去expires字典中進(jìn)行操作（增加或者修改）。
字典的實(shí)現(xiàn)主要是由下面的結(jié)構(gòu)體來(lái)實(shí)現(xiàn)，與本文有關(guān)的兩個(gè)結(jié)構(gòu)是ht[2]和rehashidx。ht[2]里面含有兩個(gè)哈希表，哈希表1用來(lái)進(jìn)行節(jié)點(diǎn)的存儲(chǔ)，哈希表2通常情況下是空指針，沒(méi)有被真實(shí)分配空間；當(dāng)哈希表1的負(fù)載因子達(dá)到了擴(kuò)容的要求時(shí)，則對(duì)哈希表2進(jìn)行內(nèi)存分配，用于進(jìn)行哈希表擴(kuò)容。
由于redis主線程是單線程的reactor模型，為了防止rehash造成線程阻塞，所以redis采用了漸進(jìn)式rehash來(lái)進(jìn)行哈希表的擴(kuò)縮容，每次對(duì)一定數(shù)量的槽位進(jìn)行rehash，并將下一次需要進(jìn)行rehash的槽位索引位置保存在rehashidx中，方便下一次進(jìn)行rehash。
//?字典結(jié)構(gòu)體
typedef?struct?dict?{
????dictType?*type;??/*?保存了一些功能函數(shù)?*/
????void?*privdata;??/*?保存一些數(shù)據(jù)用于修改字典?*/
????dictht?ht[2];????/*?哈希表?*/
????long?rehashidx;?/*?rehash進(jìn)行到的索引位置?*/??
????unsigned?long?iterators;?/*?當(dāng)前迭代器的運(yùn)行數(shù)量?*/
}
redis中的哈希表的實(shí)現(xiàn)方式可以歸結(jié)為數(shù)組加鏈表，使用拉鏈法（鏈地址法）來(lái)解決哈希地址沖突；哈希表的槽位（哈希桶）個(gè)數(shù)為2^n個(gè)，每次擴(kuò)縮容的結(jié)果都是2的冪次。
進(jìn)行key操作的時(shí)候，首先計(jì)算放入的索引位置，idx=hash(key)%sizemark，由于掩碼的值為 2^n-1,所以這里的取模運(yùn)算可以簡(jiǎn)化為按位與，提高運(yùn)算速度。
typedef?struct?dictht?{
????dictEntry?**table;?//?哈希槽數(shù)組
????unsigned?long?size;?//?哈希槽的個(gè)數(shù)（數(shù)組長(zhǎng)度）
????unsigned?long?sizemask;?//?哈希掩碼，size-1
????unsigned?long?used;?//?哈希表實(shí)際所擁有的元素個(gè)數(shù)
}?dictht;
哈希表里有一個(gè)重要的指標(biāo)：負(fù)載因子，可以通過(guò)used/size來(lái)計(jì)算。當(dāng)負(fù)載超過(guò)一定限制的時(shí)候，需要進(jìn)行擴(kuò)容。與java不同的是，redis的哈希表在某個(gè)槽位過(guò)多的時(shí)候，并不會(huì)轉(zhuǎn)化為紅黑樹(shù)；同時(shí)在負(fù)載因子過(guò)高的時(shí)候，進(jìn)行漸進(jìn)式的rehash。
當(dāng)沒(méi)有 bgsave或者bgrewriteaof的時(shí)候，負(fù)載因子大于1.0時(shí)當(dāng)進(jìn)行 bgsave或者bgrewriteaof的時(shí)候，負(fù)載因子大于5.0時(shí)當(dāng)為 ht[1]預(yù)分配空間后，內(nèi)存超過(guò)了maxmemory且負(fù)載因子大于1.618時(shí)（黃金比例0.618的倒數(shù)，此功能在redis6.2版本加入）
redis從4.0之后開(kāi)始使用siphash算法來(lái)進(jìn)行運(yùn)算，相比之前相比（murmurhash）提高了運(yùn)行速度，并且降低了哈希碰撞的概率，可以有效防止hash-dos。一個(gè)良好的hash算法能夠?qū)ey分散的比較均勻，在負(fù)載因子較小的情況下，可以保證每個(gè)槽位上的元素個(gè)數(shù)都是比較少的。hash表中每個(gè)槽位上的元素個(gè)數(shù)符合Poisson分布：
當(dāng)負(fù)載因子為0.5時(shí)，每個(gè)槽位上的元素個(gè)數(shù)概率分布如下所示：
P(x=k)?=?exp(-0.5)?*?pow(0.5,?k)?/?factorial(k)
*0?????0.606530659713
*1?????0.303265329856
*2?????0.0758163324641
*3?????0.0126360554107
*4?????0.00157950692633
*5?????0.000157950692633
*6?????1.31625577195e-05
*7?????9.40182694247e-07
*8?????5.87614183904e-08
當(dāng)元素個(gè)數(shù)多于8個(gè)時(shí)，概率小于千萬(wàn)分之一
當(dāng)負(fù)載因子為1.0時(shí)，每個(gè)槽位上當(dāng)元素個(gè)數(shù)如下所示：
P(x=k)?=?exp(-1)?*?pow(1,?k)?/?factorial(k)
*0?????0.367879441171
*1?????0.367879441171
*2?????0.183939720586
*3?????0.0613132401952
*4?????0.0153283100488
*5?????0.00306566200976
*6?????0.000510943668294
*7?????7.29919526134e-05
*8?????9.12399407667e-06
當(dāng)元素個(gè)數(shù)多于8個(gè)時(shí)，概率約為十萬(wàn)分之一
在正常情況下，每個(gè)哈希槽位上的節(jié)點(diǎn)一般都很少，可以認(rèn)為在常數(shù)級(jí)時(shí)間復(fù)雜度O(1) 獲取到元素。
2.2 redis的內(nèi)存刪除邏輯
2.2.1 redis的事件驅(qū)動(dòng)模型
redis是一個(gè)單線程事件驅(qū)動(dòng)的模型，主線程主要在aeMain中進(jìn)行，通過(guò)配置文件中的屬性hz來(lái)確定每秒鐘含有幾個(gè)循環(huán)周期，默認(rèn)為10。
redis在初始化和加載后，就在aeMain中進(jìn)行循環(huán)，直到接收到信號(hào)或發(fā)生錯(cuò)誤才會(huì)退出，每個(gè)周期都會(huì)按照如下步驟進(jìn)行處理:
處理beforesleep回調(diào)函數(shù)相關(guān)功能 處理時(shí)間事件 處理aftersleep回調(diào)函數(shù)相關(guān)功能 處理文件事件 進(jìn)入下一次循環(huán)（回到a）
void?aeMain(aeEventLoop?*eventLoop)?{
????eventLoop->stop?=?0;
????while?(!eventLoop->stop)?{
????????if?(eventLoop->beforesleep?!=?NULL)
????????????eventLoop->beforesleep(eventLoop);
????????aeProcessEvents(eventLoop,?AE_ALL_EVENTS|AE_CALL_AFTER_SLEEP);
????}
}
beforesleep回調(diào)函數(shù)主要功能有進(jìn)行一次快速的過(guò)期key淘汰，發(fā)送命令要求slave上報(bào)backlog偏移量，嘗試釋放blocking的客戶端，aof文件刷盤等時(shí)間事件主要放在一個(gè)無(wú)序鏈表里，正常運(yùn)行的redis只有一個(gè)事件事件 ServerCron（redis啟動(dòng)加載數(shù)據(jù)時(shí)，有兩個(gè)時(shí)間事件），發(fā)起一次慢速的過(guò)期key淘汰，嘗試進(jìn)行rehash，發(fā)送定時(shí)心跳，檢測(cè)部分后臺(tái)bio線程的狀態(tài)等aftersleep回調(diào)函數(shù)目前只有module相關(guān)功能的處理文件事件主要是通過(guò)io多路復(fù)用功能，獲取就緒的文件事件進(jìn)行相應(yīng)的讀寫處理
2.2.2 redis過(guò)期key刪除的實(shí)現(xiàn)
這里使用了pyhton的偽代碼代替了原始的c代碼做說(shuō)明，主要承接上文介紹了兩種清理模式（快速清理和慢速清理），這個(gè)函數(shù)是過(guò)期key淘汰功能的核心，可以動(dòng)態(tài)的調(diào)節(jié)cpu用在掃描過(guò)期鍵的時(shí)間，當(dāng)過(guò)期鍵較少時(shí)，使用更少的cpu時(shí)間片；當(dāng)過(guò)期key較多時(shí)，則會(huì)表現(xiàn)的比較激進(jìn)。
在beforesleep回調(diào)函數(shù)調(diào)用時(shí)，會(huì)嘗試一次快速清理功能，這種清理最大能持續(xù)EXPIRE_FAST_CYCLE_DURATION時(shí)間，并且在相同的時(shí)間內(nèi)不會(huì)重復(fù)調(diào)用；
在aftersleep回調(diào)函數(shù)階段，會(huì)調(diào)用慢速清理功能，最大能調(diào)用每個(gè)redis處理周期ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC百分比的時(shí)間片。
通常情況下慢速淘汰功能能夠淘汰大量的key，只有頻繁觸發(fā)時(shí)間限制的時(shí)候，說(shuō)明慢速清理還剩下很多過(guò)期的key沒(méi)有清理，需要穿插一些快速清理功能來(lái)盡可能的刪除過(guò)期key。
ACTIVE_EXPIRE_CYCLE_SLOW?=?0??#?type標(biāo)志位，持續(xù)時(shí)間比較久的慢速清理模式
ACTIVE_EXPIRE_CYCLE_FAST?=?1??#?type標(biāo)志位，持續(xù)時(shí)間比短的快速清理模式
ACTIVE_EXPIRE_CYCLE_FAST_DURATION?=?1000??#?快速清理模式的最長(zhǎng)持續(xù)時(shí)間，單位：微秒
ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP?=?20??#?每次掃描隨機(jī)抽取的key個(gè)數(shù)
ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC?=?25??#?掃描key所占用的cpu最長(zhǎng)時(shí)間片
CRON_DBS_PER_CALL?=?16??#?每次隨機(jī)掃描的db個(gè)數(shù)
dbnums?=?0??#?server里面設(shè)置了多少個(gè)redisDb的邏輯分區(qū)
current_db?=?0??#?當(dāng)前遍歷到的數(shù)據(jù)庫(kù)編號(hào)
timelimit_exit?=?0??#?flag標(biāo)識(shí)位，用于判斷是否是到達(dá)了時(shí)間上限才退出循環(huán)
last_fast_cycle?=?0??#?上一次快速淘汰開(kāi)始的時(shí)間
def?activeExpireCycle(type):
????#?獲取現(xiàn)在的運(yùn)行時(shí)間，用于信息push和計(jì)算是否需要退出的baseline
????start?=?time.time()
????#?設(shè)定每次需要遍歷的數(shù)據(jù)庫(kù)
????dbs_per_call?=?CRON_DBS_PER_CALL
????if?type?==?ACTIVE_EXPIRE_CYCLE_FAST:
????????#?如果上一次掃描沒(méi)有觸發(fā)時(shí)間限制就退出了，說(shuō)明過(guò)期key數(shù)量不多，不要浪費(fèi)性能在掃描key上
????????if?not?timelimit_exit:
????????????return
????????#?如果距離上次快速淘汰開(kāi)始的時(shí)間間隔小于2倍的快速淘汰持續(xù)時(shí)間，直接返回
????????if?start?????????????return
????????#?設(shè)定本次快速淘汰開(kāi)始的時(shí)間，為下一次調(diào)用做時(shí)間baseline
????????last_fast_cycle?=?start
????#?如果每次掃描的數(shù)據(jù)庫(kù)數(shù)量大于實(shí)際系統(tǒng)分配的邏輯分區(qū)數(shù)量，按照實(shí)際邏輯分區(qū)數(shù)量進(jìn)行掃描
????#?如果上次掃描觸發(fā)了時(shí)間限制，說(shuō)明過(guò)期key比較多，需要進(jìn)行全部邏輯分區(qū)的掃描
????if?dbs_per_call?>?server.dbnum?or?timelimit_exit:
????????dbs_per_call?=?dbnums
????#?計(jì)算本次循環(huán)最多能持續(xù)的時(shí)間，1000000微秒*（25/100）/?10
????#?1秒鐘10hz，每次redis的處理周期為100毫秒（100000微秒），25%cpu時(shí)間分片就是25000微秒
????timelimit?=?1000000?*?ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC?/?server.hz?/?100
????#?如果是快速清理模式，則每次最多能持續(xù)1000微秒
????if?type?==?ACTIVE_EXPIRE_CYCLE_FAST:
????????timelimit?=?ACTIVE_EXPIRE_CYCLE_FAST_DURATION
????#?遍歷指定數(shù)量（dbs_per_call）的數(shù)據(jù)庫(kù)
????for?i?in?range(0,?dbs_per_call):
????????#?如果觸發(fā)了時(shí)間限制，直接退出循環(huán)
????????if?time.time()?-?start?>?timelimit:
????????????break
????????#?當(dāng)前數(shù)據(jù)庫(kù)中不存在過(guò)期的key，直接掃描下一個(gè)數(shù)據(jù)庫(kù)
????????if?redisDb[i].expires.size()?==?0:
????????????continue
????????#?如果當(dāng)前數(shù)據(jù)庫(kù)含有過(guò)期時(shí)間的key數(shù)量小于1%，直接掃描下一個(gè)數(shù)據(jù)庫(kù)
????????if?redisDb[i].expires.size()?*?100.0?/?redisDb[i].dict.size()?????????????continue
????????while?True:
????????????#?獲取每次掃描的key的數(shù)量
????????????lookup_nums?=?min(redisDb[i].expires.size(),?ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
????????????#?已經(jīng)過(guò)期的key的數(shù)量
????????????expired?=?0
????????????while?lookup_nums?>?0:
????????????????#?隨機(jī)獲取一個(gè)key判斷是否過(guò)期
????????????????lookup_key?=?random_get_key_from_expire(redisDb[i])
????????????????#?如果過(guò)期了，就刪除
????????????????if?is_expire(lookup_key):
????????????????????del?(lookup_key)
????????????????????expired?+=?1
????????????#?判斷當(dāng)前時(shí)刻是否觸發(fā)了時(shí)間限制，如果觸發(fā)了限制，直接退出
????????????if?time.time()?-?start?>?timelimit:
????????????????break
????????????????break??#?兩個(gè)break，不符合python語(yǔ)法，這里表示結(jié)束全部的循環(huán)
????????????#?如果本次循環(huán)掃描出來(lái)的key已經(jīng)過(guò)期的比例小于25%，則去掃描下一個(gè)數(shù)據(jù)庫(kù)
????????????#?否則說(shuō)明本數(shù)據(jù)庫(kù)過(guò)期的key較多，立刻在本數(shù)據(jù)庫(kù)中再次掃描和清理
????????????if?expired?*?4?/?lookup_nums?????????????????break
2.2.3 redis過(guò)期key優(yōu)化點(diǎn)
上文中提到了，過(guò)期key是隨機(jī)從全部的含有過(guò)期時(shí)間的key中進(jìn)行選擇。使用的算法如下，這里存在的不足是，當(dāng)過(guò)期key數(shù)量較少時(shí)，哈希桶槽位上大部分的元素為空，隨機(jī)數(shù)生成后所得到的哈希桶槽位經(jīng)常miss，需要再次進(jìn)行隨機(jī)，會(huì)消耗過(guò)多的時(shí)間片在生成隨機(jī)數(shù)上，而不是清理過(guò)期key。
def?random_get_key_from_expire(redisDb):
????slot_nums?=?0
????#?如果在進(jìn)行rehash，則兩個(gè)哈希表都可能有key存在,需要從中隨機(jī)選擇一個(gè)
????if?(is_rehash(redisDb.expires)):
????????slot_nums?=?ht[0].size?+?ht[1].size
????else:
????????slot_nums?=?ht[0].size
????headEntry?=?None
????while?True:
????????#?從所有的槽位中隨機(jī)選擇一個(gè)
????????slot_idx?=?random.randint(0,?slot_nums)
????????#?直到找到一個(gè)槽位不為空的哈希桶，就停止循環(huán)
????????if?(slot_idx?>?ht[0].size):
????????????#?如果所得到的索引大于ht[0]的大小，說(shuō)明落在了ht[1]中
????????????tempEntry?=?ht[1].get_index(slot_idx?-?ht[0].size)
????????????if?tempEntry?!=?None:
????????????????headEntry?=?tempEntry
????????????????break
????????else:
????????????tempEntry?=?ht[0].get_index(slot_idx)
????????????if?tempEntry?!=?None:
????????????????headEntry?=?tempEntry
????????????????break
????currEntry?=?headEntry
????len?=?0
????#?遍歷鏈表獲得長(zhǎng)度
????while?currEntry.next:
????????currEntry?=?currEntry.next
????????len?+=?1
????#?從鏈表中隨機(jī)選擇一個(gè)節(jié)點(diǎn)返回
????listele?=?random.randint(0,?len)
????while?listele:
????????headEntry?=?headEntry.next
????????listele?-=?1
????return?headEntry
此外，如果redis的寫入量比較大，且key過(guò)期時(shí)間比較短，即使兩種淘汰方式同時(shí)進(jìn)行，也會(huì)超過(guò)redis的處理能力，依然會(huì)造成數(shù)據(jù)的堆積，如果容量繼續(xù)上漲超過(guò)，就會(huì)進(jìn)行內(nèi)存淘汰（使用allkeys-lru淘汰策略，會(huì)優(yōu)先刪除lru較小的key，由于惰性刪除的原因，已過(guò)期的key的lru會(huì)通常情況下比較小，會(huì)被優(yōu)先逐出）。
由于走了另外一套邏輯（逐出邏輯）造成了cpu時(shí)間片的浪費(fèi)，它們最終的結(jié)果都是key刪除，但是卻進(jìn)行了不同的篩選策略。實(shí)際使用場(chǎng)景中遇到這種情況的時(shí)刻不多，對(duì)于性能和吞吐量的影響不大，但是也是一個(gè)可以優(yōu)化的點(diǎn)。
實(shí)際使用中，還有一種人為觸發(fā)過(guò)期key淘汰的方法，就是通過(guò)scan命令來(lái)進(jìn)行全庫(kù)的掃描，通過(guò)控制scan命令的游標(biāo)和count數(shù)量，可以預(yù)期的控制淘汰的激烈程度，不會(huì)對(duì)主線程造成阻塞。
redis在進(jìn)行key的刪除的時(shí)候，如果開(kāi)啟了異步刪除，則當(dāng)被刪除的key所對(duì)應(yīng)的val占用空間大于64字節(jié)時(shí)，會(huì)將這個(gè)key標(biāo)記為刪除后直接返回+OK，然后將val放到后臺(tái)的bio線程里面進(jìn)行刪除，防止阻塞主線程；如果占用的空間小于64字節(jié)，即使開(kāi)啟了異步刪除，在最后運(yùn)行的時(shí)候也會(huì)同步的進(jìn)行刪除(redis優(yōu)秀的性能優(yōu)化在細(xì)節(jié)之末隨處可見(jiàn)，針對(duì)很多場(chǎng)景都做了優(yōu)化，并抽象出參數(shù)給用戶動(dòng)態(tài)配置，它的高性能是與redis作者精益求精的修改分不開(kāi)的)。
2.2.4 redis6對(duì)過(guò)期key刪除的優(yōu)化
redis6針對(duì)以上的問(wèn)題提出了幾個(gè)改進(jìn)點(diǎn)，首先將原來(lái)的隨機(jī)抽樣檢查過(guò)期key變成了按照哈希桶順序遍歷檢查過(guò)期key。通過(guò)在redisDb結(jié)構(gòu)體中增加long expires_cursor字段，用來(lái)記錄上一次遍歷到的游標(biāo)位置，每次遍歷都會(huì)取到這個(gè)游標(biāo)位置對(duì)應(yīng)的索引，然后繼續(xù)下去，使得cpu的時(shí)間片更多的用來(lái)進(jìn)行key過(guò)期的判斷和刪除上。
typedef?struct?redisDb?{
????dict?*dict;?????????????????
????dict?*expires;??????????????
????dict?*blocking_keys;????????
????dict?*ready_keys;???????????
????dict?*watched_keys;?????????
????int?id;?????????????????????
????long?long?avg_ttl;??????????
????unsigned?long?expires_cursor;?/*?主動(dòng)過(guò)期循環(huán)的游標(biāo)*/
????list?*defrag_later;?????????/*?key組成的鏈表，用來(lái)進(jìn)行內(nèi)存碎片整理?*/
}?redisDb;
另外在server的配置中增加了activate_expire_effort標(biāo)識(shí)位，可以被設(shè)定為1-10，用來(lái)表示定期刪除淘汰key的激烈程度。在系統(tǒng)設(shè)定好activate_expire_effort之后，redis的定期刪除循環(huán)邏輯每次都會(huì)重新計(jì)算閾值，比如快速淘汰循環(huán)最大的持續(xù)時(shí)間，慢速淘汰循環(huán)最大的持續(xù)時(shí)間，這些參數(shù)在之前的淘汰算法中都是一個(gè)確定的值。通過(guò)抽象成一個(gè)配置文件的參數(shù)，可以通過(guò)命令熱加載動(dòng)態(tài)的調(diào)節(jié)，達(dá)到redis吞吐量和容量使用的“均衡”。
struct?redisServer?{
????????????...
????int?active_expire_enabled;??????/*?Can?be?disabled?for?testing?purposes.?*/
????int?active_expire_effort;???????/*?From?1?(default)?to?10,?active?effort.?*/
????????????...
}
ACTIVE_EXPIRE_CYCLE_SLOW?=?0??#?type標(biāo)志位，持續(xù)時(shí)間比較久的慢速清理模式
ACTIVE_EXPIRE_CYCLE_FAST?=?1??#?type標(biāo)志位，持續(xù)時(shí)間比短的快速清理模式
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP?=?20??#?每次每個(gè)db掃描的key個(gè)數(shù)
ACTIVE_EXPIRE_CYCLE_FAST_DURATION?=?1000??#?快速清理模式的最長(zhǎng)持續(xù)時(shí)間，這里只是一個(gè)基線
ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC?=?25??#?掃描key所占用的cpu最長(zhǎng)時(shí)間片
ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE?=?10??#?開(kāi)啟efforts后，過(guò)期key占據(jù)的百分比
CRON_DBS_PER_CALL?=?16??#?每次隨機(jī)掃描的db個(gè)數(shù)
current_db?=?0??#?當(dāng)前遍歷到的數(shù)據(jù)庫(kù)編號(hào)
timelimit_exit?=?0??#?flag標(biāo)識(shí)位，用于判斷是否是到達(dá)了時(shí)間上限才退出循環(huán)
last_fast_cycle?=?0??#?上一次快速淘汰開(kāi)始的時(shí)間
def?activeExpireCycle(type):
????#?一個(gè)統(tǒng)計(jì)量，表示系統(tǒng)對(duì)于過(guò)期key掃描的激進(jìn)程度（0~9）
????#?該配置可以通過(guò)配置文件來(lái)進(jìn)行設(shè)置，根據(jù)集群的平均過(guò)期時(shí)間，動(dòng)態(tài)的設(shè)定
????effort?=?server.active_expire_effort?-?1,
????#?每次循環(huán)掃描的key的數(shù)量
????config_keys_per_loop?=?ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP?+?ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP?/?4?*?effort
????#?快速清理循環(huán)的持續(xù)時(shí)間
????config_cycle_fast_duration?=?ACTIVE_EXPIRE_CYCLE_FAST_DURATION?+?ACTIVE_EXPIRE_CYCLE_FAST_DURATION?/?4?*?effort
????#?清理循環(huán)周期所占用的最大cpu時(shí)間片百分比
????config_cycle_slow_time_perc?=?ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC?+?2?*?effort
????#?有過(guò)期時(shí)間的key所全部key占的最多的百分比
????config_cycle_acceptable_stale?=?ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE?-?effort
????#?全局變量，函數(shù)退出后值仍然保存，留待下一次函數(shù)調(diào)用
????global?last_fast_cycle
????global?current_db
????global?timelimit_exit
????start?=?time.time()
????dbs_per_call?=?CRON_DBS_PER_CALL
????iteration?=?0
????if?type?==?ACTIVE_EXPIRE_CYCLE_FAST:
????????#?如果上一次掃描沒(méi)有觸發(fā)時(shí)間限制就退出,并且系統(tǒng)所含有的過(guò)期key的比例小于配置的閾值直接返回
????????#?因?yàn)榇藭r(shí)過(guò)期快key的數(shù)量不多，并不需要浪費(fèi)過(guò)多的cpu時(shí)間片在掃描過(guò)期key上
????????if?(not?timelimit_exit)?and?(server.stat_expired_stale_perc?????????????return
????????#?如果距離上次快速周期循環(huán)開(kāi)始的時(shí)間間隔小于2倍的快速周期循環(huán)持續(xù)時(shí)間，直接返回
????????if?start?????????????return
????????#?設(shè)定本次快速淘汰開(kāi)始的時(shí)間，為下一次調(diào)用做時(shí)間baseline
????????last_fast_cycle?=?start
????#?如果每次掃描的數(shù)據(jù)庫(kù)數(shù)量大于實(shí)際系統(tǒng)分配的邏輯分區(qū)數(shù)量，按照實(shí)際邏輯分區(qū)數(shù)量進(jìn)行掃描
????#?如果上次掃描觸發(fā)了時(shí)間限制，說(shuō)明過(guò)期key比較多，需要進(jìn)行全部邏輯分區(qū)的掃描
????if?dbs_per_call?>?server.dbnum?or?timelimit_exit:
????????dbs_per_call?=?server.dbnums
????#?計(jì)算本次循環(huán)最多能持續(xù)的時(shí)間，1000000微秒*（25/100）/?10
????#?1秒鐘10hz，每次redis的處理周期為100毫秒（100000微秒），25%cpu時(shí)間分片就是25000微秒
????#?如果設(shè)置了effort，則會(huì)增加用于過(guò)期key刪除的cpu時(shí)間片，例如effort=6，那么將有35000微秒用于處理過(guò)期key
????timelimit?=?1000000?*?config_cycle_slow_time_perc?/?server.hz?/?100
????#?如果是快速清理模式，則每次最多能持續(xù)config_cycle_fast_duration微秒
????if?type?==?ACTIVE_EXPIRE_CYCLE_FAST:
????????timelimit?=?config_cycle_fast_duration
????#?遍歷指定數(shù)量（dbs_per_call）的數(shù)據(jù)庫(kù)
????for?i?in?range(0,?dbs_per_call):
????????#?如果觸發(fā)了時(shí)間限制，直接退出循環(huán)
????????if?time.time()?-?start?>?timelimit:
????????????break
????????#?獲取每次要掃描的數(shù)據(jù)庫(kù)編號(hào)，并記錄下來(lái)，這樣可以讓cpu將時(shí)間片公平的分給每個(gè)數(shù)據(jù)庫(kù)
????????db_idx?=?current_db?%?server.dbnum
????????#?先變更下一次要掃描的數(shù)據(jù)庫(kù)，方式程序因超時(shí)返回時(shí)忘記變更需要掃描的數(shù)據(jù)庫(kù)，
????????#?也是為了將時(shí)間片公平的分散到每個(gè)數(shù)據(jù)庫(kù)
????????db_idx?+=?1
????????while?True:
????????????#?當(dāng)前數(shù)據(jù)庫(kù)中不存在過(guò)期的key，直接掃描下一個(gè)數(shù)據(jù)庫(kù)
????????????if?redisDb[db_idx].expires.size()?==?0:
????????????????break
????????????#?如果當(dāng)前數(shù)據(jù)庫(kù)含有過(guò)期時(shí)間的key數(shù)量小于1%，直接掃描下一個(gè)數(shù)據(jù)庫(kù)
????????????if?redisDb[db_idx].expires.size()?*?100.0?/?redisDb[db_idx].dict.size()?????????????????break
????????????#?獲取每次掃描的key的數(shù)量
????????????num?=?redisDb[db_idx].expires.size()
????????????if?num?>?config_keys_per_loop:
????????????????num?=?config_keys_per_loop??#?每次至多只會(huì)選擇config_keys_per_loop個(gè)key進(jìn)行查詢
????????????#?最多遍歷的哈希桶數(shù)量
????????????max_buckets?=?num?*?20
????????????#?已經(jīng)遍歷的哈希桶數(shù)量
????????????checked_buckets?=?0
????????????#?已經(jīng)掃描的過(guò)期key的個(gè)數(shù)
????????????sampled?=?0
????????????#?已經(jīng)過(guò)期key的個(gè)數(shù)
????????????expires?=?0
????????????#?如果掃描的哈希桶數(shù)量過(guò)多或者已經(jīng)掃描了規(guī)定數(shù)量的key，就退出循環(huán)防止占用過(guò)多時(shí)間
????????????while?sampled?????????????????#?字典里只有兩個(gè)哈希表ht[0],ht[1],每次循環(huán)會(huì)選擇其中的一個(gè)
????????????????for?table?in?(0,?1):
????????????????????#?沒(méi)有進(jìn)行rehash時(shí)，ht[1]為空，遍歷到此處時(shí)直接返回
????????????????????if?table?==?1?and?is_rehash(redisDb[db_idx].expires):
????????????????????????break
????????????????????#?保存了上一次遍歷到的哈希桶索引位置
????????????????????idx?=?redisDb[db_idx].expires_cursor
????????????????????#?與掩碼進(jìn)行計(jì)算，確定本次開(kāi)始遍歷的哈希桶索引位置
????????????????????idx?=?idx?&?redisDb[db_idx].expires.ht[i].sizemark
????????????????????#?獲取哈希桶索引位置對(duì)應(yīng)的鏈表的頭節(jié)點(diǎn)
????????????????????dictEntry?=?redisDb[db_idx].expires.ht[i].bucket[idx]
????????????????????while?dictEntry:
????????????????????????#?遍歷鏈表，如果過(guò)期了就刪除，并計(jì)數(shù)已經(jīng)過(guò)期的key
????????????????????????if?is_expire(dictEntry):
????????????????????????????del?(dictEntry)
????????????????????????????expires?+=?1
????????????????????????dictEntry?=?dictEntry.next
????????????????????????sampled?+=?1
????????????????#?記錄下一次要遍歷的哈希桶的索引位置
????????????????redisDb[db_idx].expires_cursor?+=?1
????????????????#?如果掃描時(shí)間過(guò)長(zhǎng)達(dá)到了規(guī)定的閾值，則直接返回
????????????????if?time.time()?-?start?>?timelimit:
????????????????????return??#?直接返回全部的
????????????#?如果過(guò)期的key占比高于閾值，說(shuō)明當(dāng)前庫(kù)里面的過(guò)期key很多，需要再次遍歷進(jìn)行淘汰
????????????if?expires?*?100.0?/?sampled?>?config_cycle_acceptable_stale:
????????????????continue
????????????#?如果掃描到的所有的桶都是空的，觸發(fā)了max_buckets限制而退出，說(shuō)明沒(méi)有清理到過(guò)期的key
????????????#?過(guò)期的key都在其他的桶之中，需要進(jìn)行再次的掃描
????????????elif?sampled?==?0:
????????????????continue
????????????else:
????????????????break
來(lái)源：blog.csdn.net/qq_38856118/article/
details/115796879
推薦閱讀
關(guān)于程序員大白
程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運(yùn)營(yíng)維護(hù)的號(hào)，大家樂(lè)于分享高質(zhì)量文章，喜歡總結(jié)知識(shí)，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進(jìn)步！