Redis 过期删除策略和淘汰策略

当对 key 设置了过期时间， redis 会把该 key 带上过期时间存储到一个过期字典中，过期字典中保存了数据库中所有 key 的过期时间

当我们查询一个 key 时，Redis 首先检查该 key 是否存在于过期字典中：如果不在，则正常读取键值；如果存在，则会获取该 key 的过期时间，然后与当前系统时间进行比对，如果比系统时间大，那就没有过期，否则判定该 key 已过期。

如何判定 key 已过期

在设置 key 的过期时间时，同时创建一个定时事件，当时间到达时，由时间处理器自动执行 key 的删除操作

优点：可以保证过期的 key 会被尽快删除，内存可以被尽快的释放，因为，定时删除对内存是最友好的

缺点：在过期 key 比较多的情况下，删除过期 key 可能会占用相当一部分 CPU 时间，所以，定时删除策略对 CPU 不友好 

优缺点

定时删除

不主动删除过期键，每次从数据库访问 key 时，都检测 key 是否过期，如果过期则删除该 key

优点：每次访问时，才会检查 key 是否过期，只会使用很少的系统资源，对 CPU 最友好

缺点：如果一个 key 已经过期，只要这个 key 一直没有被访问，所占用的内存就不会被释放，造成了内存空间浪费，对内存不友好

惰性删除

每隔一段时间随机从数据库中取出一定数量的 key 进行检查，并删除其中的过期 key

优点：通过限制删除操作执行的时长和频率，来减少删除操作对 CPU 的影响，同时也能删除一部分过期的数据减少了过期键对空间的无效占用

内存清理方面没有定时删除效果好，同时也没有惰性删除使用的系统资源少

难以确定删除操作执行的时长和频率。

缺点

定期删除

常见的三种过期删除策略

惰性删除+定期删除，以求在合理使用 CPU 时间和避免内存浪费之间取得平衡

惰性删除实现

每隔一段时间「随机」从数据库中取出一定数量的 key 进行检查，并删除其中的过期key。

Redis 的定期删除的流程：1、从过期字典中随机抽取 20 个 key；2、检查这 20 个 key 是否过期，并删除已过期的 key；3、如果本轮检查的已过期 key 的数量，超过 5 个（20/4），也就是「已过期 key 的数量」占比「随机抽取 key 的数量」大于 25%，则继续重复步骤 1；如果已过期的 key 比例小于 25%，则停止继续删除过期 key，然后等待下一轮再检查。

定期删除是一个循环的流程，为了保证定期删除不会出现循环过度，导致卡死，为此增加了定期删除循环流程的时间上限，默认不会超过 25 ms

定期删除实现

Redis 的过期删除策略 

过期删除策略

redis.conf 中参数 maxmemory 参数

设置最大运行内存

默认： 运行内存超过最大设置内存是，不淘汰任何数据，如果有新的数据写入，会报错通知禁止写入

noeviction

不进行数据淘汰的策略

随机淘汰设置了过期时间的任意键值

volatile-random

优先淘汰更早过期的键值

volatile-ttl

淘汰所有设置里过期时间的键值中，最久未使用的键值

volatile-lru

淘汰所有设置了过期时间的键值中，最少使用的键值

volatile-lfu

在设置了过期时间的数据中进行淘汰

随机淘汰任意键值

allkeys-random

淘汰整个键值中最久未使用的键值

allkeys-lru

淘汰整个键值中最少使用的键值

allkeys-lfu

在所有数据范围内进行淘汰

进行数据淘汰的策略

内存淘汰策略

config get maxmemory-policy

查看 Redis 的内存淘汰策略

最近最少使用

基于链表结构，按照操作顺序从前往后排列，最新操作的键会被移动到表头，淘汰时淘汰链表尾部的元素

用链表来管理所有的缓存数据，会带来额外的空间开销

如果有大量数据被访问，就会带来很多的链表移动操作，会很耗时，进而降低 Redis 缓存性能

存在的问题

传统实现

近似 LRU 算法，目的是为了更好的节约内存

实现方式：在 Redis 的对象结构体中添加了一个额外的字段，用于记录此数据最后一次访问时间

当 Redis 进行内存淘汰时，会使用随机采样的方式来淘汰数据，随机取 5 个值（此值可配置），然后淘汰最久没有使用的那个

不用为所有的链表维护一个大链表，节省空间

不用再每次数据访问时都移动链表项，提升了缓存的性能

优点

无法解决缓存污染问题，比如一些数据只会被访问一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染，为了解决这个问题，后面引入了 LFU 算法来解决。

Redis 中实现

LRU算法

最近最不常用，根据数据访问次数来淘汰数据，核心思想就是“如果数据过去被访问多次，那么将来被访问的频率也更高”

记录数据访问频次信息

频次不是访问次数，频次会根据两次访问的时间差距，对访问频次做衰减计算

Redis 实现

LFU算法 

LRU 算法与 LFU 算法

过期删除策略和淘汰策略