4、LRU缓存淘汰策略：原理、实现与在搜索引擎中的变体
4.1 为什么需要LRU？
缓存不是无限大的。内存有限，磁盘太慢。你想想看，搜索引擎的倒排索引、文档摘要、热词结果，全塞进内存？不现实。
所以我们需要一个淘汰策略。当缓存满了，谁该滚蛋？
最简单的做法是FIFO（先进先出）。但我告诉你，这玩意儿在搜索引擎里基本是废的。为什么？因为用户搜的词有很强的局部性——今天搜“奥运会”，明天还搜“奥运会”。FIFO会把热词踢出去，冷词赖着不走。
LRU（Least Recently Used）就聪明多了。它的核心思想很简单：最近被访问过的数据，未来大概率还会被访问。说白了，就是“谁最近没被翻牌子，谁就先滚蛋”。
核心原则：LRU淘汰的是最久未被访问的数据，而不是最早进入缓存的数据。
4.2 LRU的经典实现
实现LRU，最经典的数据结构组合是：哈希表 + 双向链表。
哈希表负责O(1)查找，双向链表负责O(1)移动和删除。两者一结合，完美。
我直接上代码。这是我在一个搜索中间件项目里用过的简化版：
class LRUCache {
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
Node* head; // 虚拟头节点
Node* tail; // 虚拟尾节点
unordered_map<int, Node*> cache;
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int cap) : capacity(cap) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) return -1;
Node* node = cache[key];
removeNode(node);
addToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
removeNode(node);
addToHead(node);
} else {
if (cache.size() >= capacity) {
Node* toRemove = tail->prev;
removeNode(toRemove);
cache.erase(toRemove->key);
delete toRemove;
}
Node* newNode = new Node(key, value);
cache[key] = newNode;
addToHead(newNode);
}
}
};这段代码的逻辑很清晰：
- get操作：命中后把节点移到链表头部
- put操作：如果key存在，更新值并移到头部；如果不存在，先检查容量，满了就淘汰尾部节点，再插入到头部
个人习惯：我一般用虚拟头尾节点。这样能避免大量空指针判断，代码干净很多。你试试看，少写一堆if-else。
4.3 搜索引擎中的LRU变体
标准的LRU在搜索引擎里够用吗？不够。我踩过坑，所以给你讲讲几个关键变体。
4.3.1 分段LRU（Segmented LRU）
搜索引擎的缓存有个特点：有些数据被访问一次就再也没人碰了（比如冷门长尾词），有些数据则被反复访问（比如热搜词）。
标准LRU有个问题：一次突发的冷门查询，会把热词挤出缓存。这叫“缓存污染”。
分段LRU的解法很简单——把缓存分成两段：
- 试用段（Probationary Segment）：新数据先放这里，只给一次机会
- 保护段（Protected Segment）：被访问两次以上的数据晋升到这里，不会被轻易淘汰
我当年在优化搜索摘要缓存时，用了这个方案。效果很明显：热词的命中率从82%提升到了94%。
4.3.2 时钟算法（Clock）
标准LRU需要维护双向链表，每次访问都要移动节点。在高并发场景下，这个操作是有锁竞争的。
时钟算法是LRU的近似实现。它用一个环形缓冲区和一个指针，每个缓存项带一个“访问位”。
流程是这样的：
- 指针循环扫描缓冲区
- 遇到访问位为1的项，清零并跳过
- 遇到访问位为0的项，直接淘汰
说白了，这就是个“懒人版LRU”。它不需要移动数据，只需要改一个bit。在搜索引擎的倒排索引缓存里，我见过很多团队用这个方案。
我曾经踩过的坑：时钟算法的扫描步长不能太大。如果缓存很大，指针转一圈的时间太长，淘汰决策会滞后。我建议把缓存分片，每个片独立运行时钟算法。
4.3.3 权重LRU（Weighted LRU）
搜索引擎里，缓存项的大小不一样。一个文档摘要可能只有几百字节，但一个完整的倒排列表可能有几十兆。
标准LRU只考虑访问时间，不考虑大小。这会导致一个问题：大对象占着位置，小对象频繁被淘汰。
权重LRU的改进是：淘汰时综合考虑“最近使用时间”和“对象大小”。
我常用的策略是：
- 给每个缓存项一个权重 = 大小 × 时间衰减因子
- 淘汰时，选择权重最小的项
- 或者，先按大小排序，淘汰最大的冷数据
嗯，这里要注意：权重计算不能太复杂，否则CPU开销会吃掉缓存带来的收益。
4.4 实战中的选择建议
说了这么多，到底该用哪种？我根据经验给你个参考：
| 场景 | 推荐方案 | 理由 |
|---|---|---|
| 搜索词缓存（热词集中） | 分段LRU | 抗缓存污染，热词命中率高 |
| 倒排索引缓存（大对象多） | 权重LRU | 避免大对象霸占缓存 |
| 文档摘要缓存（高并发） | 时钟算法 | 无锁或低锁，吞吐量高 |
| 通用场景（中小规模） | 标准LRU | 实现简单，够用 |
我建议：不要一上来就上复杂变体。先用标准LRU跑起来，通过监控看命中率和淘汰频率。如果发现缓存污染严重，再切换到分段LRU。迭代优化，比一步到位靠谱。
4.5 小结
LRU是缓存淘汰的基石。但搜索引擎的场景更复杂，需要针对性地做变体。
记住三点：
- 标准LRU用哈希表+双向链表，O(1)操作
- 分段LRU解决缓存污染，时钟算法解决高并发锁竞争
- 权重LRU解决大小不均的问题
下一章，我会讲LFU和它的搜索引擎变体。到时候你会发现，LRU和LFU其实可以结合着用。