Redis过期删除与内存淘汰

过期删除策略

Redis会根据过期键值对删除策略将已过期的键值对删除。每当一个key被设置了过期时间后，Redis会将这个key与其过期时间存储到一个「过期字典」中。

当查询一个key时，首先检查key是否在过期字典中：

  • 若不在，则正常读取
  • 若在，则获取过期时间，并与当前系统时间对比，判断其是否过期

Redis的过期删除策略是惰性删除+定期删除这两种策略配合使用。

惰性删除策略是什么？

惰性删除策略：不主动删除过期的key，每次从数据库访问key时，检测key是否过期，若过期则删除该key，返回null给客户端。

优点：只有访问key时才检查过期与否，因此这个策略占用系统资源较少，对CPU时间最友好

缺点：若一个key已过期，那么只要这个key一直不被访问，它就会一直保留在数据库中，造成了内存空间浪费

定期删除策略是什么？

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

具体的流程为：

  • 从过期字典中随机抽20个key
  • 检查这些key并删除其中过期的key
  • 若本轮的过期key数量，超过了抽检总数的25%（即5个），则继续重复步骤1；否则，停止继续删除过期key，等待下一轮再检查

同时，为了防止删除进入过度循环阻塞线程，Redis为该循环设置了时间上限，默认为25毫秒。

优点：删除一部分过期的key，减少了无效的内存占用

缺点：定期删除的频率难以把控

综上，Redis选择了两者配合使用的删除策略，以在减少CPU时耗和避免内存浪费之间取得较好的平衡。

Redis持久化时，对于过期key如何处理？

Redis持久化文件有两种格式：RDB和AOF。下面是过期键分别在这两种格式中的呈现状态：

  • RDB文件分为两个阶段：RDB文件生成阶段和加载阶段
    • 生成阶段：从内存状态持久化成RDB文件的时候，会对key做过期检查，过期key不会被保存到新的RDB文件中
    • 加载阶段：RDB文件加载阶段时，处理方式要看服务器是主还是从，分别有以下两种情况：
      • 主服务器，在载入RDB时，程序会对文件中保存的key检查，过期key不会被载入到数据库中
      • 从服务器，在载入RDB时，无论key是否过期均会载入到数据库中；但主从同步时，从服务器的数据会被清空，因此也不会造成影响
  • AOF文件分为两个阶段：AOF文件写入阶段和重写阶段
    • 写入阶段：若数据库中某过期key尚未被删除，AOF文件会保留此过期key，当该key被删除后，Redis会向AOF文件追加一条DEL命令来显式删除该key
    • 重写阶段：AOF重写时，会检查key，过期key不会被保存到重写后的AOF文件

Redis主从模式中，对于过期key如何处理？

从库不会进行过期扫描，即使从库中的某个key过期了，客户端访问从库时，依旧可以得到该key；主服务器会控制从库的过期处理，当某个key过期后，主库会在AOF文件中追加一条DEL命令，同步到所有从库，从库执行该命令删除过期的key

内存淘汰策略

当Redis的运行内存达到了阈值，就会触发内存淘汰机制，该阈值为Redis配置文件中的maxmemory。

Redis的内存淘汰策略共有八种，根据「进行数据淘汰」与否可分为两大类。

不进行数据淘汰的策略

noeviction：Redis 3.0后默认的内存淘汰策略，当运行内存超过最大设置内存时，不淘汰任何数据，而是不再提供服务，直接返回错误

进行数据淘汰的策略

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

    • volatile-random：随机淘汰设置了过期时间的任意键值
    • volatile-ttl：优先淘汰更早过期的键值
    • volatile-lru：Redis 3.0前默认的内存淘汰策略，淘汰所有设置了过期时间的键值中最久未使用的键值
    • volatile-lfu：Redis 4.0后新增，淘汰所有设置了过期时间的键值中最少使用的键值

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

    • allkeys-random：随机淘汰任意键值
    • allkeys-lru：淘汰所有键值中最久未使用的键值
    • allkeys-lfu：Redis 4.0后新增，淘汰所有键值中最少使用的键值

LRU算法和LFU算法

LRU是最近最少使用的意思，传统的LRU算法依靠链表来进行实现，链表中的元素按照操作顺序从前往后排列，最新操作的键会移动到链表头，当需要内存淘汰时，只需要删除链表尾的键即可。

Redis并未采用这样的方式来实现LRU，因为：

  • 需要开辟链表来管理数据，带来额外的空间开销
  • 若大量数据被访问，则链表移动操作会很多，影响性能

Redis如何实现LRU算法？

为了节约内存，Redis使用的是一种近似LRU算法，其实现方式是在Redis的对象结构体中添加一个额外的字段，用来记录此数据的最后一次访问时间。

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

优缺点如下：

  • 优点：不用维护大链表，节省了内存；数据访问不需要移动链表项，提升性能
  • 缺点：无法解决缓存污染问题，例如应用一次读取了大量数据，而这些数据只会被读取这一次，那么就会留存在缓存中很长时间

因此，Redis 4.0之后引入了LFU算法来解决这个问题。

LFU是最近最不常用的意思，将数据的访问次数作为参考依据，如果数据过去被访问多次，那么将来被访问的频率也会很高。

Redis如何实现LFU算法？

Redis对象的结构体如下：

1
2
3
4
5
6
7
typedef struct redisObject {
    ...
      
    // 24 bits，用于记录对象的访问信息
    unsigned lru:24;  
    ...
} robj;

其中，lru字段在LRU算法和LFU算法下的使用方式并不相同。

在LRU算法中，这24个bit是用来记录key的访问时间戳，从而淘汰最久未被使用的key

在LFU算法中，这24个bit被分为两段，高16bit存储LDT（Last Decrement Time），用来记录key的访问时间戳；低8bit存储LOGC（Logistic Counter），用来记录key的访问频次。