Redis 過期淘汰策略

redis的過期淘汰策略是非常值得去深入了解以及考究的一個(gè)問題敬肚。很多使用者往往不能深得其意，往往停留在人云亦云的程度，若生產(chǎn)不出事故便劃水就劃過去了冕碟，但是當(dāng)生產(chǎn)數(shù)據(jù)莫名其妙的消失稠腊，或者reids服務(wù)崩潰的時(shí)候，卻又束手無策鸣哀。本文嘗試著從淺入深的將redis的過期策略剖析開來，期望幫助作者以及讀者站在一個(gè)更加系統(tǒng)化的角度去看待過期策略吞彤。

redis作為緩存數(shù)據(jù)庫我衬，其底層數(shù)據(jù)結(jié)構(gòu)主要由dict和expires兩個(gè)字典構(gòu)成，其中dict字典負(fù)責(zé)保存鍵值對(duì)饰恕，而expires字典則負(fù)責(zé)保存鍵的過期時(shí)間挠羔。訪問磁盤空間的成本是訪問緩存的成本高出非常多，所以內(nèi)存的成本比磁盤空間要大埋嵌。在實(shí)際使用中破加，緩存的空間往往極為有限，所以為了在為數(shù)不多的容量中做到真正的物盡其用雹嗦，必須要對(duì)緩存的容量進(jìn)行管控范舀。

內(nèi)存策略

redis通過配置maxmemory來配置最大容量（閾值），當(dāng)數(shù)據(jù)占有空間超過所設(shè)定值就會(huì)觸發(fā)內(nèi)部的內(nèi)存淘汰策略（內(nèi)存釋放）了罪。那么究竟要淘汰哪些數(shù)據(jù)锭环，才是最符合業(yè)務(wù)需求？或者在業(yè)務(wù)容忍的范圍內(nèi)呢泊藕？為了解決這個(gè)問題辅辩，redis提供了可配置的淘汰策略，讓使用者可以配置適合自己業(yè)務(wù)場(chǎng)景的淘汰策略娃圆，不配置的情況下默認(rèn)是使用volatile-lru玫锋。

• noeviction：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，新寫入操作會(huì)報(bào)錯(cuò)讼呢。

• allkeys-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)撩鹿，在鍵空間中，移除最近最少使用的key吝岭。

• allkeys-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)三痰，在鍵空間中，隨機(jī)移除某個(gè)key窜管。

• volatile-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)散劫，在設(shè)置了過期時(shí)間的鍵空間中，移除最近最少使用的key幕帆。

• volatile-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)获搏，在設(shè)置了過期時(shí)間的鍵空間中，隨機(jī)移除某個(gè)key。

• volatile-ttl：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)常熙，在設(shè)置了過期時(shí)間的鍵空間中纬乍，有更早過期時(shí)間的key優(yōu)先移除。

如果redis保存的key-value對(duì)數(shù)量不多（比如數(shù)十對(duì)）裸卫，那么當(dāng)內(nèi)存超過閾值后仿贬，對(duì)整個(gè)內(nèi)存空間的所有key進(jìn)行檢查，也無傷大雅墓贿。然而茧泪，在實(shí)際使用中redis保存的key-value數(shù)量遠(yuǎn)遠(yuǎn)不止于此，如果使用內(nèi)存超過閾值就逐個(gè)去檢查是否符合過期策略嗎聋袋？隨意遍歷十萬個(gè)key队伟？顯然不是，否則幽勒，redis又何以高性能著稱嗜侮？但是，檢查多少key這個(gè)問題確實(shí)存在啥容。為了解決該問題锈颗，redis的設(shè)計(jì)者們引入一個(gè)配置項(xiàng)maxmemory-samples，稱之為過期檢測(cè)樣本干毅，默認(rèn)值是3宜猜，通過它來曲線救國(guó)。

過期檢測(cè)樣本是如何配合redis來進(jìn)行數(shù)據(jù)清理呢硝逢？

當(dāng)mem_used內(nèi)存已經(jīng)超過maxmemory的設(shè)定姨拥，對(duì)于所有的讀寫請(qǐng)求，都會(huì)觸發(fā)redis.c/freeMemoryIfNeeded函數(shù)以清理超出的內(nèi)存渠鸽。注意這個(gè)清理過程是阻塞的叫乌，直到清理出足夠的內(nèi)存空間。所以如果在達(dá)到maxmemory并且調(diào)用方還在不斷寫入的情況下徽缚，可能會(huì)反復(fù)觸發(fā)主動(dòng)清理策略憨奸，導(dǎo)致請(qǐng)求會(huì)有一定的延遲。

清理時(shí)會(huì)根據(jù)用戶配置的maxmemory政策來做適當(dāng)?shù)那謇恚ㄒ话闶荓RU或TTL）凿试，這里的LRU或TTL策略并不是針對(duì)redis的的所有鍵排宰，而是以配置文件中的maxmemory樣本個(gè)鍵作為樣本池進(jìn)行抽樣清理。

redis設(shè)計(jì)者將該值默認(rèn)為3那婉，如果增加該值板甘，會(huì)提高LRU或TTL的精準(zhǔn)度，redis的作者測(cè)試的結(jié)果是當(dāng)這個(gè)配置為10時(shí)已經(jīng)非常接近全量LRU的精準(zhǔn)度了详炬，而且增加maxmemory采樣會(huì)導(dǎo)致在主動(dòng)清理時(shí)消耗更多的CPU時(shí)間盐类，所以在設(shè)置該值必須慎重把控，在業(yè)務(wù)的需求以及性能之間做權(quán)衡。建議如下：

• 盡量不要觸發(fā)maxmemory在跳，最好在mem_used內(nèi)存占用達(dá)到maxmemory的一定比例后枪萄，需要考慮調(diào)大赫茲以加快淘汰，或者進(jìn)行集群擴(kuò)容猫妙。

• 如果能夠控制住內(nèi)存瓷翻，則可以不用修改maxmemory-samples配置。如果redis本身就作為L(zhǎng)RU緩存服務(wù)（這種服務(wù)一般長(zhǎng)時(shí)間處于maxmemory狀態(tài)割坠，由redis自動(dòng)做LRU淘汰）逻悠，可以適當(dāng)調(diào)大maxmemory樣本。

freeMemoryIfNeeded源碼解讀

int freeMemoryIfNeeded(void) {

    size_t mem_used, mem_tofree, mem_freed;

    int slaves = listLength(server.slaves);

    // 計(jì)算占用內(nèi)存大小時(shí)韭脊，并不計(jì)算slave output buffer和aof buffer，

// 因此maxmemory應(yīng)該比實(shí)際內(nèi)存小单旁，為這兩個(gè)buffer留足空間沪羔。

    mem_used = zmalloc_used_memory();

    if (slaves) {

        listIter li;

        listNode *ln;

        listRewind(server.slaves,&li);

        while((ln = listNext(&li))) {

            redisClient *slave = listNodeValue(ln);

            unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);

            if (obuf_bytes > mem_used)

                mem_used = 0;

            else

                mem_used -= obuf_bytes;

        }

    }

    if (server.appendonly) {

        mem_used -= sdslen(server.aofbuf);

        mem_used -= sdslen(server.bgrewritebuf);

    }

// 判斷已經(jīng)使用內(nèi)存是否超過最大使用內(nèi)存，如果沒有超過就返回REDIS_OK象浑，

    if (mem_used <= server.maxmemory) return REDIS_OK;

// 當(dāng)超過了最大使用內(nèi)存時(shí)蔫饰，就要判斷此時(shí)redis到底采用何種內(nèi)存釋放策略，根據(jù)不同的策略愉豺，采取不同的清除算法篓吁。

// 首先判斷是否是為no-enviction策略，如果是蚪拦，則返回REDIS_ERR,然后redis就不再接受任何寫命令了杖剪。

    if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)

        return REDIS_ERR;

    // 計(jì)算需要清理內(nèi)存大小

    mem_tofree = mem_used - server.maxmemory;

    mem_freed = 0;



    while (mem_freed < mem_tofree) {

        int j, k, keys_freed = 0;

        for (j = 0; j < server.dbnum; j++) {

            long bestval = 0;

            sds bestkey = NULL;

            struct dictEntry *de;

            redisDb *db = server.db+j;

            dict *dict;

// 1、從哪個(gè)字典中剔除數(shù)據(jù)

            // 判斷淘汰策略是基于所有的鍵還是只是基于設(shè)置了過期時(shí)間的鍵驰贷，

// 如果是針對(duì)所有的鍵盛嘿，就從server.db[j].dict中取數(shù)據(jù)，

// 如果是針對(duì)設(shè)置了過期時(shí)間的鍵括袒，就從server.db[j].expires（記錄過期時(shí)間）中取數(shù)據(jù)次兆。

if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)

            {

                dict = server.db[j].dict;

            } else {

                dict = server.db[j].expires;

            }

            if (dictSize(dict) == 0) continue;

// 2、從是否為隨機(jī)策略

// 是不是random策略锹锰，包括volatile-random 和allkeys-random芥炭，這兩種策略是最簡(jiǎn)單的，就是在上面的數(shù)據(jù)集中隨便去一個(gè)鍵恃慧，然后刪掉园蝠。

            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||

                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)

            {

                de = dictGetRandomKey(dict);// 從方法名猜出是隨機(jī)獲取一個(gè)dictEntry

                bestkey = dictGetEntryKey(de);// 得到刪除的key

            }

// 3、判斷是否為lru算法

// 是lru策略還是ttl策略糕伐，如果是lru策略就采用lru近似算法

// 為了減少運(yùn)算量,redis的lru算法和expire淘汰算法一樣砰琢，都是非最優(yōu)解，

// lru算法是在相應(yīng)的dict中，選擇maxmemory_samples(默認(rèn)設(shè)置是3)份key陪汽，挑選其中l(wèi)ru的训唱，進(jìn)行淘汰

            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)

            {

                for (k = 0; k < server.maxmemory_samples; k++) {

                    sds thiskey;

                    long thisval;

                    robj *o;

                    de = dictGetRandomKey(dict);

                    thiskey = dictGetEntryKey(de);

                    /* When policy is volatile-lru we need an additonal lookup

                    * to locate the real key, as dict is set to db->expires. */

                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)

                        de = dictFind(db->dict, thiskey); //因?yàn)閐ict->expires維護(hù)的數(shù)據(jù)結(jié)構(gòu)里并沒有記錄該key的最后訪問時(shí)間

                    o = dictGetEntryVal(de);

                    thisval = estimateObjectIdleTime(o);

                    /* Higher idle time is better candidate for deletion */

// 找到那個(gè)最合適刪除的key

// 類似排序，循環(huán)后找到最近最少使用挚冤，將其刪除

                    if (bestkey == NULL || thisval > bestval) {

                        bestkey = thiskey;

                        bestval = thisval;

                    }

                }

            }

// 如果是ttl策略况增。

// 取maxmemory_samples個(gè)鍵，比較過期時(shí)間训挡，

// 從這些鍵中找到最快過期的那個(gè)鍵澳骤，并將其刪除

            else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {

                for (k = 0; k < server.maxmemory_samples; k++) {

                    sds thiskey;

                    long thisval;

                    de = dictGetRandomKey(dict);

                    thiskey = dictGetEntryKey(de);

                    thisval = (long) dictGetEntryVal(de);

                    /* Expire sooner (minor expire unix timestamp) is better candidate for deletion */

                    if (bestkey == NULL || thisval < bestval) {

                        bestkey = thiskey;

                        bestval = thisval;

                    }

                }

            }

// 根據(jù)不同策略挑選了即將刪除的key之后，進(jìn)行刪除

            if (bestkey) {

                long long delta;

                robj *keyobj = createStringObject(bestkey,sdslen(bestkey));

                // 發(fā)布數(shù)據(jù)更新消息澜薄，主要是AOF 持久化和從機(jī)

                propagateExpire(db,keyobj); //將del命令擴(kuò)散給slaves

// 注意为肮， propagateExpire() 可能會(huì)導(dǎo)致內(nèi)存的分配，

// propagateExpire() 提前執(zhí)行就是因?yàn)閞edis 只計(jì)算

// dbDelete() 釋放的內(nèi)存大小肤京。倘若同時(shí)計(jì)算dbDelete()

// 釋放的內(nèi)存和propagateExpire() 分配空間的大小颊艳，與此

// 同時(shí)假設(shè)分配空間大于釋放空間，就有可能永遠(yuǎn)退不出這個(gè)循環(huán)忘分。

// 下面的代碼會(huì)同時(shí)計(jì)算dbDelete() 釋放的內(nèi)存和propagateExpire() 分配空間的大小

                /* We compute the amount of memory freed by dbDelete() alone.

                * It is possible that actually the memory needed to propagate

                * the DEL in AOF and replication link is greater than the one

                * we are freeing removing the key, but we can't account for

                * that otherwise we would never exit the loop.

                *

                * AOF and Output buffer memory will be freed eventually so

                * we only care about memory used by the key space. */

// 只計(jì)算dbDelete() 釋放內(nèi)存的大小

                delta = (long long) zmalloc_used_memory();

                dbDelete(db,keyobj);

                delta -= (long long) zmalloc_used_memory();

                mem_freed += delta;

                server.stat_evictedkeys++;

                decrRefCount(keyobj);

                keys_freed++;

                /* When the memory to free starts to be big enough, we may

                * start spending so much time here that is impossible to

                * deliver data to the slaves fast enough, so we force the

                * transmission here inside the loop. */

                // 將從機(jī)回復(fù)空間中的數(shù)據(jù)及時(shí)發(fā)送給從機(jī)

                if (slaves) flushSlavesOutputBuffers();

            }

        }//在所有的db中遍歷一遍棋枕，然后判斷刪除的key釋放的空間是否足夠，未能釋放空間妒峦，且此時(shí)redis 使用的內(nèi)存大小依舊超額重斑，失敗返回

        if (!keys_freed) return REDIS_ERR; /* nothing to free... */

    }

    return REDIS_OK;

}

從源碼分析中可以看到redis在使用內(nèi)存中超過設(shè)定的閾值時(shí)是如何將清理key-value進(jìn)行內(nèi)管管理，其中涉及到redis的存儲(chǔ)結(jié)構(gòu)肯骇。開篇就說到redis底層數(shù)據(jù)結(jié)構(gòu)是由dict以及expires兩個(gè)字典構(gòu)成窥浪，通過一張圖可以非常清晰了解到redis中帶過期時(shí)間的key-value的存儲(chǔ)結(jié)構(gòu)，可以更加深刻認(rèn)識(shí)到redis的內(nèi)存管理機(jī)制笛丙。

輸入圖片說明

從redis的內(nèi)存管理機(jī)制中我們可以看到寒矿，當(dāng)使用的內(nèi)存超過設(shè)定的閾值，就會(huì)觸發(fā)內(nèi)存清理若债。那么一定要等到內(nèi)存超過閾值才進(jìn)行內(nèi)存清理嗎符相？非要亡羊補(bǔ)牢？redis的設(shè)計(jì)者顯然是考慮到了這個(gè)問題蠢琳，當(dāng)redis在使用過程中啊终，自行去刪除一些過期key，盡量保證不要觸發(fā)超過內(nèi)存閾值而發(fā)生的清理事件傲须。

有效時(shí)間

• expire/pexpire key time(以秒/毫秒為單位)--這是最常用的方式（Time To Live 稱為TTL）

• setex(String key, int seconds, String value)--字符串獨(dú)有的方式

在使用過期時(shí)間時(shí)蓝牲，必要注意如下三點(diǎn)：

• 除了字符串自己獨(dú)有設(shè)置過期時(shí)間的方法外，其他方法都需要依靠expire方法來設(shè)置時(shí)間

• 如果沒有設(shè)置時(shí)間泰讽，那緩存就是永不過期

• 如果設(shè)置了過期時(shí)間例衍，之后又想讓緩存永不過期昔期，使用persist key

過期鍵自動(dòng)刪除策略

1、定時(shí)刪除（主動(dòng)刪除策略）：通過使用定時(shí)器（時(shí)間事件佛玄，采用無序鏈表實(shí)現(xiàn)硼一，），定時(shí)刪除數(shù)據(jù)梦抢。定時(shí)刪除策略可以保證過期的鍵會(huì)盡可能快的被刪除了般贼，并釋放過期鍵鎖占用的內(nèi)存。

• 好處：對(duì)內(nèi)存是最友好的奥吩。

• 壞處：它對(duì)CPU時(shí)間不友好哼蛆，在過期鍵比較多的情況下，刪除過期鍵這一行為會(huì)占用相當(dāng)一部分CPU時(shí)間霞赫，在內(nèi)存不緊張但是CPU非常緊張的情況下腮介，將CPU應(yīng)用于刪除和當(dāng)前任務(wù)無關(guān)的過期鍵上，無疑會(huì)對(duì)服務(wù)器的響應(yīng)時(shí)間和吞吐量造成影響端衰。

2萤厅、惰性刪除（被動(dòng)刪除策略）：程序在每次使用到鍵的時(shí)候去檢查是否過期，如果過期則刪除并返回空靴迫。

• 好處：對(duì)CPU時(shí)間友好，永遠(yuǎn)只在操作與當(dāng)前任務(wù)有關(guān)的鍵楼誓。

• 壞處：可能會(huì)在內(nèi)存中遺留大量的過期鍵而不刪除玉锌，造成內(nèi)存泄漏。

3疟羹、定期刪除（主動(dòng)刪除）：定期每隔一段時(shí)間執(zhí)行一段刪除過期鍵操作主守，通過限制刪除操作的執(zhí)行時(shí)長(zhǎng)與頻率來減少刪除操作對(duì)CPU時(shí)間的影響。除此之外榄融，定期執(zhí)行也可以減少過期鍵長(zhǎng)期駐留內(nèi)存的影響参淫，減少內(nèi)存泄漏的可能。

• 好處：可以控制過期刪除的執(zhí)行頻率

• 壞處：服務(wù)器必須合理設(shè)置過期鍵刪除的操作時(shí)間以及執(zhí)行的頻率愧杯。

redis的過期鍵刪除策略

redis服務(wù)器實(shí)際上使用的惰性刪除和定期刪除兩種策略：通過配合使用兩種刪除策略涎才，服務(wù)器可以很好地合理使用CPU時(shí)間和避免浪費(fèi)內(nèi)存空間之間取得平衡。

惰性刪除策略的實(shí)現(xiàn)

redis提供一個(gè)expireIfNeeded函數(shù)力九，所以讀寫數(shù)據(jù)庫的命令在執(zhí)行之前都必須調(diào)用expireIfNeeded函數(shù)耍铜。（鍵是否存在）

• 如果過期 --> 刪除

• 如果非過期 --> 執(zhí)行命令（expireIfNeeded函數(shù)不做動(dòng)作）

定期刪除策略的實(shí)現(xiàn)

定期刪除有函數(shù)activeExpireCycle函數(shù)實(shí)現(xiàn)，每當(dāng)redis服務(wù)器調(diào)用serverCorn函數(shù)時(shí)執(zhí)行定期刪除函數(shù)跌前。它會(huì)在規(guī)定時(shí)間內(nèi)棕兼，分多次遍歷服務(wù)器中的各個(gè)數(shù)據(jù)庫，并在數(shù)據(jù)庫的expire字典中隨機(jī)檢查一部分鍵的過期時(shí)間抵乓，并刪除過期鍵伴挚。

遍歷數(shù)據(jù)庫（就是redis.conf中配置的"database"數(shù)量靶衍，默認(rèn)為16）

• 檢查當(dāng)前庫中的指定個(gè)數(shù)個(gè)key（默認(rèn)是每個(gè)庫檢查20個(gè)key，注意相當(dāng)于該循環(huán)執(zhí)行20次）

• 如果當(dāng)前庫中沒有一個(gè)key設(shè)置了過期時(shí)間茎芋，直接執(zhí)行下一個(gè)庫的遍歷

• 隨機(jī)獲取一個(gè)設(shè)置了過期時(shí)間的key颅眶，檢查該key是否過期，如果過期败徊，刪除key

• 判斷定期刪除操作是否已經(jīng)達(dá)到指定時(shí)長(zhǎng)帚呼，若已經(jīng)達(dá)到，直接退出定期刪除皱蹦。

參考資料：

• 《Redis設(shè)計(jì)與實(shí)現(xiàn)》

• 深入理解Redis數(shù)據(jù)淘汰策略:https://blog.csdn.net/wtyvhreal/article/details/46390065