Redis作为一个成熟的数据存储中间件，它提供了欠缺的数据管理性能，比方之前咱们提到过的数据过期和明天咱们要讲的数据淘汰(evict)策略。在开始介绍Redis数据淘汰策略前，我先抛出几个问题，帮忙大家更深刻理解Redis的数据淘汰策略。
- 何为数据淘汰，Redis有了数据过期策略为什么还要有数据淘汰策略？
- 淘汰哪些数据，有什么样的数据选取规范？
- Redis的数据淘汰策略是如何实现的？
何为Evict
我先来答复第一个问题，Redis中数据淘汰实际上是指的在内存空间有余时，清理掉某些数据以节俭内存空间。 尽管Redis曾经有了过期的策略，它能够清理掉有效期外的数据。但设想下这个场景，如果过期的数据被清理之后存储空间还是不够怎么办？是不是还能够再删除掉一部分数据？ 在缓存这种场景下 这个问题的答案是能够，因为这个数据即使在Redis中找不到，也能够从被缓存的数据源中找到。所以在某些特定的业务场景下，咱们是能够抛弃掉Redis中局部旧数据来给新数据腾出空间。
如何Evict
第二个问题，既然咱们须要有淘汰的机制，你们在具体执行时要选哪些数据淘汰掉？具体策略有很多种，但思路只有一个，那就是总价值最大化。咱们生在一个不偏心的世界里，同样数据也是，那么多数据里必然不是所有数据的价值都是一样的。所以咱们在淘汰数据时只须要抉择那些低价值的淘汰即可。
所以问题又来了，哪些数据是低价值的？这里不得不提到一个贯通计算机学科的原理局部性原理，这里能够明确通知你，局部性原理在缓存场景有这样两种景象，1. 最新的数据下次被拜访的概率越高。 2. 被拜访次数越多的数据下次被拜访的概率越高。 这里咱们能够简略认为被拜访的概率越高价值越大。基于上述两种景象，咱们能够指定出两种策略 1. 淘汰掉最早未被拜访的数据。2. 淘汰掉访被拜访频次最低的数据，这两种策略别离有个土气的英文名LRU(Least Recently Used)和LFU(Least Frequently Used)。
Redis中的Evict策略
除了LRU和LFU之外，还能够随机淘汰。这就是将数据厚此薄彼，随机选取一部分淘汰。实际上Redis实现了以上3中策略，你应用时能够依据具体的数据配置某个淘汰策略。除了上述三种策略外，Redis还为由过期工夫的数据提供了按TTL淘汰的策略，其实就是淘汰残余TTL中最小的数据。另外须要留神的是Redis的淘汰策略能够配置在全局或者是有过期工夫的数据上，所以Redis共计以下8中配置策略。
| 配置项 | 具体含意 |
|---|---|
| MAXMEMORY_VOLATILE_LRU | 仅在有过期工夫的数据上执行LRU |
| MAXMEMORY_VOLATILE_LFU | 仅在有过期工夫的数据上执行LFU |
| MAXMEMORY_VOLATILE_TTL | 在有过期工夫的数据上按TTL长度淘汰 |
| MAXMEMORY_VOLATILE_RANDOM | 仅在有过期工夫的数据上随机淘汰 |
| MAXMEMORY_ALLKEYS_LRU | 在全局数据上执行LRU |
| MAXMEMORY_ALLKEYS_LFU | 在全局数据上执行LFU |
| MAXMEMORY_ALLKEYS_RANDOM | 在全局数据上随机淘汰 |
| MAXMEMORY_NO_EVICTION | 不淘汰数，当内存空间满时插入数据会报错 |
源码分析
接下来咱们就从源码来看下Redis是如何实现以上几种策略的，MAXMEMORY_VOLATILE_和MAXMEMORY_ALLKEYS_策略实现是一样的，只是作用在不同的dict上而已。另外Random的策略也比较简单，这里就不再详解了，咱们重点看下LRU和LFU。
LRU具体实现
LRU的实质是淘汰最久没被拜访的数据，有种实现形式是用链表的形式实现，如果数据被拜访了就把它移到链表头部，那么链尾肯定是最久未拜访的数据，然而单链表的查问工夫复杂度是O(n)，所以个别会用hash表来放慢查问数据，比方Java中LinkedHashMap就是这么实现的。但Redis并没有采纳这种策略，Redis就是单纯记录了每个Key最近一次的拜访工夫戳，通过工夫戳排序的形式来选找出最早的数据，当然如果把所有的数据都排序一遍，未免也太慢了，所以Redis是每次选一批数据，而后从这批数据执行淘汰策略。这样的益处就是性能高，害处就是不肯定是全局最优，只是达到部分最优。
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr; } robj;LRU信息如何存的？ 在之前介绍redisObject的文章中 咱们已提到过了，在redisObject中有个24位的lru字段，这24位保留了数据拜访的工夫戳(秒)，当然24位无奈保留残缺的unix工夫戳，不到200天就会有一个轮回，当然这曾经足够了。
robj *lookupKey(redisDb *db, robj *key, int flags) { dictEntry *de = dictFind(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){ if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { updateLFU(val); } else { val->lru = LRU_CLOCK(); // 这里更新LRU工夫戳 } } return val; } else { return NULL; }}LFU具体实现
lru这个字段也会被lfu用到，所以你在下面lookupkey中能够看到在应用lfu策略是也会更新lru。Redis中lfu的呈现稍晚一些，是在Redis 4.0才被引入的，所以这里复用了lru字段。 lru的实现思路只有一种，就是记录下key被拜访的次数。但实现lru有个问题须要思考到，尽管LFU是按拜访频次来淘汰数据，但在Redis中随时可能有新数据就来，自身老数据可能有更屡次的拜访，新数据以后被拜访次数少，并不意味着将来被拜访的次数会少，如果不思考到这点，新数据可能一就来就会被淘汰掉，这显然是不合理的。
Redis为了解决上述问题，将24位被分成了两局部，高16位的工夫戳(分钟级)，低8位的计数器。每个新数据计数器初始有肯定值，这样能力保障它能走出新手村，而后计数值会随着时间推移衰减，这样能够保障老的但以后不罕用的数据才有机会被淘汰掉，咱们来看下具体实现代码。
LFU计数器增长
计数器只有8个二进制位，充其量数到255，怎么会够? 当然Redis应用的不是准确计数，而是近似计数。具体实现就是counter概率性增长，counter的值越大增长速度越慢，具体增长逻辑如下：
/* 更新lfu的counter，counter并不是一个精确的数值，而是概率增长，counter的数值越大其增长速度越慢 * 只能反映出某个工夫窗口的热度，无奈反映出具体拜访次数 */uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; double r = (double)rand()/RAND_MAX; double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL为5 if (baseval < 0) baseval = 0; double p = 1.0/(baseval*server.lfu_log_factor+1); // server.lfu_log_factor可配置，默认是10 if (r < p) counter++; return counter;}从代码逻辑中能够看出，counter的值越大，增长速度会越慢，所以lfu_log_factor配置较大的状况下，即使是8位有能够存储很大的访问量。下图是不同lfu_log_factor在不同拜访频次下的增长状况，图片来自Redis4.0之基于LFU的热点key发现机制。
LFU计数器衰减
如果说counter始终增长，即使增长速度很慢也有一天会增长到最大值255，最终导致无奈做数据的筛选，所以要给它加一个衰减策略，思路就是counter随工夫增长衰减，具体代码如下：
/* lfu counter衰减逻辑, lfu_decay_time是指多久counter衰减1，比方lfu_decay_time == 10 * 示意每10分钟counter衰减一，但lfu_decay_time为0时counter不衰减 */unsigned long LFUDecrAndReturn(robj *o) { unsigned long ldt = o->lru >> 8; unsigned long counter = o->lru & 255; unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; if (num_periods) counter = (num_periods > counter) ? 0 : counter - num_periods; return counter;}server.lfu_decay_time也是可配置的，默认是10 标识每10分钟counter值减去1。
evict执行过程
evict何时执行
在Redis每次解决命令的时候，都会查看内存空间，并尝试去执行evict，因为有些状况下不须要执行evict，这个能够从isSafeToPerformEvictions中能够看出端倪。
static int isSafeToPerformEvictions(void) { /* 没有lua脚本执行超时，也没有在做数据超时 */ if (server.lua_timedout || server.loading) return 0; /* 只有master才须要做evict */ if (server.masterhost && server.repl_slave_ignore_maxmemory) return 0; /* 当客户端暂停时，不须要evict，因为数据是不会变动的 */ if (checkClientPauseTimeoutAndReturnIfPaused()) return 0; return 1;}evict.c
evict代码都在evict.c中。外面蕴含了每次evict的执行过程。
int performEvictions(void) { if (!isSafeToPerformEvictions()) return EVICT_OK; int keys_freed = 0; size_t mem_reported, mem_tofree; long long mem_freed; /* May be negative */ mstime_t latency, eviction_latency; long long delta; int slaves = listLength(server.slaves); int result = EVICT_FAIL; if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK) return EVICT_OK; if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION) return EVICT_FAIL; /* We need to free memory, but policy forbids. */ unsigned long eviction_time_limit_us = evictionTimeLimitUs(); mem_freed = 0; latencyStartMonitor(latency); monotime evictionTimer; elapsedStart(&evictionTimer); while (mem_freed < (long long)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. * 先从dict中采样key并放到pool中 */ 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. */ /* 从pool中抉择最适宜淘汰的key. */ 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 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 策略 */ else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM) { /* 当随机淘汰时，咱们用动态变量next_db来存储以后执行到哪个db了*/ 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; } } } /* 从dict中移除被选中的key. */ if (bestkey) { db = server.db+bestdbid; robj *keyobj = createStringObject(bestkey,sdslen(bestkey)); propagateExpire(db,keyobj,server.lazyfree_lazy_eviction); /*咱们独自计算db*Delete()开释的内存量。实际上，在AOF和正本流传所需的内存可能大于咱们正在开释的内存（删除key） ，如果咱们思考这点的话会很绕。由signalModifiedKey生成的CSC生效音讯也是这样。 因为AOF和输入缓冲区内存最终会被开释，所以咱们只须要关怀key空间应用的内存即可。*/ 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++; if (keys_freed % 16 == 0) { /*当要开释的内存开始足够大时，咱们可能会在这里破费太多工夫，不可能足够快地将数据传送到正本，因而咱们会在循环中强制传输。*/ if (slaves) flushSlavesOutputBuffers(); /*通常咱们的进行条件是开释一个固定的，事后计算的内存量。然而，当咱们*在另一个线程中删除对象时， 最好不断*查看是否曾经达到目标*内存，因为“mem\u freed”量只在dbAsyncDelete（）调用中*计算， 而线程能够*始终开释内存。*/ if (server.lazyfree_lazy_eviction) { if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) { break; } } /*一段时间后，尽早退出循环-即便尚未达到内存限度*。如果咱们忽然须要开释大量的内存，不要在这里花太多工夫。*/ if (elapsedUs(evictionTimer) > eviction_time_limit_us) { // We still need to free memory - start eviction timer proc if (!isEvictionProcRunning) { isEvictionProcRunning = 1; aeCreateTimeEvent(server.el, 0, evictionTimeProc, NULL, NULL); } break; } } } else { goto cant_free; /* nothing to free... */ } } /* at this point, the memory is OK, or we have reached the time limit */ result = (isEvictionProcRunning) ? EVICT_RUNNING : EVICT_OK;cant_free: if (result == EVICT_FAIL) { /* At this point, we have run out of evictable items. It's possible * that some items are being freed in the lazyfree thread. Perform a * short wait here if such jobs exist, but don't wait long. */ if (bioPendingJobsOfType(BIO_LAZY_FREE)) { usleep(eviction_time_limit_us); if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) { result = EVICT_OK; } } } latencyEndMonitor(latency); latencyAddSampleIfNeeded("eviction-cycle",latency); return result;}执行的过程能够简略分为三步，首先按不同的配置策略填充evictionPoolEntry，pool大小默认是16，而后从这16个key中依据具体策略选出最适宜被删掉的key(bestkey)，而后执行bestkey的删除和一些后续逻辑。
总结
能够看出，Redis为了性能，就义了LRU和LFU的准确性，只能说是近似LRU和LFU，但在理论应用过程中也齐全足够了，毕竟Redis这么多年也是经验了有数我的项目的考验仍旧耸立不倒。Redis的这种设计方案也给咱们软件设计时提供了一条新的思路，就义精确度来换取性能。
本文是Redis源码分析系列博文，同时也有与之对应的Redis中文正文版，有想深刻学习Redis的同学，欢送star和关注。
Redis中文注解版仓库：https://github.com/xindoo/Redis
Redis源码分析专栏：https://zxs.io/s/1h
如果感觉本文对你有用，欢送一键三连。