Redis 缓存淘汰策略
(1) 缓存淘汰是什么
(2) 为什么要缓存淘汰
(3) 缓存淘汰算法/页面置换算法原理
(3.1) LRU
LRU 算法背后的想法非常朴素：它认为刚刚被访问的数据，肯定还会被再次访问。
选择最近最久未被使用的数据进行淘汰。
优点：
不足：
可能造成缓存污染。
缓存污染：在一些场景下，有些数据被访问的次数非常少，甚至只会被访问一次。当这些数据服务完访问请求后，如果还继续留存在缓存中的话，就只会白白占用缓存空间。
典型场景：全表扫描，对所有数据进行一次读取，每个数据都被读取到了，
(3.2) LFU
记录数据被访问的频率，选择在最近使用最少的数据进行淘汰。
LFU算法是根据数据访问的频率来选择被淘汰数据的，所以LFU算法会记录每个数据的访问次数。当一个数据被再次访问时，就会增加该数据的访问次数。
不过，访问次数和访问频率还不能完全等同。访问频率是指在一定时间内的访问次数，也就是说，在计算访问频率时，我们不仅需要记录访问次数，还要记录这些访问是在多长时间内执行的。
(4) Redis里缓存有哪些淘汰策略
| 内存淘汰策略 | 解释 | 备注 |
|---|---|---|
| noeviction | 不进行数据淘汰 | |
| allkeys-random | 在所有key里随机筛选数据 | |
| allkeys-lru | 在所有key里筛选最近最久未使用的数据 | |
| allkeys-lfu | 在所有key里筛选最近最少使用的数据 | Redis 4.0 新增 |
| volatile-ttl | 在有过期时间key里根据过期时间的先后筛选 | |
| volatile-random | 在有过期时间key里随机筛选数据 | |
| volatile-lru | 在有过期时间key里筛选最近最久未使用的数据 | |
| volatile-lfu | 在有过期时间key里筛选最近最少使用的数据 | Redis 4.0 新增 |
lru (Least Recently Used) 最近最久未使用
lfu (Least Frequently Used) 最近最少使用
在redis3.0之前，默认淘汰策略是volatile-lru；在redis3.0及之后(包括3.0)，默认淘汰策略是noeviction。
在3.0及之后的版本，Redis 在使用的内存空间超过 maxmemory 值时，并不会淘汰数据。
对应到 Redis 缓存，也就是指，一旦缓存被写满了，再有写请求来时，Redis 不再提供服务，而是直接返回错误。
(4.1) Redis内存淘汰机制如何启用
Redis 的内存淘汰机制是如何启用近似 LRU 算法的
和Redis配置文件redis.conf中的两个配置参数有关：
maxmemory，该配置项设定了 Redis server 可以使用的最大内存容量，一旦 server 使用的实际内存量超出该阈值时，server 就会根据 maxmemory-policy 配置项定义的策略，执行内存淘汰操作；
maxmemory-policy，该配置项设定了 Redis server 的内存淘汰策略，主要包括近似 LRU 算法、LFU 算法、按 TTL 值淘汰和随机淘汰等几种算法。
(5) Redis里缓存淘汰算法原理
(5.1) Redis-LRU
LRU 算法在实际实现时，需要用链表管理所有的缓存数据，这会带来额外的空间开销。
而且，当有数据被访问时，需要在链表上把该数据移动到 MRU 端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 性能。
在 Redis 中，LRU 算法被做了简化，以减轻数据淘汰对缓存性能的影响。
Redis 并没有为所有的数据维护一个全局的链表，而是通过随机采样方式，选取一定数量（例如 100 个）的数据放入候选集合，后续在候选集合中根据 lru 字段值的大小进行筛选。
(3.2) Redis-LFU
LFU 缓存策略是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。
当使用 LFU 策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。
如果两个数据的访问次数相同，LFU 策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。
Redis 在实现 LFU 策略的时候，只是把原来 24bit 大小的 lru 字段，又进一步拆分成了两部分。
ldt 值：lru 字段的前 16bit，表示数据的访问时间戳；
counter 值：lru 字段的后 8bit，表示数据的访问次数。
在实现 LFU 策略时，Redis 并没有采用数据每被访问一次，就给对应的 counter 值加 1 的计数规则，而是采用了一个更优化的计数规则。
LFU 策略实现的计数规则是：每当数据被访问一次时，首先，用计数器当前的值乘以配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r 值时，计数器才加 1。
double r = (double)rand()/RAND_MAX;
...
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++; (4) LRU源码解读
(4.1) 全局LRU时钟值的计算
LRU算法需要知道数据的最近一次访问时间。因此，Redis设计了LRU时钟来记录数据每次访问的时间戳。
// file: src/server.h
/*
* redis对象
*/
typedef struct redisObject {
unsigned type:4; // 数据类型 （string/list/hash/set/zset等）
unsigned encoding:4; // 编码方式
unsigned lru:LRU_BITS; // LRU时间(相对于全局 lru_clock)
// 或 LFU数据(低8位保存频率 和 高16位保存访问时间)。
// LRU_BITS为24个bits
int refcount; // 引用计数 4字节
void *ptr; // 指针 指向对象的值 8字节
} robj;// file: src/server.c
void initServerConfig(void) {
// 计算全局LRU时钟值
server.lruclock = getLRUClock();
}// file: src/evict.c
/*
* 根据时钟分辨率返回 LRU 时钟。
* 这是一个减少位格式的时间，可用于设置和检查 redisObject 结构的 object->lru 字段。
*/
unsigned int getLRUClock(void) {
// mstime()是毫秒时间戳 // mstime()/1000=秒级时间戳
// 与运算 保证值 <= LRU_CLOCK_MAX
return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}从代码可以看出，LRU时钟精度是1000毫秒，也就是1秒。
#define LRU_BITS 24
// obj->lru的最大值 // LRU_CLOCK_MAX = 1^24 - 1
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
// LRU 时钟分辨率(毫秒)
#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
// file: src/server.c
/*
* 返回UNIX毫秒时间戳
* Return the UNIX time in milliseconds
*/
mstime_t mstime(void) {
return ustime()/1000;
}// file: src/server.c
/*
* 返回UNIX微秒时间戳
* Return the UNIX time in microseconds
*/
long long ustime(void) {
struct timeval tv;
long long ust;
gettimeofday(&tv, NULL);
ust = ((long long)tv.tv_sec)*1000000;
ust += tv.tv_usec;
return ust;
}(4.2) 在运行过程中LRU时钟值是如何更新的
和 Redis server 在事件驱动框架中，定期运行的时间事件所对应的 serverCron 函数有关。
serverCron 函数作为时间事件的回调函数，本身会按照一定的频率周期性执行，其频率值是由 Redis 配置文件 redis.conf 中的 hz 配置项决定的。
hz 配置项的默认值是 10，这表示 serverCron 函数会每 100 毫秒(1秒 / 10 = 100 毫秒)运行一次。
// file: src/server.c
/* This is our timer interrupt, called server.hz times per second.
* Here is where we do a number of things that need to be done asynchronously.
* For instance:
*
* - Active expired keys collection (it is also performed in a lazy way on
* lookup).
* - Software watchdog.
* - Update some statistic.
* - Incremental rehashing of the DBs hash tables.
* - Triggering BGSAVE / AOF rewrite, and handling of terminated children.
* - Clients timeout of different kinds.
* - Replication reconnection.
* - Many more...
*
* Everything directly called here will be called server.hz times per second,
* so in order to throttle execution of things we want to do less frequently
* a macro is used: run_with_period(milliseconds) { .... }
*/
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
/* We have just LRU_BITS bits per object for LRU information.
* So we use an (eventually wrapping) LRU clock.
*
* Note that even if the counter wraps it's not a big problem,
* everything will still work but some object will appear younger
* to Redis. However for this to happen a given object should never be
* touched for all the time needed to the counter to wrap, which is
* not likely.
*
* Note that you can change the resolution altering the
* LRU_CLOCK_RESOLUTION define. */
// 默认情况下，每100毫秒调用getLRUClock函数更新一次全局LRU时钟值
server.lruclock = getLRUClock();
}这样一来，每个键值对就可以从全局 LRU 时钟获取最新的访问时间戳了。
(4.3) key-value-LRU时钟值的初始化与更新
(4.3.1) key-LRU时钟初始化
对于key-value来说，它的 LRU 时钟值最初是在这个键值对被创建的时候，进行初始化设置的，这个初始化操作是在 createObject 函数中调用的。
// file: src/object.c
/*
* 创建一个redisObject对象
*
* @param type redisObject的类型
* @param *ptr 值的指针
*/
robj *createObject(int type, void *ptr) {
// 为redisObject结构体分配内存空间
robj *o = zmalloc(sizeof(*o));
// 省略部分代码
// 将lru字段设置为当前的 lruclock（分钟分辨率），或者 LFU 计数器。
// 判断内存过期策略
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
// 对应lfu
// LFU_INIT_VAL=5 对应二进制是 0101
// 或运算
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
// 对应lru
o->lru = LRU_CLOCK();
}
return o;
}(4.3.2) key-LRU时钟更新
只要一个key被访问了，它的 LRU 时钟值就会被更新。而当一个键值对被访问时，访问操作最终都会调用 lookupKey 函数。
// file: src/db.c
/*
* 低级key查找API
* 实际上并没有直接从应该依赖lookupKeyRead()、lookupKeyWrite()和lookupKeyReadWithFlags()的命令实现中调用。
*/
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
// 如果节点存在
if (de) {
// 从节点里获取redisObject
robj *val = dictGetVal(de);
/*
* 更新老化算法的访问时间。
* 如果我们有一个正在保存的子进程，请不要这样做，因为这会触发疯狂写入副本。
*/
// 没有活跃子进程 并且
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
// 更新lfu
updateLFU(val);
} else {
// 更新lru时间
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}(4.4) 近似LRU算法的实际执行
Redis 之所以实现近似 LRU 算法的目的，是为了减少内存资源和操作时间上的开销。
何时触发算法执行？
算法具体如何执行？
(4.4.1) 触发时机
近似 LRU 算法的主要逻辑是在 freeMemoryIfNeeded 函数中实现的
processCommand -> freeMemoryIfNeededAndSafe -> freeMemoryIfNeeded
(4.4.2) 近似LRU算法执行
主要分3大步
- 判断当前内存使用情况-getMaxmemoryState
- 更新待淘汰的候选键值对集合-evictionPoolPopulate
- 选择被淘汰的键值对并删除-freeMemoryIfNeeded
// file: src/evict.c
/* This function is periodically called to see if there is memory to free
* according to the current "maxmemory" settings. In case we are over the
* memory limit, the function will try to free some memory to return back
* under the limit.
*
* The function returns C_OK if we are under the memory limit or if we
* were over the limit, but the attempt to free memory was successful.
* Otherwise if we are over the memory limit, but not enough memory
* was freed to return back under the limit, the function returns C_ERR.
*/
int freeMemoryIfNeeded(void) {
int keys_freed = 0;
/* By default replicas should ignore maxmemory
* and just be masters exact copies. */
if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;
size_t mem_reported, mem_tofree, mem_freed;
mstime_t latency, eviction_latency, lazyfree_latency;
long long delta;
int slaves = listLength(server.slaves);
int result = C_ERR;
/* When clients are paused the dataset should be static not just from the
* POV of clients not being able to write, but also from the POV of
* expires and evictions of keys not being performed. */
if (clientsArePaused()) return C_OK;
// 如果当前内存使用量没有超过 maxmemory，返回
if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
return C_OK;
// 已经释放的内存大小
mem_freed = 0;
latencyStartMonitor(latency);
if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
goto cant_free; /* We need to free memory, but policy forbids. */
// 已经释放的内存大小 < 计划要释放的内存大小
while (mem_freed < mem_tofree) {
int j, k, i;
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)
{
// 淘汰池 / 采样key集合
struct evictionPoolEntry *pool = EvictionPoolLRU;
while(bestkey == NULL) {
unsigned long total_keys = 0, keys;
// 在keys过期时我们不想创建本地数据库去选择(哪些key删除)，
// 因此开始在每个数据库中填充采样key的淘汰池。
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. */
/* Go backward from best to worst element 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);
}
/* Remove the entry from the pool. */
if (pool[k].key != pool[k].cached)
sdsfree(pool[k].key);
pool[k].key = NULL;
pool[k].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... Iterate again. */
}
}
}
}
/* volatile-random and allkeys-random policy */
else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
{
/* When evicting a random key, we try to evict a key for
* each DB, so we use the static 'next_db' variable to
* incrementally visit all DBs. */
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;
}
}
}
/* Finally remove the selected key. */
if (bestkey) {
db = server.db+bestdbid;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
/* We compute the amount of memory freed by db*Delete() 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.
*
* Same for CSC invalidation messages generated by signalModifiedKey.
*
* 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);
if (server.lazyfree_lazy_eviction)
dbAsyncDelete(db,keyobj);
else
dbSyncDelete(db,keyobj);
latencyEndMonitor(eviction_latency);
latencyAddSampleIfNeeded("eviction-del",eviction_latency);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
signalModifiedKey(NULL,db,keyobj);
notifyKeyspaceEvent(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();
/* Normally our stop condition is the ability to release
* a fixed, pre-computed amount of memory. However when we
* are deleting objects in another thread, it's better to
* check, from time to time, if we already reached our target
* memory, since the "mem_freed" amount is computed only
* across the dbAsyncDelete() call, while the thread can
* release the memory all the time. */
if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
/* Let's satisfy our stop condition. */
mem_freed = mem_tofree;
}
}
} else {
goto cant_free; /* nothing to free... */
}
}
result = C_OK;
cant_free:
/* We are here if we are not able to reclaim memory. There is only one
* last thing we can try: check if the lazyfree thread has jobs in queue
* and wait... */
if (result != C_OK) {
latencyStartMonitor(lazyfree_latency);
while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
result = C_OK;
break;
}
usleep(1000);
}
latencyEndMonitor(lazyfree_latency);
latencyAddSampleIfNeeded("eviction-lazyfree",lazyfree_latency);
}
latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return result;
}
(4.4.2.1) 判断当前内存使用情况-getMaxmemoryState
// file: src/evict.c
/* Get the memory status from the point of view of the maxmemory directive:
* if the memory used is under the maxmemory setting then C_OK is returned.
* Otherwise, if we are over the memory limit, the function returns
* C_ERR.
*
* The function may return additional info via reference, only if the
* pointers to the respective arguments is not NULL. Certain fields are
* populated only when C_ERR is returned:
*
* 'total' total amount of bytes used.
* (Populated both for C_ERR and C_OK)
*
* 'logical' the amount of memory used minus the slaves/AOF buffers.
* (Populated when C_ERR is returned)
*
* 'tofree' the amount of memory that should be released
* in order to return back into the memory limits.
* (Populated when C_ERR is returned)
*
* 'level' this usually ranges from 0 to 1, and reports the amount of
* memory currently used. May be > 1 if we are over the memory
* limit.
* (Populated both for C_ERR and C_OK)
*/
int getMaxmemoryState(size_t *total, size_t *logical, size_t *tofree, float *level) {
size_t mem_reported, mem_used, mem_tofree;
/* Check if we are over the memory usage limit. If we are not, no need
* to subtract the slaves output buffers. We can just return ASAP. */
mem_reported = zmalloc_used_memory();
if (total) *total = mem_reported;
/* We may return ASAP if there is no need to compute the level. */
int return_ok_asap = !server.maxmemory || mem_reported <= server.maxmemory;
if (return_ok_asap && !level) return C_OK;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = mem_reported;
size_t overhead = freeMemoryGetNotCountedMemory();
mem_used = (mem_used > overhead) ? mem_used-overhead : 0;
/* Compute the ratio of memory usage. */
if (level) {
if (!server.maxmemory) {
*level = 0;
} else {
*level = (float)mem_used / (float)server.maxmemory;
}
}
if (return_ok_asap) return C_OK;
/* Check if we are still over the memory limit. */
if (mem_used <= server.maxmemory) return C_OK;
/* Compute how much memory we need to free. */
mem_tofree = mem_used - server.maxmemory;
if (logical) *logical = mem_used;
if (tofree) *tofree = mem_tofree;
return C_ERR;
}(4.4.2.2) 更新待淘汰的候选键值对集合-evictionPoolPopulate
// file: src/evict.c
/* This is an helper function for freeMemoryIfNeeded(), it is used in order
* to populate the evictionPool with a few entries every time we want to
* expire a key. Keys with idle time smaller than one of the current
* keys are added. Keys are always added if there are free entries.
*
* We insert keys on place in ascending order, so keys with the smaller
* idle time are on the left, and keys with the higher idle time on the
* right. */
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);
for (j = 0; j < count; j++) {
unsigned long long idle;
sds key;
robj *o;
dictEntry *de;
de = samples[j];
key = dictGetKey(de);
/* If the dictionary we are sampling from is not the main
* dictionary (but the expires one) we need to lookup the key
* again in the key dictionary to obtain the value object. */
if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
if (sampledict != keydict) de = dictFind(keydict, key);
o = dictGetVal(de);
}
/* Calculate the idle time according to the policy. This is called
* idle just because the code initially handled LRU, but is in fact
* just a score where an higher score means better candidate. */
if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
idle = estimateObjectIdleTime(o);
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
/* When we use an LRU policy, we sort the keys by idle time
* so that we expire keys starting from greater idle time.
* However when the policy is an LFU one, we have a frequency
* estimation, and we want to evict keys with lower frequency
* first. So inside the pool we put objects using the inverted
* frequency subtracting the actual frequency to the maximum
* frequency of 255. */
idle = 255-LFUDecrAndReturn(o);
} else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
/* In this case the sooner the expire the better. */
idle = ULLONG_MAX - (long)dictGetVal(de);
} else {
serverPanic("Unknown eviction policy in evictionPoolPopulate()");
}
/* Insert the element inside the pool.
* First, find the first empty bucket or the first populated
* bucket that has an idle time smaller than our idle time. */
k = 0;
while (k < EVPOOL_SIZE &&
pool[k].key &&
pool[k].idle < idle) k++;
if (k == 0 && pool[EVPOOL_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 < EVPOOL_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[EVPOOL_SIZE-1].key == NULL) {
/* Free space on the right? Insert at k shifting
* all the elements from k to end to the right. */
/* Save SDS before overwriting. */
sds cached = pool[EVPOOL_SIZE-1].cached;
memmove(pool+k+1,pool+k,
sizeof(pool[0])*(EVPOOL_SIZE-k-1));
pool[k].cached = cached;
} 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. */
sds cached = pool[0].cached; /* Save SDS before overwriting. */
if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);
memmove(pool,pool+1,sizeof(pool[0])*k);
pool[k].cached = cached;
}
}
/* Try to reuse the cached SDS string allocated in the pool entry,
* because allocating and deallocating this object is costly
* (according to the profiler, not my fantasy. Remember:
* premature optimization bla bla bla. */
int klen = sdslen(key);
if (klen > EVPOOL_CACHED_SDS_SIZE) {
pool[k].key = sdsdup(key);
} else {
memcpy(pool[k].cached,key,klen+1);
sdssetlen(pool[k].cached,klen);
pool[k].key = pool[k].cached;
}
pool[k].idle = idle;
pool[k].dbid = dbid;
}
}(4.4.2.3) 选择被淘汰的键值对并删除-freeMemoryIfNeeded
// file: src/evict.c
/* This function is periodically called to see if there is memory to free
* according to the current "maxmemory" settings. In case we are over the
* memory limit, the function will try to free some memory to return back
* under the limit.
*
* The function returns C_OK if we are under the memory limit or if we
* were over the limit, but the attempt to free memory was successful.
* Otherwise if we are over the memory limit, but not enough memory
* was freed to return back under the limit, the function returns C_ERR. */
int freeMemoryIfNeeded(void) {
int keys_freed = 0;
/* By default replicas should ignore maxmemory
* and just be masters exact copies. */
if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;
size_t mem_reported, mem_tofree, mem_freed;
mstime_t latency, eviction_latency, lazyfree_latency;
long long delta;
int slaves = listLength(server.slaves);
int result = C_ERR;
/* When clients are paused the dataset should be static not just from the
* POV of clients not being able to write, but also from the POV of
* expires and evictions of keys not being performed. */
if (clientsArePaused()) return C_OK;
if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
return C_OK;
mem_freed = 0;
latencyStartMonitor(latency);
if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
goto cant_free; /* We need to free memory, but policy forbids. */
while (mem_freed < mem_tofree) {
int j, k, i;
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;
/* We don't want to make local-db choices when expiring keys,
* so to start populate the eviction pool sampling keys from
* every DB. */
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. */
/* Go backward from best to worst element 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);
}
/* Remove the entry from the pool. */
if (pool[k].key != pool[k].cached)
sdsfree(pool[k].key);
pool[k].key = NULL;
pool[k].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... Iterate again. */
}
}
}
}
/* volatile-random and allkeys-random policy */
else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
{
/* When evicting a random key, we try to evict a key for
* each DB, so we use the static 'next_db' variable to
* incrementally visit all DBs. */
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;
}
}
}
/* Finally remove the selected key. */
if (bestkey) {
db = server.db+bestdbid;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
/* We compute the amount of memory freed by db*Delete() 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.
*
* Same for CSC invalidation messages generated by signalModifiedKey.
*
* 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);
if (server.lazyfree_lazy_eviction)
dbAsyncDelete(db,keyobj);
else
dbSyncDelete(db,keyobj);
latencyEndMonitor(eviction_latency);
latencyAddSampleIfNeeded("eviction-del",eviction_latency);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
signalModifiedKey(NULL,db,keyobj);
notifyKeyspaceEvent(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();
/* Normally our stop condition is the ability to release
* a fixed, pre-computed amount of memory. However when we
* are deleting objects in another thread, it's better to
* check, from time to time, if we already reached our target
* memory, since the "mem_freed" amount is computed only
* across the dbAsyncDelete() call, while the thread can
* release the memory all the time. */
if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
/* Let's satisfy our stop condition. */
mem_freed = mem_tofree;
}
}
} else {
goto cant_free; /* nothing to free... */
}
}
result = C_OK;
cant_free:
/* We are here if we are not able to reclaim memory. There is only one
* last thing we can try: check if the lazyfree thread has jobs in queue
* and wait... */
if (result != C_OK) {
latencyStartMonitor(lazyfree_latency);
while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
result = C_OK;
break;
}
usleep(1000);
}
latencyEndMonitor(lazyfree_latency);
latencyAddSampleIfNeeded("eviction-lazyfree",lazyfree_latency);
}
latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return result;
}(5) LFU源码解读
LFU 算法的启用，是通过设置 Redis 配置文件 redis.conf 中的 maxmemory 和 maxmemory-policy。
LFU 算法的实现可以分成三部分内容，分别是键值对访问频率记录、键值对访问频率初始化和更新，以及LFU算法淘汰数据。
(5.1) 键值对访问频率记录
每个键值对的值都对应了一个 redisObject 结构体，其中有一个 24 bits 的 lru 变量。
LRU 算法和 LFU 算法并不会同时使用。为了节省内存开销，Redis 源码就复用了 lru 变量来记录 LFU 算法所需的访问频率信息。
记录LFU算法的所需信息时，它会用24 bits中的低8 bits作为计数器，来记录键值对的访问次数，同时它会用24 bits中的高16 bits，记录访问的时间戳。
|<---访问时间戳--->|< 计数器 >|
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+ (5.2) 键值对访问频率初始化和更新
(5.2.1) 初始化
键值对 lru变量初始化是在 创建redisObject调用 createObject 函数时完成的。
主要分2步：
第一部是 lru 变量的高16位，是以1分钟为精度的 UNIX 时间戳。(LFUGetTimeInMinutes)
第二部是 lru 变量的低8位，被设置为宏定义 LFU_INIT_VAL，默认值为 5。
源码如下
// file: src/object.c
/*
* 创建一个redisObject对象
*
* @param type redisObject的类型
* @param *ptr 值的指针
*/
robj *createObject(int type, void *ptr) {
// 为redisObject结构体分配内存空间
robj *o = zmalloc(sizeof(*o));
// 省略部分代码
// 将lru字段设置为当前的 lruclock（分钟分辨率），或者 LFU 计数器。
// 判断内存过期策略
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
// 对应lfu
// LFU_INIT_VAL=5 对应二进制是 0101
// 或运算 高16位是时间，低8位是次数， LFU_INIT_VAL = 5
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
// 对应lru
o->lru = LRU_CLOCK();
}
return o;
} counter会被初始化为LFU_INIT_VAL，默认5。
// file: src/evict.c
/* ----------------------------------------------------------------------------
* LFU (Least Frequently Used) implementation.
*
* 为了实现 LFU（最不常用）驱逐策略，我们在每个对象中总共有 24 位空间，因为我们为此目的重新使用了 LRU 字段。
*
* 我们将 24 位分成两个字段：
*
* 16 bits 8 bits
* +----------------+--------+
* + Last decr time | LOG_C |
* +----------------+--------+
*
* LOG_C 是提供访问频率指示的对数计数器。
* 然而，这个字段也必须递减，否则过去经常访问的键将永远保持这样的排名，而我们希望算法适应访问模式的变化。
*
* 因此，剩余的 16 位用于存储“递减时间”，
* 这是一个精度降低的 Unix 时间(我们将 16 位时间转换为分钟，因为我们不关心回绕)，
* 其中 LOG_C 计数器减半 如果它具有高值，或者如果它具有低值则只是递减。
*
* 新key不会从零开始，以便能够在被淘汰之前收集一些访问，因此它们从 COUNTER_INIT_VAL 开始。
* COUNTER_INIT_VAL = 5
* 因此从5(或具有较小值)开始的键在访问时递增的可能性非常高。
*
* 在递减期间，如果对数计数器的当前值大于5的两倍，则对数计数器的值减半，否则它只减一。
*
* --------------------------------------------------------------------------*/
/*
* 以分钟为单位返回当前时间，只取最低有效16位。
* 返回的时间适合存储为 LFU 实现的 LDT(最后递减时间)。
*/
unsigned long LFUGetTimeInMinutes(void) {
// 65535 = 2^16 - 1 对应二进制是 1111 1111 1111 1111
// (server.unixtime/60) & 1111 1111 1111 1111
return (server.unixtime/60) & 65535;
}(5.2.2) 更新LFU值
当一个键值对被访问时，Redis 会调用 lookupKey 函数进行查找。lookupKey 函数会调用 updateLFU 函数来更新键值对的访问频率。
// file: src/db.c
/*
* 访问对象时更新 LFU。
* 首先，如果达到递减时间，则递减计数器。
* 然后以对数方式递增计数器，并更新访问时间。
*/
void updateLFU(robj *val) {
// 获取计数器
unsigned long counter = LFUDecrAndReturn(val);
// 更新计数器
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}(5.2.2.1) 递减计数器-LFUDecrAndReturn
/*
* 如果达到对象递减时间，则 递减LFU计数器 但 不更新对象的LFU字段，
* 我们在真正访问对象时以显式方式更新访问时间和计数器。
*
* 并且我们将根据 经过的时间/server.lfu_decay_time 将计数器减半。
* 返回对象频率计数器。
* redis.conf配置文件里 lfu-decay-time 默认是 1
* And we will times halve the counter according to the times of
* elapsed time than server.lfu_decay_time.
*
* 此函数用于扫描数据集以获得最佳对象
* 适合：当我们检查候选对象时，如果需要，我们会递减扫描对象的计数器。
*/
unsigned long LFUDecrAndReturn(robj *o) {
// 高16位存的是 上次访问时间(分钟级的) Last decr time
unsigned long ldt = o->lru >> 8;
// 255 对应二进制 1111 1111
// o->lru & 1111 1111 相当于取低8位的值
// 获取计数器
unsigned long counter = o->lru & 255;
// 0 <= LFUTimeElapsed(ldt) < 65535
// 过了的分钟数 / server.lfu_decay_time
// num_periods 是过了 n轮 衰减时间(lfu_decay_time)
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
// 如果经过的轮数不为0 (超过1分钟了)
if (num_periods)
// 如果 n轮衰减 > 访问次数，counter设置为0，相当于重新开始计算
// 否则，n轮衰减 <= 访问次数，counter设置为 counter - num_periods，相当于每过1轮衰减时间(lfu_decay_time)，减1
counter = (num_periods > counter) ? 0 : counter - num_periods;
// 如果没有超过1分钟，num_periods=0，直接返回counter
// 如果超过1分钟，num_periods！=0，至少过了1轮衰减时间(lfu_decay_time)了，更新counter后返回
return counter;
} LFUDecrAndReturn 得到的计数结果
- 如果在当前分钟时间戳内，counter不变
- 如果不在当前分钟时间戳内，每过1轮衰减时间(lfu_decay_time)，counter减1 (代码里是过了num_periods轮，减num_periods)
/*
* 计算过了多少分钟
*
* 给定对象的上次访问时间，计算自上次访问以来经过的最小分钟数。
* 处理溢出(ldt 大于当前 16 位分钟时间)，将时间视为正好回绕一次。
*
* @param ldt 上一次访问的时间(分钟级)
*/
unsigned long LFUTimeElapsed(unsigned long ldt) {
// 获取分钟级时间戳
unsigned long now = LFUGetTimeInMinutes();
// 计算过了多少分钟
if (now >= ldt) return now-ldt;
// 实际上now永远是在ldt(上一次访问时间之后)
// 但是现在 now < ldt，不符合预期
// ldt是 (server.unixtime/60) & 1111 1111 1111 1111 得到的，相当于取余，也就是至少过了1轮了
// 假设 ldt = 65534 now = 1，其实过了2分钟
return 65535-ldt+now;
}(5.2.2.2) 更新LFU计数器-LFULogIncr
/*
* 以对数方式递增计数器。 当前计数器值越大，它真正实现的可能性就越小。 在255时饱和。
*
* Logarithmically increment a counter.
* The greater is the current counter value
* the less likely is that it gets really implemented.
* Saturate it at 255.
*/
uint8_t LFULogIncr(uint8_t counter) {
// 最大255
if (counter == 255) return 255;
// 获取一个随机数
double r = (double)rand()/RAND_MAX;
// 基础值 = counter - 5
double baseval = counter - LFU_INIT_VAL;
// 最小=0
if (baseval < 0) baseval = 0;
// 取对数
double p = 1.0/(baseval*server.lfu_log_factor+1);
// 随机数 < 对数时，计数器+1
if (r < p) counter++;
return counter;
}counter并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。
取一个0-1之间的随机数r与p比较，当r < p时，才增加counterp取决于当前counter值与lfu_log_factor因子，counter值与lfu_log_factor因子越大，p越小，r<p的概率也越小，counter增长的概率也就越小。
增长情况如下
+--------+------------+------------+------------+------------+------------+
| factor | 100 hits | 1000 hits | 100K hits | 1M hits | 10M hits |
+--------+------------+------------+------------+------------+------------+
| 0 | 104 | 255 | 255 | 255 | 255 |
+--------+------------+------------+------------+------------+------------+
| 1 | 18 | 49 | 255 | 255 | 255 |
+--------+------------+------------+------------+------------+------------+
| 10 | 10 | 18 | 142 | 255 | 255 |
+--------+------------+------------+------------+------------+------------+
| 100 | 8 | 11 | 49 | 143 | 255 |
+--------+------------+------------+------------+------------+------------+(5.3) LFU算法淘汰数据
主要有三步
第一步，调用 getMaxmemoryState 函数计算待释放的内存空间；
第二步，调用 evictionPoolPopulate 函数随机采样键值对，并插入到待淘汰集合 EvictionPoolLRU 中；
第三步，遍历待淘汰集合 EvictionPoolLRU，选择实际被淘汰数据，并删除。
(5.3.1) 判断当前内存使用情况-getMaxmemoryState
// file: src/evict.c
/* Get the memory status from the point of view of the maxmemory directive:
* if the memory used is under the maxmemory setting then C_OK is returned.
* Otherwise, if we are over the memory limit, the function returns
* C_ERR.
*
* The function may return additional info via reference, only if the
* pointers to the respective arguments is not NULL. Certain fields are
* populated only when C_ERR is returned:
*
* 'total' total amount of bytes used.
* (Populated both for C_ERR and C_OK)
*
* 'logical' the amount of memory used minus the slaves/AOF buffers.
* (Populated when C_ERR is returned)
*
* 'tofree' the amount of memory that should be released
* in order to return back into the memory limits.
* (Populated when C_ERR is returned)
*
* 'level' this usually ranges from 0 to 1, and reports the amount of
* memory currently used. May be > 1 if we are over the memory
* limit.
* (Populated both for C_ERR and C_OK)
*/
int getMaxmemoryState(size_t *total, size_t *logical, size_t *tofree, float *level) {
size_t mem_reported, mem_used, mem_tofree;
/* Check if we are over the memory usage limit. If we are not, no need
* to subtract the slaves output buffers. We can just return ASAP. */
mem_reported = zmalloc_used_memory();
if (total) *total = mem_reported;
/* We may return ASAP if there is no need to compute the level. */
int return_ok_asap = !server.maxmemory || mem_reported <= server.maxmemory;
if (return_ok_asap && !level) return C_OK;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = mem_reported;
size_t overhead = freeMemoryGetNotCountedMemory();
mem_used = (mem_used > overhead) ? mem_used-overhead : 0;
/* Compute the ratio of memory usage. */
if (level) {
if (!server.maxmemory) {
*level = 0;
} else {
*level = (float)mem_used / (float)server.maxmemory;
}
}
if (return_ok_asap) return C_OK;
/* Check if we are still over the memory limit. */
if (mem_used <= server.maxmemory) return C_OK;
/* Compute how much memory we need to free. */
mem_tofree = mem_used - server.maxmemory;
if (logical) *logical = mem_used;
if (tofree) *tofree = mem_tofree;
return C_ERR;
}(5.3.2) 更新待淘汰的候选键值对集合-evictionPoolPopulate
// file: src/evict.c
/* This is an helper function for freeMemoryIfNeeded(), it is used in order
* to populate the evictionPool with a few entries every time we want to
* expire a key. Keys with idle time smaller than one of the current
* keys are added. Keys are always added if there are free entries.
*
* We insert keys on place in ascending order, so keys with the smaller
* idle time are on the left, and keys with the higher idle time on the
* right. */
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);
for (j = 0; j < count; j++) {
unsigned long long idle;
sds key;
robj *o;
dictEntry *de;
de = samples[j];
key = dictGetKey(de);
/* If the dictionary we are sampling from is not the main
* dictionary (but the expires one) we need to lookup the key
* again in the key dictionary to obtain the value object. */
if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
if (sampledict != keydict) de = dictFind(keydict, key);
o = dictGetVal(de);
}
/* Calculate the idle time according to the policy. This is called
* idle just because the code initially handled LRU, but is in fact
* just a score where an higher score means better candidate. */
if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
idle = estimateObjectIdleTime(o);
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
/* When we use an LRU policy, we sort the keys by idle time
* so that we expire keys starting from greater idle time.
* However when the policy is an LFU one, we have a frequency
* estimation, and we want to evict keys with lower frequency
* first. So inside the pool we put objects using the inverted
* frequency subtracting the actual frequency to the maximum
* frequency of 255. */
idle = 255-LFUDecrAndReturn(o);
} else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
/* In this case the sooner the expire the better. */
idle = ULLONG_MAX - (long)dictGetVal(de);
} else {
serverPanic("Unknown eviction policy in evictionPoolPopulate()");
}
/* Insert the element inside the pool.
* First, find the first empty bucket or the first populated
* bucket that has an idle time smaller than our idle time. */
k = 0;
while (k < EVPOOL_SIZE &&
pool[k].key &&
pool[k].idle < idle) k++;
if (k == 0 && pool[EVPOOL_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 < EVPOOL_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[EVPOOL_SIZE-1].key == NULL) {
/* Free space on the right? Insert at k shifting
* all the elements from k to end to the right. */
/* Save SDS before overwriting. */
sds cached = pool[EVPOOL_SIZE-1].cached;
memmove(pool+k+1,pool+k,
sizeof(pool[0])*(EVPOOL_SIZE-k-1));
pool[k].cached = cached;
} 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. */
sds cached = pool[0].cached; /* Save SDS before overwriting. */
if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);
memmove(pool,pool+1,sizeof(pool[0])*k);
pool[k].cached = cached;
}
}
/* Try to reuse the cached SDS string allocated in the pool entry,
* because allocating and deallocating this object is costly
* (according to the profiler, not my fantasy. Remember:
* premature optimization bla bla bla. */
int klen = sdslen(key);
if (klen > EVPOOL_CACHED_SDS_SIZE) {
pool[k].key = sdsdup(key);
} else {
memcpy(pool[k].cached,key,klen+1);
sdssetlen(pool[k].cached,klen);
pool[k].key = pool[k].cached;
}
pool[k].idle = idle;
pool[k].dbid = dbid;
}
}(5.3.3) 选择被淘汰的键值对并删除-freeMemoryIfNeeded
// file: src/evict.c
/* This function is periodically called to see if there is memory to free
* according to the current "maxmemory" settings. In case we are over the
* memory limit, the function will try to free some memory to return back
* under the limit.
*
* The function returns C_OK if we are under the memory limit or if we
* were over the limit, but the attempt to free memory was successful.
* Otherwise if we are over the memory limit, but not enough memory
* was freed to return back under the limit, the function returns C_ERR. */
int freeMemoryIfNeeded(void) {
int keys_freed = 0;
/* By default replicas should ignore maxmemory
* and just be masters exact copies. */
if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;
size_t mem_reported, mem_tofree, mem_freed;
mstime_t latency, eviction_latency, lazyfree_latency;
long long delta;
int slaves = listLength(server.slaves);
int result = C_ERR;
/* When clients are paused the dataset should be static not just from the
* POV of clients not being able to write, but also from the POV of
* expires and evictions of keys not being performed. */
if (clientsArePaused()) return C_OK;
if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
return C_OK;
mem_freed = 0;
latencyStartMonitor(latency);
if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
goto cant_free; /* We need to free memory, but policy forbids. */
while (mem_freed < mem_tofree) {
int j, k, i;
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;
/* We don't want to make local-db choices when expiring keys,
* so to start populate the eviction pool sampling keys from
* every DB. */
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. */
/* Go backward from best to worst element 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);
}
/* Remove the entry from the pool. */
if (pool[k].key != pool[k].cached)
sdsfree(pool[k].key);
pool[k].key = NULL;
pool[k].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... Iterate again. */
}
}
}
}
/* volatile-random and allkeys-random policy */
else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
{
/* When evicting a random key, we try to evict a key for
* each DB, so we use the static 'next_db' variable to
* incrementally visit all DBs. */
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;
}
}
}
/* Finally remove the selected key. */
if (bestkey) {
db = server.db+bestdbid;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
/* We compute the amount of memory freed by db*Delete() 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.
*
* Same for CSC invalidation messages generated by signalModifiedKey.
*
* 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);
if (server.lazyfree_lazy_eviction)
dbAsyncDelete(db,keyobj);
else
dbSyncDelete(db,keyobj);
latencyEndMonitor(eviction_latency);
latencyAddSampleIfNeeded("eviction-del",eviction_latency);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
signalModifiedKey(NULL,db,keyobj);
notifyKeyspaceEvent(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();
/* Normally our stop condition is the ability to release
* a fixed, pre-computed amount of memory. However when we
* are deleting objects in another thread, it's better to
* check, from time to time, if we already reached our target
* memory, since the "mem_freed" amount is computed only
* across the dbAsyncDelete() call, while the thread can
* release the memory all the time. */
if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
/* Let's satisfy our stop condition. */
mem_freed = mem_tofree;
}
}
} else {
goto cant_free; /* nothing to free... */
}
}
result = C_OK;
cant_free:
/* We are here if we are not able to reclaim memory. There is only one
* last thing we can try: check if the lazyfree thread has jobs in queue
* and wait... */
if (result != C_OK) {
latencyStartMonitor(lazyfree_latency);
while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
result = C_OK;
break;
}
usleep(1000);
}
latencyEndMonitor(lazyfree_latency);
latencyAddSampleIfNeeded("eviction-lazyfree",lazyfree_latency);
}
latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return result;
}参考资料
[1] Redis 核心技术与实战 - 24 | 替换策略：缓存满了怎么办？
[2] Redis 核心技术与实战 - 27 | 缓存被污染了，该怎么办？
[3] Redis 源码剖析与实战 - 15 | 为什么LRU算法原理和代码实现不一样？
[4] Redis 源码剖析与实战 - 16 | LFU算法和其他算法相比有优势吗？
[5] Redis中的LFU算法