Redis 中有哪些内存淘汰策略？

Redis 内存淘汰策略详解

【核心定义】

Redis 内存淘汰策略是指当 Redis 实例使用的内存达到 maxmemory 配置的阈值时，Redis 根据预设的算法自动删除部分键值对以释放内存空间，从而保证新数据能够写入的一系列机制。

【关键要点】

策略分类：Redis 内存淘汰策略主要分为两大类、八种具体策略，其核心区别在于淘汰的范围（所有键 vs 有过期时间的键）和标准（LRU、LFU、TTL、随机）。
不淘汰策略：noeviction 是默认策略，当内存不足时，新写入操作会报错，读操作不受影响，适用于对数据完整性要求极高的场景。
随机淘汰策略：包括 allkeys-random 和 volatile-random，随机选择键进行删除，实现简单但缺乏对数据价值的判断，可能误删热点数据。
LRU 近似策略：包括 allkeys-lru 和 volatile-lru，基于“最近最少使用”原则淘汰数据。Redis 采用近似 LRU 算法，通过随机采样（默认采样数 maxmemory-samples 为 5）并淘汰其中最久未使用的键，在性能和精度间取得平衡。
LFU 策略：包括 allkeys-lfu 和 volatile-lfu，基于“最不经常使用”原则淘汰数据。Redis 4.0 引入，通过统计访问频率（使用 Morris 计数器实现，访问频次衰减机制）来识别并淘汰冷数据，对热点数据的保护优于 LRU。
TTL 策略：volatile-ttl 从设置了过期时间的键中，优先淘汰剩余生存时间（TTL）最短的键，即最快过期的数据。

【深度推导/细节】

1. 近似 LRU 算法的实现与权衡

Redis 并未维护一个全局的、精确的 LRU 链表，因为这会带来巨大的内存和性能开销（每次访问都需更新链表）。其实现原理如下：

数据结构：每个 Redis 对象（redisObject）内部都有一个 lru 字段（24位），用于记录对象最后一次被访问的时间戳（单位为秒，精度为 1/255秒）。
淘汰过程：
- Step 1: 当需要淘汰时，从键空间中随机抽取 N（maxmemory-samples）个键。
- Step 2: 比较这 N 个键的 lru 时间戳，找出其中最久未被访问的键。
- Step 3: 将这个“候选键”放入一个淘汰池（大小为 N），然后重复上述抽样和比较过程。
- Step 4: 最终从淘汰池中选出 lru 值最小的键（即最久未访问）进行删除。
精度与性能：增大 N 值可以提高淘汰的准确性（更接近真实 LRU），但也会增加 CPU 消耗。通常 N=10 就能获得非常接近精确 LRU 的效果。

2. LFU 算法的实现细节

LFU 策略复用 redisObject.lru 字段，但将其拆分为两部分：

高 16 位：记录最近一次访问的时间戳（分钟级精度），用于衰减计数。
低 8 位：记录访问频率计数器（logc），范围 0-255。其增长和衰减逻辑是核心：
- 计数器增长：并非每次访问都 +1。计数器增长的概率公式为：P = 1.0 / (counter * lfu_log_factor + 1)。lfu_log_factor 可配置（默认 10），值越大，计数器增长越慢，越能区分高频访问。
- 计数器衰减：如果某个键长时间未被访问，其计数器需要减少。Redis 会计算当前时间与 lru 高16位记录时间的差值（单位：分钟），如果超过 lfu_decay_time（默认 1），则按差值衰减计数器。这保证了“旧热点”数据不会永久占据优势。

3. 策略选择与配置建议

allkeys-* vs volatile-*：如果所有数据都重要且没有设置 TTL，应选择 allkeys-* 策略。如果部分数据是缓存（有 TTL），部分数据是持久化（无 TTL），则选择 volatile-* 策略可以保护持久化数据不被淘汰。
LRU vs LFU：如果访问模式存在明显的“最近访问更可能被再次访问”的特点（如新闻 Feed），使用 LRU。如果访问模式是“频繁访问的键未来也更可能被访问”（如热门商品），使用 LFU 效果更好。
配置命令：通过 CONFIG SET maxmemory-policy <policy> 动态设置，或在 redis.conf 中配置 maxmemory-policy。

【关联/对比】

与 JVM GC 的类比：内存淘汰策略类似于 JVM 的垃圾回收，都是在资源（内存）不足时进行的清理动作。noeviction 类似 OutOfMemoryError；LRU/LFU 类似于分代 GC 中对不同“年龄”对象的处理。
与 Memcached 的对比：Memcached 默认使用 LRU 淘汰策略，且是全局统一的。Redis 提供了更丰富的策略选择，并且通过近似算法和 LFU 实现了更精细和高效的管理。
与数据库缓冲池的关联：数据库（如 MySQL InnoDB）的缓冲池（Buffer Pool）也使用 LRU 及其变种（如改进型 LRU）来管理内存页，其核心思想与 Redis 一致，都是为了在有限内存下最大化缓存命中率。

『面试官追问』

LRU 和 LFU 在算法思想和适用场景上有什么区别？
- LRU 关注时间局部性，认为最近被访问的数据未来更可能被访问。适用于访问模式随时间快速变化的场景（如社交媒体的最新内容）。
- LFU 关注访问频率，认为历史访问次数多的数据未来更可能被访问。适用于存在稳定热点数据的场景（如电商的热门商品、经典文章）。LFU 的缺点是可能“历史包袱”重，旧的热点数据长期占据内存。
为什么 Redis 使用近似 LRU 而不是精确 LRU？
- 性能考量：精确 LRU 需要维护全局链表，每次数据访问都要进行链表移动操作，时间复杂度为 O(1) 但常数项大，对高性能的 Redis 来说是显著开销。
- 内存考量：维护链表需要额外的内存指针（每个节点前后指针）。
- 效果权衡：实践表明，通过适当的随机采样，近似 LRU 在效果上非常接近精确 LRU，而性能开销和内存占用却小得多，这是一种典型的工程上的权衡（Trade-off）。
如何监控和优化内存淘汰的效果？
- 通过 INFO stats 命令查看 evicted_keys 指标，了解淘汰发生的频率。如果淘汰频繁，应考虑扩容或优化数据结构。
- 通过 OBJECT freq <key> 命令（Redis 4.0+）可以查看某个键的 LFU 访问频率。
- 调整 maxmemory-samples、lfu-log-factor、lfu-decay-time 等参数来优化 LRU/LFU 算法的行为。
volatile-lru 和 allkeys-lru 在实现上有什么区别？
- 两者的算法逻辑完全一致，区别仅在于筛选候选键的范围。
- volatile-lru 只从设置了过期时间（TTL）的键的集合中进行随机采样和淘汰。
- allkeys-lru 从所有的键的集合中进行随机采样和淘汰。这是通过底层不同的键空间迭代器实现的。

【版本差异】

Redis 4.0 之前：支持 noeviction, allkeys-lru, volatile-lru, allkeys-random, volatile-random, volatile-ttl 这六种策略。
Redis 4.0：引入了基于 LFU 的两种新策略：allkeys-lfu 和 volatile-lfu，为缓存场景提供了更优的选择。
后续版本：策略种类保持稳定，主要在对 LFU 算法的调优参数（如 lfu-log-factor）和监控命令上有所增强。

# Redis 中有哪些内存淘汰策略？