Redis 过期字典与删除策略

redisDB 结构的 expires 字典保存了数据库中所有键的过期时间，该字典被称为过期字典：

• 过期字典的键是一个指针，指向键空间中的某个键对象
• 过期字典的值是一个 long long 类型的整数，这个整数保存了键所指向的数据库键的过期时间

过期字典

在实际中，键空间的键和过期字典的键都指向同一个键对象，所以不会出现任何重复对象，也不会浪费任何空间

过期键删除策略

几种可选的删除策略：

• 定时删除：
  在设置键的过期时间的同时，创建一个定时器，通过定时器执行对键的删除操作
• 惰性删除：
  每次从键空间获取键时，都检查是否过期，过期就删除
• 定期删除：
  每隔一段时间，就对数据库进行一次检查，删除其中的过期键

定时删除

定时删除策略对内存是最友好的：通过定时器，定时删除策略可以保证过期键会尽快被删除，并释放过期键所占用的内存

另一方面，定时删除策略的缺点是，它对 CPU 时间不友好：在过期键比较多的情况下，删除过期键可能会占用相当一部分 CPU 时间，在内存不紧张但 CPU 时间紧张的情况下，将 CPU 时间用于删除和当前任务无关的过期键上，无疑会对服务器的响应时间和吞吐量造成影响

此外，创建一个定时器需要用到 Redis 服务器中的时间事件，而当前时间事件的实现方式为无序链表，查找一个事件的时间为 O(N)，并不能高效地处理大量时间事件

惰性删除

惰性删除策略对 CPU 时间最友好：程序只会在取出键时才对键进行过期检查，这可以保证删除过期键的操作只会在非做不可的情况下进行，并且删除的目标仅限于当前处理的键，这个策略不会在删除其他无关的过期键上花费任何 CPU 时间

惰性删除的缺点是，它对内存是最不友好的：如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，它所占用的内存就不会释放，这可以看作是一种内存泄漏

定期删除

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

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

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

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

Redis 的过期键删除策略

Redis 实际使用的是惰性删除和定期删除两种策略，以求在合理使用 CPU 时间和避免内存浪费之间取得平衡

惰性删除实现

定期删除实现

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

• 函数每次运行时，都从一定数量的数据库中取出一定数量的键进行检查，并删除其中的过期键
• 用一个全局变量记录检查的进度，并在下一次函数调用时，接着上一次的进度进行处理
• 直到所有数据库都被检查一遍，全局变量重置为 0