2023-07-01：redis过期策略都有哪些？LRU 算法知道吗？ - 福大大架构师每日一题

2023-07-01：redis过期策略都有哪些？LRU 算法知道吗？

答案2023-07-01：

缓存淘汰算法（过期策略）

当Redis的内存超出物理内存限制时，内存中的数据就会频繁地与磁盘进行交换，这个过程叫做交换（swap）。由于交换的高开销，Redis的性能会急剧下降。对于访问频率较高的Redis实例来说，这样低效的存取效率几乎等同于不可用。

maxmemory

在生产环境中，我们严禁Redis发生交换行为。为了限制Redis的最大内存使用量，Redis提供了一个配置参数maxmemory，用于设置期望的最大内存大小。

当实际内存超出maxmemory限制时，Redis提供了几种可选策略（maxmemory-policy），供用户自行选择如何释放空间以便继续提供读写服务。

• noeviction: 这种策略不会继续为写请求提供服务（DEL请求可以继续提供服务），但读请求可以继续进行。这保证不会丢失数据，但会导致在线业务无法持续进行。这是默认的淘汰策略。

• volatile-lru: 该策略尝试淘汰设置了过期时间的键，优先淘汰最近最少使用的键。没有设置过期时间的键不会被淘汰，以确保持久化数据不会突然丢失。

• volatile-ttl: 与前面的策略相似，但淘汰的依据是键的剩余生存时间（TTL）值，TTL越小的键优先被淘汰。

• volatile-random: 与前面的策略类似，但是淘汰过期键集合中的键时是随机的。

• allkeys-lru: 与volatile-lru不同，该策略淘汰的是整个键集合，而不仅限于过期键集合。这意味着没有设置过期时间的键也会被淘汰。

• allkeys-random: 与前面的策略类似，但淘汰的键是整个键集合中的随机键。

策略中的"volatile-xxx"仅针对带有过期时间的键进行淘汰，而"allkeys-xxx"策略会对所有键进行淘汰。如果您只是将Redis用作缓存，应该使用"allkeys-xxx"策略，客户端在写入缓存时不需要提供过期时间。如果您还希望同时使用Redis的持久化功能，则应使用"volatile-xxx"策略，这样可以保留未设置过期时间的键，它们将被视为永久键而不会被LRU算法淘汰。

LRU 算法

LRU算法的实现通常涉及两个数据结构：字典和链表。字典用于以键值对的形式存储数据，而链表用于维护键的访问顺序。链表中的元素按照最近访问的时间顺序排列，最近访问的元素位于链表的头部，而不常使用的元素位于尾部。当缓存空间已满时，将会踢掉链表尾部的元素。

链表尾部的元素是不被频繁访问的，因此在空间满时会被移除。而链表头部的元素是最近被访问过的，暂时不会被移除。

近似 LRU 算法

Redis使用的是近似LRU算法，与LRU算法有一些不同。由于LRU算法需要消耗大量的额外内存并需要对数据结构进行较大改造，所以Redis选择使用近似LRU算法。

近似LRU算法在现有数据结构的基础上采用了随机采样法来淘汰元素，能够达到非常接近LRU算法的效果。为了实现近似LRU算法，Redis为每个键增加了一个额外的小字段，该字段的长度为24个比特，表示最后一次访问该键的时间戳。

当Redis执行写操作时，如果发现内存超出maxmemory限制，它会执行一次LRU淘汰算法。该算法非常简单：随机选择5个键（可配置为maxmemory-samples数），然后淘汰最旧的键。如果淘汰后仍然超出maxmemory，Redis将继续随机采样淘汰，直到内存低于maxmemory为止。

maxmemory-policy的配置决定了采样的方式。若为"allkeys"，则从所有键的字典中进行随机采样；若为"volatile"，则从带有过期时间的键字典中随机采样。每次采样的键数量由maxmemory-samples配置确定，默认为5。

采样数量越大，近似LRU算法的效果越接近严格的LRU算法。

此外，Redis 3.0引入了淘汰池的概念，新的算法会维护一个候选池（大小为16）。池中的数据按访问时间排序，首次随机选取的键将放入池中。随后的每次随机选取只有在访问时间小于池中最小时间时，才会放入池中，直到池满为止。当池满时，如果有新的键需要放入，将移除最后访问时间最大（最近被访问）的键。这进一步提升了近似LRU算法的效果。