深入理解Redis主鍵失效原理及實(shí)現(xiàn)機(jī)制

2013-08-28 10:11:37

本文來(lái)自@梁喜健的熱心投稿，原文見(jiàn)作者的新浪博客，對(duì)于緩存失效，不同的緩存有不同的處理機(jī)制，可以說(shuō)是大同中有小異，作者通過(guò)對(duì) Redis 文檔與相關(guān)源碼的仔細(xì)研讀，為大家詳細(xì)剖析了 Redis 的緩存過(guò)期/失效機(jī)制相關(guān)的技術(shù)原理與實(shí)現(xiàn)細(xì)節(jié)。

下面是作者原文：

作為一種定期清理無(wú)效數(shù)據(jù)的重要機(jī)制，主鍵失效存在于大多數(shù)緩存系統(tǒng)中，Redis 也不例外。在 Redis 提供的諸多命令中，EXPIRE、EXPIREAT、PEXPIRE、PEXPIREAT 以及 SETEX 和 PSETEX 均可以用來(lái)設(shè)置一條 Key-Value 對(duì)的失效時(shí)間，而一條 Key-Value 對(duì)一旦被關(guān)聯(lián)了失效時(shí)間就會(huì)在到期后自動(dòng)刪除（或者說(shuō)變得無(wú)法訪問(wèn)更為準(zhǔn)確）。可以說(shuō)，主鍵失效這個(gè)概念還是比較容易理解的，但是在具體實(shí)現(xiàn)到 Redis 中又是如何呢？最近本博主就對(duì) Redis 中的主鍵失效機(jī)制產(chǎn)生了幾個(gè)疑問(wèn)，并根據(jù)這些疑問(wèn)對(duì)其進(jìn)行了仔細(xì)的探究，現(xiàn)總結(jié)所得如下，以饗各位看客。

一、失效時(shí)間的控制

除了調(diào)用PERSIST命令外，還有沒(méi)有其他情況會(huì)撤銷一個(gè)主鍵的失效時(shí)間？答案是肯定的。首先，在通過(guò) DEL 命令刪除一個(gè)主鍵時(shí)，失效時(shí)間自然會(huì)被撤銷（這不是廢話么，哈哈）。其次，在一個(gè)設(shè)置了失效時(shí)間的主鍵被更新覆蓋時(shí)，該主鍵的失效時(shí)間也會(huì)被撤銷（這貌似也是廢話，哈哈）。但需要注意的是，這里所說(shuō)的是主鍵被更新覆蓋，而不是主鍵對(duì)應(yīng)的 Value 被更新覆蓋，因此 SET、MSET 或者是 GETSET 可能會(huì)導(dǎo)致主鍵被更新覆蓋，而像 INCR、DECR、LPUSH、HSET 等都是更新主鍵對(duì)應(yīng)的值，這類操作是不會(huì)觸碰主鍵的失效時(shí)間的。此外，還有一個(gè)特殊的命令就是 RENAME，當(dāng)我們使用 RENAME 對(duì)一個(gè)主鍵進(jìn)行重命名后，之前關(guān)聯(lián)的失效時(shí)間會(huì)自動(dòng)傳遞給新的主鍵，但是如果一個(gè)主鍵是被RENAME所覆蓋的話（如主鍵 hello 可能會(huì)被命令 RENAME world hello 所覆蓋），這時(shí)被覆蓋主鍵的失效時(shí)間會(huì)被自動(dòng)撤銷，而新的主鍵則繼續(xù)保持原來(lái)主鍵的特性。

二、失效的內(nèi)部實(shí)現(xiàn)

Redis 中的主鍵失效是如何實(shí)現(xiàn)的，即失效的主鍵是如何刪除的？實(shí)際上，Redis 刪除失效主鍵的方法主要有兩種：

消極方法（passive way），在主鍵被訪問(wèn)時(shí)如果發(fā)現(xiàn)它已經(jīng)失效，那么就刪除它
積極方法（active way），周期性地從設(shè)置了失效時(shí)間的主鍵中選擇一部分失效的主鍵刪除

失效的內(nèi)部表示

接下來(lái)我們就通過(guò)代碼來(lái)探究一下這兩種方法的具體實(shí)現(xiàn)，但在此之前，我們先看一看Redis是如何管理和維護(hù)主鍵的吧（注：本博文中的源碼全部來(lái)自 Redis-2.6.12）。

【代碼段一】給出了 Redis 中關(guān)于數(shù)據(jù)庫(kù)的結(jié)構(gòu)體定義，這個(gè)結(jié)構(gòu)體定義中除了 id 以外都是指向字典的指針，其中我們只看 dict 和 expires，前者用來(lái)維護(hù)一個(gè) Redis 數(shù)據(jù)庫(kù)中包含的所有 Key-Value 對(duì)（其結(jié)構(gòu)可以理解為 dict[key]:value，即主鍵與值之間的映射），后者則用于維護(hù)一個(gè) Redis 數(shù)據(jù)庫(kù)中設(shè)置了失效時(shí)間的主鍵（其結(jié)構(gòu)可以理解為 expires[key]:timeout，即主鍵與失效時(shí)間的映射）。當(dāng)我們使用 SETEX 和 PSETEX 命令向系統(tǒng)插入數(shù)據(jù)時(shí)，Redis 首先將 Key 和 Value 添加到 dict 這個(gè)字典表中，然后將 Key 和失效時(shí)間添加到 expires 這個(gè)字典表中。當(dāng)我們使用 EXPIRE、EXPIREAT、PEXPIRE 和 PEXPIREAT 命令設(shè)置一個(gè)主鍵的失效時(shí)間時(shí)，Redis 首先到 dict 這個(gè)字典表中查找要設(shè)置的主鍵是否存在，如果存在就將這個(gè)主鍵和失效時(shí)間添加到 expires 這個(gè)字典表。簡(jiǎn)單地總結(jié)來(lái)說(shuō)就是，設(shè)置了失效時(shí)間的主鍵和具體的失效時(shí)間全部都維護(hù)在 expires 這個(gè)字典表中。

【代碼段一】

typedef struct redisDb {  
    dict *dict;  
    dict *expires;  
    dict *blocking_keys;  
    dict *ready_keys;  
    dict *watched_keys;  
    int id;  
} redisDb;

消極方法

在大致了解了 Redis 是如何維護(hù)設(shè)置了失效時(shí)間的主鍵之后，我們就先來(lái)看一看 Redis 是如何實(shí)現(xiàn)消極地刪除失效主鍵的。【代碼段二】給出了一個(gè)名為 expireIfNeeded 的函數(shù)，這個(gè)函數(shù)在任何訪問(wèn)數(shù)據(jù)的函數(shù)中都會(huì)被調(diào)用，也就是說(shuō) Redis 在實(shí)現(xiàn) GET、MGET、HGET、LRANGE 等所有涉及到讀取數(shù)據(jù)的命令時(shí)都會(huì)調(diào)用它，它存在的意義就是在讀取數(shù)據(jù)之前先檢查一下它有沒(méi)有失效，如果失效了就刪除它。【代碼段二】中給出了 expireIfNeeded 函數(shù)的所有相關(guān)描述，這里就不再重復(fù)它的實(shí)現(xiàn)方法了。這里需要說(shuō)明的是在 expireIfNeeded 函數(shù)中調(diào)用的另外一個(gè)函數(shù) propagateExpire，這個(gè)函數(shù)用來(lái)在正式刪除失效主鍵之前廣播這個(gè)主鍵已經(jīng)失效的信息，這個(gè)信息會(huì)傳播到兩個(gè)目的地：一個(gè)是發(fā)送到 AOF文件，將刪除失效主鍵的這一操作以 DEL Key 的標(biāo)準(zhǔn)命令格式記錄下來(lái)；另一個(gè)就是發(fā)送到當(dāng)前 Redis 服務(wù)器的所有 Slave，同樣將刪除失效主鍵的這一操作以 DEL Key 的標(biāo)準(zhǔn)命令格式告知這些 Slave 刪除各自的失效主鍵。從中我們可以知道，所有作為 Slave 來(lái)運(yùn)行的 Redis 服務(wù)器并不需要通過(guò)消極方法來(lái)刪除失效主鍵，它們只需要對(duì) Master 唯命是從就 OK 了！

【代碼段二】

int expireIfNeeded(redisDb *db, robj *key) {  
    //獲取主鍵的失效時(shí)間  
    long long when = getExpire(db,key);  
    //假如失效時(shí)間為負(fù)數(shù)，說(shuō)明該主鍵未設(shè)置失效時(shí)間（失效時(shí)間默認(rèn)為-1），直接返回0  
    if (when < 0) return 0;  
    //假如Redis服務(wù)器正在從RDB文件中加載數(shù)據(jù)，暫時(shí)不進(jìn)行失效主鍵的刪除，直接返回0  
    if (server.loading) return 0;  
    //假如當(dāng)前的Redis服務(wù)器是作為Slave運(yùn)行的，那么不進(jìn)行失效主鍵的刪除，因?yàn)镾lave  
    //上失效主鍵的刪除是由Master來(lái)控制的，但是這里會(huì)將主鍵的失效時(shí)間與當(dāng)前時(shí)間進(jìn)行  
    //一下對(duì)比，以告知調(diào)用者指定的主鍵是否已經(jīng)失效了  
    if (server.masterhost != NULL) {  
        return mstime() > when;  
    }  
    //如果以上條件都不滿足，就將主鍵的失效時(shí)間與當(dāng)前時(shí)間進(jìn)行對(duì)比，如果發(fā)現(xiàn)指定的主鍵  
    //還未失效就直接返回0  
    if (mstime() <= when) return 0;  
    //如果發(fā)現(xiàn)主鍵確實(shí)已經(jīng)失效了，那么首先更新關(guān)于失效主鍵的統(tǒng)計(jì)個(gè)數(shù)，然后將該主鍵失  
    //效的信息進(jìn)行廣播，最后將該主鍵從數(shù)據(jù)庫(kù)中刪除  
    server.stat_expiredkeys++;  
    propagateExpire(db,key);  
    return dbDelete(db,key);  
}

【代碼段三】

void propagateExpire(redisDb *db, robj *key) {  
    robj *argv[2];  
    //shared.del是在Redis服務(wù)器啟動(dòng)之初就已經(jīng)初始化好的一個(gè)常用Redis對(duì)象，即DEL命令  
    argv[0] = shared.del;  
    argv[1] = key;  
    incrRefCount(argv[0]);  
    incrRefCount(argv[1]);  
    //檢查Redis服務(wù)器是否開(kāi)啟了AOF，如果開(kāi)啟了就為失效主鍵記錄一條DEL日志  
    if (server.aof_state != REDIS_AOF_OFF)  
        feedAppendOnlyFile(server.delCommand,db->id,argv,2);  
    //檢查Redis服務(wù)器是否擁有Slave，如果是就向所有Slave發(fā)送DEL失效主鍵的命令，這就是  
    //上面expireIfNeeded函數(shù)中發(fā)現(xiàn)自己是Slave時(shí)無(wú)需主動(dòng)刪除失效主鍵的原因了，因?yàn)樗? 
    //只需聽(tīng)從Master發(fā)送過(guò)來(lái)的命令就OK了  
    if (listLength(server.slaves))  
        replicationFeedSlaves(server.slaves,db->id,argv,2);  
    decrRefCount(argv[0]);  
    decrRefCount(argv[1]);  
}

積極方法

以上我們通過(guò)對(duì) expireIfNeeded 函數(shù)的介紹了解了 Redis 是如何以一種消極的方式刪除失效主鍵的，但是僅僅通過(guò)這種方式顯然是不夠的，因?yàn)槿绻承┦У闹麈I遲遲等不到再次訪問(wèn)的話，Redis 就永遠(yuǎn)不會(huì)知道這些主鍵已經(jīng)失效，也就永遠(yuǎn)也不會(huì)刪除它們了，這無(wú)疑會(huì)導(dǎo)致內(nèi)存空間的浪費(fèi)。因此，Redis 還準(zhǔn)備了一招積極的刪除方法，該方法利用 Redis 的時(shí)間事件來(lái)實(shí)現(xiàn)，即每隔一段時(shí)間就中斷一下完成一些指定操作，其中就包括檢查并刪除失效主鍵。這里我們說(shuō)的時(shí)間事件的回調(diào)函數(shù)就是 serverCron，它在 Redis 服務(wù)器啟動(dòng)時(shí)創(chuàng)建，每秒的執(zhí)行次數(shù)由宏定義 REDIS_DEFAULT_HZ 來(lái)指定，默認(rèn)每秒鐘執(zhí)行10次。【代碼段四】給出該時(shí)間事件創(chuàng)建時(shí)的程序代碼，該代碼在 redis.c文件的 initServer 函數(shù)中。實(shí)際上，serverCron 這個(gè)回調(diào)函數(shù)不僅要進(jìn)行失效主鍵的檢查與刪除，還要進(jìn)行統(tǒng)計(jì)信息的更新、客戶端連接超時(shí)的控制、BGSAVE 和 AOF 的觸發(fā)等等，這里我們僅關(guān)注刪除失效主鍵的實(shí)現(xiàn)，也就是函數(shù) activeExpireCycle。

【代碼段四】

if(aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL) == AE_ERR) {  
        redisPanic("create time event failed");  
        exit(1);  
}

#p#

【代碼段五】給出了函數(shù) activeExpireCycle 的實(shí)現(xiàn)及其詳細(xì)描述，其主要實(shí)現(xiàn)原理就是遍歷處理 Redis 服務(wù)器中每個(gè)數(shù)據(jù)庫(kù)的 expires 字典表中，從中嘗試著隨機(jī)抽樣 REDIS_EXPIRELOOKUPS_PER_CRON（默認(rèn)值為10）個(gè)設(shè)置了失效時(shí)間的主鍵，檢查它們是否已經(jīng)失效并刪除掉失效的主鍵，如果失效的主鍵個(gè)數(shù)占本次抽樣個(gè)數(shù)的比例超過(guò)25%，Redis 會(huì)認(rèn)為當(dāng)前數(shù)據(jù)庫(kù)中的失效主鍵依然很多，所以它會(huì)繼續(xù)進(jìn)行下一輪的隨機(jī)抽樣和刪除，直到剛才的比例低于25%才停止對(duì)當(dāng)前數(shù)據(jù)庫(kù)的處理，轉(zhuǎn)向下一個(gè)數(shù)據(jù)庫(kù)。這里我們需要注意的是，activeExpireCycle 函數(shù)不會(huì)試圖一次性處理Redis中的所有數(shù)據(jù)庫(kù)，而是最多只處理 REDIS_DBCRON_DBS_PER_CALL（默認(rèn)值為16），此外 activeExpireCycle 函數(shù)還有處理時(shí)間上的限制，不是想執(zhí)行多久就執(zhí)行多久，凡此種種都只有一個(gè)目的，那就是避免失效主鍵刪除占用過(guò)多的CPU資源。【代碼段五】有對(duì) activeExpireCycle 所有代碼的詳細(xì)描述，從中可以了解該函數(shù)的具體實(shí)現(xiàn)方法。

【代碼段五】

void activeExpireCycle(void) {  
    //因?yàn)槊看握{(diào)用activeExpireCycle函數(shù)不會(huì)一次性檢查所有Redis數(shù)據(jù)庫(kù)，所以需要記錄下  
    //每次函數(shù)調(diào)用處理的最后一個(gè)Redis數(shù)據(jù)庫(kù)的編號(hào)，這樣下次調(diào)用activeExpireCycle函數(shù)  
    //還可以從這個(gè)數(shù)據(jù)庫(kù)開(kāi)始繼續(xù)處理，這就是current_db被聲明為static的原因，而另外一  
    //個(gè)變量timelimit_exit是為了記錄上一次調(diào)用activeExpireCycle函數(shù)的執(zhí)行時(shí)間是否達(dá)  
    //到時(shí)間限制了，所以也需要聲明為static 
    static unsigned int current_db = 0;  
    static int timelimit_exit = 0;  
    unsigned int j, iteration = 0;  
    //每次調(diào)用activeExpireCycle函數(shù)處理的Redis數(shù)據(jù)庫(kù)個(gè)數(shù)為REDIS_DBCRON_DBS_PER_CALL  
    unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;  
    long long start = ustime(), timelimit;  
    //如果當(dāng)前Redis服務(wù)器中的數(shù)據(jù)庫(kù)個(gè)數(shù)小于REDIS_DBCRON_DBS_PER_CALL，則處理全部數(shù)據(jù)庫(kù)，  
    //如果上一次調(diào)用activeExpireCycle函數(shù)的執(zhí)行時(shí)間達(dá)到了時(shí)間限制，說(shuō)明失效主鍵較多，也  
    //會(huì)選擇處理全部數(shù)據(jù)庫(kù)  
    if (dbs_per_call > server.dbnum || timelimit_exit)  
        dbs_per_call = server.dbnum;  
    //執(zhí)行activeExpireCycle函數(shù)的最長(zhǎng)時(shí)間（以微秒計(jì)），其中REDIS_EXPIRELOOKUPS_TIME_PERC  
    //是單位時(shí)間內(nèi)能夠分配給activeExpireCycle函數(shù)執(zhí)行的CPU時(shí)間比例，默認(rèn)值為25，server.hz  
    //即為一秒內(nèi)activeExpireCycle的調(diào)用次數(shù)，所以這個(gè)計(jì)算公式更明白的寫法應(yīng)該是這樣的，即  
    (1000000 * (REDIS_EXPIRELOOKUPS_TIME_PERC / 100)) / server.hz  
    timelimit = 1000000*REDIS_EXPIRELOOKUPS_TIME_PERC/server.hz/100;  
    timelimit_exit = 0;  
    if (timelimit <= 0) timelimit = 1;  
    //遍歷處理每個(gè)Redis數(shù)據(jù)庫(kù)中的失效數(shù)據(jù)  
    for (j = 0; j < dbs_per_call; j++) {  
        int expired;  
        redisDb *db = server.db+(current_db % server.dbnum);  
        //此處立刻就將current_db加一，這樣可以保證即使這次無(wú)法在時(shí)間限制內(nèi)刪除完所有當(dāng)前  
        //數(shù)據(jù)庫(kù)中的失效主鍵，下一次調(diào)用activeExpireCycle一樣會(huì)從下一個(gè)數(shù)據(jù)庫(kù)開(kāi)始處理，  
        //從而保證每個(gè)數(shù)據(jù)庫(kù)都有被處理的機(jī)會(huì)  
        current_db++;  
        //開(kāi)始處理當(dāng)前數(shù)據(jù)庫(kù)中的失效主鍵  
        do {  
            unsigned long num, slots;  
            long long now;  
            //如果expires字典表大小為0，說(shuō)明該數(shù)據(jù)庫(kù)中沒(méi)有設(shè)置失效時(shí)間的主鍵，直接檢查下  
            //一數(shù)據(jù)庫(kù)  
            if ((num = dictSize(db->expires)) == 0) break;  
            slots = dictSlots(db->expires);  
            now = mstime();  
            //如果expires字典表不為空，但是其填充率不足1%，那么隨機(jī)選擇主鍵進(jìn)行檢查的代價(jià)  
            //會(huì)很高，所以這里直接檢查下一數(shù)據(jù)庫(kù)  
            if (num && slots > DICT_HT_INITIAL_SIZE &&  
                (num*100/slots < 1)) break;  
            expired = 0;  
            //如果expires字典表中的entry個(gè)數(shù)不足以達(dá)到抽樣個(gè)數(shù)，則選擇全部key作為抽樣樣本  
            if (num > REDIS_EXPIRELOOKUPS_PER_CRON)  
                num = REDIS_EXPIRELOOKUPS_PER_CRON;  
            while (num--) {  
                dictEntry *de;  
                long long t;  
                //隨機(jī)獲取一個(gè)設(shè)置了失效時(shí)間的主鍵，檢查其是否已經(jīng)失效  
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;  
                t = dictGetSignedIntegerVal(de);  
                if (now > t) {  
                    //發(fā)現(xiàn)該主鍵確實(shí)已經(jīng)失效，刪除該主鍵  
                    sds key = dictGetKey(de);  
                    robj *keyobj = createStringObject(key,sdslen(key));  
                    //同樣要在刪除前廣播該主鍵的失效信息  
                    propagateExpire(db,keyobj);  
                    dbDelete(db,keyobj);  
                    decrRefCount(keyobj);  
                    expired++;  
                    server.stat_expiredkeys++;  
                }  
            }  
            //每進(jìn)行一次抽樣刪除后對(duì)iteration加一，每16次抽樣刪除后檢查本次執(zhí)行時(shí)間是否  
            //已經(jīng)達(dá)到時(shí)間限制，如果已達(dá)到時(shí)間限制，則記錄本次執(zhí)行達(dá)到時(shí)間限制并退出  
            iteration++;  
            if ((iteration & 0xf) == 0 &&  
                (ustime()-start) > timelimit)  
            {  
                timelimit_exit = 1;  
                return;  
            }  
        //如果失效的主鍵數(shù)占抽樣數(shù)的百分比大于25%，則繼續(xù)抽樣刪除過(guò)程  
        } while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4);  
    }  
}

三、Memcached 刪除失效主鍵的方法與 Redis 有何異同？

首先，Memcached 在刪除失效主鍵時(shí)也是采用的消極方法，即 Memcached 內(nèi)部也不會(huì)監(jiān)視主鍵是否失效，而是在通過(guò) Get 訪問(wèn)主鍵時(shí)才會(huì)檢查其是否已經(jīng)失效。其次，Memcached 與 Redis 在主鍵失效機(jī)制上的最大不同是，Memcached 不會(huì)像 Redis 那樣真正地去刪除失效的主鍵，而只是簡(jiǎn)單地將失效主鍵占用的空間回收。這樣當(dāng)有新的數(shù)據(jù)寫入到系統(tǒng)中時(shí)，Memcached 會(huì)優(yōu)先使用那些失效主鍵的空間。如果失效主鍵的空間用光了，Memcached 還可以通過(guò) LRU 機(jī)制來(lái)回收那些長(zhǎng)期得不到訪問(wèn)的空間，因此 Memcached 并不需要像 Redis 中那樣的周期性刪除操作，這也是由 Memcached 使用的內(nèi)存管理機(jī)制決定的。同時(shí)，這里需要指出的是 Redis 在出現(xiàn) OOM 時(shí)同樣可以通過(guò)配置 maxmemory-policy 這個(gè)參數(shù)來(lái)決定是否采用 LRU 機(jī)制來(lái)回收內(nèi)存空間（感謝@Jonathan_Dai 同學(xué)在《Redis的LRU機(jī)制》中對(duì)原文的指正）。

四、Redis 的主鍵失效機(jī)制會(huì)不會(huì)影響系統(tǒng)性能？

通過(guò)以上對(duì) Redis 主鍵失效機(jī)制的介紹，我們知道雖然 Redis 會(huì)定期地檢查設(shè)置了失效時(shí)間的主鍵并刪除已經(jīng)失效的主鍵，但是通過(guò)對(duì)每次處理數(shù)據(jù)庫(kù)個(gè)數(shù)的限制、activeExpireCycle 函數(shù)在一秒鐘內(nèi)執(zhí)行次數(shù)的限制、分配給 activeExpireCycle 函數(shù)CPU時(shí)間的限制、繼續(xù)刪除主鍵的失效主鍵數(shù)百分比的限制，Redis 已經(jīng)大大降低了主鍵失效機(jī)制對(duì)系統(tǒng)整體性能的影響，但是如果在實(shí)際應(yīng)用中出現(xiàn)大量主鍵在短時(shí)間內(nèi)同時(shí)失效的情況還是會(huì)使得系統(tǒng)的響應(yīng)能力降低，所以這種情況無(wú)疑應(yīng)該避免。

參考文獻(xiàn)鏈接：