- int freeMemoryIfNeeded(void) {
- 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. */ 计算占用内存大小时, 并不计算 slave output buffer 和 aof buffer, 因此 maxmemory 应该比实际内存小, 为这两个 buffer 留足空间.
- 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.appendonly) {
- mem_used -= sdslen(server.aofbuf);
- mem_used -= sdslen(server.bgrewritebuf);
- }
- /* 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;
- 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 = dictGetEntryKey(de);
- }// 如果是 random delete, 则从 dict 中随机选一个 key
- /* 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 = dictGetEntryKey(de);
- /* When policy is volatile-lru we need an additonal 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); // 因为 dict->expires 维护的数据结构里并没有记录该 key 的最后访问时间
- o = dictGetEntryVal(de);
- thisval = estimateObjectIdleTime(o);
- /* Higher idle time is better candidate for deletion */
- if (bestkey == NULL || thisval> bestval) {
- bestkey = thiskey;
- bestval = thisval;
- }
- }// 为了减少运算量, redis 的 lru 算法和 expire 淘汰算法一样, 都是非最优解, lru 算法是在相应的 dict 中, 选择 maxmemory_samples(默认设置是 3) 份 key, 挑选其中 lru 的, 进行淘汰
- }
- /* 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 = dictGetEntryKey(de);
- thisval = (long) dictGetEntryVal(de);
- /* Expire sooner (minor expire unix timestamp) is better
- * candidate for deletion */
- if (bestkey == NULL || thisval < bestval) {
- bestkey = thiskey;
- bestval = thisval;
- }
- }// 注意 ttl 实现和上边一样, 都是挑选出 maxmemory_samples 份进行挑选
- }
- /* Finally remove the selected key. */
- if (bestkey) {
- long long delta;
- robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
- propagateExpire(db,keyobj); // 将 del 命令扩散给 slaves
- /* 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++;
- 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();
- }
- }// 在所有的 db 中遍历一遍, 然后判断删除的 key 释放的空间是否足够
- if (!keys_freed) return REDIS_ERR; /* nothing to free... */
- }
- return REDIS_OK;
- }
来源: http://www.jianshu.com/p/02e2065ad609