Redis学习之主键失效机制和LRU机制

一、Redis 的主键失效内部机制 Key失效机制有两种： 消极方法（当访问该key的时候，判断Key是否过期，如果过期，删除key，并返回nil） 积极方法（定时删除一部分失效的key） 失效的内部表示 Redis内部使用一个dict来保存所有Key-Value对，使用expires来保存

一、Redis 的主键失效内部机制

Key失效机制有两种：

• 消极方法（当访问该key的时候，判断Key是否过期，如果过期，删除key，并返回nil）
• 积极方法（定时删除一部分失效的key）

失效的内部表示

Redis内部使用一个dict来保存所有Key-Value对，使用expires来保存所有设置了超时的key和timeout的关系。
当添加一个key-value的时候，并设置timeout，它的过程是，先将key-value对保存在dict中，再将该key和对应的超时时间保存在expires中。

【代码段一】

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

消极方法

所有查询数据操作都会先调用一个函数，该检查一下这个key是否失效，如果失效了就删除它。
检查是否失效函数如下：

【代码段二】

int expireIfNeeded(redisDb *db, robj *key) {
    //获取主键的失效时间
    long long when = getExpire(db,key);
    //假如失效时间为负数，说明该主键未设置失效时间（失效时间默认为-1），直接返回0
    if (when < 0) return 0;
    //假如Redis服务器正在从RDB文件中加载数据，暂时不进行失效主键的删除，直接返回0
    if (server.loading) return 0;
    //假如当前的Redis服务器是作为Slave运行的，那么不进行失效主键的删除，因为Slave
    //上失效主键的删除是由Master来控制的，但是这里会将主键的失效时间与当前时间进行
    //一下对比，以告知调用者指定的主键是否已经失效了
    if (server.masterhost != NULL) {
        return mstime() > when;
    }
    //如果以上条件都不满足，就将主键的失效时间与当前时间进行对比，如果发现指定的主键
    //还未失效就直接返回0
    if (mstime() <= when) return 0;
    //如果发现主键确实已经失效了，那么首先更新关于失效主键的统计个数，然后将该主键失
    //效的信息进行广播，最后将该主键从数据库中删除
    server.stat_expiredkeys++;
    propagateExpire(db,key);
    return dbDelete(db,key);
}

【代码段三】

void propagateExpire(redisDb *db, robj *key) {
    robj *argv[2];
    //shared.del是在Redis服务器启动之初就已经初始化好的一个常用Redis对象，即DEL命令
    argv[0] = shared.del;
    argv[1] = key;
    incrRefCount(argv[0]);
    incrRefCount(argv[1]);
    //检查Redis服务器是否开启了AOF，如果开启了就为失效主键记录一条DEL日志
    if (server.aof_state != REDIS_AOF_OFF)
        feedAppendOnlyFile(server.delCommand,db->id,argv,2);
    //检查Redis服务器是否拥有Slave，如果是就向所有Slave发送DEL失效主键的命令，这就是
    //上面expireIfNeeded函数中发现自己是Slave时无需主动删除失效主键的原因了，因为它
    //只需听从Master发送过来的命令就OK了
    if (listLength(server.slaves))
        replicationFeedSlaves(server.slaves,db->id,argv,2);
    decrRefCount(argv[0]);
    decrRefCount(argv[1]);
}

积极方法

以上我们通过对 expireIfNeeded 函数的介绍了解了 Redis 是如何以一种消极的方式删除失效主键的，但是仅仅通过这种方式显然是不够的，因为如果某些失效的主键迟迟等不到再次访问的话，Redis 就永远不会知道这些主键已经失效，也就永远也不会删除它们了，这无疑会导致内存空间的浪费。因此，Redis 还准备了一招积极的删除方法，该方法利用 Redis 的时间事件来实现，即每隔一段时间就中断一下完成一些指定操作，其中就包括检查并删除失效主键。这里我们说的时间事件的回调函数就是 serverCron，它在 Redis 服务器启动时创建，每秒的执行次数由宏定义 REDIS_DEFAULT_HZ 来指定，默认每秒钟执行10次。【代码段四】给出该时间事件创建时的程序代码，该代码在 redis.c文件的 initServer 函数中。实际上，serverCron 这个回调函数不仅要进行失效主键的检查与删除，还要进行统计信息的更新、客户端连接超时的控制、BGSAVE 和 AOF 的触发等等，这里我们仅关注删除失效主键的实现，也就是函数 activeExpireCycle。

【代码段四】

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

【代码段五】给出了函数 activeExpireCycle 的实现及其详细描述，其主要实现原理就是遍历处理 Redis 服务器中每个数据库的 expires 字典表中，从中尝试着随机抽样 REDIS_EXPIRELOOKUPS_PER_CRON（默认值为10）个设置了失效时间的主键，检查它们是否已经失效并删除掉失效的主键，如果失效的主键个数占本次抽样个数的比例超过25%，Redis 会认为当前数据库中的失效主键依然很多，所以它会继续进行下一轮的随机抽样和删除，直到刚才的比例低于25%才停止对当前数据库的处理，转向下一个数据库。这里我们需要注意的是，activeExpireCycle 函数不会试图一次性处理Redis中的所有数据库，而是最多只处理 REDIS_DBCRON_DBS_PER_CALL（默认值为16），此外 activeExpireCycle 函数还有处理时间上的限制，不是想执行多久就执行多久，凡此种种都只有一个目的，那就是避免失效主键删除占用过多的CPU资源。【代码段五】有对 activeExpireCycle 所有代码的详细描述，从中可以了解该函数的具体实现方法。

【代码段五】

void activeExpireCycle(void) {
    //因为每次调用activeExpireCycle函数不会一次性检查所有Redis数据库，所以需要记录下
    //每次函数调用处理的最后一个Redis数据库的编号，这样下次调用activeExpireCycle函数
    //还可以从这个数据库开始继续处理，这就是current_db被声明为static的原因，而另外一
    //个变量timelimit_exit是为了记录上一次调用activeExpireCycle函数的执行时间是否达
    //到时间限制了，所以也需要声明为static
    static unsigned int current_db = 0;
    static int timelimit_exit = 0;
    unsigned int j, iteration = 0;
    //每次调用activeExpireCycle函数处理的Redis数据库个数为REDIS_DBCRON_DBS_PER_CALL
    unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
    long long start = ustime(), timelimit;
    //如果当前Redis服务器中的数据库个数小于REDIS_DBCRON_DBS_PER_CALL，则处理全部数据库，
    //如果上一次调用activeExpireCycle函数的执行时间达到了时间限制，说明失效主键较多，也
    //会选择处理全部数据库
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;
    //执行activeExpireCycle函数的最长时间（以微秒计），其中REDIS_EXPIRELOOKUPS_TIME_PERC
    //是单位时间内能够分配给activeExpireCycle函数执行的CPU时间比例，默认值为25，server.hz
    //即为一秒内activeExpireCycle的调用次数，所以这个计算公式更明白的写法应该是这样的，即
    (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;
    //遍历处理每个Redis数据库中的失效数据
    for (j = 0; j < dbs_per_call; j++) {
        int expired;
        redisDb *db = server.db+(current_db % server.dbnum);
        //此处立刻就将current_db加一，这样可以保证即使这次无法在时间限制内删除完所有当前
        //数据库中的失效主键，下一次调用activeExpireCycle一样会从下一个数据库开始处理，
        //从而保证每个数据库都有被处理的机会
        current_db++;
        //开始处理当前数据库中的失效主键
        do {
            unsigned long num, slots;
            long long now;
            //如果expires字典表大小为0，说明该数据库中没有设置失效时间的主键，直接检查下
            //一数据库
            if ((num = dictSize(db->expires)) == 0) break;
            slots = dictSlots(db->expires);
            now = mstime();
            //如果expires字典表不为空，但是其填充率不足1%，那么随机选择主键进行检查的代价
            //会很高，所以这里直接检查下一数据库
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;
            expired = 0;
            //如果expires字典表中的entry个数不足以达到抽样个数，则选择全部key作为抽样样本
            if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
                num = REDIS_EXPIRELOOKUPS_PER_CRON;
            while (num--) {
                dictEntry *de;
                long long t;
                //随机获取一个设置了失效时间的主键，检查其是否已经失效
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                t = dictGetSignedIntegerVal(de);
                if (now > t) {
                    //发现该主键确实已经失效，删除该主键
                    sds key = dictGetKey(de);
                    robj *keyobj = createStringObject(key,sdslen(key));
                    //同样要在删除前广播该主键的失效信息
                    propagateExpire(db,keyobj);
                    dbDelete(db,keyobj);
                    decrRefCount(keyobj);
                    expired++;
                    server.stat_expiredkeys++;
                }
            }
            //每进行一次抽样删除后对iteration加一，每16次抽样删除后检查本次执行时间是否
            //已经达到时间限制，如果已达到时间限制，则记录本次执行达到时间限制并退出
            iteration++;
            if ((iteration & 0xf) == 0 &&
                (ustime()-start) > timelimit)
            {
                timelimit_exit = 1;
                return;
            }
        //如果失效的主键数占抽样数的百分比大于25%，则继续抽样删除过程
        } while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4);
    }
}

二、Redis LRU机制

Redis和Memcached一样，也拥有LRU机制，在内存不足的时候，通过LRU算法，移除相应的Key，作者原文如下：
Another way to use Redis as a cache is the?maxmemory?directive, a feature that allows specifying a maximum amount of memory to use. When new data is added to the server, and the memory limit was already reached, the server will remove some old data deleting a?volatile key, that is, a key with an EXPIRE (a timeout) set, even if the key is still far from expiring automatically.
可以设置一个内存使用上限，当Redis使用的内存达到了该上限，Redis会通过LRU算法，移除设置了超时时间的Key，尽管这些key还未达到超时时间。
配置方法如下：

# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached? You can select among five behavior:
#
# volatile-lru -> remove the key with an expire set using an LRU algorithm
# allkeys-lru -> remove any key accordingly to the LRU algorithm
# volatile-random -> remove a random key with an expire set
# allkeys-random -> remove a random key, any key
# volatile-ttl -> remove the key with the nearest expire time (minor TTL)
# noeviction -> don’t expire at all, just return an error on write operations

三、Redis 的主键失效机制会不会影响系统性能？

通过以上对 Redis 主键失效机制的介绍，我们知道虽然 Redis 会定期地检查设置了失效时间的主键并删除已经失效的主键，但是通过对每次处理数据库个数的限制、activeExpireCycle 函数在一秒钟内执行次数的限制、分配给 activeExpireCycle 函数CPU时间的限制、继续删除主键的失效主键数百分比的限制，Redis 已经大大降低了主键失效机制对系统整体性能的影响，但是如果在实际应用中出现大量主键在短时间内同时失效的情况还是会使得系统的响应能力降低，所以这种情况无疑应该避免。

Redis学习之主键失效机制和LRU机制，首发于Programer. 大猫。