Redis(十九) -- 过期删除策略和内存淘汰策略

1. 过期删除策略

1.1 redis支持三种过期删除策略：

  • 定时删除：在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作
  • 惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键
  • 定期删除： 每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。至于要删除多个过期键，以及要检查多少个数据库，则由算法决定

第一种和第三种为主动删除策略，而第二种则为被动删除策略

1.1.1 定时删除
  • 优点：对内存是最友好的：通过使用定时器，定时删除策略可以保证过期键会尽可能快地被删除，并释放过期键所占用的内存
  • 缺点：对CPU时间是最不友好的：在过期键比较多的情况下，删除过期键这一行为可能会占用相当一部分CPU时间。创建一个定时器需要用到Redis服务器中的时间事件，而当前时间事件的实现方式——无序列表，查找一个事件的时间复杂度为O(N)——并不能高效地处理大量时间事件
1.1.2 惰性删除
  • 优点：对CPU时间来说是最友好的：程序只会在取出键时才对键进行过期检查，这可以保证删除过期键的操作只会在非做不可的情况下进行，并且删除的目标仅限于当前处理的键，这个策略不会再删除其他无关的过期键上花费任何CPU时间
  • 缺点：它对内存是最不友好的：如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，它所占用的内存就不会释放
1.1.3 定期删除

定期删除策略是前两种策略的一种整合和折中：

  • 定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响
  • 通过定期删除过期键，定期删除策略有效地减少了因为过期键而带来的内存浪费

定期删除策略的难点是确定删除操作执行的时长和频率：

  • 如果删除操作执行得太频繁，或者执行的时间太长，定期删除策略就会退化成定时删除策略，以至于将CPU时间过多地消耗在删除过期键上面
  • 如果删除操作执行得太少，或者执行的时间太短，定期删除策略又会和惰性删除策略一样，出现浪费内存的情况

在这里插入图片描述

1.2 Redis使用的过期删除策略

Redis服务器实际使用的是惰性删除和定期删除两种策略：通过配合使用这两种策略，服务器可以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡

1.2.1 惰性删除策略的实现

过期键的惰性删除策略由db.c/expireIfNeeded函数实现，所有读写数据库的Redis命令在执行之前都会调用expireIfNeeded函数对输入键进行检查：

  • 如果输入键已经过期，那么expireIfNeeded函数将输入键从数据库中删除
  • 如果输入键未过期，那么expireIfNeeded函数不做动作
1.2.2 定期删除策略的实现

过期键的定期删除策略由redis.c/activeExpireCycle函数实现，每当Redis的服务器周期性操作redis.c/serverCron函数执行时，activeExpireCycle函数就会被调用，它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键

activeExpireCycle函数的工作模式：

  • 函数每次运行时，都会从一定数量的数据库中取出一定数量的随机键进行检查，并删除其中的过期键
  • 有一个全局变量current_db会记录当前activeExpireCycle函数检查的进度，并在下一次activeExpireCycle函数调用时，接着上一次的进度进行处理
  • 随着activeExpireCycle函数的不断执行，服务器中的所有数据库都会被检查一遍，这时函数将current_db变量重置为0，然后再次开始新一轮的检察工作
1.2.3 这样还存在的问题：

如果某个key过期后，定期删除没删除成功，然后也没再次去请求key，也就是说惰性删除也没生效。这时，如果大量过期的key堆积在内存中，redis的内存会越来越高，导致redis的内存块耗尽。那么就应该采用内存淘汰机制。

1.3 RDB对过期键的处理

1.3.1 生成RDB文件

在执行SAVE命令或者BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，已过期的键不会被保存到新创建的RDB文件中

1.3.2 载入RDB文件

在启动Redis服务器时，如果服务器开启了RDB功能，那么服务器将对RDB文件进行载入：

  • 如果服务器以主服务器模式运行，那么在载入RDB文件时，程序会对文件中保存的键进行检查，未过期的键会被载入到数据库中，而过期键则会被忽略，所以过期键对载入RDB文件的主服务器不会造成影响
  • 如果服务器以从服务器模式运行，那么在载入RDB文件时，文件中保存的所有键，不论是否过期，都会被载入到数据库中。不过，因为主从服务器在进行数据同步的时候，从服务器的数据库就会被清空，所以一般来说，过期键在载入RDB文件的从服务器也不会造成影响

1.4 AOF对过期键的处理

1.4.1 AOF文件写入

当服务器以AOF持久化模式运行时，如果数据库中的某个键已经过期，但它还没有被惰性删除或者定期删除，那么AOF文件不会因为这个过期键而产生任何影响

当过期键被惰性删除或者定期删除之后，程序会向AOF文件追加一个DEL命令，来显式地记录该键已被删除

1.4.2 AOF重写

和生成RDB文件时类似，在执行AOF重写的过程中，程序会对数据库中的键进行检查，已过期的键不会被保存到重写后的AOF文件中

1.5 复制对过期键的处理

当服务器运行在复制模式下时，从服务器的过期键删除动作由主服务器控制：

  • 主服务器在删除一个过期键之后，会显示地向所有从服务器发送一个DEL命令，告知从服务器删除这个过期键
  • 从服务器在执行客户端发送的读命令时，即使碰到过期键也不会将过期键删除，而是继续处理未过期的键一样来处理过期键
  • 从服务器只有在接到主服务器发来的DEL命令之后，才会删除过期键

通过由主服务器来控制从服务器统一地删除过期键，可以保证主从服务器数据的一致性，也正是因为这个原因，当一个过期键仍然存在于主服务器的数据库时，这个过期键在从服务器里的复制品也会继续存在

2. 内存淘汰策略

在使用Redis时，我们一般会为Redis的缓存空间设置一个大小，不会让数据无限制地放入Redis缓存中。可以使用下面命令来设定缓存的大小，比如设置为4GB：

CONFIG SET maxmemory 4gb

既然 Redis 设置了缓存的容量大小，那缓存被写满就是不可避免的。当缓存被写满时，我们需要考虑下面两个问题：决定淘汰哪些数据，如何处理那些被淘汰的数据。

2.1 redis提供的缓存淘汰策略

Redis共提供了8中缓存淘汰策略，其中 volatile-lfu 和 allkeys-lfu 是Redis 4.0版本新增的。

  • 不进行淘汰数据。
    • noeviction：一旦缓存被写满，再有写请求进来，Redis就不再提供服务，而是直接返回错误。Redis 用作缓存时，实际的数据集通常都是大于缓存容量的，总会有新的数据要写入缓存，这个策略本身不淘汰数据，也就不会腾出新的缓存空间，我们不把它用在 Redis 缓存中。
  • 进行淘汰数据
    • 对设置了过期时间的数据进行淘汰：
      • volatile-ttl：在设置了过期时间的键值对中，移除即将过期的键值对
      • volatile-random：在设置了过期时间的键值对中，随机移除某个键值对。
      • volatile-lru：在设置了过期时间的键值对中，移除最近最少使用的键值对
      • volatile-lfu：在设置了过期时间的键值对中，移除最近最不频繁使用的键值对
    • 对所有数据进行淘汰：
      • allkeys-random：在所有键值对中，随机移除某个key。
      • allkeys-lru：在所有的键值对中，移除最近最少使用的键值对。
      • allkeys-lfu：在所有的键值对中，移除最近最不频繁使用的键值对

2.2 淘汰策略的选用：

  • 通常情况下推荐优先使用 allkeys-lru 策略。这样可以充分利用 LRU 这一经典缓存算法的优势，把最近最常访问的数据留在缓存中，提升应用的访问性能。
  • 如果你的业务数据中有明显的冷热数据区分，建议使用 allkeys-lru 策略。
  • 如果业务应用中的数据访问频率相差不大，没有明显的冷热数据区分，建议使用 allkeys-random 策略，随机选择淘汰的数据就行。
  • 如果没有设置过期时间的键值对，那么 volatile-lru，volatile-lfu，volatile-random 和 volatile-ttl 策略的行为, 和 noeviction 基本上一致。

2.3 Redis中的LRU和LFU算法：

2.3.1 LRU算法

LRU 算法的全称是 Least Recently Uses，按照最近最少使用的原则来筛选数据，最不常用的数据会被筛选出来。LRU 会把所有的数据组织成一个链表，链表的头和尾分别表示 MRU 端和 LRU 端，分别代表最近最常使用的数据和最近最不常用的数据。我们看一个例子。
在这里插入图片描述

如果有一个新数据 45 要被写入缓存，但此时已经没有缓存空间了，也就是链表没有空余位置了，那么LRU 算法做两件事：数据 45 是刚被访问的，所以它会被放到 MRU 端；算法把 LRU 端的数据 5 从缓存中删除，相应的链表中就没有数据 5 的记录了。LRU认为刚刚被访问的数据，肯定还会被再次访问，所以就把它放在 MRU 端；长久不访问的数据，肯定就不会再被访问了，所以就让它逐渐后移到 LRU 端，在缓存满时，就优先删除它。

LRU 算法在实际实现时，需要用链表管理所有的缓存数据，移除元素时直接从链表队尾移除，增加时加到头部就可以了，但这会带来额外的空间开销。而且，当有数据被访问时，需要在链表上把该数据移动到 MRU 端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

所以，在 Redis 中，LRU 算法被做了简化，以减轻数据淘汰对缓存性能的影响。具体来说：Redis 默认会记录每个数据的最近一次访问的时间戳（由键值对数据结构 RedisObject 中的 lru 字段记录）。然后，Redis 在决定淘汰的数据时，第一次会随机选出 N 个数据，把它们作为一个候选集合。接下来，Redis 会比较这 N 个数据的 lru 字段，把 lru 字段值最小的数据从缓存中淘汰出去。当需要再次淘汰数据时，Redis 需要挑选数据进入第一次淘汰时创建的候选集合。这里的挑选标准是：能进入候选集合的数据的 lru 字段值必须小于候选集合中最小的 lru 值。当有新数据进入候选数据集后，如果候选数据集中的数据个数达到了 N 个，Redis 就把候选数据集中 lru 字段值最小的数据淘汰出去。这样一来，Redis 缓存不用为所有的数据维护一个大链表，也不用在每次数据访问时都移动链表项，提升了缓存的性能。

Redis 提供了一个配置参数 maxmemory-samples，这个参数就是 Redis 选出的数据个数 N。例如，我们执行如下命令，可以让 Redis 选出 100 个数据作为候选数据集：

CONFIG SET maxmemory-samples 100

RedisObject 的定义如下：（简单理解为一个 key-value）

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;
2.3.2 LFU算法：

LFU是在Redis4.0后出现的，它的核心思想是根据key的最近被访问的频率进行淘汰，很少被访问的优先被淘汰，被访问的多的则被留下来。LFU算法能更好的表示一个key被访问的热度。假如你使用的是LRU算法，一个key很久没有被访问到，只刚刚是偶尔被访问了一次，那么它就被认为是热点数据，不会被淘汰，而有些key将来是很有可能被访问到的则被淘汰了。如果使用LFU算法则不会出现这种情况，因为使用一次并不会使一个key成为热点数据。它的使用与LRU有所区别：

  • LFU (Least Frequently Used) ：最近最不频繁使用，跟使用的次数有关，淘汰使用次数最少的。
  • LRU (Least Recently Used)：最近最少使用，跟使用的最后一次时间有关，淘汰最近使用时间离现在最久的。

LRU的最近最少使用实际上并不精确，考虑下面的情况，如果在 “|” 处删除，那么A距离的时间最久，但实际上A的使用频率要比D频繁，所以合理的淘汰策略应该是淘汰D。LFU就是为应对这种情况而生的。

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~R~~R~~R~~R~~R~~R~~R~~R~~R~~R~~R~~R~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

每个波浪号代表一秒，A 每五秒，R 每两秒，C 和 D 每十秒 ， 最近被访问的字符是 D，但显然按照现有的规律，下一个被访问的更可能是 R 而不是 D。

LFU 实现比较复杂，需要考虑几个问题：

  • 如果实现为链表，当对象被访问时按访问次数移动到链表的某个有序位置可能是低效的，因为可能存在大量访问次数相同的 key，最差情况是O(n)
  • 某些 key 访问次数可能非常之大，理论上可以无限大，但实际上我们并不需要精确的访问次数
  • 访问次数特别大的 key 可能以后都不再访问了，但是因为访问次数大而一直占用着内存不被淘汰，需要一个方法来逐步“驱除”（有点 LRU的意思），最简单的就是逐步衰减访问次数

本着能省则省的原则，Redis 只用了 24bit （server.lruclock 也是24bit）来记录上述的信息，是的不是 24byte，连32位指针都放不下！

  • 16bit : 上一次递减时间 （解决第三个问题）
  • 8bit : 访问次数 （解决第二个问题）

访问次数的计算如下：

uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

核心就是访问次数越大，访问次数被递增的可能性越小，最大 255，可以在配置 redis.conf 中写明访问多少次递增多少。由于访问次数是有限的，所以第一个问题也被解决了，直接一个255数组或链表都可以。

16bit 部分保存的是时间戳的后16位（分钟），表示上一次递减的时间，算法是这样执行，随机采样N个key，检查递减时间，如果距离现在超过 N 分钟（可配置），则递减或者减半（如果访问次数数值比较大）。

此外，由于新加入的 key 访问次数很可能比不被访问的老 key小，为了不被马上淘汰，新key访问次数设为 5。

2.4 相关面试题：

在这里插入图片描述