Redis過期鍵刪除策略

redis是內(nèi)存型數(shù)據(jù)庫，可對鍵設(shè)置過期時(shí)間，當(dāng)鍵過期時(shí)時(shí)怎么淘汰這些鍵的呢？
我們先來想一想，如果讓我們設(shè)計(jì)，我們會想到哪些過期刪除策略呢？

1. 定時(shí)器，創(chuàng)建一個(gè)定時(shí)器，定時(shí)器經(jīng)過expire時(shí)間后開始執(zhí)行鍵的刪除操作。
2. 周期刪除，啟動一個(gè)周期性的后臺任務(wù)，掃描鍵，發(fā)現(xiàn)過期鍵則進(jìn)行刪除。
3. 惰性刪除，當(dāng)訪問一個(gè)鍵時(shí)，如果發(fā)現(xiàn)鍵過期，再執(zhí)行刪除。

• 首先，定時(shí)器方式，資源消耗很大，不可能為每一個(gè)鍵創(chuàng)建一個(gè)定時(shí)器；另外當(dāng)過期時(shí)間被重置時(shí)，定時(shí)器需要復(fù)位和重置，相當(dāng)繁瑣。
• 其次，周期刪除，過期鍵的刪除與周期執(zhí)行時(shí)間有關(guān)，可能會存在過期鍵很長時(shí)間沒有被刪除的情況，同時(shí)如果本周期內(nèi)過期鍵很多，刪除耗時(shí)會很長，增加服務(wù)負(fù)擔(dān)。
• 最后，惰性刪除，只針對熱點(diǎn)數(shù)據(jù)有效，有些冷數(shù)據(jù)可能會常駐內(nèi)存。

而Redis采用了周期刪除和惰性刪除結(jié)合的方式，同時(shí)定期刪除會限制刪除耗時(shí)和鍵數(shù)來防止依次定期刪除執(zhí)行太久。

• 惰性刪除(訪問到過期鍵時(shí)刪除)，
• 定期刪除(周期性的后臺刪除任務(wù))。在源碼中兩種方式的入口如下:

定期刪除

redis在啟動初始化時(shí)（initServer）會注冊周期任務(wù)aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL), serverCron函數(shù)中包含了所有周期任務(wù)，其中databasesCron 是操作數(shù)據(jù)庫的函數(shù)。

• 對于master節(jié)點(diǎn)執(zhí)行過期鍵刪除activeExpireCycle
• 對于從節(jié)點(diǎn)執(zhí)行expireSlaveKeys, 這里注意如果從節(jié)點(diǎn)只讀，那么是不會有過期鍵淘汰的，此時(shí)依靠的是master節(jié)點(diǎn)同步刪除命令。但是對于可寫的從節(jié)點(diǎn)，會有一個(gè)dict(slaveKeysWithExpire)記錄從節(jié)點(diǎn)設(shè)置了過期鍵的節(jié)點(diǎn)，從這個(gè)dict中進(jìn)行過期淘汰

周期淘汰過期鍵的任務(wù)activeExpireCycle，該函數(shù)會一次遍歷db，檢查db->expires字典(存儲設(shè)置了過期時(shí)間鍵的ttl)，對過期鍵進(jìn)行刪除。

activeExpireCycle核心流程

下面是activeExpireCycle函數(shù)的主要邏輯，我們省略很多代碼，來看下淘汰的主要流程是什么。

1. 首先是根據(jù)本次淘汰需要遍歷的db數(shù)(dbs_per_call ), 接著上一次遍歷的db開始繼續(xù)遍歷。timelimit_exit 表示一次定期淘汰策略執(zhí)行是有時(shí)間限制的。
2. 對每個(gè)db來說，在do{}while()中進(jìn)行鍵的淘汰，我們來看一下退出條件：直到過期比例(expired*100/sampled)小于配置參數(shù)(config_cycle_acceptable_stale),退出循環(huán)，認(rèn)為該db淘汰任務(wù)執(zhí)行完畢。
3. 然后對每個(gè)db來說，需要依次遍歷兩個(gè)dict(0:前臺字典，1:rehash用的字典)。此時(shí)的退出條件是sampled >= num || checked_buckets >= max_buckets,也就是說采樣鍵數(shù)量(sampled )達(dá)到設(shè)定值或者h(yuǎn)ash槽數(shù)量(checked_buckets )達(dá)到設(shè)定值。這里說明，在淘汰每個(gè)db中的鍵時(shí)，采樣和檢查的鍵數(shù)時(shí)有限的。
4. 對于兩個(gè)字典來說，依賴db->expires_cursor的自增來訪問每個(gè)hash槽，驗(yàn)證該槽上的鍵是否過期。

    // 依次遍歷db
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        unsigned long expired, sampled;
        redisDb *db = server.db+(current_db % server.dbnum);
        current_db++;
        // 針對每個(gè)db
        do {
            while (sampled < num && checked_buckets < max_buckets) {
                // 針對每個(gè)字典
                for (int table = 0; table < 2; table++) {
                    if (table == 1 && !dictIsRehashing(db->expires)) break;
                    unsigned long idx = db->expires_cursor;
                    idx &= DICTHT_SIZE_MASK(db->expires->ht_size_exp[table]);
                    dictEntry *de = db->expires->ht_table[table][idx];
                    checked_buckets++;
                    while(de) {
                        dictEntry *e = de;
                        de = de->next;
                        if (activeExpireCycleTryExpire(db,e,now)) expired++;
                        sampled++;
                    }
                }
                db->expires_cursor++;
            }
        } while (sampled == 0 || (expired*100/sampled) > config_cycle_acceptable_stale);
    }

淘汰相關(guān)的關(guān)鍵參數(shù)

有一些關(guān)鍵參數(shù)用于控制周期任務(wù)執(zhí)行的時(shí)間在一個(gè)可接受的范圍。

• 采樣鍵數(shù)num的設(shè)置。num是控制每個(gè)db的采樣鍵數(shù)。num取的是過期字典db->expire的鍵數(shù)量和config_keys_per_loop中的最小值， config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP + ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort, ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP=20， effort是配置參數(shù)屬于[0,9]區(qū)間，則config_keys_per_loop 屬于[20, 65]區(qū)間。
• 采樣槽數(shù)max_buckets, 控制的是最大hash槽數(shù)。而訪問hash槽采用的是自增index的方式，所以可能存在大量的hash槽對應(yīng)的空節(jié)點(diǎn)，因此最大hash槽的設(shè)置是大于采樣鍵數(shù)的，取得是20倍采樣鍵數(shù)。

• 單次執(zhí)行時(shí)間限制 timelimit、timelimit_exit。timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;, 執(zhí)行時(shí)間是根據(jù)CPU占比(ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +2*effort)估算出來的一個(gè)時(shí)間。每執(zhí)行16次do{}while()中的內(nèi)容會計(jì)算一次耗時(shí)。
• ACTIVE_EXPIRE_CYCLE_FAST，快速淘汰模式。在快速淘汰模式下，會增加單詞執(zhí)行的時(shí)間限制和遍歷的db數(shù)。

activeExpireCycleTryExpire

該函數(shù)會判斷鍵是否過期，過期的話執(zhí)行刪除。首先計(jì)算節(jié)點(diǎn)de是否過期， now > t(改鍵的過期時(shí)間戳) 時(shí)表明該鍵已經(jīng)過期，然后生成一個(gè)key對象，執(zhí)行從db中刪除指定key的操作。

int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    long long t = dictGetSignedIntegerVal(de);
    if (now > t) {
        sds key = dictGetKey(de);
        robj *keyobj = createStringObject(key,sdslen(key));
        deleteExpiredKeyAndPropagate(db,keyobj);
        decrRefCount(keyobj);
        return 1;
    } else {
        return 0;
    }
}

惰性刪除

expireIfNeeded 該函數(shù)會在查找指定鍵時(shí)被調(diào)用，用于檢查該鍵是否過期，過期的話執(zhí)行刪除(deleteExpiredKeyAndPropagate)。

void deleteExpiredKeyAndPropagate(redisDb *db, robj *keyobj) {
    mstime_t expire_latency;
    latencyStartMonitor(expire_latency);
    if (server.lazyfree_lazy_expire)
        dbAsyncDelete(db,keyobj);
    else
        dbSyncDelete(db,keyobj);
    latencyEndMonitor(expire_latency);
    latencyAddSampleIfNeeded("expire-del",expire_latency);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,"expired",keyobj,db->id);
    signalModifiedKey(NULL, db, keyobj);
    propagateDeletion(db,keyobj,server.lazyfree_lazy_expire);
    server.stat_expiredkeys++;
}

刪除接口

下圖對redis的刪除接口進(jìn)行了總結(jié)，方便進(jìn)行理解和源碼閱讀。

從字典中刪除key接口

1. 真正從字典中刪除對應(yīng)key(dictFreeUnlinkedEntry)

void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
    if (he == NULL) return;
    dictFreeKey(d, he);
    dictFreeVal(d, he);
    zfree(he);
}

dictFreeUnlinkedEntry 函數(shù)會調(diào)用字典d的key,value銷毀函數(shù)先銷毀he的key,value，然后釋放he。

2. 從字典中搜索并刪除對應(yīng)key(dictGenericDelete)

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    /* dict is empty */
    if (dictSize(d) == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        prevHe = NULL;
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht_table[table][idx] = he->next;
                if (!nofree) {
                    dictFreeUnlinkedEntry(d, he);
                }
                d->ht_used[table]--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* not found */
}

1. 檢查字典是否正在進(jìn)行rehash，由于redis采用的是漸進(jìn)式rehash，對于處在rehash狀態(tài)的字典這里會執(zhí)行一步rehash操作
2. 計(jì)算key的hash值
3. 遍歷字典。我們知道redis的字典中實(shí)際存在兩個(gè)hashtable, 依次遍歷這兩個(gè)hashtable，查找對應(yīng)的key是否存在
4. 找到對應(yīng)key后首先改變鏈表鏈接關(guān)系，若nofree為0則執(zhí)行真實(shí)刪除操作，從字典中刪除key
5. 最終返回找到的節(jié)點(diǎn)地址

3. 真實(shí)刪除（dictDelete）

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

從字典中刪除key對應(yīng)節(jié)點(diǎn)并釋放對應(yīng)內(nèi)存。

4. Unlink(dictUnlink)

dictEntry *dictUnlink(dict *d, const void *key) {
    return dictGenericDelete(d,key,1);
}

從字典中移除key對應(yīng)的節(jié)點(diǎn)并返回，但并不釋放節(jié)點(diǎn)內(nèi)存。

從db中刪除key接口

1. dbGenericDelete

static int dbGenericDelete(redisDb *db, robj *key, int async) {
    /* Deleting an entry from the expires dict will not free the sds of
     * the key, because it is shared with the main dictionary. */
    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
    dictEntry *de = dictUnlink(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        /* Tells the module that the key has been unlinked from the database. */
        moduleNotifyKeyUnlink(key,val,db->id);
        /* We want to try to unblock any client using a blocking XREADGROUP */
        if (val->type == OBJ_STREAM)
            signalKeyAsReady(db,key,val->type);
        if (async) {
            freeObjAsync(key, val, db->id);
            dictSetVal(db->dict, de, NULL);
        }
        if (server.cluster_enabled) slotToKeyDelEntry(de, db);
        dictFreeUnlinkedEntry(db->dict,de);
        return 1;
    } else {
        return 0;
    }
}

• 首先從過期字典中刪除對應(yīng)key
• 從字典中unlink掉key對應(yīng)節(jié)點(diǎn)

總結(jié)

redis對于設(shè)置了過期時(shí)間的鍵，會在db->expires中存儲該鍵對應(yīng)的過期時(shí)間戳。過期鍵刪除策略是定期刪除和惰性刪除相結(jié)合的策略。惰性刪除是指訪問到該鍵時(shí)校驗(yàn)是否過期，過期執(zhí)行刪除。
對于周期刪除，策略較復(fù)雜，為了保證定期刪除可控，嚴(yán)格控制了每次定期刪除時(shí)遍歷db數(shù)量、采樣鍵數(shù)量、執(zhí)行時(shí)間等指標(biāo)。定期刪除提供了fast模式，該模式下會放寬執(zhí)行時(shí)間和遍歷的db數(shù)。
通過這兩種方式，來處理redis的過期鍵，保證過期邏輯和內(nèi)存可控。

以上就是Redis過期鍵的刪除策略分享的詳細(xì)內(nèi)容，更多關(guān)于Redis過期鍵刪除的資料請關(guān)注腳本之家其它相關(guān)文章！