3. 缓存淘汰策略深度解析：LRU、LFU、FIFO、ARC、2Q，以及它们在向量场景下的适配性分析

缓存淘汰策略，说白了就是当缓存满了，你决定把谁踢出去的问题。别小看这个决策，选错了，你的缓存命中率可能直接腰斩。我在向量检索项目里见过太多次因为淘汰策略不当，导致整个系统响应时间从 5ms 飙升到 200ms 的惨案。

今天咱们就把主流的几种策略掰开揉碎，看看它们各自的脾气秉性，以及在向量场景下到底谁更靠谱。

3.1 五大经典淘汰策略速览

先给个全景图，让你心里有个谱。我习惯把淘汰策略分成两派：一派是「只看时间」，一派是「既看时间又看频率」。

策略	核心思想	数据结构	时间复杂度	向量场景适配度
FIFO	谁先进来，谁先出去	队列	O(1)	★☆☆☆☆
LRU	最近最少使用	双向链表 + 哈希表	O(1)	★★★☆☆
LFU	最不经常使用	哈希表 + 最小堆	O(log n)	★★☆☆☆
2Q	两次机会队列	三个队列	O(1)	★★★★☆
ARC	自适应替换缓存	四个链表	O(1)	★★★★★

3.2 FIFO：简单但粗暴

FIFO（先进先出）是最朴素的策略。它维护一个队列，新数据从队尾入，淘汰时从队头出。实现起来确实简单，但问题也很明显——它完全不考虑数据的访问频率和最近访问时间。

举个例子，你有一个高频访问的向量，只要它待的时间够长，FIFO 照样会把它踢出去。这在向量检索场景下几乎是灾难性的。我曾经在一个实验里用 FIFO 做向量缓存，结果命中率只有 12%，还不如不做缓存。

3.3 LRU：最经典的「最近最少使用」

LRU（Least Recently Used）的核心假设是：如果一个数据最近被访问过，那么它将来被访问的概率也更高。它维护一个双向链表，每次访问就把数据移到链表头部，淘汰时从尾部移除。

实现上，LRU 通常用「双向链表 + 哈希表」的组合，能做到 O(1) 的访问和淘汰。代码大概长这样：

class LRUCache {
    // 双向链表节点
    class Node {
        int key;
        float[] vector;  // 向量数据
        Node prev, next;
    }
    
    // 哈希表：key -> 节点指针
    HashMap<Integer, Node> map;
    // 虚拟头尾节点，简化边界处理
    Node head, tail;
    int capacity;
    
    // 访问时：将节点移到头部
    void get(int key) {
        Node node = map.get(key);
        removeNode(node);
        addToHead(node);
        return node.vector;
    }
    
    // 淘汰时：移除尾部节点
    void evict() {
        Node toRemove = tail.prev;
        removeNode(toRemove);
        map.remove(toRemove.key);
    }
}

在向量场景下，LRU 表现如何？说实话，中规中矩。它能很好地应对「突发热点」——比如某个向量突然被大量查询，它会被迅速移到头部，不会被淘汰。但问题在于，它不区分「访问 1 次」和「访问 100 次」的区别。如果一个向量被频繁访问但间隔较长，它可能因为中间被其他数据挤到尾部而被误杀。

3.4 LFU：频率优先，但有个大坑

LFU（Least Frequently Used）的思路是：淘汰访问次数最少的数据。它维护每个数据的访问计数，每次访问加 1，淘汰时选计数最小的。

听起来很合理对吧？但实际用起来有个大问题——「缓存污染」。想象一下，某个向量在短时间内被刷了 100 万次查询，计数飙到 100 万。然后热点过去了，这个向量再也没人访问。但因为它的计数太高，LFU 会一直把它留在缓存里，占着位置不走。这就是所谓的「历史残留」问题。

3.5 2Q：给 LRU 加个「观察期」

2Q（Two Queues）是对 LRU 的改进。它把缓存分成三个区域：

• Am 队列：存放只被访问过一次的数据（FIFO 策略）
• A1 队列：存放被访问过两次以上的数据（LRU 策略）
• 淘汰区：记录被淘汰数据的 key，用于快速判断是否该重新入队

它的逻辑是：新数据先进入 Am 队列，如果再次被访问，就晋升到 A1 队列。这样能有效过滤掉「一次性访问」的噪声数据，避免它们污染主缓存。

我在一个向量检索项目中用过 2Q，效果比纯 LRU 提升了大约 15% 的命中率。特别是对于那种「查询一次就不再访问」的冷数据，2Q 能很好地把它们挡在门外。

3.6 ARC：自适应的「智能选手」

ARC（Adaptive Replacement Cache）是我个人最推崇的策略。它由 IBM 研究院提出，核心思想是动态调整「最近使用」和「频繁使用」的权重比例。

ARC 维护四个链表：

• T1：最近使用过的数据（LRU）
• T2：频繁使用的数据（LFU）
• B1：从 T1 淘汰的数据的 key（幽灵队列）
• B2：从 T2 淘汰的数据的 key（幽灵队列）

关键在 B1 和 B2 这两个「幽灵队列」。它们不存实际数据，只存 key。当缓存未命中时，如果 key 在 B1 中，说明最近刚被淘汰，ARC 会认为「最近使用」的权重应该增加；如果在 B2 中，则认为「频繁使用」的权重应该增加。通过这种方式，ARC 能自适应地调整 T1 和 T2 的大小比例。

3.7 向量场景下的适配性深度对比

咱们用一张图来总结一下各策略在向量场景下的表现：

3.8 我的实战建议

说了这么多，到底该怎么选？我根据自己在几个向量检索项目中的经验，给出一些具体建议：

1. 中小规模系统（缓存条目 < 10 万）：优先用 2Q。实现简单，效果不错，性价比最高。
2. 大规模系统（缓存条目 > 100 万）：上 ARC。虽然实现复杂，但自适应能力在大规模场景下优势明显。
3. 访问模式极其稳定：可以考虑 LRU + 手动调参。但说实话，我很少见到真正「稳定」的向量检索场景。
4. 千万别用纯 FIFO 或纯 LFU：这两个在向量场景下基本是灾难，我踩过的坑不想让你再踩一遍。