拿个offer - 开源&项目实战 拿个offer - 开源&项目实战
首页
后端技术
🚀大话面试
  • 校&社招实战项目

    • 12306(铁路购票平台)
    • 短链接(Sass平台)
  • 社招进阶项目

    • 刚果商城(DDD领域驱动)
  • 基础架构项目

    • 幂等基础组件(支持接口及多种MQ)
    • 企业基础架构组件库
  • 校&社招实战项目

    • 12306(铁路购票平台) (opens new window)
    • 短链接(Sass平台) (opens new window)
  • 社招进阶项目

    • 刚果商城(DDD领域驱动) (opens new window)
加入群聊
🔋知识星球
代码仓库 (opens new window)
首页
后端技术
🚀大话面试
  • 校&社招实战项目

    • 12306(铁路购票平台)
    • 短链接(Sass平台)
  • 社招进阶项目

    • 刚果商城(DDD领域驱动)
  • 基础架构项目

    • 幂等基础组件(支持接口及多种MQ)
    • 企业基础架构组件库
  • 校&社招实战项目

    • 12306(铁路购票平台) (opens new window)
    • 短链接(Sass平台) (opens new window)
  • 社招进阶项目

    • 刚果商城(DDD领域驱动) (opens new window)
加入群聊
🔋知识星球
代码仓库 (opens new window)
  • 小册简介

    • 什么是大话面试
  • Redis

    • Redis为什么这么快?
    • Redis宕机数据会丢失么?
    • Redis的AOF是怎么实现的?
    • Redis的RDB是怎么实现的?
    • Redis如何实现到期删除的?
    • Redis常用内存淘汰策略?
      • 答题思路
      • 回答话术
      • 问题详解
        • 1. 淘汰策略
        • 2. LRU 的实现
        • 3. LFU 的实现
        • 4. 如何选择
    • Redis字符串底层数据结构?
    • Redis的压缩列表是什么?
    • Redis的跳表是什么?
    • Redis的ZSet底层是怎么实现的?
    • 什么是布隆过滤器?
    • 布隆过滤器容量如何评估?
    • 布隆过滤器容量不够用如何解决?
    • Redis节点CPU核数越高越好?
    • 为什么Redis不适合海量请求?
    • Redis如何应对海量请求?
    • 如何提升Redis批量访问性能?
  • 缓存

    • 如何解决缓存击穿?
    • 如何解决缓存穿透?
    • 如何解决缓存雪崩?
    • 如何解决大Key问题?
    • 缓存如何预热?
    • 如何发现缓存中热Key?
    • 如何解决热Key问题?
    • 缓存与数据库一致性?
    • 先写DB再删除缓存解决一致性?
    • Binlog配合MQ如何解决一致性?
目录

Redis常用内存淘汰策略?

# 答题思路

从淘汰范围来说可以分为不淘汰任何数据、只从设置了到期时间的键中淘汰和从所有键中淘汰三类。而从淘汰算法来分,又主要分为 random(随机),LRU(最近最少使用),以及 LFU(最近最不常使用)三种。

# 回答话术

内存总是有限的,因此当 Redis 内存超出最大内存时,就需要根据一定的策略去主动的淘汰一些 key,来腾出内存,这就是内存淘汰策略。我们可以在配置文件中通过 maxmemory-policy 配置指定策略。

与到期删除策略不同,内存淘汰策略主要目的则是为了防止运行时内存超过最大内存,所以尽管最终目的都是清理内存中的一些 key,但是它们的应用场景和触发时机是不同的。

算上在 4.0 添加的两种基于 LFU 算法的策略, Redis 一共提供了八种策略供我们选择:

  • noeviction,不淘汰任何 key,直接报错。它是默认策略**。**
  • volatile-random:从所有设置了到期时间的 key 中,随机淘汰一个 Key。
  • volatile-lru: 从所有设置了到期时间的 key 中,淘汰最近最少使用的 key。
  • volatile-lfu: 从所有设置了到期时间的 key 中,淘汰最近最不常用使用的 key(4.0 新增)。
  • volatile-ttl: 从所有设置了到期时间的 key 中,优先淘汰最早过期的 key。
  • allkeys-random:从所有 key中,随机淘汰一个键(4.0 新增)。
  • allkeys-lru: 从所有 key 中,淘汰最近最少使用的 key。
  • allkeys-lfu: 从所有 key 中,淘汰最近最不常用使用的键。

从淘汰范围来说可以分为不淘汰任何数据、只从设置了到期时间的键中淘汰和从所有键中淘汰三类。而从淘汰算法来分,又主要分为 random(随机),LRU(最近最少使用),以及 LFU(最近最不常使用)三种。

其中,关于 LRU 算法,它是一种非常常见的缓存淘汰算法。我们可以简单理解为 Redis 会在每次访问 key 的时候记录访问时间,当淘汰时,优先淘汰最后一次访问距离现在最早的 key。

而对于 LFU 算法,我们可以理解为 Redis 会在访问 key 时,根据两次访问时间的间隔计算并累加访问频率指标,当淘汰时,优先淘汰访问频率指标最低的 key。相比 LRU 算法,它避免了低频率的大批量查询造成的缓存污染问题。

顺带一提,只要是有类似缓存机制的应用或多或少都会面对这种问题,比如老生常谈的 MySQL 连表查询,在数据量大的时候也会造成缓存污染。

# 问题详解

# 1. 淘汰策略

按 key 的淘汰范围来分,我们可以把这些策略分为三类

1)不淘汰任何数据

也就是noeviction,它是默认的策略。

2)只从设置的了到期时间的 key 中淘汰

  • volatile-random:从所有设置了到期时间的 key 中,随机淘汰一个 key。
  • volatile-lru: 从所有设置了到期时间的 key 中,淘汰最近最少使用的 key。
  • volatile-lfu: 从所有设置了到期时间的 key 中,淘汰最近最不常用使用的 key(4.0 新增)。
  • volatile-ttl: 从所有设置了到期时间的 key 中,优先淘汰最早过期的 key。

3)从所有的 key 中进行淘汰

  • allkeys-random:从所有 key中,随机淘汰一个键(4.0 新增)。
  • allkeys-lru: 从所有 key 中,淘汰最近最少使用的 key。
  • allkeys-lfu: 从所有 key 中,淘汰最近最不常用使用的键。

# 2. LRU 的实现

LRU 的全称为 Least Recently Used,也就是最近最少使用。一般来说,LRU 会从一批 key 中淘汰上次访问时间最早的 key。

它是一种非常常见的缓存回收算法,在诸如 Guava Cache、Caffeine等缓存库中都提供了类似的实现。我们自己也可以基于 JDK 的 LinkedHashMap 实现支持 LRU 算法的缓存功能。

传统的 LRU 算法实现通常会维护一个链表,当访问过某个节点后就将该节点移至链表头部。如此反复后,链表的节点就会按最近一次访问时间排序。当缓存数量到达上限后,我们直接移除尾节点,即可移除最近最少访问的缓存。

近似 LRU

Redis 中的 LRU 是近似 LRU(NearlyLRU)。当每次访问 key 时,Redis 会在结构体中记录本次访问时间,而当需要淘汰 key 时,将会从全部数据中进行抽样,然后再移除样本中上次访问时间最早的 key。

它的特点是:

  • 仅当需要时再抽样,因而不需要维护全量数据组成的链表,这避免了额外内存消耗。
  • 访问时仅在结构体上记录操作时间,而不需要操作链表节点,这避免了额外的性能消耗。

当然,有利就有弊,这种实现方式也决定 Redis 的 LRU 是并不是百分百准确的,被淘汰的 key 未必真的就是所有 key 中最后一次访问时间最早的。

# a. 抽样大小

根据上述的内容,我们不难理解,当抽样的数量越大,LRU 淘汰 key 就越准确,相对的开销也更大。因此,Redis 允许我们通过 maxmemory-samples 配置采样数量(默认为 5),从而在性能和精度上取得平衡。

# b. 缓存污染

LRU 有个最大问题,就是它只认最近一次访问时间。而如果出现系统偶尔需要一次性读取大量数据的时候,会大规模更新 key 的最近访问时间,从而导致真正需要被频繁访问的 key 因为最近一次访问时间更早而被直接淘汰。这种情况被称为缓存污染。为此,我们需要使用 LFU 算法来

具体可直接参见:深入解析Redis的LRU与LFU算法实现 (opens new window)

# 3. LFU 的实现

LFU 全称为 Least Frequently Used ,也就是最近最不常用。相比起 LRU,它的特点如下:

  • 同样是基于抽样实现的近似算法,maxmemory-samples 对其同样有效。
  • 比较的不是最后一次访问时间,而是数据的访问频率。当淘汰的时候,优先淘汰范围频率最低 key。

在 Redis 用来存储数据的结构体 redisObj 中,有一个 24 位的 lru数值字段:

  • 当使用 LRU 算法时,它用于记录最后一次访问时间的时间戳。
  • 当使用 LFU 算法时,它被分为两部分,高 16 位关于记录最近一次访问时间(Last Decrement Time),而低 8 位作为记录访问频率计数器(Logistic Counter)。

LFU 的核心就在于低 8 位表示的访问频率计数器(下面我们简称为 counter),它是一个介于 0 ~ 255 的特殊数值,它会每次访问 key 时,基于时间衰减和概率递增机制动态改变。

# a. 时间衰减

每当访问 key 时,根据当前实际与该 key 的最后一次访问时间的时间差对 counter 进行衰减。

衰减值取决于 lfu_decay_time 配置,该配置表示一个衰减周期。我们可以简单的认为,每当时间间隔满足一个衰减周期时,就会对 counter 减一。

比如,我们设置 lfu_decay_time为 1 分钟,那么如果 key 最后一次访问距离现在已有 3 分 30 秒,那么 counter 就需要减 3。

# b. 概率递增

在完成衰减后,Redis 将根据 lfu_log_factor 配置对应概率值对 counter 进行递增。

这里直接放上源码:

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    // 若已达最大值 255,直接返回
    if (counter == 255) return 255;
    // 获取一个介于 0 到 1 之间的随机值
    double r = (double)rand()/RAND_MAX;
    // 根据当前 counter 减去初始值得到 baseval
    double baseval = counter - LFU_INIT_VAL; 
    if (baseval < 0) baseval = 0;
    // 使用 baseval*server.lfu_log_factor+1 得到一个概率值 p
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    // 当 r < p 时,递增 counter
    if (r < p) counter++;
    return counter;
}

简而言之,直接从代码上理解,我们可以认为 counter和 lfu_log_factor 越大,则递增的概率越小:

当然,实际上也要考虑到访问次数对其的影响,Redis 官方给出了相关数据:

具体可直接参见:深入解析Redis的LRU与LFU算法实现 (opens new window)

# c. 初始值

为了防止新的 key 由于 counter 为 0 导致直接被淘汰,Redis 会默认将 counter设置为 5。

# 4. 如何选择

软件工程没有银弹,我们不可能指望存在一个能完美适用于所有场景的内存淘汰策略。

在实际场景中,我们需要结合业务特点、数据量大小、数据的冷热……等多个维度来选择合适的淘汰策略。

比如:

  • 当使用 Redis 来缓存用户动态时,由于热门用户的动态相对于普通用户往往会被更高频的访问,因此我们可以选择基于 LRU 或者 LFU 算法的策略保证热点数据不会被轻易淘汰。
  • 当使用 Redis 缓存菜单树时,由于菜单树数据大部分情况下没有明确的热点区分,因此可以考虑使用随机淘汰策略平衡各个数据的访问频率。

当然,调整淘汰策略也只是优化方案的一种。条件允许的话,在特定情况下直接增加内存、将单机改为集群或者缓存预热同样可以带来显著的收益。

上次更新: 2023/11/06, 23:14:13
Redis如何实现到期删除的?
Redis字符串底层数据结构?

← Redis如何实现到期删除的? Redis字符串底层数据结构?→

Theme by Vdoing | Copyright © 2022-2023 马丁玩编程 | Apache2 License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式