Redis 的 LFU（Least Frequently Used，最不频繁使用）淘汰策略，是在 LRU 基础上做的“升级版”近似算法。它复用了对象头上同一个 24 位的 lru 字段，通过巧妙的编码和对数计数，用极小的内存代价，实现了对访问频率的近似跟踪。

下面从存储结构、计数器增减、淘汰决策到参数配置，逐一细究。

1. 24 位字段的位划分

每个 Redis 对象都有一个 lru 属性（24 位），在 LFU 模式下，它不再存放秒级时间戳，而是被拆成两段：

 高 16 位：最后衰减时间（Last Decay Time，单位：分钟）
 低  8 位：对数访问计数器（Logarithmic Counter，范围 0–255）
  • 高 16 位：存储的是 (server.unixtime / 60) & 0xFFFF，即当前分钟时间戳的低 16 位。最大表示约 45 天，足够覆盖淘汰场景，即使回绕，只要间隔不超过 45 天就可以正确计算差值。
  • 低 8 位：是一个 0–255 的频率计数器，但它不是访问次数的直接累加，而是经过对数平滑处理的“近似频率”。

当键被访问时，Redis 会调用 updateLFU()，先根据已流逝的时间衰减计数器，再概率性地递增计数器，最后把新的分钟时间戳和计数器重新编码写回 lru。

2. 计数器递增：对数增长

为了让 8 位计数器（0–255）既能表示低频也能区分高频，同时不让热门键快速打满，Redis 采用概率递增。

递增公式（源码级）：

double p = 1.0 / ((counter - LFU_INIT_VAL) * server.lfu_log_factor + 1);
if ((random() & 0xFFFF) < p * 0xFFFF) counter++;
  • LFU_INIT_VAL 默认为 5，新键的计数器初始值就是 5。
  • lfu_log_factor 是可配置的对数因子，默认 10。
  • 随着 counter 增大，p 会越来越小，递增越来越难。

举例（factor = 10 时，典型访问次数与计数器值）：

访问次数 近似计数器值
10 ~10
100 ~18
1000 ~27
10000 ~36
100000 ~46
1000000 ~55
1 千万 ~63
1 亿 ~73
10 亿 ~82
… …
理论最大值 255（极难达到）

可以看到，计数器初期增长较快，后期极其平缓，这样既能让新键快速摆脱“初始低分”，又能让极度热点的键在 8 位空间内被有效区分。

3. 计数器衰减：随时间线性递减

LFU 的核心是“频率”，但长时间不用的键频率应该降下去。衰减逻辑发生在每次访问键以及淘汰评估时。

衰减计算：

// 当前分钟时间戳（16 位）
now = LFUGetTimeInMinutes();      // (server.unixtime/60) & 65535
ldt = o->lru >> 8;               // 上次衰减时间
time_diff = now - ldt;           // 无符号差值（自动处理回绕）

num_periods = time_diff / server.lfu_decay_time;  // 衰减周期数
counter = counter - num_periods;  // 若负数则置为 0
  • lfu_decay_time 配置项，默认 1（分钟）。
  • 意思就是：每过 1 分钟，计数器减 1。
  • 如果 lfu_decay_time = 2，则每 2 分钟才减 1，衰减变慢。

因为这个衰减是“一次性追回历史流逝”，例如一个键的计数器现在是 20，最后访问时间是 10 分钟前，decay_time = 1，那么它一被访问（或淘汰评估时），计数器会直接减掉 10，变成 10。长期不碰的键计数会降至 0，非常容易被淘汰。

4. 新键的保护：初始值

新创建的键不是从 0 开始，而是直接赋予初始计数器 LFU_INIT_VAL（默认 5）。
这样做的好处是：避免新键一出生还没积累足够访问，就在抽样淘汰中被“冤杀”。

初始化时的字段编码：

o->lru = (LFUGetTimeInMinutes() << 8) | LFU_INIT_VAL;

5. 淘汰决策：抽样近似 LFU

Redis 不会维护全局频率排序（代价太大），而是采用抽样近似：

  1. 每次需要淘汰时，从数据库中随机抽取 maxmemory-samples 个键（默认 5）。
  2. 对每个样本键，调用 LFUDecrAndReturn(o) 获取衰减后的最新计数器值。
  3. 将样本按计数器从小到大排序，放入淘汰候选池。
  4. 最终从池中淘汰计数器最小的键。

因此，即使一个键的原始计数器很高，但只要它很久没被访问，衰减后的值会急剧缩小，在淘汰时依然会被优先移除。这正是“频率 + 时间”的综合效果。

6. 关键配置参数总结

配置项 默认值 含义
maxmemory-policy 无（需主动设置） 设置为 volatile-lfu（仅对设置了过期时间的键）或 allkeys-lfu（所有键）
lfu-log-factor 10 对数递增因子，越大增长越慢，计数器可区分的高频范围越广
lfu-decay-time 1（分钟） 衰减周期，每经过这个时间计数器减 1
maxmemory-samples 5 淘汰时的样本数，越大越接近全局 LFU，但 CPU 开销也越大

调优方向：

  • 如果访问频率差异巨大，可适当加大 lfu-log-factor（如 20），让 8 位计数器能区分更高频次的键。
  • 如果希望冷数据老化更快，减小 lfu-decay-time（甚至 0，但 0 意味着每访问一次就衰减到几乎 0，不推荐）；反之，想让热数据“保温”更久，可增大该值。
  • 提高 maxmemory-samples 可让淘汰更准确，建议不超过 10 以防明显性能下降。

7. 注意事项与局限

  • 回绕问题：16 位分钟时间戳约 45 天回绕一次。只要键的闲置时间小于 45 天（这在淘汰场景下几乎总是成立），无符号差值计算就是正确的。
  • 短时间内大量写入：新键初始值 5，若短时间涌入大量新键，它们可能因采样而互相淘汰，但因其初始值相同，又会退化为近似随机淘汰，可通过适当提高初始值（需修改源码）或结合其他策略缓解。
  • 计数器溢出：由于对数增长极慢，8 位几乎不可能打满，即使面对每秒百万次请求的热键，也需要天文数字的访问才会达到 255，实际生产无虞。
  • 版本差异：LFU 自 Redis 4.0 引入，机制至今保持稳定，上述细节适用于 4.0 至 7.x/8.x 等主流版本。

总结起来，Redis 的 LFU 通过对数计数 + 分钟级衰减 + 抽样淘汰，在常数的内存和 CPU 开销下，巧妙实现了近似频率淘汰，非常适合存在稳定热点、且不希望周期性扫描键被误淘汰的场景。