参考资料：

《Redis的LRU缓存淘汰算法实现》

《一文读懂Redis内存淘汰策略》

《Redis 的过期策略和内存淘汰机制有什么区别》

《Redis内存淘汰策略》

写在开头：本文为学习后的总结，可能有不到位的地方，错误的地方，欢迎各位指正。

目录

一、内存管理

二、过期策略

        1、定期删除

        2、惰性删除

三、内存淘汰

        1、LRU

        2、LFU

四、近似LRU

---

一、内存管理

        Redis通过将热点数据存储到内存中实现了高效的数据读取，但是内存如果使用不当也是会造成一些问题的。

• Redis中有很多无效的缓存，这些缓存数据会降低数据IO的性能，因为不同的数据类型时间复杂度算法不同，数据越多可能会造成性能下降
• 随着系统的运行，redis的数据越来越多，会导致物理内存不足。通过使用虚拟内存（VM），将很少访问的数据交换到磁盘上，腾出内存空间的方法来解决物理内存不足的情况。虽然能够解决物理内存不足导致的问题，但是由于这部分数据是存储在磁盘上，如果在高并发场景中，频繁访问虚拟内存空间会严重降低系统性能。

        因此，Redis为了更好的管理内存，提供了一些管理方案，包括过期策略与内存淘汰。

二、过期策略

        过期策略是指对每个存储到redis中的key设置过期时间。Redis提供了 EXPIRE 与 EXPIREAT 来为 key 设置过期时间。

redis> SET mykey "Hello"
"OK"
redis> EXPIRE mykey 10
(integer) 1
redis> TTL mykey
(integer) 10
redis> SET mykey "Hello World"
"OK"
redis> TTL mykey
(integer) -1
redis>

        当到达过期时间后，就需要将这个key删除掉（准确来说，是该key会变为不可使用，而后再利用专门的过期策略对其进行删除）。Redis中提供了两种过期删除策略：惰性删除和定期删除。

        1、定期删除

        定期删除类似一个守护线程，每间隔一段时间就执行一次（默认100ms一次，可以通过修改配置文件redis.conf 的 hz 选项来调整这个次数），将过期的Key进行删除，具体过程如下：

• 从过期字典中随机选出20个key；
• 删除这20个key中已经过期的key；
• 如果过期的key的比例超过了1/4，那就重复从步骤1开始执行；

        之所以不一次性将所有过期的key都删除，是从性能角度做出的考量，当过期key特别多时，每次扫描全部的过期key，都会给CPU带来较大负担。既然无法一下子全部删除，那么我就进行多次（指每100ms执行一次，提高删除的频次）、部分的删除（只每次只抽取部分进行删除），以此来达到效果。

        当然，这样随机的抽取过期key进行删除明显会遗漏很多过期key，这就要用到惰性删除。

        2、惰性删除

        惰性删除即当查询某个Key时，判断该key是否已过期，如果已过期则从缓存中删除，同时返回空。

        这一块的思路其实挺类似mysql的内存数据写回策略Merge buffer，只不过一个是写回磁盘一个是从内存删除。有兴趣的朋友可以看看我之前的文章《mysql中的Innodb_buffer_pool》

        再回头看看过期策略，无论是定期删除还是惰性删除，都是一种不完全精确的删除策略，始终还是会存在已经过期的key无法被删除的场景。而且这两种过期策略都是只针对设置了过期时间的key，不适用于没有设置过期时间的key的淘汰，所以，Redis还提供了内存淘汰策略，用来筛选淘汰指定的key。

三、内存淘汰

        在配置文件redis.conf 中，可以通过参数 maxmemory <bytes> 来设定最大内存，当数据内存达到 maxmemory 时，便会触发redis的内存淘汰策略（我们一般会将该参数设置为物理内存的四分之三）。

        当 Redis 的内存超过最大允许的内存之后，Redis 会触发内存淘汰策略。（过期策略是指正常情况下清除过期键，内存淘汰是指内存超过最大值时的保护策略）。内存淘汰策略可以通过maxmemory-policy进行配置，目前Redis提供了以下几种（2个LFU的策略是4.0后出现的）：

• volatile-lru，针对设置了过期时间的key，使用lru算法进行淘汰。
• allkeys-lru，针对所有key使用lru算法进行淘汰。
• volatile-lfu，针对设置了过期时间的key，使用lfu算法进行淘汰。
• allkeys-lfu，针对所有key使用lfu算法进行淘汰。
• volatile-random，从所有设置了过期时间的key中使用随机淘汰的方式进行淘汰。
• allkeys-random，针对所有的key使用随机淘汰机制进行淘汰。
• volatile-ttl，针对设置了过期时间的key，越早过期的越先被淘汰。
• noeviction，不会淘汰任何数据，当使用的内存空间超过 maxmemory 值时，再有写请求来时返回错误。

        除了比较特殊的noeviction与volatile-ttl，其余6种策略都有一定的关联性。我们可以通过前缀将它们分为2类，volatile-与allkeys-，这两类策略的区别在于二者选择要清除的键时的字典不同，volatile-前缀的策略代表从设置了过期时间的key中选择键进行清除；allkeys-开头的策略代表从所有key中选择键进行清除。这里面值得介绍的就是lru与lfu了，下面会对这两种方式进行介绍。

        1、LRU

        LRU是Least Recently Used的缩写，也就是表示最近很少使用，也可以理解成最久没有使用。也就是说当内存不够的时候，每次添加一条数据，都需要抛弃一条最久时间没有使用的旧数据。（一个key上一次的访问时间存储redisObject中的lru字段中，该点前文中有介绍《Redis：数据对象与底层实现》）

        LRU 是基于链表结构实现的，链表中的元素按照操作顺序从前往后排列，最新操作的键会被移动到表头，当需要进行内存淘汰时，只需要删除链表尾部的元素即可。LRU的具体实现可以看看LeetCode上的经典题目146. LRU 缓存

        需要注意的是Redis并没有使用标准的LRU实现方法作为LRU淘汰策略的实现方式，这是因为：    

• 为了实现LRU，需要将所有数据维护一个链表，这就需额外内存空间来保存链表
• 每当有新数据插入或现有数据被再次访问，都要调整链表中节点的位置，尤其是频繁的操作将会造成巨大的开销（不要忘了Redis就是为了存储热点数据而出现的）

        为了解决这一问题，Redis使用了近似的LRU策略进行了优化，平衡了时间与空间的效率。具体的实现细节我们会在下文中介绍，有兴趣的朋友可以看看官网的介绍《Key eviction》

        LRU虽然看起来实现了按照数据的热度对内存中的key进行管理，但是在某些情况下却仍然存在一些问题，假设有一个数据很久没有被访问了，偶然间被访问了一次，那么在lru的策略下，他又会被认为是热点数据而保留，这样显然是不合适的，于是就有了LFU。

        2、LFU

        LFU（Least Frequently Used），表示最近最少使用，它和key的使用次数有关，其思想是：根据key最近被访问的频率进行淘汰，比较少访问的key优先淘汰，反之则保留。

        相比LRU算法,LFU算法去增加了访问频率的这样一个维度来统计数据的热点情况，LFU主要使用了两个双向链表去形成一个二维的双向链表，一个用来保存访问频率，另一个用来访问频率相同的所有元素。

•  当添加元素的时候访问频次默认为1，于是找到相同频次的节点，然后添加到相同频率节点对应的双向链表的头部，
• 当元素被访问的时候就会增加对应key的访问频率，并且把访问的节点移动到下一个频次的节点。

        LFU算法通过使用频率和上次访问时间来标记数据的这样一个热度，如果某个数据有读和写那么就增加访问的频率，如果一段时间内这个数据没有读写,那么就减少访问频率。所以通过LFU算法改进之后，就可以真正达到非热点数据的淘汰，当然LFU也有缺点，相比LRU算法，LFU增加了访问频次的一个维护，以及实现的复杂度比LRU更高。

       

四、近似LRU

        整个近似LRU的流程如下（图片来源《Redis的LRU缓存淘汰算法实现》）：

        为淘汰数据，Redis定义数组EvictionPoolLRU（默认大小为16），保存待淘汰的候选KV对，元素类型是evictionPoolEntry结构体，保存了待淘汰KV对的空闲时间idle、对应K等信息

 

        在淘汰数据的循环流程中，就会更新这个待淘汰的候选KV对集合，即EvictionPoolLRU数组。

        通过dictGetSomeKeys方法对目标集合进行抽取，抽取的数量由配置项maxmemory-samples决定，默认5：

         evictionPoolPopulate根据实际采样到的KV对数量count，执行循环：调用estimateObjectIdleTime计算在采样集合中的每一个KV对的空闲时间（redisObject中的lru存储的是上一次的访问时间，这里需要转换为空闲时间）。

        evictionPoolPopulate遍历待淘汰的候选KV对集合，即EvictionPoolLRU数组，尝试把采样的每个KV对插入EvictionPoolLRU数组，取决于如下条件之一：

• 能在数组中找到一个尚未插入KV对的空位
• 能在数组中找到一个KV对的空闲时间＜采样KV对的空闲时间

        满足其中之一，evictionPoolPopulate就能把采样KV对插入EvictionPoolLRU数组。等所有采样键值对都处理完后，evictionPoolPopulate函数就完成对待淘汰候选键值对集合的更新了。

        EvictionPoolLRU数组，且该数组里的K，是按空闲时间从小到大排好序了。所以，performEvictions遍历一次EvictionPoolLRU数组，从数组的最后一个K开始选择，若选到的K非空，就把它作为最终淘汰的K。

         一旦选到被淘汰的K，performEvictions就会根据Redis server的惰性删除配置，进行删除。

        至此，performEvictions就淘汰了一个K。若此时释放的内存空间还不够，即没有达到待释放空间，则performEvictions还会重复执行前面所说的更新待淘汰候选KV对集合、选择最终淘汰K的过程，直到满足待释放空间的大小要求。