Redis过期键的删除策略分享

目录

• Redis过期键删除策略
• 定期删除
• activeExpireCycle核心流程
• 淘汰相关的关键参数
• activeExpireCycleTryExpire
• 惰性删除
• 删除接口
• 从字典中删除key接口
• 从db中删除key接口
• 总结

Redis过期键删除策略

redis是内存型数据库，可对键设置过期时间，当键过期时时怎么淘汰这些键的呢？

我们先来想一想，如果让我们设计，我们会想到哪些过期删除策略呢？

1. 定时器，创建一个定时器，定时器经过expire时间后开始执行键的删除操作。
2. 周期删除，启动一个周期性的后台任务，扫描键，发现过期键则进行删除。
3. 惰性删除，当访问一个键时，如果发现键过期，再执行删除。

• 首先，定时器方式，资源消耗很大，不可能为每一个键创建一个定时器；另外当过期时间被重置时，定时器需要复位和重置，相当繁琐。
• 其次，周期删除，过期键的删除与周期执编程客栈行时间有关，可能会存在过期键很长时间没有被删除的情况，同时如果本周期内过期键很多，删除耗时会很长，增加服务负担。
• 最后，惰性删除，只针对热点数据有效，有些冷数据可能会常驻内存。

而Redis采用了周期删除和惰性删除结合的方式，同时定期删除会限制删除耗时和键数来防止依次定期删除执行太久。

• 惰性删除(访问到过期键时删除)，
• 定期删除(周期性的后台删除任务)。在源码中两种方式的入口如下:

定期删除

redis在启动初始化时（initServer）会注册周期任务aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL), serverCron函数中包含了所有周期任务，其中databasesCron 是操作数据库的函数。

• 对于master节点执行过期键删除activeExpireCycle
• 对于从节点执行expireSlaveKeys, 这里注意如果从节点只读，那么是不会有过期键淘汰的，此时依靠的是master节点同步删除命令。但是对于可写的从节点，会有一个dict(slaveKeysWithExpire)记录从节点设置了过期键的节点，从这个dict中进行过期淘汰

周期淘汰过期键的任务activeExpireCycle，该函数会一次遍历db，检查db->expires字典(存储设置了过期时间键的ttl)，对过期键进行删除。

activeExpireCycle核心流程

下面是activeExpireCycle函数的主要逻辑，我们省略很多代码，来看下淘汰javascript的主要流程是什么。

1. 首先是根据本次淘汰需要遍历的db数(dbs_per_call ), 接着上一次遍历的db开始继续遍历。timelimit_exit 表示一次定期淘汰策略执行是有时间限制的。
2. 对每个db来说，在do{}while()中进行键的淘汰，我们来看一下退出条件：直到过期比例(expired*100/sampled)小于配置参数(config_cycle_acceptable_stale),退出循环，认为该db淘汰任务执行完毕。
3. 然后对每个db来说，需要依次遍历两个dict(0:前台字典，1:rehash用的字典)。此时的退出条件是sampled >= num || checked_buckets >= max_buckets,也就是说采样键数量(sampled )达到设定值或者hash槽数量(checked_buckets )达到设定值。这里说明，在淘汰每个db中的键时，采样和检查的键数时有限的。
4. 对于两个字典来说，依赖db->expires_cursor的自增来访问每个hash槽，验证该槽上的键是否过期。

    // 依次遍历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++;
        // 针http://www.devze.com对每个db
        do {
            while (sampled < num && checked_buckets < max_buckets) {
                // 针对每个字典
                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);
    }

淘汰相关的关键参数

有一些关键参数用于控制周期任务执行的时间在一个可接受的范围。

• 采样键数num的设置。num是控制每个db的采样键数。num取的是过期字典db->expire的键数量和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是配置参数属于[0,9]区间，则config_keys_per_loop 属于[20, 65]区间。
• 采样槽数max_buckets, 控制的是最大hash槽数。而访问hash槽采用的是自增index的方式，所以可能存在大量的hash槽对应的空节点，因此最大hash槽的设置是大于采样键数的，取得是20倍采样键数。

• 单次执行时间限制 timelimit、timelimit_exit。timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;, 执行时间是根据CPU占比(ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PEFaxhIfSgwRC +2*effort)估算出来的一个时间。每执行16次do{}while()中的内容会计算一次耗时。
• ACTIVE_EXPIRE_CYCLE_FAST，快速淘汰模式。在快速淘汰模式下，会增加单词执行的时间限制和遍历的db数。

activeExpireCycleTryExpire

该函数会判断键是否过期，过期的话执行删除。首先计算节点de是否过期， now > t(改键的过期时间戳) 时表明该键已经过期，然后生成一个key对象，执行从db中删除指定key的操作。

int activeExpireCycleTryExpire(redisDFaxhIfSgwb *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 该函数会在查找指定键时被调用，用于检查该键是否过期，过期的话执行删除(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的删除接口进行了总结，方便进行理解和源码阅读。

从字典中删除key接口

1. 真正从字典中删除对应key(dictFreeUnlinkedEntry)

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

dictFreeUnlinkedEntry 函数会调用字典d的key,value销毁函数先销毁he的key,value，然后释放he。

2. 从字典中搜索并删除对应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. 检查字典是否正在进行rehash，由于redis采用的是渐进式rehash，对于处在rehash状态的字典这里会执行一步rehash操作
2. 计算key的hash值
3. 遍历字典。我们知道redis的字典中实际存在两个hashtable, 依次遍历这两个hashtable，查找对应的key是否存在
4. 找到对应key后首先改变链表链接关系，若nofree为0则执行真实删除操作，从字典中删除key
5. 最终返回找到的节点地址

3. 真实删除（dictDelete）

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

从字典中删除key对应节点并释放对应内存。

4. Unlink(dictUnlink)

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

从字典中移除key对应的节点并返回，但并不释放节点内存。

从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;
    }
}

• 首先从过期字典中删除对应key
• 从字典中unlink掉key对应节点

总结

redis对于设置了过期时间的键，会在db->expires中存储该键对应的过期时间戳。过期键删除策略是定期删除和惰性删除相结合的策略。惰性删除是指访问到该键时校验是否过期，过期执行删除。

对于周期删除，策略较复杂，为了保证定期删除可控，严格控制了每次定期删除时遍历db数量、采样键数量、执行时间等指标。定期删除提供了fast模式，该模式下会放宽执行时间和遍历的db数。

通过这两种方式，来处理redis的过期键，保证过期逻辑和内存可控。

以上就是Redis过期键的删除策略分享的详细内容，更多关于Redis过期键删除的资料请关注编程客栈(www.devze.com)其它相关文章！