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 算法的效果。