Redis 淘汰策略详解：LRU 与 LFU 的博弈

一句话结论（30s）

Redis 淘汰策略的本质是「用近似换性能」：不做精确的 LRU/LFU，而是随机采样 + 候选比较。关键设计：因为真正的 LRU 需要每 key 两个指针的双向链表、内存开销大且单线程下高频移动节点有 CPU 代价，Redis 用 redisObject 里 24 位 lru 字段 + 随机采样 maxmemory-samples（默认 5）个 key 淘汰最差者，精度即可接近真实 LRU。权衡：LFU 进一步把 24 位复用为「高 16 位衰减时间 ldt + 低 8 位对数计数器 logc」，用对数增长 + 时间衰减，8 位既能区分冷热又能「忘记」历史热 key。

核心原理（2min）

内存达 maxmemory 时按 8 种策略淘汰：noeviction（默认，拒绝写入）、volatile-（只淘汰带过期时间）、allkeys-（所有 key）。近似 LRU 在每个 redisObject 的 24 位 lru 字段记录最后访问时间，淘汰时随机采样 N 个 key 挑 lru 最小者，Redis 7.0 加 16 位淘汰池小顶堆跨轮采样提高精度。LFU（4.0+）复用该 24 位：高 16 位 ldt 记录上次衰减分钟、低 8 位 logc 对数计数，每次访问以概率 1/(counter*lfu_log_factor+1) 递增，并按 lfu_decay_time 做时间衰减。生产常用 allkeys-lru/allkeys-lfu，最忌 allkeys-random。

底层深入（5-10min）

问题：Redis 内存满了怎么办？

Redis 是内存数据库。当 maxmemory 达到上限，再写入新数据时，必须做出选择：拒绝写入（报错），还是删除一些旧数据腾出空间。这个选择就是淘汰策略（Eviction Policy）。

Redis 提供了 8 种淘汰策略，分为三大类：不淘汰、仅淘汰带过期时间的 key、淘汰所有 key。

第一类：不淘汰 —— noeviction

默认策略。 当内存达到 maxmemory 上限，对任何可能增加内存的写操作（SET、LPUSH、SADD 等）直接返回错误，读操作和删除操作不受影响。

这是最保守的策略。生产环境中通常不建议用默认值，因为一旦内存满了服务就写不进去，等同于只读。

第二类：仅淘汰带过期时间的 key —— volatile-*

这组策略只看设置了 EXPIRE 的键，忽略永久键。包含 4 种：

volatile-ttl 很特殊——它不看使用频率，只看剩余生存时间。场景：缓存预热时，越接近过期时间的数据越没有继续缓存的必要。

第三类：淘汰所有 key —— allkeys-*

这组策略不区分 key 是否设置了过期时间，全局扫描。同样 4 种：

生产环境最常用：allkeys-lru。大部分缓存场景下，访问模式接近幂律分布，LRU 能精准淘汰冷数据、保留热数据。

Redis 的近似 LRU：为什么不用真正的双向链表？

经典 LRU 实现：HashMap + 双向链表。每次访问把节点移到链表头，淘汰时从链表尾移除。O(1) 时间、O(n) 空间。

但 Redis 不用。 原因：

1. 内存开销大。每个 key 都要维护 prev 和 next 两个指针，在内存型数据库中是巨大浪费。
2. Redis 已经是单线程。真正的 LRU 每次访问都要移动链表节点，高频 key 的链表操作本身就是 CPU 开销。

思考：为什么真正的 LRU 在 Redis 里行不通？两个成本一起看——空间上每个 key 要维护 prev/next 两个指针，内存型数据库里是巨大浪费；时间上 Redis 单线程，每次访问都要移动链表节点，高频 key 的链表操作本身就是 CPU 负担。所以 Redis 的取舍是：用「随机采样 + 挑最差」近似，省掉链表结构和每次访问的移动开销，精度却已足够接近真 LRU。

Redis 的近似 LRU 算法

Redis 在每个 redisObject 中维护一个 24 位的 lru 字段（LRU 时钟），记录该 key 的最后一次访问时间戳。

┌────────────────────────────────────┐
│ redisObject                        │
│  type | encoding | lru:24 | refcount | ptr  │
│                     ↑                │
│               最后访问时间戳          │
└────────────────────────────────────┘

淘汰时，Redis 不扫描全部 key，而是：

1. 随机抽取 maxmemory-samples（默认 5）个候选 key。
2. 在这 N 个候选中，挑出 lru 值最小（最久未访问）的那个淘汰。
3. 如果释放的内存还不够，重复步骤 1-2。

这个算法来自 Redis 作者 antirez 的一个洞察：对 LRU 来说，不需要在所有 key 中找绝对最久未访问的，在 N 个随机候选中找相对最久的，已经足够好。

思考：为什么「随机采样挑最差」就够，而不是全量扫？概率直觉——访问分布是幂律的（少数热 key 占绝大多数访问），随机采样 N 个几乎总能撞到冷 key；在采到的 key 里挑最旧的那个，误淘汰热 key 的概率随 N 增大急剧下降。antirez 的洞察就是「相对最旧」和「绝对最旧」在幂律分布下差别不大，用 N=5~10 就能逼近 99% 精度，还不用遍历全库。

算法的精度取决于 N：

• N=5：速度最快，但可能误淘汰一些刚被访问过的 key。
• N=10：精度接近真正的 LRU，但 CPU 消耗翻倍。

Redis 7.0 的改进：淘汰池（Eviction Pool）。维护一个最多 16 个候选 key 的小顶堆，每轮采样 N 个 key 放入池中，只淘汰池中最差的 key。这样既控制了采样开销，又提高了精度——因为候选池跨越多轮采样，覆盖范围更大。

24 位 LRU 时钟

lru 字段（24 bits）：
┌──────────────────────────────────────────────────────────┐
│        高 16 位：秒级时间戳（后 16 位）                    │
│        低  8 位：亚秒精度（每毫秒约增加 1）               │
└──────────────────────────────────────────────────────────┘

24 位能表示的最大值约 1677 万秒，约 194 天才会回绕。Redis 的 server.lruclock 每 100ms 由 serverCron 更新一次，访问 key 时将当前时钟值写入 redisObject.lru。

淘汰时比较两个 key 的 lru 值：值越小，距上次访问越久。即使发生时钟回绕（溢出归零），Redis 也能正确处理——因为比较的是相对时间差，不是绝对值。

LFU：从”最近用过”到”最近常用”

LRU 只看”最近一次访问”，对以下场景失效：

时间轴 ─────────────────────────────────────────────>

Key A: ████████████░░░░░░░░░░░░░░░░░░░░░░░░░  ← 1小时前高频，最近1小时没人用
Key B: ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██  ← 一直没人用，刚才访问了1次

LRU 会淘汰 A 保留 B，但显然 A 更重要。

LFU（Least Frequently Used）解决这个问题：不仅要看最近有没有被访问，还要看历史上被访问了多少次。

Redis LFU 的 24 位复用

Redis 在 4.0 引入了 LFU，巧妙复用了 redisObject 中原来用于 LRU 的 24 位字段：

lru 字段复用为 LFU 数据：
┌──────────────────────────┬────────────────────┐
│  高 16 位：ldt           │  低 8 位：logc      │
│  (last decrement time)   │  (logarithmic       │
│  上次衰减时间（分钟级）    │   counter）          │
│                          │  对数访问计数         │
└──────────────────────────┴────────────────────┘

高 16 位 ldt：记录该 key 上一次被”衰减”的 UNIX 时间戳（精确到分钟）。不是实际时钟，而是一个分钟级计数器。用于计算两次衰减之间的时间间隔。

低 8 位 logc：对数计数器。不是记录精确的访问次数，而是用对数增长的方式记录”大致访问频率”。8 位最大值为 255。

对数计数器的精妙之处

为什么用对数计数器而不是精确计数？因为 8 位最多存 255，但一个热 key 可能被访问几百万次。直接计数会溢出。

对数计数器的原理：

每次访问，计数器增加的概率 = 1 / (counter * lfu_log_factor + 1)

设 lfu_log_factor = 10：

这个设计的优雅之处在于：8 位足够区分冷热。 被访问 10 次（计数器约 3）和被访问 100 万次（计数器约 13）之间只差 10，但差别已经足够显著——淘汰时数值低的被优先淘汰。

思考：为什么计数器用「对数增长」而不是精确计数？因为只有 8 位、最大 255，热 key 可能被访问几百万次，直接计数必然溢出；对数增长让计数器以「数量级」而非「次数」增长——访问 10 次≈3、100 万次≈13，8 位就够拉开冷热差距。这本质是「用信息压缩换空间」：丢弃精确次数，保留「冷热量级」这个淘汰真正需要的信息。

lfu_log_factor 默认 10。调大：计数器增长更慢，冷热区分更精细；调小：计数器增长更快，但容易饱和。

时间衰减：让 LFU 也能”忘记”

纯 LFU 有一个致命问题：一个曾经火爆的 key（比如双十一大促页面），即使之后再也不被访问，计数器仍然很高，永远不会被淘汰。

思考：纯 LFU 的致命伤在哪？一个曾经爆火、现在没人用的 key，计数器永远居高不下、永远不会被淘汰——它「记住」了历史热度，却「忘不掉」当下的冷。所以 Redis 加时间衰减，让计数器随时间按 lfu_decay_time 递减，历史热度逐渐归零。这一加，LFU 就从「永远记住」变成「会遗忘」，恰好和 LRU 的「只看最近」形成互补，两个策略各自堵住对方的一个漏洞。

Redis LFU 通过时间衰减解决：

两次访问之间的间隔（分钟）= 当前分钟 - ldt

衰减后的计数器 ≈ logc * (衰减因子 ^ 间隔分钟)

每访问一次 key，先根据上次衰减时间计算衰减，再加上本次增长的计数。lfu_decay_time（默认 1 分钟）控制衰减速度：

• 设为 1：每分钟计数器减 1。
• 设为 0：不衰减，退化为纯 LFU。

LFU 淘汰流程

1. 随机采样 maxmemory-samples 个 key
2. 对每个 key：
   a. 计算两次衰减之间的时间间隔（当前分钟 - ldt）
   b. 按衰减因子衰减 logc
   c. 更新 ldt = 当前分钟
3. 选出 logc 最小的 key 淘汰
4. 如果释放内存不够，重复

生产环境选择建议

最不推荐 allkeys-random——除非你的访问分布完全均匀（现实中不存在）。

总结

Redis 的淘汰策略展现了 antirez 一贯的设计哲学：用近似换性能，用简单换可靠。 真正的 LRU 需要双向链表，Redis 用随机采样 + 小顶堆达到 99% 的精度；真正的 LFU 需要计数器，Redis 用 8 位对数计数器 + 时间衰减，在节省内存的同时区分冷热。

三个关键数字：maxmemory-samples 5（采样大小）、lfu_log_factor 10（对数增长系数）、lfu_decay_time 1（衰减时间）。理解这三个参数，就能精确控制 Redis 在内存压力和命中率之间的平衡。

章末提问

Q1：Redis 为什么不用真正的 LRU（HashMap + 双向链表），而用近似 LRU？

回答思路：结论——真 LRU 每个 key 两个指针、每次访问都要移动链表节点，内存和单线程 CPU 成本都高；Redis 用 24 位 lru 字段 + 随机采样挑最旧来近似。因为：内存型数据库里每 key 两个指针是巨大浪费，单线程下高频移动节点有 CPU 开销；近似 LRU 随机采样 N=5 就能逼近 99% 精度，省掉链表结构和移动成本，是「用近似换性能」。

Q2：LFU 是怎么复用 24 位字段的？对数计数器和时间衰减分别解决什么问题？

回答思路：结论——高 16 位 ldt 记录上次衰减时间、低 8 位 logc 做对数计数，两者配合。因为：8 位存不下精确访问次数，对数增长让计数器按数量级增长（访问 10 次≈3、100 万次≈13），8 位够区分冷热；但纯 LFU 会「记住历史忘不掉冷」，时间衰减让计数随时间递减，解决「曾经爆火永远不被淘汰」的问题。对应参数是 lfu_log_factor 和 lfu_decay_time。

Q3：noeviction、volatile-lru、allkeys-lru 有什么区别？生产环境怎么选？

回答思路：结论——noeviction 拒绝写入、volatile-* 只淘汰带过期时间的 key、allkeys-* 淘汰所有 key；生产最常用 allkeys-lru/allkeys-lfu。因为：大部分缓存场景访问呈幂律分布，LRU/LFU 能精准淘汰冷数据保留热数据；若部分 key 不能淘汰则用 volatile-lru；最忌 allkeys-random，因为真实访问几乎从不是均匀分布。再结合 maxmemory-samples、lfu_log_factor、lfu_decay_time 三个参数调精度。