本文浅显的谈谈redis删除key的源码部分，希望本篇文章对于学习redis并且看源码的你能够起到抛砖引玉的作用，并在此记下自己阅读源码的足迹。

本文主要由以下几个部分组成

一、为什么要删除key？

二、内存淘汰的策略主要有哪些？

三、删除key的时机或者说手段有哪些？

四、删除key的源码整体脉络

五、源码的阅读

ANSWER 一
首先，为什么要删除key呢？这是因为redis是基于内存的数据库，计算机的内存容量是有限的，试想你一直往里面写入数据而没有一定的策略去删除你写的数据，内存早晚会被用完的，所以有必要删除删除那些老的数据，给新插入的数据腾挪地方。有的同学可能会说redis集群是可以扩展的，这样我就不用删除旧数据，我可以一直加机器解决内存不足的问题。这种方式显然是行不通的，因为你基于hash的方法分发数据，可能会导致数据失衡，从而导致某台服务器过载。所以就有必要对旧数据(过期key)进行删除。

ANSWER 二
既然要对key进行删除，我们就要有一定的策略进行删除，而不是随意的进行删除。redis中给出了以下策略用于淘汰key
// 根据lru算法删除带有过期时间的key
1】volatile-lru -> remove the key with an expire set using an LRU algorithm
// 根据lru算法删除任意的key
2】allkeys-lru -> remove any key accordingly to the LRU algorithm
// 随机删除带有过期时间的key
3】volatile-random -> remove a random key with an expire set
// 随机删除任何一个key
4】 allkeys-random -> remove a random key, any key
// 删除ttl最近的key
5】 volatile-ttl -> remove the key with the nearest expire time (minor TTL)
// 不删
6】noeviction -> don’t expire at all, just return an error on write operations
问题：你所在的公司用了哪种策略进行key的删除，为什么要用这种策略呢？可以探讨一番。

ANSWER 三
以上说了key的淘汰策略有哪些，也就是我们要删除key的时候要遵守的规则，并按照这个规则执行的key删除。那么策略有了，删除key的时机或者方式有哪些呢？在redis中有三个时机删除key。1、定时删除 2、定期删除 3、惰性删除。 redis目前删除的时机是 定期删除+惰性删除。至于这三个时机有什么优缺点，自己查阅相关书籍就能找到答案【redis设计与实现 P107】

ANSWER 四
本篇文章只讲惰性删除，也就是当执行命令时进行key的删除。这里给出执行命令时删除key的一个大致脉络，也就是函数的调用流程

客户端发送请求，redis服务端最终会调用这个函数处理客户端的命令请求
------------processCommand(redisClient *c) 
            在处理命令时，会调用这个函数进行内存释放，也就是进行key的删除，返回删除成功or失败
     --------------freeMemoryIfNeeded（）
         ------------evictionPoolPopulate（dict, db->dict, db->eviction_pool）得到要删除的key
               ---------estimateObjectIdleTime(o) 计算key的过期时间
在对key惰性删除的时候，基本上调用上述四个函数。在讲解具体函数之前，我们还是来熟悉下几个数据结构
/*
 * 哈希表节点
 */
typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;


typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用计数
    int refcount;

    // 指向实际值的指针
    void *ptr;

} robj;

typedef struct redisDb {

    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;                 /* The keyspace for this DB */

    // 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳
    dict *expires;              /* Timeout of keys with a timeout set */

    // 正处于阻塞状态的键
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */

    // 可以解除阻塞的键
    dict *ready_keys;           /* Blocked keys that received a PUSH */

    // 正在被 WATCH 命令监视的键
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */

    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */

    // 数据库号码
    int id;                     /* Database ID */

    // 数据库的键的平均 TTL ，统计信息
    long long avg_ttl;          /* Average TTL, just for stats */

} redisDb;

这个就是存储要删除key的数据结构
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time. */
    sds key;                    /* Key name. */
};

ANSWER 五
下面我们依次讲解上述的几个函数

/* If this function gets called we already read a whole
 * command, arguments are in the client argv/argc fields.
 * processCommand() execute the command or prepare the
 * server for a bulk read from the client.
 *
 * 这个函数执行时，我们已经读入了一个完整的命令到客户端，
 * 这个函数负责执行这个命令，
 * 或者服务器准备从客户端中进行一次读取。
 *
 * If 1 is returned the client is still alive and valid and
 * other operations can be performed by the caller. Otherwise
 * if 0 is returned the client was destroyed (i.e. after QUIT). 
 *
 * 如果这个函数返回 1 ，那么表示客户端在执行命令之后仍然存在，
 * 调用者可以继续执行其他操作。
 * 否则，如果这个函数返回 0 ，那么表示客户端已经被销毁。
 */

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. */
    // 如果设置了最大内存，那么检查内存是否超过限制，并做相应的操作
    // 其中 maxmemory是我们在配置文件中可以设置的，在C语言中只要不等于0就是真
   @1 if (server.maxmemory) {
        // 如果内存已超过限制，那么尝试通过删除过期键来释放内存
        int retval = freeMemoryIfNeeded();
        // 如果即将要执行的命令可能占用大量内存（REDIS_CMD_DENYOOM）
        // 并且前面的内存释放失败的话
        // 那么向客户端返回内存错误
        if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
            flagTransaction(c);
            addReply(c, shared.oomerr);
            return REDIS_OK;
        }
    }
    return REDIS_OK;
}

processCommand()这个函数在处理命令时在@1处如果说我们设置了maxmemory那么会调用freeMemoryIfNeeded()这个方法进行内存释放[也就是删除key的操作]，如果释放失败，返回错误。在我们没有分析freeMemoryIfNeeded()之前，如果让我们自己设计一个删除key的函数，想一想都有哪些步骤？我想无非是这样几个步骤：
1、计算目前已经使用了多少内存，需要释放多少内存？假设需要释放的内存为x。
2、遍历redis的每一个库，根据一定的策略【ANSWER2中的6个策略】找出要删除的key
3.删除key，释放内存，计算一下释放的内存是否已经大于等于步骤1中需要释放的内存x，如果达到这个条件本次删除key的任务结束【这里我觉得是考虑到服务性能的问题，想一想步骤1中不设置一个释放内存的阈值会出现什么问题？】。等分析完这个函数后，我会绘制一张流程图。我们现在只分析一种策略，那就是all-keys-lru这种内存淘汰策略
现在让我进入freeMemoryIfNeeded()这个重磅函数

int freeMemoryIfNeeded(void) {
     /*
          mem_used:已经使用的内存
          mem_tofree：需要释放的内存
          mem_freed:已经释放的内存
     */
    size_t mem_used, mem_tofree, mem_freed;
    int slaves = listLength(server.slaves);

    /* Remove the size of slaves output buffers and AOF buffer from the
     * count of used memory. */
    // 计算出 Redis 目前占用的内存总数，但有两个方面的内存不会计算在内：
    // 1）从服务器的输出缓冲区的内存
    // 2）AOF 缓冲区的内存
    mem_used = zmalloc_used_memory();
   // @1 这部分计算内存的逻辑我们可以略过，无非就是 已经使用的内存-最大内存=需要释放的内存
    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. */
    // 如果目前使用的内存大小比设置的 maxmemory 要小，那么无须执行进一步操作
    if (mem_used <= server.maxmemory) return REDIS_OK;

    // 如果占用内存比 maxmemory 要大，但是 maxmemory 策略为不淘汰，那么直接返回
    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;

    // 初始化已释放内存的字节数为 0
    mem_freed = 0; 
    // 根据 maxmemory 策略，
    // 遍历每个数据库，释放内存【删除key】并记录被释放内存的字节数
   // @2已经释放的内存如果>=需要释放的内存  wilie循环终止，释放内存工作【惰性删key工作结束】
    while (mem_freed < mem_tofree) {
        int j, k, keys_freed = 0;

        // @3 遍历所有数据库找出要删除的key，释放内存
        for (j = 0; j < server.dbnum; j++) {
            long bestval = 0; /* just to prevent warning */
            sds bestkey = NULL; // 要删除的最合适的key
            dictEntry *de;   
            redisDb *db = server.db+j; // 第j个数据库
            dict *dict; // 数据库的词典，redis数据是键值对，存储在词典中

            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
            {
                // 如果策略是 allkeys-lru 或者 allkeys-random 
                // 那么淘汰的目标为所有数据库键
                // @4 我们目前就是分析这个策略 all-keys-lru,所以词典就是第j个数据库中全部键值对
                dict = server.db[j].dict;
            } else {
                // 如果策略是 volatile-lru 、 volatile-random 或者 volatile-ttl 
                // 那么淘汰的目标为带过期时间的数据库键
                dict = server.db[j].expires;
            }

            // 跳过空字典，接着下一次for循环
            if (dictSize(dict) == 0) continue;

            /* volatile-random and allkeys-random policy */
            // 如果使用的是随机策略，那么从目标字典中随机选出键，我们暂时略过个if
            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 策略，
            // @5 那么从一个sample 键中选出 IDLE 时间最长的那个键， 让我重点分析这个分支
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            {
                // @6 pool是一个数组，所有要删除的key按照idle time从小到大排序
                // 这个数组在服务启动时进行初始化
                struct evictionPoolEntry *pool = db->eviction_pool;
                // @7 这个while循环就是要找出第j个数据库中要删除的最合适的key，也就是idle time
                // 最长的那个key
                while(bestkey == NULL) {
                    
                    // @8 这个方法就是要找出词典中要删除的key，这些要删除的key
                    // 以idle time递增的方式保存在 eviction_pool
                    // 因为我们分析的是 all-keys-lru,它的 sampledict和dict是一样的，这里先不
                    // 详细解释解释这个函数，稍后我们再分析，只需要记住，他填充eviction_pool，里面是                                                 //字典中需要删除的 key就行了
                    evictionPoolPopulate(dict, db->dict, db->eviction_pool);
                    /* Go backward from best to worst element to evict. */
                    for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                        if (pool[k].key == NULL) continue;
                        de = dictFind(dict,pool[k].key);

                        /* Remove the entry from the pool. */
                        // 从数组中删除这个key
                        sdsfree(pool[k].key);
                        /* Shift all elements on its right to left. */
                        // 这个可以忽略，就是调整数组
                        memmove(pool+k,pool+k+1,
                            sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
                        /* Clear the element on the right which is empty
                         * since we shifted one position to the left.  */
                        pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
                        pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;

                        /* If the key exists, is our pick. Otherwise it is
                         * a ghost and we need to try the next element. */
                       
                        if (de) {
                            // @9 返回指定节点的键，说明在第j个数据库中找到这个要删除的最合适的key了
                            bestkey = dictGetKey(de);
                            break;
                        } else {
                            /* Ghost... */
                            // 继续遍历
                            continue;
                        }
                    } // 遍历 pool数组的for循环结束
                }// 找 第j个数据中最合适的key结束
            
            /* Finally remove the selected key. */
            // @10 这一步是真正的删除被选中的键
            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. */
                // 计算删除键所释放的内存数量
                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();
            }
        }

         // 如果遍历完所有的数据库，删除key的个数为0，则返回错误，这个是快速失败
        if (!keys_freed) return REDIS_ERR; /* nothing to free... */
    } // end 最外层的while，删除key的工作结束

    return REDIS_OK;
}

流程图如下：

至此我们分析完了freeMemoryIfNeeded（），还不算太复杂吧。在分析过程中我删掉了一些无用代码和分支。大家再比照着源码分析一下，相信很快就能掌握它。现在，我们总结下这个函数所做的事情是不是和我们开头所列举的吻合呢？我想应该吻合吧。在分析freeMemoryIfNeeded()这个函数的时候，大家是否还记得有一个pool数组用来盛放要删除的key，还有一个函数evictionPoolPopulate()用来填充pool数组。那它究竟是怎样计算的呢？我们在下篇文章接着进行分析。
总结
学好redis，并用好redis并非那么容易。有时候学习源码并非为了装逼，而是学习作者的思路和其优秀思想并能借鉴之。的确，学习源码能让我们对其内部实现了解一二，在平时看来神秘的东西，通过阅读源码感觉“也不过尔尔”。在信息轰炸和科技日新月异的今天，我们需要自己冷静，需要自己思考，需要自己有独特的判断力，我们不能被别人裹挟着前进，我们更不可能把所有计算机的技术都了如指掌，我们只需要有一方面技术的沉淀就行了，知识都是相似相通的。

tips:

　　Redis提供了四个命令来设置过期时间（生存时间）。

　　①、EXPIRE <key> <ttl> ：表示将键 key 的生存时间设置为 ttl 秒。

　　②、PEXPIRE <key> <ttl> ：表示将键 key 的生存时间设置为 ttl 毫秒。

　　③、EXPIREAT <key> <timestamp> ：表示将键 key 的生存时间设置为 timestamp 所指定的秒数时间戳。

　　④、PEXPIREAT <key> <timestamp> ：表示将键 key 的生存时间设置为 timestamp 所指定的毫秒数时间戳。

　　PS：在Redis内部实现中，前面三个设置过期时间的命令最后都会转换成最后一个PEXPIREAT 命令来完成。

　　另外补充两个知识点：

　　一、移除键的过期时间

　　PERSIST <key> ：表示将key的过期时间移除。

　　二、返回键的剩余生存时间

　　TTL <key> ：以秒的单位返回键 key 的剩余生存时间。

　　PTTL <key> ：以毫秒的单位返回键 key 的剩余生存时间

假如你的redis中存在有10w个key，这时有大量的key是设置了过期时间的，当key的过期时间到了之后，有以下几个问题：

1.redis是如何淘汰这些过期的数据的？

        首先我们需要知道redis获取一个key时，对过期时间的判定：

在Redis内部，每当我们设置一个键的过期时间时，Redis就会将该键带上过期时间存放到一个过期字典中。当我们查询一个键时，Redis便首先检查该键是否存在过期字典中，如果存在，那就获取其过期时间。然后将过期时间和当前系统时间进行比对，比系统时间大，那就没有过期；反之判定该键过期

        redis过期时删除数据得方式有三种：定期删除与惰性删除

        1.定期删除

        redis默认每隔100ms,就会随机抽取一些设置了过期时间的key,检查其是否过期，过期就删除，注意这里是随机抽取一部分，不是全部。因为如果redis中存在大量key时，比如10w个，这时不可能去检查所有的key,严重影响性能,cpu压力巨大。所以只是抽取部分key。正因为如此，会导致部分key过期了，但没有被随机抽取到。这时候就需要惰性删除进行补充，这也是redis设计时同时除了定期删除，还有惰性删除的原因。

        2.定时删除

        当我们设置一个key到redis时，用一个定时器来负责监视key，当这个key过期就自动删除，虽然内存及时释放，但是十分消耗CPU资源，在大并发请求下CPU要尽可能的把时间都用在处理请求，而不是删除key，定时删除能保证内存中数据的最大新鲜度，因为它保证过期键值会在过期后马上被删除，其所占用的内存也会随之释放。但是立即删除对cpu是最不友好的。因为删除操作会占用cpu的时间，如果刚好碰上了cpu很忙的时候，比如正在做交集或排序等计算的时候，就会给cpu造成额外的压力，一般情况下不会使用。

        3.惰性删除

        惰性删除是指当我们获取某个key的时候，再临时检查该key是否过期，过期则删除。惰性删除的缺点也很明显，就是如果一些key使用频率低，那么它可能长时间存在内存中，占用大量内存

redis使用的过期删除策略是：惰性删除+定期删除。使用这两种结合能很大程度上提高优化redis性能，降低冗余。但还是会有问题，假如定期删除刚好没有删除掉某些过期key,而且这些key又没有使用，这时候就不会触发惰性删除，这些key将长时间存在内存中，占用大量内存，这时候就需要使用内存淘汰机制处理掉这些key.

2.设置完一个键的过期时间后，到了这个时间，这个键还能获取到么？假如获取不到那这个键还占据着内存吗？

        答案是到了时间这个key是获取不到的，但是这个key有可能还占据着内存。redis采用的定期删除+惰性删除的过期策略，会导致某些key躲过了定期删除，并且在未使用时，不会发生惰性删除，而长时间滞留在内存中。

3.redis的内存淘汰机制

        redis可以配置内存淘汰策略，具体实现可以了解下LRU算法，根据自己项目的实际情况使用：
1）noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。（应该没人用吧）。
2）allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。推荐使用，目前项目在用这种，这种用的最多。

        例如：有3个key,a最近10分钟使用了100次，b最近10分钟使用的50次，c最近一小时使用了1次。那么会淘汰掉c
3）allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。应该也没人用吧，你不删最少使用Key,去随机删。
4）volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。这种情况一般是把redis既当缓存，又做持久化存储的时候才用。不推荐
5）volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。依然不推荐
6）volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。不推荐
ps：如果没有设置 expire 的key, 不满足先决条件(prerequisites); 那么 volatile-lru, volatile-random 和 volatile-ttl 策略的行为, 和 noeviction(不删除) 基本上一致。

卑微小吴励志写博客第29天。

删除策略

过期删除

redis中的数据特征

• redis是一种内存级数据库，所有的数据均存储在内存中，通过TTL指令可以查看数据的状态。
  xx:具有时效性的数据
  -1：代表永久性数据
  -2：已经过期的数据 或 已经删除了的数据 或 未定义的数据

已经过期的数据真的被删除了吗？

redis让cpu处理很多指令的时候，cpu一下子处理不过来，但是删除的操作又没那么重要。所以就先没删，继续保存在内存中，什么时候删除呢？这就是redis的删除策略做的事，redis有三种删除策略。

时效性数据的存储结构

expires空间相当于是redis开辟的一个存放值的地址和对应过期时间的空间，删除策略相当于是维护下面这个空间中的东西，上面存的值不变。

删除策略的目标
在内存和cpu占用之间找到一个平衡，顾此失彼会造成整个redis的性能下降，甚至引发服务器宕机或者内存泄露。
就是在cpu闲的时候把那些过期的数据删除，忙的时候就不占用cpu了。

1、定时删除

• 创建一个定时器，当key设置有过期时间，且过期时间到达时，由定时器立即执行对key的删除。
• 
  到点了就干掉expires中和上面的key值。用处理器性能换内存空间。

优点：

• 节约内存，到点了就立即释放掉不必要的内存空间。

缺点

• cpu的压力会很大，不会考虑删除的时候cpu是否空闲，会影响redis服务器的响应时间和吞吐量。

2、惰性删除

• 数据到达过期时间，不做处理。等下次访问该数据时，发现未过期，则返回值；发现已经过期，删除（删除expires空间和key值），并返回不存在。

优点

• 节约cpu性能，当数据必须删除的时候才删除。

缺点

• 内存压力很大，出现过期数据会长期占用内存的情况。

其实就是拿内存换cpu性能。

3、定期删除

上面的两种方案都比较极端，要么牺牲空间，要么牺牲时间。有没有这种的方案？

• 周期性轮询redis库中的时效性数据，采用随机抽取策略，利用过期数据占比的方式控制删除的频度。

特点
1、CPU性能占用设置了峰值，检测频度可以自己配置。
2、内存压力不是很大，长期占用内存的冷数据会被持续清理。

总结：周期性抽查存储空间（随机抽查，重点抽查）。
redis内部用的是惰性删除和定期删除。

逐出算法

新数据进入redis时，如果内存不足怎么办？

redis使用内存存储数据，在执行每一条命令前，会调用freeMemoryIfNeeded（）检测内存是否充足，如果内存不满足新加入数据的最低存储要求，redis要临时删除一些数据为当前指令清理存储空间。
注意
逐出数据的过程不是100%能成功，如果执行一次后内存任然无法到达要求，会再次执行，如果对所有数据尝试完毕后，还是不是达到内存的要求，会爆出错误。

影响数据逐出的相关配置

数据逐出策略配置依据

• 使用info命令输出监控信息，查询缓存hit和miss的次数，根据业务需求调优Redis配置。