Redis 服务等过期策略和内存淘汰策略解析

redis服务是基于内存运行的，所以很多数据都存放在内存中，但是内存又不是无限的，所以redis就引出了key的过期和淘汰策略。

一、Redis的过期策略：

我们在set key的时候，可以给它设置一个过期时间，比如expire key 60。指定这key在60s后过期，60s后那redis是如何处理的嘛？

我们先来介绍几种过期策略：

1、定时过期:

每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即对key进行清除。

优点：该策略可以立即清除过期的数据，对内存很友好；

缺点：但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。

2、惰性过期:

只有当访问一个key时，才会判断该key是否已过期，过期则清除。

优点：该策略可以最大化地节省CPU资源；

缺点：却对内存非常不友好。

注：极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。

3、定期过期:

每隔一定的时间，会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。

该策略是前两者的一个折中方案。

通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。
expires字典会保存所有设置了过期时间的key的过期时间数据，其中，key是指向键空间中的某个键的指针，value是该键的毫秒精度的UNIX时间戳表示的过期时间。

键空间是指该Redis集群中保存的所有键。

4、惰性过期和定期过期结合使用：

假设Redis当前存放30万个key，并且都设置了过期时间，如果你每隔100ms就去检查这全部的key，CPU负载会特别高，最后可能会挂掉。
因此，redis采取的是定期过期，每隔100ms就随机抽取一定数量的key来检查和删除的。
但是呢，最后可能会有很多已经过期的key没被删除。这时候，redis采用惰性删除。在你获取某个key的时候，redis会检查一下，这个key如果设置了过期时间并且已经过期了，此时就会删除。
但是呀，如果定期删除漏掉了很多过期的key，然后也没走惰性删除。就会有很多过期key积在内存内存，直接会导致内存爆的。或者有些时候，业务量大起来了，redis的key被大量使用，内存直接不够了，Redis用8（2^3）种内存淘汰策略保护自己~

二、Redis 内存淘汰策略：

1、volatile-lru：

当内存不足以容纳新写入数据时，从设置了过期时间的key中使用LRU（最近最少使用）算法进行淘汰；

2、allkeys-lru：

当内存不足以容纳新写入数据时，从所有key中使用LRU（最近最少使用）算法进行淘汰。

3、volatile-lfu：

4.0版本新增的策略，当内存不足以容纳新写入数据时，在过期的key中，使用LFU（最不经常使用）算法进行删除key。

4、allkeys-lfu：

4.0版本新增，当内存不足以容纳新写入数据时，从所有key中使用LFU（最不经常使用）算法进行淘汰；

5、volatile-random：

当内存不足以容纳新写入数据时，从设置了过期时间的key中，随机淘汰数据；

6、allkeys-random：

当内存不足以容纳新写入数据时，从所有key中随机淘汰数据。

7、volatile-ttl：

当内存不足以容纳新写入数据时，在设置了过期时间的key中，根据过期时间进行淘汰，越早过期的优先被淘汰；

8、noeviction：

默认策略，当内存不足以容纳新写入数据时，新写入操作会报错。

三、 LRU算法与LFU算法：

Redis 在 4.0 版本之前的缓存淘汰算法，只支持 random 和 LRU。random 太简单粗暴了，可能把热点数据给淘汰掉，一般不会使用。

LRU比 random 好一点，会优先淘汰最久没被访问的数据，但是它也有一个缺点，就是无法真正表示数据的冷热程度。

1、什么是LRU算法：

LRU是一种基于时间的内存淘汰策略(最近最少使用，会淘汰掉长时间不使用的数据)。它假设最近被访问的数据在未来也更有可能被访问，而较长时间未被访问的数据更可能不再被使用。根据这个策略，LRU算法会淘汰最久未被访问的数据，以腾出内存空间。

LRU算法示意图：

流程解析：

向一个缓存空间依次插入三个数据A/B/C，填满了缓存空间；
读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
插入数据D的时候，由于缓存空间已满，触发了LRU的淘汰策略，数据B被移出，缓存空间只保留了D/A/C。

2、如何实现LRU算法：

LRU算法比较核心的思想是要记录最近被访问的、最早被访问的数据，在访问数据和修改数据(编辑、新增、删除)数据时，该部分数据就会变成最新的数据，内存不够时会把最早被访问的数据删除掉。

很快我们锁定了List，最近被访问的数据(最新的数据) 可以存在在List的第一个位置，最早被访问的(最老的数据)可以存放在List的最后一个位置。

但是由于数据的访问、数据的修改都会导致数据位置的变动，所以使用List会存在一定的性能问题，因此我们可以采用一个双向链表来暂时解决该问题，可以采用一个双向链表维护缓存的上一次使用时间，并且可以使数据插入/删除等操作的时间复杂度是O(1)。

此外当链表（linkedlist）越来越长时，我们访问某个元素时需要遍历访问，性能较差，因此新增一个哈希表（hashtable），记录链表节点的映射关系，解决如果只使用双向链表每次判断key是否存在时都需要遍历整个链表的问题。

3、什么是LFU算法：

LFU是一种基于访问频率的内存淘汰策略（最不经常使用，会淘汰掉使用次数最少的数据）。它假设经常被访问的数据在未来仍然频繁被访问，而较少被访问的数据更可能不再被使用。根据这个策略，LFU算法会淘汰访问频率最低的数据，以释放内存空间。

4、如何实现LFU算法：

实现LFU算法的一种常见方法是使用三个数据结构：

哈希表（keyToValue）：用于存储键值对，提供快速的键值查找功能。
哈希表（keyToFreq）：用于存储键的访问频率，记录每个键被访问的次数。
哈希表（freqToKeys）：用于存储相同访问频率的键的集合，以便快速获取具有相同访问频率的键。

LFU算法的实现步骤如下：

（1）、初始化缓存容量、最小访问频率为0以及上述三个哈希表。

（2）、当需要获取缓存中的数据项时，首先检查键是否存在于keyToValue哈希表中。如果不存在，则返回-1表示未找到；如果存在，则获取对应的值，并更新该键的访问频率。

（3）、当需要插入新的数据项时，首先检查缓存是否已满。如果已满，则根据LFU原则淘汰一个访问频率最低的数据项。然后将新的键值对添加到keyToValue哈希表中，并将访问频率设置为1，并将键添加到对应访问频率的键集合中。如果缓存未满，则直接将新的键值对添加到keyToValue哈希表中，并将访问频率设置为1，并将键添加到对应访问频率的键集合中。