Redis过期淘汰与内存释放机制

1.Redis过期机制

在实际应用中,有些信息是有时效性的,比如我们发了一个广告,和这个广告相关的一些信息就只有在约定好的广告期间才有效。所以,我们有时候需要对redis中的一些数据设置他们的有效期,当数据过了有效期之后就需要删除他们,因为redis本身可用内存有限,所以不能让这些垃圾信息来占用内存。

1.1.Redis过期命令及演示

在redis设置键过期的命令是 expire key ttl (ttl以秒为单位),如果返回1则说明设置成功,如果返回0则说明失败(键不存在或在低版本的redis中只能对键设置一次过期时间)。

如下图所示,我们启动我们redis服务器和客户端,然后设置一个叫name的键,然后将它的过期时间设置为10秒之后。然后我们可以用ttl(time to live)命令查看它还有多久的生存时间,如下图返回的7说明它还有7秒中的生存时间。当过了设置的过期时间,我们再来查看name的剩余生存时间,发现返回了-2,说明name已经过期被删除了,然后我们查看name,发现果然数据库里已经没有这个键了。

这里要注意的一点是,在对一个键执行set命令后,原来加在它身上的过期时间就会失效,它就会变成一个persistent key了。所以编程的时候要注意,或者我们用persist key 这个命令,也可以将一个键身上的过期时间移除让它变成一个persistent key。演示如下图:


当name设置了过期时间后,变成了一个volatile key,然后这个时候我们再它还没过期的时间马上用set命令改变它的值,然后这个时候他就变成了一个persistent key了,然后就算我们过了过期时间查看name发现它还是存在。Persist命令也是同样的效果,读者可以自己去尝试。

1.2.Redis过期机制原理

在Redis中,对键的过期淘汰采取了两种策略,一种是懒惰淘汰策略,一种是定期淘汰策略。
1. 懒惰淘汰策略
在redis源码中,实现懒惰淘汰策略的是函数expireIfNeeded,所有读写数据库命令在执行之前都会调用expireIfNeeded函数对输入键进行检查。如果过期就删除,如果没过期就正常访问。

int expireIfNeeded(redisDb *db, robj *key) {
    mstime_t when = getExpire(db,key);
    mstime_t now;
 
    if (when < 0) return 0; /* No expire for this key */ /* Don't expire anything while loading. It will be done later. */ if (server.loading) return 0; /* If we are in the context of a Lua script, we claim that time is * blocked to when the Lua script started. This way a key can expire * only the first time it is accessed and not in the middle of the * script execution, making propagation to slaves / AOF consistent. * See issue #1525 on Github for more information. */ now = server.lua_caller ? server.lua_time_start : mstime(); /* If we are running in the context of a slave, return ASAP: * the slave key expiration is controlled by the master that will * send us synthesized DEL operations for expired keys. * * Still we try to return the right information to the caller, * that is, 0 if we think the key should be still valid, 1 if * we think the key is expired at this time. */ /*如果我们正在slaves上执行读写命令,就直接返回, *因为slaves上的过期是由master来发送删除命令同步给slaves删除的, *slaves不会自主删除*/ if (server.masterhost != NULL) return now > when;
    /*只是回了一个判断键是否过期的值,0表示没有过期,1表示过期
     *但是并没有做其他与键值过期相关的操作*/
 
    /* Return when this key has not expired */
    /*如果没有过期,就返回当前键*/
    if (now <= when) return 0; /* Delete the key */ /*增加过期键个数*/ server.stat_expiredkeys++; /*传播键过期的消息*/ propagateExpire(db,key); notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,"expired",key,db->id);
    /*删除过期键*/
    return dbDelete(db,key);
}

以上是expireIfNeeded函数的源码,源码中的注释已经很清楚的描述出了它的逻辑,我只是将他翻译成中文,然后加了一点自己的注释。值得注意的如果是slaves,它是不能自主删除键的,需要由master发del命令,然后同步到所有的slaves,这样就不会造成主从数据不一致的问题。

2. 定期删除策略
在redis源码中,实现定期淘汰策略的是函数activeExpireCycle,每当周期性函数serverCron执行时,该函数会调用databasesCron函数;然后databasesCron会调用activeExpireCycle函数进行主动的过期键删除。具体方法是在规定的时间内,多次从expires中随机挑一个键,检查它是否过期,如果过期则删除。

这个函数的源码有点长,没办法一次贴出来,就分步讲解吧。首先这个函数有两种执行模式,一个是快速模式一个是慢速模式,体现在代码中就是timelimit这个变量中,这个变量是用来约束这个函数的运行时间的,我们可以考虑这样一个场景,就是数据库中有很多过期的键需要清理,那么这个函数就会一直运行很长时间,这样一直占用CPU显然是不合理的,所以需要这个变量来约束,当函数运行时间超过了这个阈值,就算还有很多过期键没有清理,函数也强制退出。

在快速模式下,timelimit的值是固定的,是一个预定义的常量ACTIVE_EXPIRE_CYCLE_FAST_DURATION,在慢速模式下,这个变量的值是通过下面的代码计算的

/* We can use at max ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC percentage of CPU time
  * per iteration. Since this function gets called with a frequency of
  * server.hz times per second, the following is the max amount of
  * microseconds we can spend in this function. */
  timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;

就像注释说的,他的计算依据是之前预定义好的每次迭代只能占用的CPU时间比例,以及这个函数被调用的频率。

Redis中也可能有多个数据库,所以这个函数会遍历多个数据库来清楚过期键 ,但是是根据下面代码的原则来确定要遍历的数据库的个数的。

/* We usually should test REDIS_DBCRON_DBS_PER_CALL per iteration, with
     * two exceptions:
     *
     * 1) Don't test more DBs than we have.
     * 2) If last time we hit the time limit, we want to scan all DBs
     * in this iteration, as there is work to do in some DB and we don't want
     * expired keys to use memory for too much time. */
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;

dbs_per_call变量就是函数会遍历的数据库的个数,他有一个预定义的值REDIS_DBCRON_DBS_PER_CALL,但是如果这个值大于现在redis中本身的数据库的个数,我们就要将它的值变成当前的数据库的实际个数,或者上次的函数是因为超时强制退出了,说明可能有的数据库在上次函数调用时没有遍历到,里面的过期键没有清理掉,所以也要将这次遍历的数据库的个数改成实际数据库的个数。

for (j = 0; j < dbs_per_call; j++) {
    int expired;
    redisDb *db = server.db+(current_db % server.dbnum);
 
    /* Increment the DB now so we are sure if we run out of time
     * in the current DB we'll restart from the next. This allows to
     * distribute the time evenly across DBs. */
    current_db++;

数据库的遍历是在这个大的for循环里,其中值得留意的是current_db这个变量是一个static变量,这么做的好处是,如果真的发生了我们上面说的情况,上一次函数调用因为超时而强制退出,这个变量就会记录下这一次函数应该从哪个数据库开始遍历,这样会使得函数用在每个数据库的时间尽量平均,就不会出现有的数据库里面的过期键一直没有清理的情况。

每个数据库的过期键清理的操作是在下面的这个do while 循环中(由于代码过长,所以中间有很多代码我把它隐藏了,现在看到的只是一个大框架,稍后我会对其中的部分详细讲解)

/* Continue to expire if at the end of the cycle more than 25%
 * of the keys were expired. */
do {
    ... 
    /* If there is nothing to expire try next DB ASAP. */
    if ((num = dictSize(db->expires)) == 0) {
    ... 
    }
    slots = dictSlots(db->expires);
    now = mstime();
 
    if (num && slots > DICT_HT_INITIAL_SIZE &&
        (num*100/slots < 1)) break; ... if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
        num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
 
    while (num--) {
     ... 
    }
    /* Update the average TTL stats for this database. */
    if (ttl_samples) {
    ...
    }
    iteration++;
    if ((iteration & 0xf) == 0) { /* check once every 16 iterations. */
    ...
    }
    if (timelimit_exit) return;
 
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);

注意while循环条件,ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP是我们每个循环希望查到的过期键的个数,如果我们每次循环过后,被清理的过期键的个数超过了我们期望的四分之一,我们就会继续这个循环,因为这说明当前数据库中过期键的个数比较多,需要继续清理,如果没有达到我们期望的四分之一,就跳出while循环,遍历下一个数据库。

这个函数最核心的功能就是清除过期键,这个功能的实现就是在while(num--)这个循环里面。

while (num--) {
    dictEntry *de;
    long long ttl;
 
    if ((de = dictGetRandomKey(db->expires)) == NULL) break;
    ttl = dictGetSignedIntegerVal(de)-now;
    if (activeExpireCycleTryExpire(db,de,now)) expired++;
    if (ttl < 0) ttl = 0;
    ttl_sum += ttl;
    ttl_samples++;
}

他先从数据库中设置了过期时间的键的集合中随机抽取一个键,然后调用activeExpireCycleTryExpire函数来判断这个键是否过期,如果过期就删除键,activeExpireCycleTryExpire函数的源码如下:

int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    long long t = dictGetSignedIntegerVal(de);
    if (now > t) {
        sds key = dictGetKey(de);
        robj *keyobj = createStringObject(key,sdslen(key));
 
        propagateExpire(db,keyobj);
        dbDelete(db,keyobj);
        notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
            "expired",keyobj,db->id);
        decrRefCount(keyobj);
        server.stat_expiredkeys++;
        return 1;
    } else {
        return 0;
    }
}

这个函数的逻辑很简单,就是先获取键de的过期时间,和现在的时间比较,如果过期,就生成该键de的对象,然后传播该键de的过期信息,并且删除这个键,然后增加过期键总数。

最后就是控制函数运行时间的部分了,代码如下:

/* We can't block forever here even if there are many keys to
 * expire. So after a given amount of milliseconds return to the
 * caller waiting for the other active expire cycle. */
iteration++;
if ((iteration & 0xf) == 0) { /* check once every 16 iterations. */
    long long elapsed = ustime()-start;
 
    latencyAddSampleIfNeeded("expire-cycle",elapsed/1000);
    if (elapsed > timelimit) timelimit_exit = 1;
}
if (timelimit_exit) return;

这里有一个迭代次数的变量iteration,每迭代16次就来计算函数已经运行的时间,如果这个时间超过了之前的限定时间timelimit,就将timelimit_exit这个标志置为1,说明程序超时,需要强制退出了。

懒惰淘汰机制和定时淘汰机制是一起合作的,就好像你开一家餐馆一样,定时淘汰机制就是你每隔几小时去查看所有的菜品是否还有,如果有的菜品现在卖光了,就将他从菜单上划掉。懒惰淘汰机制就是有客人要点宫保鸡丁,你马上去查看还有没有,如果今天的已经卖完了,就告诉客人不好意思,我们卖完了,然后将宫保鸡丁从菜单上划掉。只有等下次有原料再做的时候,才又把它放到菜单上去。

2.Redis内存释放机制

像我们前面的章节介绍过一样,每台redis的服务器的内存都是有限的,而且也不是所有的内存都用来存储信息。而且redis的实现并没有在内存这块做太多的优化,所以实现者为了防止内存过于饱和,采取了一些措施,第一种措施就是第1节所讲的,通过删除过期键可以一定程度上释放内存,但是最主要的还是增加了一个maxmemory的配置,和6种内存释放策略。

2.1.演示

最大内存的设置是通过设置maxmemory来完成的,格式为maxmemory bytes ,当目前使用的内存超过了设置的最大内存,就要进行内存释放了, 当需要进行内存释放的时候,需要用某种策略对保存的的对象进行删除。Redis有六种策略(默认的策略是volatile-lru。):

  • volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰
  • volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数据淘汰
  • volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据淘汰
  • allkeys-lru:从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰
  • allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
  • no-enviction:禁止淘汰数据
    除此之外还有一个配置项,就是maxmemory-samples,默认值是3,因为上面的策略代码实现的都是近似算法,所以不管是lru算法,还是ttl,都并不是在数据库中所有的数据为基础的算法,因为当数据库的数据很多的时候,这样效率太低,所以代码中都是基于maxmemory-samples个数据的近似算法。
    下面我们先来开启redis服务,然后为了演示方便,我将最大使用内存设置得比较小,可以用config set 命令直接在客户端修改服务器配置,如下所示:


由上图所示,我在之前随便用set命令写了很多数据,然后我用config set 命令将最大使用内存设置为900000 bytes,9k(k=1000,kb=1024),然后这个时候服务器就会打印以下的信息:

提示我们现在已经使用的内存已经超过了设置的最大使用内存,这将会导致键的删除或者是让redis无法接受写命令。因为内存释放策略默认的是volatile-lru,但是在刚才的数据中我没有设置任何键的过期时间,所以再这个策略下,并不会删除任何数据,这样就会导致redis无法再接受任何写命令,如上图,我这是再用 set 命令,就会报OOM的错误。

2.2.Redis内存释放原理

Redis释放内存是由函数freeMemoryIfNeeded完成的,redis用processCommand函数处理每条命令,函数中在真正处理命令之前都会调用freeMemoryIfNeeded函数,这个函数会判断当前使用的内存是否超过了最大使用内存,如果超过,就会根据内存释放策略释放内存。
freeMemoryIfNeeded函数首先会计算出当前使用了多少内存,注意,这里并不会包括slaves 输出缓存以及AOF缓存,源码如下:

/* 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();
}

然后就会判断已经使用内存是否超过最大使用内存,如果没有超过就返回REDIS_OK,

/* Check if we are over the memory limit. */
if (mem_used <= server.maxmemory) return REDIS_OK;

当超过了最大使用内存时,就要判断此时redis到底采用的是那种内存释放策略,根据不同的策略,采取不同的手段。

1.首先判断是否是为no-enviction策略,如果是,则返回REDIS_ERR,然后redis就不再接受任何写命令了。

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

2.接下来就判断淘汰策略是基于所有的键还是只是基于设置了过期时间的键,如果是针对所有的键,就从server.db[j].dict中取数据,如果是针对设置了过期时间的键,就从server.db[j].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;
}

3.然后判断是不是random策略,包括volatile-random 和allkeys-random,这两种策略是最简单的,就是在上面的数据集中随便去一个键,然后删掉。

if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
    server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
    de = dictGetRandomKey(dict);
    bestkey = dictGetKey(de);
}

4.然后就是判断是lru策略还是ttl策略,如果是lru策略就采用lru近似算法,代码如下:

/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
    server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
    struct evictionPoolEntry *pool = db->eviction_pool;
 
    while(bestkey == NULL) {
        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. */
            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) {
                bestkey = dictGetKey(de);
                break;
            } else {
                /* Ghost... */
                continue;
            }
        }
    }
}

实现lru算法,用了一个辅助数据结构evictionPoolEntry(驱逐池)和辅助函数evictionPoolPopulate(驱逐池填充),evictionPoolEntry的数据结构如下:

#define REDIS_EVICTION_POOL_SIZE 16
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time. */
    sds key;                    /* Key name. */
};

这个数据结构记录了一个键的名字和他的空闲时间(未使用的时间,这个值越长,说明该键越长时间没有使用),我们之前介绍过,这里的lru算法是一个近似算法,它只是基于一小部分数据的lru算法,这里的小部分数据在代码中的体现就是这个“驱逐池”中的数据,其实就是一个结构数组,数组的排列是以每个键的空闲时间为顺序,空闲时间长的在右边,短的在左边。

在lru算法开始前,函数首先调用evictionPoolPopulate来将这个“池”填满数据,下面主要介绍他的填充逻辑,当要填充一个键时,首先从“池”里面已有的数据中从左到右找到第一个键的空闲时间比要填充的键的空闲时间大的键,用变量k记录位置。如果k为0,而且数组不为空,则说明要填充的键的空闲时间比数组中原有的键的空闲时间都要小,这样的键我们直接抛弃,因为lru淘汰的是空闲时间长的键。如果k不为0,而且此时数组还有空闲的位置,则将目标键插入k的位置,然后将原数组从k到尾部的键都向右移动一个位置。如果此时数组没有空闲位置,就将目标数据插到k-1的位置,然后将数组开始到k的键都向左移动一个位置,再次申明,lru淘汰的是空闲时间长的键,所以我们并不关心空闲时间短的数据(也就是数组左边的键)。

while (k < REDIS_EVICTION_POOL_SIZE &&
       pool[k].key &&
       pool[k].idle < idle) k++;
if (k == 0 && pool[REDIS_EVICTION_POOL_SIZE-1].key != NULL) {
    /* Can't insert if the element is < the worst element we have
     * and there are no empty buckets. */
    continue;
} else if (k < REDIS_EVICTION_POOL_SIZE && pool[k].key == NULL) {
    /* Inserting into empty position. No setup needed before insert. */
} else {
    /* Inserting in the middle. Now k points to the first element
     * greater than the element to insert.  */
    if (pool[REDIS_EVICTION_POOL_SIZE-1].key == NULL) {
        /* Free space on the right? Insert at k shifting
         * all the elements from k to end to the right. */
        memmove(pool+k+1,pool+k,
            sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
    } else {
        /* No free space on right? Insert at k-1 */
        k--;
        /* Shift all elements on the left of k (included) to the
         * left, so we discard the element with smaller idle time. */
        sdsfree(pool[0].key);
        memmove(pool,pool+1,sizeof(pool[0])*k);
    }
}
pool[k].key = sdsdup(key);
pool[k].idle = idle;

evictionPoolPopulate函数到这里就介绍的差不多了,当“驱逐池“填充完毕后,就开始从池子里面获取将要删除的键了,删除数据的顺序是从右向左,因为右边的空闲时间大,获取了将要删除的键之后要将这个键从这个“池”里面删除。

如果是ttl策略。ttl策略很简单,就是取maxmemory_samples个键,然后比较他们的过期时间,然后从这些键中找到最快过期的那个键,就是我们将要删除的键。代码如下:

/* 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;
        }
    }
}

根据不同的策略,我们找到了将要删除的键,下面就是将他们删除的时候了,代码如下:

/* 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. */
    delta = (long long) zmalloc_used_memory();
    latencyStartMonitor(eviction_latency);
    dbDelete(db,keyobj);    
    latencyEndMonitor(eviction_latency);
    latencyAddSampleIfNeeded("eviction-del",eviction_latency);
    latencyRemoveNestedEvent(latency,eviction_latency);
    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();
}

还没有评论,快来抢沙发!

发表评论

  • 😉
  • 😐
  • 😡
  • 😈
  • 🙂
  • 😯
  • 🙁
  • 🙄
  • 😛
  • 😳
  • 😮
  • emoji-mrgree
  • 😆
  • 💡
  • 😀
  • 👿
  • 😥
  • 😎
  • ➡
  • 😕
  • ❓
  • ❗
  • 67 queries in 0.419 seconds