redis源码之惰性删除策略分析(一)

2021/6/19 19:27:18

本文主要是介绍redis源码之惰性删除策略分析(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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



这篇关于redis源码之惰性删除策略分析(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程