用户工具

站点工具


about_redis_20

Redis那些事儿 第二十章 内存的分配驱逐策略

作者:陈科

联系方式:chenke1818@gmail.com

转载请说明出处:http://www.dumpcache.com/wiki/doku.php?id=about_redis_20

1.内存申请/释放原理

redis的内存分配,完全依赖malloc/calloc的系统调用:

void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);
 
    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}
 
void *zcalloc(size_t size) {
    void *ptr = calloc(1, size+PREFIX_SIZE);
 
    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}

2.内存淘汰策略

2.1主动失效

在某些场景会触发主动失效:

int expireIfNeeded(redisDb *db, robj *key) {
    获取主键的失效时间
    long long when = getExpire(db,key);
    假如失效时间为负数,说明该主键未设置失效时间(失效时间默认为-1),直接返回0
    if (when < 0) return 0;
    假如Redis服务器正在从RDB文件中加载数据,暂时不进行失效主键的删除,直接返回0
    if (server.loading) return 0;
    假如当前的Redis服务器是作为Slave运行的,那么不进行失效主键的删除,因为Slave
    上失效主键的删除是由Master来控制的,但是这里会将主键的失效时间与当前时间进行
    一下对比,以告知调用者指定的主键是否已经失效了
    if (server.masterhost != NULL) {
        return mstime() > when;
    }
    如果以上条件都不满足,就将主键的失效时间与当前时间进行对比,如果发现指定的主键
    还未失效就直接返回0
    if (mstime() <= when) return 0;
    如果发现主键确实已经失效了,那么首先更新关于失效主键的统计个数,然后将该主键失
    效的信息进行广播,最后将该主键从数据库中删除
    server.stat_expiredkeys++;
    propagateExpire(db,key);
    return dbDelete(db,key);
}

2.2被动失效

在beforeSleep的主循环以及databasesCron定时器都会调用activeExpireCycle:

void activeExpireCycle(void) {
    因为每次调用activeExpireCycle函数不会一次性检查所有Redis数据库,所以需要记录下
    每次函数调用处理的最后一个Redis数据库的编号,这样下次调用activeExpireCycle函数
    还可以从这个数据库开始继续处理,这就是current_db被声明为static的原因,而另外一
    个变量timelimit_exit是为了记录上一次调用activeExpireCycle函数的执行时间是否达
    到时间限制了,所以也需要声明为static
    static unsigned int current_db = 0;
    static int timelimit_exit = 0;      
    unsigned int j, iteration = 0;
    每次调用activeExpireCycle函数处理的Redis数据库个数为REDIS_DBCRON_DBS_PER_CALL
    unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
    long long start = ustime(), timelimit;
    如果当前Redis服务器中的数据库个数小于REDIS_DBCRON_DBS_PER_CALL,则处理全部数据库,
    如果上一次调用activeExpireCycle函数的执行时间达到了时间限制,说明失效主键较多,也
    会选择处理全部数据库
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;
    执行activeExpireCycle函数的最长时间(以微秒计),其中REDIS_EXPIRELOOKUPS_TIME_PERC
    是单位时间内能够分配给activeExpireCycle函数执行的CPU时间比例,默认值为25,server.hz
    即为一秒内activeExpireCycle的调用次数,所以这个计算公式更明白的写法应该是这样的,即
    (1000000 * (REDIS_EXPIRELOOKUPS_TIME_PERC / 100)) / server.hz
    timelimit = 1000000*REDIS_EXPIRELOOKUPS_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;
    遍历处理每个Redis数据库中的失效数据
    for (j = 0; j < dbs_per_call; j++) {
        int expired;
        redisDb *db = server.db+(current_db % server.dbnum);
        此处立刻就将current_db加一,这样可以保证即使这次无法在时间限制内删除完所有当前
       数据库中的失效主键,下一次调用activeExpireCycle一样会从下一个数据库开始处理,
       从而保证每个数据库都有被处理的机会
        current_db++;
        开始处理当前数据库中的失效主键
        do {
            unsigned long num, slots;
            long long now;
            如果expires字典表大小为0,说明该数据库中没有设置失效时间的主键,直接检查下
           一数据库
            if ((num = dictSize(db->expires)) == 0) break;
            slots = dictSlots(db->expires);
            now = mstime();
            如果expires字典表不为空,但是其填充率不足1%,那么随机选择主键进行检查的代价
           会很高,所以这里直接检查下一数据库
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;
            expired = 0;
            如果expires字典表中的entry个数不足以达到抽样个数,则选择全部key作为抽样样本
            if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
                num = REDIS_EXPIRELOOKUPS_PER_CRON;
            while (num--) {
                dictEntry *de;
                long long t;
                随机获取一个设置了失效时间的主键,检查其是否已经失效
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                t = dictGetSignedIntegerVal(de);
                if (now > t) {
            发现该主键确实已经失效,删除该主键
                    sds key = dictGetKey(de);
                    robj *keyobj = createStringObject(key,sdslen(key));
                    同样要在删除前广播该主键的失效信息
                    propagateExpire(db,keyobj);
                    dbDelete(db,keyobj);
                    decrRefCount(keyobj);
                    expired++;
                    server.stat_expiredkeys++;
                }
            }
            每进行一次抽样删除后对iteration加一,每16次抽样删除后检查本次执行时间是否
           已经达到时间限制,如果已达到时间限制,则记录本次执行达到时间限制并退出
            iteration++;
            if ((iteration & 0xf) == 0 &&
                (ustime()-start) > timelimit)
            {
                timelimit_exit = 1;
                return;
            }
        如果失效的主键数占抽样数的百分比大于25%,则继续抽样删除过程
        } while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4); 
    }
}

2.3key的lru策略

针对cache redis,可以设置key的lru策略,这样可以限制内存的最大上限。

maxmemory 2mb
maxmemory-policy allkeys-lru

在processCommand执行的时候,假如设置了maxmemory就会触发该场景:

if (server.maxmemory) {
        int retval = freeMemoryIfNeeded();
        if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
            flagTransaction(c);
            addReply(c, shared.oomerr);
            return REDIS_OK;
        }
    }

我们来看freeMemoryIfNeeded:

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;
 
        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;
 
            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;
            }
            if (dictSize(dict) == 0) continue;
 
            /* volatile-random and allkeys-random policy */
            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*/
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            {
                for (k = 0; k < server.maxmemory_samples; k++) {
                    sds thiskey;
                    long thisval;
                    robj *o;
 
                    de = dictGetRandomKey(dict);
                    thiskey = dictGetKey(de);
                    /* When policy is volatile-lru we need an additional lookup
                     * to locate the real key, as dict is set to db->expires. */
                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
                        de = dictFind(db->dict, thiskey);
                    o = dictGetVal(de);
                    thisval = estimateObjectIdleTime(o);
 
                    /* Higher idle time is better candidate for deletion */
                    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;
                    }
                }
            }
 
            /* 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();
                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;
}

上面代码假如配置了lru并且内存大小超过了maxmemory,则会对server.db[j].dict中的数据随机选择maxmemory_samples个key进行淘汰,maxmemory_samples默认为3

about_redis_20.txt · 最后更改: 2018/10/14 15:31 (外部编辑)