深圳信息港

【天天播资讯】2023-07-01:redis过期策略都有哪些?LRU 算法知道吗?

2023-07-01 21:20:37 来源:博客园

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

关键词:

热门推荐