Redis过期删除策略与内存淘汰策略

Redis/缓存系统
425
0
0
2023-02-02
Redis 数据库配置与应用
上一篇
redis实现消息队列
下一篇
标签   Redis
目录
  • 过期删除策略
  • 设置Redis中key的过期时间 (单位：秒)
  • 常见的三种过期删除策略
  • Redis使用用的过期删除策略
  • Redis的定期删除的流程
  • 内存淘汰策略
  • 设置Redis最大运行内存
  • Redis 内存淘汰策略有哪些？
  • LRU 算法和 LFU 算法有什么区别？
  • Redis 是如何实现 LRU 算法的？
  • 什么是 LFU 算法？
  • Redis 是如何实现 LFU 算法的？

过期删除策略

过期删除策略： redis可以对key设置过期时间，因此要有相应的机制将已过期的键值对删除。

设置Redis中key的过期时间 (单位：秒)

  • 1）expire key time 这是最常用的方式
  • 2）setex key, seconds, value 字符串独有的方式

如果未设置时间，那就是永不过期。 如果设置了过期时间，使用 persist key 让key永不过期。

每当我们对一个 key 设置了过期时间，Redis 会把该 key 带上过期时间存储到一个过期字典（expires dict）中，也就是说过期字典保存了数据库中所有 key 的过期时间。

过期字典存储在 redisDb 结构中，如下：

typedef struct redisDb {
    dict *dict;    /* 存放着所有的键值对 */
    dict *expires; /* 过期字典: 键和键的过期时间 */
    ....
} redisDb;
/*
	过期字典数据结构结构如下：
    过期字典的 key 是一个指针，指向某个键对象；
    过期字典的 value 是一个 long long 类型的整数，这个整数保存了 key 的过期时间；
*/

字典实际上是哈希表，哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找。

当我们查询一个 key 时，Redis首先检查该 key是否存在于过期字典中：

  • 如果不在，则正常读取键值（没有设置过期时间）
  • 如果存在，则会获取该 key 的过期时间，然后与当前系统时间进行比对，判定该 key是否过期

常见的三种过期删除策略

  • 定时删除：在设置key的过期时间时，同时创建一个定时事件，当时间到达时，由事件处理器自动执行key的删除操作。
  • 惰性删除：不主动删除过期键，每次从数据库访问key时，都检测key是否过期，如果过期则删除该key。
  • 定期删除：每隔一段时间「随机」从数据库中取出一定数量的key进行检查，并删除其中的过期key。

Redis使用用的过期删除策略

Redis 采用了 惰性删除 + 定期删除 的方式处理过期数据，以求在合理使用 CPU 时间和避免内存浪费之间取得平衡 。

  • 惰性删除的使用：当我们访问一个key时，会先检查这个key是否过期，如果过期则删除这个key并返回给客户端null，否则返回对应value
  • 定期删除的使用：定期检查一次数据库，此配置可通过 Redis 的配置文件 redis.conf 进行配置，配置键为 hz 它的默认值是 hz 10( 从数据库中随机抽取20个key 进行过期检查 )

Redis的定期删除的流程

  • 从过期字典中随机抽取 20 个 key（20是写死在代码中的，不可修改）
  • 检查这 20个key是否过期，并删除过期的 key
  • 如果本轮检查的已过期 key 的数量，超过 5 个(过期 key 的数量 / 20 > 25%)，则再次抽取20个检查检查，如果某一次该比例小于 25%，则结束检查，然后等待下一轮再检查

Redis 为了保证定期删除不会出现循环过度，导致线程卡死现象，为此增加了定期删除循环流程的时间上限，默认不会超过 25ms（超过就停止检查）。

内存淘汰策略

内存淘汰策略：redis 的运行内存已经超过redis设置的最大内存后，会使用内存淘汰策略删除符合条件的 key，以此来保障 Redis 高效的运行。

设置Redis最大运行内存

 在配置文件 redis.conf 中，可以通过参数 maxmemory 来设定最大运行内存，只有在 Redis 的运行内存达到了我们设置的最大运行内存，才会触发内存淘汰策略。

不同位数的操作系统，maxmemory 的默认值是不同的：

  • 在 64 位操作系统中，maxmemory 的默认值是 0，表示没有内存大小限制，那么不管用户存放多少数据到 Redis 中，Redis 也不会对可用内存进行检查，直到 Redis 实例因内存不足而崩溃也无作为。
  • 在 32 位操作系统中，maxmemory 的默认值是 3G，因为 32 位的机器最大只支持 4GB 的内存，而系统本身就需要一定的内存资源来支持运行，所以 32 位操作系统限制最大 3 GB 的可用内存是非常合理的，这样可以避免因为内存不足而导致 Redis 实例崩溃

Redis 内存淘汰策略有哪些？

Redis 内存淘汰策略共有八种，这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略

不进行数据淘汰的策略：

  • noeviction（Redis3.0之后，默认的内存淘汰策略）：它表示当运行内存超过最大设置内存时，不淘汰任何数据，而是不再提供服务，直接返回错误
  • 进行数据淘汰的策略（ 又可以细分为在设置了过期时间的数据中进行淘汰和在所有数据范围内进行淘汰这两类策略 ）

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

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

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

  • allkeys-random：随机淘汰任意键值
  • allkeys-lru：淘汰整个键值中最久未使用的键值
  • allkeys-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰整个键值中最少使用的键值

可以使用 config get maxmemory-policy 命令，来查看当前 Redis 的内存淘汰策略，命令如下：

 127.0.0.1:6379> config get maxmemory-policy
 1) "maxmemory-policy"
 2) "noeviction"

Redis 使用的是 noeviction 类型的内存淘汰策略，它是 Redis 3.0 之后默认使用的内存淘汰策略，表示当运行内存超过最大设置内存时，不淘汰任何数据，但新增操作会报错。

设置内存淘汰策略有两种方法：

  • 方式一：通过config set maxmemory-policy <策略>命令设置。立即生效，不需要重启 Redis 服务，但重启 Redis 之后，设置就会失效
  • 方式二：通过修改 Redis 配置文件修改，设置maxmemory-policy <策略>，重启 Redis 服务后配置不会丢失（修改了配置文件，必须重启Redis服务，设置才能生效）

LRU 算法和 LFU 算法有什么区别？

LRU全称是 Least Recently Used 翻译为 最近最少使用，会选择淘汰最近最少使用的数据

Redis 并没有使用这样的方式实现 LRU 算法，因为传统的 LRU 算法存在两个问题：

  • 需要用链表管理所有的缓存数据，这会带来额外的空间开销；
  • 当有数据被访问时，需要在链表上把该数据移动到头端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

Redis 是如何实现 LRU 算法的？

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

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

Redis 实现的 LRU 算法的优点：

  • 不用为所有的数据维护一个大链表，节省了空间占用
  • 不用在每次数据访问时都移动链表项，提升了缓存的性能

但是 LRU 算法有一个问题，无法解决缓存污染问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染。因此，在 Redis 4.0 之后引入了 LFU 算法来解决这个问题

什么是 LFU 算法？

LFU 全称是 Least Frequently Used 翻译为最近最不常用的，LFU 算法是根据数据访问次数来淘汰数据的，它的核心思想是"如果数据过去被访问多次，那么将来被访问的频率也更高"。所以， LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时，就会增加该数据的访问次数。这样就解决了偶尔被访问一次之后，数据留存在缓存中很长一段时间的问题，相比于 LRU 算法也更合理一些.

Redis 是如何实现 LFU 算法的？

LFU 算法相比于 LRU 算法的实现，多记录了「数据的访问频次」的信息。

Redis 对象的结构如下：

 typedef struct redisObject {
     ...
     unsigned lru:24;  // 24 bits，用于记录对象的访问信息
     ...
 } robj;

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

 在 LRU 算法中，Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳，因此在 LRU 模式下，Redis可以根据对象头中的 lru 字段记录的值，来比较最后一次 key 的访问时间长，从而淘汰最久未被使用的 key。

在 LFU 算法中，Redis对象头的 24 bits 的 lru 字段被分成两段来存储，高 16bit 存储 ldt(Last Decrement Time)，低 8bit 存储 logc(Logistic Counter)。

  • ldt 是用来记录 key 的访问时间戳
  • logc 是用来记录 key 的访问频次，它的值越小表示使用频率越低，越容易淘汰，每个新加入的 key 的logc 初始值为 5。
注意：logc并不是单纯的访问次数，而是访问频次(访问频率)，因为logc会随时间推移而衰减的。

在每次 key 被访问时，会先对 logc 做一个衰减操作，衰减的值跟前后访问时间的差距有关系，如果上一次访问的时间与这一次访问的时间差距很大，那么衰减的值就越大，这样实现的 LFU 算法是根据访问频率来淘汰数据的，而不只是访问次数。访问频率需要考虑 key 的访问是多长时间段内发生的。key 的先前访问距离当前时间越长，那么这个 key 的访问频率相应地也就会降低，这样被淘汰的概率也会更大。

对 logc 做完衰减操作后，就开始对 logc 进行增加操作，增加操作并不是单纯的 + 1，而是根据概率增加，如果 logc 越大的 key，它的 logc 就越难再增加。

所以，Redis 在访问 key 时，对于 logc 是这样变化的： 先按照上次访问距离当前的时长，来对 logc 进行衰减； 然后，再按照一定概率增加 logc 的值

redis.conf 提供了两个配置项，用于调整 LFU 算法从而控制 logc 的增长和衰减：

  • lfu-decay-time：用于调整 logc 的衰减速度，它是一个以分钟为单位的数值，默认值为1，lfu-decay-time 值越大，衰减越慢；
  • lfu-log-factor：用于调整 logc 的增长速度，lfu-log-factor 值越大，logc 增长越慢。
Redis 数据库配置与应用
上一篇
redis实现消息队列
下一篇