Redis 过期删除策略和内存淘汰机制

     

Redis 设置过期时间

Redis 有四个不同的命令可以用于设置键的生存时间（键可以存在多久）或过期时间（键什么时候会被删除）：

• EXPIRE ——将键 key 的生存时间设置为 ttl 秒。
• PEXPIRE ——将键 key 的生存时间设置为 ttl 毫秒。
• EXPIREAT ——将键 key 的过期时间设置为 timestamp 所指定的秒数时间戳。
• PEXPIREAT ——将键 key 的过期时间设置为 timestamp 所指定的毫秒数时间戳。

虽然有多种不同单位和不同形式的设置命令，但实际上 EXPIRE 、PEXPIRE 、EXPIREAT 三个命令都是使用 PEXPIREAT 命令来实现的：无论客户端执行的是四个命令中的哪一个，经过转换之后，最终的执行效果都和执行 PEXPIREAT 命令一样。  

 

Redis 计算并返回剩余时间

Redis 提供了两个命令，其中 TTL 命令以秒为单位返回键的剩余生存时间；PTTL 命令则以毫秒为单位返回键的剩余生存时间。TTL 和 PTTL 两个命令都是通过计算键的过期时间和当前时间之间的差来实现的。    

 

Redis 过期字典

redisDb 结构的 expires 字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典：

• 过期字典的键是一个指针，这个指针指向键空间的某个键对象（也即是某个数据库键）。
• 过期字典的值是一个 long long 类型的整数，这个整数保存了键所指向的数据库键的过期时间——一个毫秒精度的 UNIX 时间戳。

   

 

Redis 过期键的判定

通过过期字典，程序可以用以下步骤检查一个给定键是否过期：

1. 检查给定键是否存在于过期字典，如果存在，那么取得键的过期时间。
2. 检查当前 UNIX 时间戳是否大于键的过期时间，如果是的话，那么键已经过期，否则的话，键未过期。

   

 

三种过期键删除策略

定时删除

在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键的过期时间来临时，立即执行对键的删除操作。

优点：

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

缺点：

• 对 CPU 时间是最不友好的。在过期键比较多的情况下，删除过期键这一行为可能会占用相当一部分 CPU 时间，在内存不紧张但是 CPU 时间非常紧张的情况下，将 CPU 时间用在删除和当前任务无关的过期键上，无疑会对服务器的响应时间和吞吐量造成影响。
• 创建一个定时器需要用到 Redis 服务器中的时间事件，而当前时间事件的实现方式是无序链表，查找一个事件的时间复杂度为 O(N)，这并不能高效地处理大量时间事件。

 

惰性删除

放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。

优点：

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

缺点：

• 对内存是最不友好的。如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，它所占用的内存就不会释放。如果数据库中有非常多的过期键，而这些过期键又恰好没有被访问到的话，那么它们也许永远也不会被删除（除非用户手动执行 FLUSHDB），我们甚至可以将这种情况看作是一种内存泄露，无用的垃圾数据占用了大量内存，而服务器却不会自己去释放它们。

 

定期删除

每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。至于要删除多少过期键，以及要检查多少个数据库，则由算法决定。

优点：

• 之前讨论的两种删除策略都有明显的缺陷，定期删除策略是前两种策略的一种整合和折中。
• 定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对 CPU 时间的影响。
• 除此以外，通过定期删除过期键，定期删除策略有效地减少了因为过期键而带来的内存浪费。

缺点：

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

   

 

Redis 的过期删除策略

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

惰性删除策略的实现

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

1. 如果输入键已经过期，那么 expireIfNeeded 函数将输入键从数据库中删除。
2. 如果输入键未过期，那么 expireIfNeeded 函数不做动作。

 

定期删除策略的实现

过期键的定期删除策略由 redis.c/activeExpireCycle 函数实现，每当 Redis 的服务器周期性操作 redis.c/serverCron 函数执行时，activeExpireCycle 函数就会调用，它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的 expires 字典中随机检查一部分键的过期时间，并删除其中的过期键。 Redis 默认每秒进行 10 次过期扫描（Redis 的配置文件里面的 hz 参数配置），过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略，步骤如下：

1. 从过期字典中随机选出 20 个 key。
2. 删除这 20 个 key 中已经过期的 key。
3. 如果过期的 key 的比例超过 1/4，那就重复步骤（1）。

同时，为了保证过期扫描不会出现循环过度，导致线程卡死的现象，算法还增加了扫描时间的上限，默认不会超过 25ms。      

 

Redis 的内存淘汰机制

为了限制最大使用内存，Redis 提供了配置参数 maxmemory 来限制内存超出期望大小。 当实际内存超出 maxmemory 时，Redis 提供了几种可选策略（maxmemory-policy）来让用户自己决定该如何腾出新的空间以继续提供读写服务。

• noeviction：不会继续服务写请求（del 请求可以继续服务），读请求可以继续进行。这样可以保证不会丢失数据，但是会让线上的业务不能持续进行。这是默认的淘汰策略。
• volatile-lru：尝试淘汰设置了过期时间的 key，最少使用的 key 优先被淘汰。没有设置过期时间的 key 不会被淘汰，这样可以保证需要持久化的数据不会突然丢失。
• volatile-ttl：跟上面几乎一样，不过淘汰的策略不是 LRU，而是比较 key 的剩余寿命 ttl 的值，ttl 越小越优先被淘汰。
• volatile-random：跟上面几乎一样，不过淘汰的 key 是过期 key 集合中随机的 key。
• alllkeys-lru：区别于 volatille-lru，这个策略要淘汰的 key 对象是全体的 key 集合，而不只是过期的 key 集合，这意味着一些没有设置过期时间的 key 也会被淘汰。
• alllkeys-random：跟上面几乎一样，不过淘汰的 key 是随机的 key。

  volatile-xxx 策略只会针对带过期时间的 key 进行淘汰，allkeys-xxx 策略会对所有的 key 进行淘汰。如果你只是拿 Redis 做缓存，那么应该使用 allkeys-xxx 策略，客户端写缓存时不必携带过期时间。如果你还想同时使用 Redis 的持久化功能，那就使用 volatile-xxx 策略，这样可以保留没有设置过期时间的 key，它们是永久的 key，不会被 LRU 算法淘汰。      

 

Redis 的 LRU 算法

　　Redis 使用的是一种近似 LRU 算法。之所以不使用 LRU 算法，是因为其需要消耗大量的额外内存，需要对现有的数据结构进行较大的改造。近似 LRU 算法很简单，在现有数据结构的基础上使用随机采样法来淘汰元素，能达到和 LRU 算法非常近似的效果。 　　当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行一次 LRU 淘汰算法。这个算法也很简单，就是随机采样出 5 个 key（数量可以配置，maxmemory_samples），然后淘汰掉最旧的 key，如果淘汰后内存还是超出 maxmemory，那就继续随机采样淘汰，直到内存低于 maxmemory 为止。 如何采样要看 maxmemory-policy 的设置，如果是 allkeys，就从所有的 key 字典中随机采样，如果是 volatile，就从带过期时间的 key 字典中随机采样。每次采样多少个 key 取决于 maxmemory_samples 的设置，默认为 5。 　　Redis 3.0 在算法中增加了淘汰池，进一步提升了近似 LRU 算法的效果。淘汰池是一个数组，它的大小是 maxmemory_samples，在每一次淘汰循环中，新的随机得出的 key 列表会和淘汰池中的 key 列表进行融合，淘汰掉最旧的一个 key 之后，保留剩余较旧的 key 列表放入淘汰池中留待下一个循环。