redis Key淘汰策略的实现

1 配置文件中的最大内存删除策略
    在redis的配置文件中，可以设置redis内存使用的最大值，当redis使用内存达到最大值时(如何知道已达到最大值？)，redis会根据配置文件中的策略选取要删除的key，并删除这些key-value的值。若根据配置的策略，没有符合策略的key，也就是说内存已经容不下新的key-value了，但此时有不能删除key，那么这时候写的话，将会出现写错误。


1.1 最大内存参数设置
若maxmemory参数设置为0，则分两种情况：
*在64位系统上，表示没有限制。
*在32为系统上，是3G，redis官方文档的说法是，32位系统最大内存是4G，预留1G给系统。而且策略会自动设置为noeviction。
也就是说在32位系统上，若maxmemory设置为0，则默认是3G，当到达3G，再往reidis中写入时，则会报错。


1.2 到达最大内存时的几种删除key的策略
*  volatile-lru -> remove the key with an expire set using an LRU algorithm
    按照LRU算法（最少最近没使用）来选取，并删除已经设置了expire时间的key。
*  allkeys-lru -> remove any key accordingly to the LRU algorithm
    根据LRU算法，删除任意的key。不论这个key是否设置了expire时间。
*  volatile-random -> remove a random key with an expire set
    随机删除一个设置了expire时间的key。
*  allkeys-random -> remove a random key, any key
    随机删除任意一个key，不论这个key是否设置了expire时间。
*  volatile-ttl -> remove the key with the nearest expire time (minor TTL)
    删除具有最近终止时间值(TTL)的key。
*  noeviction -> don't expire at all, just return an error on write operations
    若没有设置终止时间，返回一个错误。


1.3 配置内存最大值策略
以下这些命令的默认策略是：volatile-lru
 # At the date of writing this commands are: set setnx setex append
 # incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
 # sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
 # zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
 # getset mset msetnx exec sort
 #
 # The default is:
 # maxmemory-policy volatile-lru


1.4 配置要删除key的检测样本个数
maxmemory-samples
由于LRU和最小TTL算法都是不是精确的算法。因此你可以选择要检测样本的个数。例如，默认情况下redis将会检查3个key，并从这3个key中选取一个最近没有使用的key。当然你可以修改检查样本的个数的值。
要修改这个值，可以通过在配置文件中设置参数：
maxmemory-samples 3

2 实现
    这几种删除策略的实现都是在函数 freeMemoryIfNeeded(void) 中完成的。下面具体讲解每种策略是如何实现的。

2.1 什么时候去删除key-value
当设置了maxmemory-policy策略后，什么时候会去删除key呢？
实际上，当设置了maxmemory参数后，在处理每个命令的时候都会根据maxmemory-policy去删除对应的key值。


代码如下：
// 处理客户端的每个命令，都会调用这个函数
int processCommand(redisClient *c) {
    ... ...
    /* Handle the maxmemory directive.
     *
     * First we try to free some memory if possible (if there are volatile
     * keys in the dataset). If there are not the only thing we can do
     * is returning an error. */
    // 以上意思是：若存在可以删除的key，就释放一些内存，若不存在，给客户端返回一个错误。
    if (server.maxmemory) {                             // 若maxmemory不为0，则调用以下函数，释放其中一些key
        int retval = freeMemoryIfNeeded();      // 根据配置策略删除key
        if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {   // 若出错，就终止处理命令，把错误返回给客户端
            flagTransaction(c);
            addReply(c, shared.oomerr);
            return REDIS_OK;
        }
    }
    ... ...
}


实战1：若没有设置maxmemory变量，即使设置了maxmemory-policy，也不会起作用。
实战2：若没有设置maxmemory变量，在处理命令时将不会调用释放策略，会加速命令的处理过程。

2.2 删除key的总体流程
当内存达到最大值时需要按策略删除老的key，所有的删除操作和删除策略的实现都是在函数freeMemoryIfNeeded()中实现的。
在执行删除策略之前，先要选取db和查找key。总体步骤如下：


int freeMemoryIfNeeded(void) {
    size_t mem_used, mem_tofree, mem_freed;
    int slaves = listLength(server.slaves);
    mstime_t latency;


    /* Remove the size of slaves output buffers and AOF buffer from the
     * count of used memory. */
    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.aof_state != REDIS_AOF_OFF) {
        mem_used -= sdslen(server.aof_buf);
        mem_used -= aofRewriteBufferSize();
    }


    /* Check if we are over the memory limit. */
    // 检查目前系统是否超过内存的限制
    if (mem_used <= server.maxmemory) return REDIS_OK;


    if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
        return REDIS_ERR; /* We need to free memory, but policy forbids. */


    /* Compute how much memory we need to free. */
    mem_tofree = mem_used - server.maxmemory;
    mem_freed = 0;
    latencyStartMonitor(latency);
    while (mem_freed < mem_tofree) {
        int j, k, keys_freed = 0;
        // 遍历16个数据库


        for (j = 0; j < server.dbnum; j++) {
            long bestval = 0; /* just to prevent warning */
            sds bestkey = NULL;
            struct dictEntry *de;
            redisDb *db = server.db+j;
            dict *dict;


            // 这里要注意，若是ALLKEYS_xx策略，则直接在对应库结构的dict中查找key。
            // 若是非ALLKEYS_xx策略，也就是可能是 volatile-xxx等策略，操作的库结构将设置成expires结构。


            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;
            }
            // 若数据库的大小为0，说明没有key存在，继续在下一个数据库中查找
            if (dictSize(dict) == 0) continue;


... ... 


}


2.2 volatile-lru机制和allkeys-lru的实现
2.2.1 redis中的LRU机制
对于LRU机制，redis的官方文档有这样的解释：
Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
 
However since Redis 3.0 (that is currently in beta) the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.
What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:

maxmemory-samples 5

The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.

大意是说，redis的LRU算法不是正真意思上的LRU。而是使用另外一种方式实现的。也就意味着，redis并不能每次都选择一个最好的key来删除。没有使用正真的LRU算法的原因是，它可能会消耗更多的内存。该算法和正真的LRU算法效果大概相同。
redis是在一小部分key中选择最优的要删除的key。这一小部分key的个数可以指定，可以在配置文件中设置参数maxmemory-samples 。

2.2.2 LRU机制的实现
freeMemoryIfNeeded()函数，首先要计算最大空余内存和目前已经使用的内存大差值，若不够了，就要释放老的key-value。
若使用的是LRU策略，就会走以下代码，先进行最优删除key的选择，然后进行删除操作：

int freeMemoryIfNeeded(void) {
    size_t mem_used, mem_tofree, mem_freed;
    int slaves = listLength(server.slaves);
    mstime_t latency;


    /* Remove the size of slaves output buffers and AOF buffer from the
     * count of used memory. */
    mem_used = zmalloc_used_memory(); // 计算目前使用的内存大小，要排除slave和AOF使用的buffer大小
    if (slaves) { //遍历slaves链表，减去slave使用的内存数量
        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.aof_state != REDIS_AOF_OFF) { //减去AOF使用的内存大小
        mem_used -= sdslen(server.aof_buf);
        mem_used -= aofRewriteBufferSize();
    }


    /* Check if we are over the memory limit. */ //检查是否达到设置的内存上限
    if (mem_used <= server.maxmemory) return REDIS_OK;
    // 不释放内存
    if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
        return REDIS_ERR; /* We need to free memory, but policy forbids. */


    /* Compute how much memory we need to free. */ //计算要释放的内存量
    mem_tofree = mem_used - server.maxmemory;
    mem_freed = 0;
    latencyStartMonitor(latency);
    while (mem_freed < mem_tofree) { //已经释放的内存小于要释放的内存量
        int j, k, keys_freed = 0;


        for (j = 0; j < server.dbnum; j++) { //遍历所有数据库开始释放内存
            long bestval = 0; /* just to prevent warning */
            sds bestkey = NULL;
            struct dictEntry *de;
            redisDb *db = server.db+j;
            dict *dict;


             // 这一步要先选择淘汰取值的数据库的dict
            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
            { //若maxmemory-policy的值是LRU或RANDOM时，直接在主数据库中进行淘汰
                dict = server.db[j].dict;
            } else { // 其他策略，在已经设置了终止时间的key中间进行淘汰。
                dict = server.db[j].expires;
            }
            if (dictSize(dict) == 0) continue; //当前数据库没有数据跳过


            /* volatile-random and allkeys-random policy */ //若是RANDOM策略中的一个
            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
            {
                de = dictGetRandomKey(dict);
                bestkey = dictGetKey(de);
            }


            /* volatile-lru and allkeys-lru policy */// 若删除策略是LRU策略中的一个
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            {
                // 根据配置文件中maxmemory_samples的值，决定做几次选择，删除的key要从这些key中选出来。
                for (k = 0; k < server.maxmemory_samples; k++) {
                    sds thiskey;
                    long thisval;
                    robj *o;


                    // 从库中随机选取一个key-value结构(dictEntry类型)的节点
                    de = dictGetRandomKey(dict);
                    thiskey = dictGetKey(de); // // 从该节点中获取key的字符串地址
                    /* When policy is volatile-lru we need an additional lookup
                     * to locate the real key, as dict is set to db->expires. */
                    // 若最大内存删除策略是volatile-lru，则需要从db中查找thiskey。
                    // 若是VOLATILE-xx策略，则目前操作的库的存储结构是expires，此时需要从dict中找到该key
                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
                        de = dictFind(db->dict, thiskey);
                    // 获取key de的value值
                    o = dictGetVal(de);
                    // 查看该key的剩下的生存时间
                    thisval = estimateObjectIdleTime(o);


                    /* Higher idle time is better candidate for deletion */
                    // 每次都从遍历的几个Key中选出lru最长的key。
                    // 那么如何更新key的lru值呢？每次查找该key的时候就会更新该key的lru值，该值是系统的时间戳。
                    if (bestkey == NULL || thisval > bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }


            /* volatile-ttl */
            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 = dictGetKey(de);
                    thisval = (long) dictGetVal(de);


                    /* Expire sooner (minor expire unix timestamp) is better
                     * candidate for deletion */
                    if (bestkey == NULL || thisval < bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }


            ... ...
            // 到这里，要删除的最优key已经选出来了。现在进入删除阶段。
            // 不论哪种策略，只要选出了最优key，就会执行以下删除流程。


            /* Finally remove the selected key. */
            if (bestkey) {
                long long delta;


                robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
                propagateExpire(db,keyobj);
                /* 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. */
                // 删除该bestkey对应的key-value值。注意这里既要从dict中删除，还要从expires中删除。
                delta = (long long) zmalloc_used_memory();
                dbDelete(db,keyobj);
                delta -= (long long) zmalloc_used_memory();
                mem_freed += delta;
                server.stat_evictedkeys++;
                notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
                    keyobj, db->id);
                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. */
                if (slaves) flushSlavesOutputBuffers();
            }
        }
        if (!keys_freed) {
            latencyEndMonitor(latency);
            latencyAddSampleIfNeeded("eviction-cycle",latency);
            return REDIS_ERR; /* nothing to free... */
        }
    }
    latencyEndMonitor(latency);
    latencyAddSampleIfNeeded("eviction-cycle",latency);
    return REDIS_OK;
}