4. 常见缓存策略（二）：LFU 与 FIFO

上节课聊了 LRU，今天我们来看另外两位选手：LFU 和 FIFO。说实话，在很多高性能场景下，这俩策略的表现差距还挺大的。我个人习惯把 LFU 叫做“最勤快清除冷数据”，而 FIFO 更像“公平但不太聪明”。

4.1 LFU：谁用得少，谁先走

LFU（Least Frequently Used）的核心逻辑很简单：统计每个数据被访问的次数，访问次数最少的数据优先被淘汰。你想想看，如果一个数据很久才被碰一次，说明它大概率不是热点，清掉它合情合理。

我在项目中遇到过这样一个场景：一个全局配置缓存，某些配置项只在系统启动时读一次，后面再也不会访问。如果用 LRU，这些冷配置可能会因为偶尔的“顺序淘汰”残留在缓存里；而 LFU 能准确地把它们踢出去——因为访问次数始终是 1。

LFU 的实现要点

• 频次计数器：每个 key 绑定一个整数计数。每次命中+1。
• 最小频次维护：淘汰时找到最小计数的 key。如果有多个相同最小频次，需要辅助机制（比如 FIFO 或 LRU）来二次选择。
• 复杂度问题：纯 LFU 的实现通常需要 O(log n) 或 O(1) 的数据结构（比如最小堆 + 哈希表）。

来看一个极简的 LFU 伪代码

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_freq = {}    # key -> 访问次数
        self.key_to_value = {}   # key -> 值
        self.freq_to_keys = {}   # 频次 -> 对应keys集合
        self.min_freq = 0

    def get(self, key):
        if key not in self.key_to_value:
            return -1
        # 增加频次
        old_freq = self.key_to_freq[key]
        self.key_to_freq[key] = old_freq + 1
        # 移动 key 到新频次列表
        if old_freq == self.min_freq and len(self.freq_to_keys[old_freq]) == 0:
            self.min_freq += 1
        return self.key_to_value[key]

    def put(self, key, value):
        if self.capacity <= 0: return
        if key in self.key_to_value:
            self.key_to_value[key] = value
            self.get(key)  # 触发频次更新
            return
        if len(self.key_to_value) >= self.capacity:
            # 淘汰最小频次的一个key
            evict_key = next(iter(self.freq_to_keys[self.min_freq]))
            del self.key_to_value[evict_key]
            del self.key_to_freq[evict_key]
        # 插入新key，频次为1
        self.key_to_value[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1].add(key)
        self.min_freq = 1

LFU 的坑

• 新数据饿死问题：某个超高频 key 一旦累积了大量计数，新来的冷数据很难被访问到足够次数，结果长期占用缓存。实际场景下，可以对计数做“衰减”或“老化”。
• 内存占用：每个 key 额外存一个 32 位或 64 位整数，对于千万级缓存来说开销不小。

对于“新数据饿死”，我曾经在广告点击缓存中遇到过。一个用户行为 key 每秒被击打几十万次，计数飙到上亿，导致新加入的 key 永远不会被淘汰，缓存彻底撑爆。解决方案：给计数加一个软上限，比如超过 100 万时每命中一次衰减一半。

4.2 FIFO：公平到有点傻

FIFO（First In First Out）就是“先进先出”。哪个 key 最早进来，淘汰时就先踢哪个。说白了，它完全忽略访问频率和访问时间的新鲜度，只管排队顺序。

用 FIFO 做缓存策略，十有八九会出问题。你想想看，一个热点数据访问了 100 万次，它只是运气好排在前面，结果被最先淘汰；而一个冷数据因为来得晚，反而赖在缓存里一直不出。所以生产环境里，我几乎不会用纯 FIFO 做读写缓存。

FIFO 的适用场景

• 写缓冲（比如日志批处理）：数据只要保证顺序写入磁盘即可，无所谓热点不热点。
• 防抖缓存：某些重复请求需要去重，优先丢弃最早到达的那个。
• 简单的速率限制：比如 Nginx 的限流队列常用 FIFO，因为它实现代价最低。

4.3 LFU vs FIFO：一张表格说明白

下面这张图展示了两者的数据流动差异