2024.06.08 更新

补充了思维导图：

image

过期删除策略

Redis 实际上使用了一个哈希表来记录每个 key 的过期时间

在给 Redis 的 key 设置 TTL，实际上就是新增（修改）哈希表中的数据

image

在获取 key 的 value 时，首先要先判断 key 是否过期，这点可以通过读取哈希表的数据实现

那什么时候删除过期的 key 呢？

容易想到三种方案：

  • 直接删除：可以给每个 key 设置一个回调，过期自动删除（成本高）
  • 懒删除：key 过期了不删除，而是等到访问时，判断过期再删除，存在数据永远删不掉的可能，造成内存浪费
  • 周期删除：开一个后台线程，定期扫描过期的 key，删除

Redis 采取了 懒删除 + 周期删除 结合的策略

懒删除的过程与上文描述一致，而周期删除用于弥补懒删除无法完整删除数据的问题

Redis 实现的周期删除有两种模式：

  • SLOW 模式
  • FAST 模式

SLOW 模式规则：

  • 执行频率受 server.hz 影响，默认为 10，即每秒执行 10 次，每个执行周期 100ms
  • 执行清理耗时不超过一次执行周期的 25%
  • 抽取 20 个 key 判断是否过期
  • 如果没达到时间上限（25ms） 并且过期 key 比例大于 10%，再进行一次抽样，否则结束

FAST 模式规则（过期 key 比例小于 10%不执行）：

  • 执行频率受 beforesleep（调用频率影响，但两次 FAST 模式间隔不低于 2ms
  • 执行清理耗时不超过 1ms
  • 抽取 20 个 key 判断是否过期
  • 如果没达到时间上限（1ms） 并且过期 key 比例大于 10%，再进行一次抽样，否则结束

周期删除的时机：

  • Redis 会设置一个定时任务，模式为 SLOW
  • 每次事件循环前（epoll_wait 前）执行 beforeSleep 函数，内部会执行过期 key 清理，模式为 FAST（避免因清理时间过长，导致主线程阻塞）

内存淘汰策略

我们可以给 Redis Server 设置一个可使用内存的上限（通过 maxmemory ）

  • 32 位 OS，默认上限为 3G
  • 64 位 OS，默认没有上限

超出内存使用上限，Redis 就会采取内存淘汰策略，来淘汰掉一些 key，回收内存

内存淘汰策略大致分为两类：

  • 不淘汰（noeviction）：不淘汰任何 key，但是 内存满时不允许写入新数据，默认就是这种策略。
  • 淘汰策略：内存满后，采用内存淘汰策略，来淘汰掉一些 key，回收内存

而淘汰的范围进一步分为两类：

  • 在设置了 TTL 的 key 淘汰，以 volatile 为前缀
  • 在所有 key 中淘汰，以 all 为前缀

淘汰策略又进一步分为三类：

  • 随机淘汰
  • LRU
  • LFU

随机淘汰这种方式不推荐使用

LRU 和 LFU 都依赖于 RedisObject 的 lru 属性

Redis 实现的 LRU 与常规的 LRU 不太一样：

  • 不维护 LRU 链表（节省内存空间）
  • 在淘汰的每一轮，随机选 5 个（默认值），然后淘汰最久没有访问的

但 LRU 存在一个问题：如果一个 key 是个热点 key，但仅仅是最近还没有访问，LRU 算法有可能将这个热点 key 淘汰了

于是 4.0 版本引入了 LFU 算法

不同于 LRU 算法，LFU 是淘汰使用频率最低的 key

使用 LFU 算法，lru 字段记录的格式如下：

image

图片来自小林 Coding

  • 高 16 位记录 key 上一次访问的时间戳
  • 低 8 位记录 key 的「逻辑访问次数」

LFU 的访问次数之所以叫做逻辑访问次数，是因为并不是每次 key 被访问都计数，而是通过运算：

  1. 生成 0~1 之间的随机数 R
  2. 计算 1 / (旧次数 * lfu_log_factor+1)，记录为 P，lfu_log_factor 默认为 10
  3. 如果 R < P，则计数器 + 1，且最大不超过 255
  4. 访问次数会随时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟（默认 1），计数器 - 1

可以看出，随着实际访问次数的增加，逻辑访问次数也会增加，但增加的幅度会越来越小（P 越来越小，R < P 的概率越来越小），最多为 255