常见的缓存淘汰策略有哪些？LRU 和 LFU 有什么区别？

简化版

缓存内存有限，装满后要淘汰一些数据腾地方，这就是淘汰策略。三种经典：FIFO（先进先出，淘汰最早放入的）、LRU（Least Recently Used，淘汰最久没被访问的，看「最近有没有用过」）、LFU（Least Frequently Used，淘汰访问次数最少的，看「用得频不频」）。LRU 关注时间（最近性），LFU 关注频率（热度）。Redis 提供了 8 种淘汰策略（如 allkeys-lru、allkeys-lfu、volatile-ttl 等）供配置。

详细版

三种经典策略对比：

策略	淘汰依据	淘汰谁	缺点
FIFO	进入时间	最早放入的	不管冷热，可能淘汰掉常用数据
LRU	最近访问时间	最久未被访问的	偶发的批量访问会冲掉真热点
LFU	访问频率	访问次数最少的	历史高频但现在冷的数据难淘汰

LRU 的经典实现：哈希表 + 双向链表。哈希表 O(1) 定位节点，双向链表维护访问顺序（每次访问把节点移到头部，淘汰时删尾部）。

Redis 的 8 种淘汰策略：

noeviction：不淘汰，内存满写入报错（默认）。
allkeys-lru / volatile-lru：对所有 key / 只对设了过期时间的 key 用 LRU。
allkeys-lfu / volatile-lfu：LFU（Redis 4.0+）。
allkeys-random / volatile-random：随机淘汰。
volatile-ttl：淘汰剩余存活时间最短的。

完整版教学

一、为什么需要淘汰策略

缓存放在内存里，内存容量有限（也昂贵），不可能无限存。当缓存写满、又要放新数据时，必须踢掉一些旧数据腾出空间。踢谁？这就是淘汰策略要回答的。好的策略应该尽量踢掉「以后不太会用」的数据，保留「以后还会频繁用」的数据，从而维持高命中率。但「以后会不会用」无法预知，所以各策略用不同的「历史规律」去近似预测。

二、FIFO：先进先出，最简单也最粗糙

FIFO（First In First Out） 按数据进入缓存的先后顺序淘汰，最早进来的最先被踢。实现简单（一个队列即可）。但它的问题是完全不考虑数据冷热——一个很早放入但一直被高频访问的热点数据，会仅仅因为「进来得早」被淘汰，命中率差。所以实际很少单独用 FIFO 做缓存淘汰。

三、LRU：淘汰「最久没用过的」，赌最近性

LRU（Least Recently Used，最近最少使用） 的假设是：最近被访问过的数据，接下来也更可能被访问（时间局部性）。所以它淘汰最久没有被访问的数据。

每次访问一个数据（读或写），就把它标记为「最新使用」。
淘汰时，踢掉「最久未被使用」的那个。

经典实现：哈希表 + 双向链表（LeetCode 146 就考这个）：

双向链表按访问时间排序：头部是最近用的，尾部是最久没用的。
哈希表存 key → 链表节点，实现 O(1) 查找。
访问/更新：把对应节点移到链表头部。
淘汰：删除链表尾部节点（最久未用），O(1)。

LRU 的缺点：偶发的批量扫描会污染缓存。比如一次性遍历大量冷数据（如全表扫描），会把这些一次性数据全塞进缓存头部，把真正的热点挤到尾部淘汰掉。

四、LFU：淘汰「用得最少的」，赌频率

LFU（Least Frequently Used，最不经常使用） 的假设是：访问频率高的数据更有价值。它淘汰访问次数最少的数据，给每个数据维护一个访问计数器。

LFU 解决了 LRU 的批量扫描污染问题——一次性访问的冷数据计数低，很快被淘汰，不会挤掉高频热点。但 LFU 也有缺点：

历史包袱：某个数据过去访问量巨大、现在已经不热了，但因为历史计数高，迟迟淘汰不掉（需要计数衰减机制来缓解，Redis 的 LFU 就带衰减）。
新数据劣势：刚进来的数据计数低，还没来得及积累访问就可能被淘汰。

LRU vs LFU 简明区分：：LRU 看「最近有没有用」（时间维度），LFU 看「一共用了多少次」（频率维度）。

五、Redis 的淘汰策略配置

Redis 通过 maxmemory-policy 配置，提供 8 种策略，可分两个维度理解：

维度一：对哪些 key 生效

allkeys-*：对所有 key。
volatile-*：只对设置了过期时间的 key（没设过期的永不淘汰）。

维度二：用什么算法

-lru：LRU（Redis 的 LRU 是近似 LRU——不维护完整链表，而是随机采样几个 key 淘汰其中最久未用的，省内存）。
-lfu：LFU（4.0+）。
-random：随机。
volatile-ttl：淘汰剩余存活时间最短的（快过期的先走）。

外加 noeviction（默认）：不淘汰，内存满时写操作直接报错。

注意：Redis 的 LRU/LFU 是近似算法（采样实现），不是严格的全局 LRU/LFU，这是为了在海量 key 下节省维护成本，用少量精度换性能。

六、常见误区与追问

考点	正确口径
LRU	淘汰最近最少使用，关注时间近远
LFU	淘汰访问频率最低，关注次数
TTL	按过期时间失效，不等同于内存淘汰

LRU example:
access A,B,C,A
cache full, insert D -> evict B

LFU example:
A count=10, B count=1, C count=2
insert D -> evict B

LRU 看“最近有没有用”，LFU 看“用得多不多”，两者适合的热点形态不同。

误区：LRU 和 LFU 都是按过期时间淘汰。 它们是内存不足时的淘汰策略，TTL 是键的生命周期。
误区：LRU 一定识别真正热点。 偶发批量扫描会污染 LRU，让最近访问但不常用的数据挤掉长期热点。
误区：LFU 没有历史包袱。 历史高频 key 可能长期占据缓存，需要衰减机制。
追问：Redis 有哪些近似淘汰策略？ 如 allkeys-lru、volatile-lru、allkeys-lfu、volatile-ttl、random、noeviction 等。
追问：什么时候选 LRU？ 访问局部性强、最近访问更可能再次访问时适合 LRU。
追问：什么时候选 LFU？ 热点稳定且希望抵抗偶发扫描污染时 LFU 更合适。

七、加强记忆

缓存淘汰策略 = 内存满时决定踢掉谁。三经典：FIFO（按进入顺序踢，不看冷热、最粗糙）、LRU（踢最久没被访问的，赌「最近用过的还会用」，经典实现 哈希表+双向链表 O(1)，缺点是批量扫描污染缓存）、LFU（踢访问次数最少的，赌「高频更有价值」，缺点是历史高频包袱、新数据劣势）。LRU 看时间（最近性）、LFU 看频率（热度）。Redis 提供 8 种（allkeys/volatile × lru/lfu/random/ttl + noeviction），且 LRU/LFU 是采样近似实现。核心区分：LRU 问「多久没用」，LFU 问「用了几次」。

简化版

详细版