江苏龙网

  1. 主页 > 生活百科 > >

Redis数据淘汰算法( 二 )

算法Redis


当然，如果配置的淘汰策略为 noeviction，表示不能进行数据淘汰，所以需要返回 C_ERR 表示有错误 。
接着分析剩余的代码片段：
latencyStartMonitor(latency); while (mem_freed < mem_tofree) { int j, k, i, keys_freed = 0; static unsigned int next_db = 0; sds bestkey = NULL; int bestdbid; redisDb *db; dict *dict; dictEntry *de; if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) || server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { struct evictionPoolEntry *pool = EvictionPoolLRU; while(bestkey == NULL) { unsigned long total_keys = 0, keys; for (i = 0; i < server.dbnum; i++) { db = server.db+i; dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ? db->dict : db->expires; if ((keys = dictSize(dict)) != 0) { evictionPoolPopulate(i, dict, db->dict, pool); total_keys += keys; } } if (!total_keys) break; /* No keys to evict. */ for (k = EVPOOL_SIZE-1; k >= 0; k--) { if (pool[k].key == NULL) continue; bestdbid = pool[k].dbid; if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) { de = dictFind(server.db[pool[k].dbid].dict, pool[k].key); } else { de = dictFind(server.db[pool[k].dbid].expires, pool[k].key); } if (pool[k].key != pool[k].cached) sdsfree(pool[k].key); pool[k].key = NULL; pool[k].idle = 0; if (de) { bestkey = dictGetKey(de); break; } else { /* Ghost... Iterate again. */ } } } }如果内存使用总量超出限制，并且配置了淘汰策略，那么就开始数据淘汰过程 。在上面的代码中，mem_tofree 变量表示要淘汰的数据总量，而 mem_freed 变量表示已经淘汰的数据总量 。所以在 while 循环中的条件是 mem_freed < mem_tofree，表示淘汰的数据总量一定要达到 mem_tofree 为止 。
前面介绍过，Redis的淘汰策略有很多中，所以进行数据淘汰时需要根据配置的策略进行 。如果配置的淘汰策略是 LRU/LFU/TTL 的话，那么就进入 if 代码块 。在 if 代码块里，首先调用 evictionPoolPopulate() 函数选择一些缓存对象样本放置到 EvictionPoolLRU 数组中 。evictionPoolPopulate() 函数后面会进行分析，现在只需要知道 evictionPoolPopulate() 函数是选取一些缓存对象样本就可以了 。
获取到缓存对象样本后，还需要从样本中获取最合适的缓存对象进行淘汰，因为在选择样本时会把最合适的缓存对象放置在 EvictionPoolLRU 数组的尾部，所以只需要从 EvictionPoolLRU 数组的尾部开始查找一个不为空的缓存对象即可 。
else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM) { for (i = 0; i < server.dbnum; i++) { j = (++next_db) % server.dbnum; db = server.db+j; dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ? db->dict : db->expires; if (dictSize(dict) != 0) { de = dictGetRandomKey(dict); bestkey = dictGetKey(de); bestdbid = j; break; } } }如果使用随机淘汰策略，那么就进入 else if 代码块，这部分代码的逻辑很简单，如果配置的淘汰策略是 volatile-random，那么就从有过期时间的缓存对象中随机获取，否则就从所有的缓存对象中随机获取 。
if (bestkey) { db = server.db+bestdbid; robj *keyobj = createStringObject(bestkey,sdslen(bestkey)); propagateExpire(db,keyobj,server.lazyfree_lazy_eviction); delta = (long long) zmalloc_used_memory(); latencyStartMonitor(eviction_latency); // 删除缓存对象 if (server.lazyfree_lazy_eviction) dbAsyncDelete(db,keyobj); else dbSyncDelete(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(NOTIFY_EVICTED, "evicted", keyobj, db->id); decrRefCount(keyobj); keys_freed++; if (slaves) flushSlavesOutputBuffers(); if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) { if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) { mem_freed = mem_tofree; } } }如果找到要淘汰的缓存对象，那么就开始释放缓存对象所占用的内存空间 。除了需要释放缓存对象占用的内存空间外，还需要进行一些其他的操作，比如把淘汰的缓存对象同步到从服务器和把淘汰的缓存对象追加到 AOF文件 中等 。
当条件 mem_freed < mem_tofree 为假时便会退出 while 循环，说明Redis的内存使用总量已经小于最大的内存使用限制，freeMemoryIfNeeded() 函数便会返回 C_OK 表示成功执行 。
淘汰数据样本采集前面说了，当使用非随机淘汰策略时需要进行数据采样（volatile-lru/volatile-lfu/volatile-ttl/allkeys-lru/allkeys-lfu），数据采样通过 evictionPoolPopulate() 函数进行，由于此函数比较庞大，所以对代码分段分析：
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) { int j, k, count; dictEntry *samples[server.maxmemory_samples]; count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);


推荐阅读


上一篇：玩壶时要注意的方方面面

下一篇：可以从这几方面进行紫砂茶具保养