Redis的内存淘汰算法

博客主页：🏆看看是李XX还是李歘歘 🏆

🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点，以及职场小菜鸡的生活。🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

⛽️今天的内容是 Redis的内存淘汰算法 ⛽️💻💻💻

首先来讨论一下Redis的过期键的删除策略有哪些？

定时过期：每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。

惰性过期：只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。

定期删除：每隔一定的时间，会扫描redis数据库的expires(过期)字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。

Redis的内存满了怎么办？

实际上Redis定义了「8种内存淘汰策略」用来处理redis内存满的情况：

在Redis中是可以设置内存最大限制的，因此我们不用担心Redis占满机器的内存影响其他服务，这个参数maxmemory是可以配置的，maxmemory参数默认值为0。因32位系统支持的最大内存为4GB，所以在32位系统上Redis的默认最大内存限制为3GB；在64位系统上默认Redis最大内存即为物理机的可用内存；

Redis的maxmemory支持的内存淘汰机制使得其成为一种有效的缓存方案，成为memcached（一套分布式的高速缓存系统）的有效替代方案。

当内存达到maxmemory后，Redis会按照maxmemory-policy启动淘汰策略。

Redis 3.0中已有淘汰机制：

maxmemory-policy	含义	特性
noeviction	不淘汰	内存超限后写命令会返回错误(如OOM, del命令除外)
allkeys-lru	所有key的LRU机制	在所有key中按照最近最少使用LRU原则剔除key，释放空间
volatile-lru	易失key的LRU	仅以设置过期时间key范围内的LRU(如均未设置过期时间，则不会淘汰)
allkeys-random	所有key随机淘汰	一视同仁，随机
volatile-random	易失Key的随机	仅设置过期时间key范围内的随机
volatile-ttl	易失key的TTL淘汰	优先删除剩余时间(time to live,TTL)短的key

其中LRU(less recently used)经典淘汰算法在Redis实现中有一定优化设计，来保证内存占用与实际效果的平衡，这也体现了工程应用是空间与时间的平衡性。

PS：值得注意的，在主从复制模式Replication下，从节点达到maxmemory时不会有任何异常日志信息，但现象为增量数据无法同步至从节点。

Redis 3.0中近似LRU算法

Redis中LRU是近似LRU实现，并不能取出理想LRU理论中最佳淘汰Key，而是通过从小部分采样后的样本中淘汰局部LRU键。

Redis 3.0中近似LRU算法通过增加待淘汰元素池的方式进一步优化，最终实现与精确LRU非常接近的表现。

精确LRU会占用较大内存记录历史状态，而近似LRU则用较小内存实现近似效果。

以下是理论LRU和近似LRU的效果对比：

总结图中展示规律，

结论：

数据访问模式非常接近幂次分布时，也就是大部分的访问集中于部分键时，LRU近似算法会处理得很好。

在模拟实验的过程中，我们发现如果使用幂次分布的访问模式，真实LRU算法和近似LRU算法几乎没有差别。

采样值设置通过maxmemory-samples指定，可通过CONFIG SET maxmemory-samples <count>动态设置，也可启动配置中指定maxmemory-samples <count>

源码解析

int freeMemoryIfNeeded(void){while (mem_freed < mem_tofree) {if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)return REDIS_ERR; /* We need to free memory, but policy forbids. */if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM){......}/* volatile-random and allkeys-random policy */if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM){......}/* volatile-lru and allkeys-lru policy */else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU){// 淘汰池函数evictionPoolPopulate(dict, db->dict, db->eviction_pool);while(bestkey == NULL) {evictionPoolPopulate(dict, db->dict, db->eviction_pool);// 从后向前逐一淘汰for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {if (pool[k].key == NULL) continue;de = dictFind(dict,pool[k].key); // 定位目标/* Remove the entry from the pool. */sdsfree(pool[k].key);/* Shift all elements on its right to left. */memmove(pool+k,pool+k+1,sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));/* Clear the element on the right which is empty* since we shifted one position to the left.  */pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;pool[REDIS_EVICTION_POOL_SIZE-1].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... */continue;}}}}/* volatile-ttl */else if (server.maxmemory_policy == EDIS_MAXMEMORY_VOLATILE_TTL) {......}// 最终选定待删除键bestkeyif (bestkey) {long long delta;robj *keyobj = createStringObject(bestkey,sdslenbestkey)); // 目标对象propagateExpire(db,keyobj);latencyStartMonitor(eviction_latency); // 延迟监控开始dbDelete(db,keyobj); // 从db删除对象latencyEndMonitor(eviction_latency);// 延迟监控结束latencyAddSampleIfNeeded("eviction-del",iction_latency); // 延迟采样latencyRemoveNestedEvent(latency,eviction_latency);delta -= (long long) zmalloc_used_memory();mem_freed += delta; // 释放内存计数server.stat_evictedkeys++; // 淘汰key计数，info中可见notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted", keyobj, db->id); // 事件通知decrRefCount(keyobj); // 引用计数更新keys_freed++;// 避免删除较多键导致的主从延迟，在循环内同步if (slaves) flushSlavesOutputBuffers();}}
}