Skip to content

redis LFU策略是如何实现的

Redis 从 4.0 版本开始引入 LFU 淘汰策略，旨在解决 LRU (Least Recently Used, 最近最少使用) 策略无法有效处理“偶发性批量访问”场景的缺陷。LFU 的核心思想是，淘汰近期最不常被访问的数据，它认为过去一段时间内访问频率高的数据，在未来被访问的概率也更高。

为了在不引入额外数据结构、节省内存的前提下实现 LFU，Redis 复用了每个对象头（redisObject）中原用于 LRU 的 24-bit lru 字段。它巧妙地将这 24 位拆分为两部分，以同时记录访问时间和访问频率。

lru 字段的再分配

在 LFU 模式下，24 位的 lru 字段被划分为：

  • 高 16 位：ldt (Last Decrement Time)，用于记录计数器最后一次衰减的时间。
  • 低 8 位：logc (Logistic Counter)，用于记录一个基于对数增长的访问频率计数器。

关键组成部分

1. ldt (Last Decrement Time) - 记录时间

ldt 占据了高 16 位，它存储的不是一个标准的 Unix 时间戳，而是 Unix 时间戳（秒）除以 60 后的分钟数，再对 2^16 (65535) 取模的结果。

  • 为什么是分钟？ 这样做可以大大延长 16 位所能表示的时间范围。16 位的最大值为 65535，如果以分钟为单位，大约可以表示 65535 分钟，约等于 45.5 天。这意味着时间戳大约每 45.5 天会发生一次“折返”（从 65535 回到 0）。
  • 时间差计算：当需要计算距离上次衰减过去了多久时，Redis 会用当前的分钟时间戳减去 ldt。为了处理“折返”问题，代码会判断当前时间戳是否小于 ldt，如果小于，则认为发生了一次折返，计算时会加上 65535。

2. logc (Logistic Counter) - 记录频率

logc 使用低 8 位，其最大值只能到 255。显然，它无法直接记录一个 key 的真实访问总次数。因此，Redis 采用了一种巧妙的对数增长方式来管理这个计数器。

初始值 每个新创建的 key，其 logc 初始值被设置为 LFU_INIT_VAL（默认为 5）。这样做是为了让新加入的数据有一定的“保护期”，不会因为初始频率为 0 而立即被淘汰池中的老数据替换掉，这给予了新数据“表现”的机会。

计数器增长 (LFULogIncr) 当一个 key 被访问时，它的 logc 计数器并不会简单地加 1，而是根据一个概率模型来决定是否增加：

  1. 最大值限制：如果计数器已经达到 255，则不再增加。
  2. 概率计算：增长的概率 p 是通过一个公式计算得出的：p = 1.0 / ( (counter - LFU_INIT_VAL) * lfu-log-factor + 1 )。
  3. 随机决策：系统会生成一个 0 到 1 之间的随机数 r，只有当 r < p 时，计数器才会加 1。

从这个公式可以看出： * counter 值越小，p 的值越大，计数器增长的概率就越高。 * lfu-log-factor：这个可配置的“对数因子”（默认为 10）起到了关键的调节作用。因子越大，p 的值越小，计数器增长得就越慢。这意味着你需要更多次的访问才能让计数器增加。

这种设计使得 logc 的增长呈现出一种对数曲线的形态：在访问初期，计数器增长较快；但随着访问频率的提高，需要更多的访问次数才能让计数器再增加 1。这有效地将一个可能无限大的访问次数映射到了 0-255 这个有限的区间内。

计数器衰减 (LFUDecrAndReturn) 如果一个 key 长时间不被访问，它的热度应该随时间下降。logc 的衰减机制正是为此设计的：

  1. 计算衰减周期：首先，通过 ldt 计算出距离上次衰减过去了多少分钟 (elapsed_minutes)。
  2. 计算衰减值：然后用 elapsed_minutes 除以可配置的 lfu-decay-time（衰减时间，单位分钟，默认为 1），得出需要衰减的“周期数” (num_periods)。这个值就是 logc 需要减去的数值。
  3. 执行衰减：将当前的 logc 值减去 num_periods。如果 num_periods 大于 logc，则 logc 直接变为 0。

这个机制意味着，lfu-decay-time 的值越大，计数器衰减得越慢。如果设置为 0，则表示不进行衰减。

3. 淘汰池 (Eviction Pool)

和 LRU 一样，当 Redis 内存达到 maxmemory 限制需要进行数据淘汰时，它并不会遍历所有的 key 去寻找最不频繁使用的那一个（因为性能开销太大）。

取而代之的是，Redis 会根据配置的策略（如 allkeys-lfu 或 volatile-lfu）进行 随机采样。它会随机选出若干个 key（默认为 5 个），将它们放入一个大小固定的“淘汰池”中。淘汰池中的 key 会根据其“热度”（即 logc 的值）进行排序。

每次需要淘汰数据时，Redis 就会从淘汰池中选择 logc 值最小的那个 key 进行淘汰。同时，新的采样候选 key 会不断地被放入淘汰池，并挤出池中热度较高的 key，从而维持池中始终保留着当前已采样范围内最“冷”的数据。