本文浅显的谈谈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并非那么容易。有时候学习源码并非为了装逼，而是学习作者的思路和其优秀思想并能借鉴之。的确，学习源码能让我们对其内部实现了解一二，在平时看来神秘的东西，通过阅读源码感觉“也不过尔尔”。在信息轰炸和科技日新月异的今天，我们需要自己冷静，需要自己思考，需要自己有独特的判断力，我们不能被别人裹挟着前进，我们更不可能把所有计算机的技术都了如指掌，我们只需要有一方面技术的沉淀就行了，知识都是相似相通的。