作为开发者，我们经常听到这样一句话：“计算机科学中的任何问题都可以通过增加一个中间层来解决”。而在现代系统设计中，这个“中间层”往往就是缓存。缓存极大地提升了数据访问速度，但同时也引入了一个棘手的问题：当空间有限时，我们该如何决定保留哪些数据，丢弃哪些数据？
这就是我们今天要深入探讨的核心话题——缓存淘汰策略。在这篇文章中，我们将不仅学习这些算法的理论基础，还会通过实际的代码示例和架构设计场景，看看如何为我们的系统选择最合适的策略。无论你是在构建高并发的电商系统，还是在优化数据库查询，理解这些策略都将是你技术武库中的重要一环。
什么是缓存淘汰？
想象一下，你的书桌只有那么大，你把常用的书放在桌面上（缓存），把不常用的书放在书架上（数据库）。当你的桌面被堆满，而你需要拿一本新书上来时，你必须决定把桌面上哪本书放回书架。这个过程，在计算机科学中，就是缓存淘汰。
它是当缓存达到容量上限时，为了给新数据腾出空间而移除现有数据的过程。一个优秀的淘汰策略，能确保我们保留的总是最“有价值”的数据，从而最大限度地提高缓存的命中率，减少对慢速存储（如数据库或磁盘）的访问次数。
1. 最近最少使用 (LRU)
LRU（Least Recently Used）是业界最常见、也是面试中最常被问到的策略。它的核心逻辑非常符合直觉：如果一个数据在最近一段时间没有被访问到，那么它在将来被访问的可能性也很小。
#### 它是如何工作的？
当缓存已满且需要插入新数据时，LRU 会查找距离上一次访问时间最久的那条数据并将其移除。为了实现这一点，我们需要维护一个访问顺序的列表。
#### 实战代码示例
让我们通过一段 Python 代码来实现一个简单的 LRU 缓存。为了让你更清楚地理解其内部机制，我将展示基于 OrderedDict 的实现方式，这比普通的字典操作更直观：
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
"""
初始化 LRU 缓存
:param capacity: 缓存的最大容量
"""
self.cache = OrderedDict() # 有序字典，用于记录访问顺序
self.capacity = capacity
def get(self, key: int) -> int:
"""
获取数据：如果存在，将其移动到末尾（表示最近使用）
:param key: 查询的键
:return: 对应的值，如果不存在返回 -1
"""
if key not in self.cache:
return -1
# 这是一个关键操作：将访问的元素移动到 OrderedDict 的末尾
# 在 OrderedDict 中，末尾代表“最近使用”，头部代表“最久未使用”
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
"""
写入数据：如果已存在则更新值并移动到末尾；如果不存在则插入
:param key: 键
:param value: 值
"""
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
# 检查是否超出容量
if len(self.cache) > self.capacity:
# popitem(last=False) 会弹出并移除头部的元素（即最久未使用的）
self.cache.popitem(last=False)
# --- 测试我们的 LRU ---
# 场景：容量为 3 的缓存
print("--- LRU 缓存演示 ---")
lru_cache = LRUCache(3)
lru_cache.put(1, ‘A‘) # 缓存: {1: A}
lru_cache.put(2, ‘B‘) # 缓存: {1: A, 2: B}
lru_cache.put(3, ‘C‘) # 缓存: {1: A, 2: B, 3: C}
print(f"当前缓存内容: {list(lru_cache.cache.items())}")
lru_cache.put(4, ‘D‘) # 缓存已满，移除最久未使用的 Key 1。缓存: {2: B, 3: C, 4: D}
print(f"插入 D 后的缓存: {list(lru_cache.cache.items())}")
print(f"获取 Key 2 (值为: {lru_cache.get(2)})") # 访问 Key 2，它变为最近使用。缓存顺序: {3: C, 4: D, 2: B}
lru_cache.put(5, ‘E‘) # 缓存已满，移除最久未使用的 Key 3。缓存: {4: D, 2: B, 5: E}
print(f"插入 E 后的缓存: {list(lru_cache.cache.items())}")
#### LRU 的优劣势与场景
优势：
- 符合时间局部性原理： 对于具有连续访问模式的应用（如用户浏览网页、循环读取列表数据）效果极佳。
- 实现成熟： 许多语言和框架都有内置的 LRU 实现（如 Java 的 INLINECODE8fee9892，Redis 的 INLINECODE7b019f7f 配置）。
劣势：
- 内存开销： 需要额外的空间来存储访问顺序或时间戳。
- 偶发失效： 如果突然发生一次全量扫描（例如备份数据库），可能会将真正的“热点数据”冲刷掉，导致缓存命中率骤降（即 Cache Pollution 问题）。
最佳应用场景：
- Web 网页代理缓存： 用户倾向于在短时间内多次访问相同的页面。
- 数据库内存缓冲池： InnoDB 引擎就对 LRU 进行了优化以处理全表扫描。
—
2. 最不经常使用 (LFU)
LFU（Least Frequently Used）采取了另一种视角。它不再关心“你最后一次用是什么时候”，而是关心“你一共用了多少次”。
#### 核心逻辑
LFU 假设：如果一个数据在历史上被访问的频率很低，那么它在未来被访问的概率也很低。当缓存满时，LFU 会优先淘汰那些访问频率最低的数据项。
#### 实战代码示例
实现 LFU 比实现 LRU 要复杂得多，因为我们不仅要记录访问的顺序，还要记录每个 Key 的访问频次。我们需要两个数据结构：一个哈希表存储缓存内容，另一个哈希表存储每个频次对应的 Key 列表。
import collections
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0 # 当前记录到的最小频次
# key 到 {value, freq} 的映射
self.key_to_val_freq = {}
# freq 到 key 列表的映射（使用普通 dict + 记录访问顺序的辅助结构）
# 为了简化实现并保持 O(1)，我们可以维护 freq 到 OrderedDict 的映射
self.freq_to_keys = collections.defaultdict(collections.OrderedDict)
def get(self, key: int) -> int:
if key not in self.key_to_val_freq:
return -1
val, freq = self.key_to_val_freq[key]
# 增加频次
self._increment_freq(key, val, freq)
return val
def put(self, key: int, value: int) -> None:
if self.capacity = self.capacity:
# 从最小频次的列表中弹出最久未使用的那个 Key
# popitem(last=False) 弹出头部（最旧的）
evicted_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
del self.key_to_val_freq[evicted_key]
# 添加新数据，频次初始化为 1
self.key_to_val_freq[key] = (value, 1)
self.freq_to_keys[1][key] = None # 占位符，这里只需要 Key
self.min_freq = 1 # 新数据的频次肯定是 1
def _increment_freq(self, key, value, old_freq):
"""
辅助方法：更新 Key 的频次，并调整它在不同频次列表中的位置
"""
# 先从旧频次列表中移除
del self.freq_to_keys[old_freq][key]
# 如果旧频次列表为空，且旧频次恰好是最小频次，则更新最小频次
if not self.freq_to_keys[old_freq]:
if self.min_freq == old_freq:
self.min_freq += 1
# 加入新频次列表
new_freq = old_freq + 1
self.key_to_val_freq[key] = (value, new_freq)
self.freq_to_keys[new_freq][key] = None # 将 key 移到新频次列表的末尾
# --- 测试 LFU ---
print("
--- LFU 缓存演示 ---")
lfu_cache = LFUCache(2)
lfu_cache.put(1, ‘A‘) # Freq: 1
lfu_cache.put(2, ‘B‘) # Freq: 1
lfu_cache.get(1) # Key 1 Freq 变为: 2, Key 2 Freq 仍为: 1
lfu_cache.put(3, ‘C‘) # 缓存满，淘汰 Freq 最低的 Key 2。
print(f"淘汰 Key 2 后，Key 1 仍在: {lfu_cache.get(1)}")
print(f"尝试获取 Key 2 (已被淘汰): {lfu_cache.get(2)}")
#### LFU 的适用场景
LFU 非常适合那些访问频率差异明显的场景。例如，在社交媒体平台上，某些热点新闻（高频）会长期占据流量，而大多数旧闻（低频）则迅速冷却。在这种情况下，LFU 能比 LRU 更好地保护热点数据不被冷数据“挤”出去。
—
3. 先进先出 (FIFO)
这是最简单的策略，就像排队买票一样，谁先来，谁先走。
#### 实现逻辑
FIFO 不关心数据是否被访问过，只关心它进来的时间。当缓存满时，直接移除最早进入缓存的那条数据。
class FIFOCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
# 注意：FIFO 在 get 时不调整顺序
return self.cache.get(key, -1)
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 即使是更新操作，在简单 FIFO 中通常也视作“写入”
# 这里我们选择直接覆盖，不改变它的位置（除非特殊实现）
# 为了演示纯粹的 FIFO（覆盖值不重置排队位置），我们这样处理：
self.cache.pop(key) # 先移除旧的，再插入新的（这会重置位置）
self.cache[key] = value
else:
if len(self.cache) >= self.capacity:
# 弹出最旧的一个
self.cache.popitem(last=False)
self.cache[key] = value
# --- 测试 FIFO ---
print("
--- FIFO 缓存演示 ---")
fifo = FIFOCache(3)
fifo.put(1, ‘A‘); fifo.put(2, ‘B‘); fifo.put(3, ‘C‘) # 队列: A -> B -> C
print(f"当前队列: {list(fifo.cache.keys())}")
fifo.get(1) # 获取 A，但在 FIFO 中 A 依然是最早进入的
fifo.put(4, ‘D‘) # 淘汰 A
print(f"插入 D 后，Key 1 是否还存在? {fifo.get(1)}") # 返回 -1
#### 场景分析
FIFO 适用于那些对访问模式不敏感，或者数据生命周期非常固定的场景。比如，如果你在做一个消息队列的滑动窗口，或者仅仅是一个简单的环形缓冲区，FIFO 是最高效的选择。然而，在典型的应用级缓存中，由于它容易淘汰热点数据（如果热点数据恰好是第一批进来的），性能通常不如 LRU。
—
4. 随机替换
正如其名，当缓存满时，随机选择一个槽位进行替换。你可能觉得这听起来很儿戏，但在某些特定的重负载场景下，它却有一席之地。
#### 为什么要随机？
在极高并发的系统中，维护 LRU 或 LFU 的链表锁竞争可能会成为性能瓶颈。随机算法不需要维护任何元数据（时间戳、计数器），几乎没有任何锁开销。
import random
class RandomCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key: int) -> int:
return self.cache.get(key, -1)
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key] = value
return
if len(self.cache) >= self.capacity:
# 随机选择一个 Key 进行删除
evict_key = random.choice(list(self.cache.keys()))
del self.cache[evict_key]
self.cache[key] = value
场景： Redis 在某些模式下曾使用随机淘汰作为策略之一。当数据访问模式是完全随机的，没有任何局部性特征时，Random 可能会做得和 LRU 一样好，而且实现成本低得多。
—
实战见解与最佳实践
在理解了这四种基本策略后，你在实际系统设计中该如何选择？作为过来人，我有几点建议分享给你：
- 没有银弹： 不要指望一种策略打天下。你应该根据业务的数据访问模式来决定。
- 避免 Cache Stampede（缓存击穿）： 当一个热点 Key 被 LRU 淘汰的瞬间，如果瞬间有大量请求进来，可能会同时击穿到数据库。解决方案是使用 锁 或者 逻辑过期 策略，而不是单纯依赖淘汰算法。
- 监控命中率： 在上线任何缓存策略后，务必监控
Hit Rate（命中率）。如果你发现命中率一直上不去，可能是因为你的淘汰策略选错了，或者是缓存容量设得太小。 - 成本考量： LRU/LFU 需要额外的内存开销来维护元数据。如果你的 Key/Value 特别小（比如只是存一个 ID），那么元数据的开销占比就会很高，此时考虑简单的 FIFO 或 TinyLFU（一种基于频率的近似算法）可能更划算。
总结
在这篇文章中，我们通过代码和理论深入探讨了四种核心的缓存淘汰策略：LRU、LFU、FIFO 和 Random。
- LRU 是通用性最强的首选，利用时间局部性。
- LFU 适合访问频率极度不均的长尾场景。
- FIFO 简单高效，适合对顺序敏感或对一致性要求极高的场景。
- Random 是极端性能需求下的备选方案。
希望这篇文章能帮助你更好地理解系统设计中的这一关键环节。下次当你配置 Redis 或设计自己的本地缓存时，你会更有信心地做出选择。动手试试上面的代码吧，感受一下不同算法处理数据的节奏，你会有更深的体会。