当前位置：首页 > news >正文

缓存系统-淘汰策略

news 2025/7/2 5:20:09

一、LRU（最近最少使用）

工作原理

操作流程

基本特征

二、LFU（最不常使用）

工作原理

操作流程

基本特征

三、ARC 自适应

工作原理

操作流程

基本特征

四、TTL（生存时间）

工作原理

操作流程

基本特征

五、FIFO

工作原理

操作流程

基本特征

六、Random

工作原理

操作流程

基本特征

七、使用建议

一、LRU（最近最少使用）

工作原理

LRU（Least Recently Used）策略基于“时间局部性”原理，认为最近被访问过的数据在未来更可能被访问。它维护一个按访问时间排序的数据结构（通常使用双向链表），最近访问的放在头部，最久未访问的放在尾部。当缓存达到容量上限时，淘汰最久未访问的数据（即链表尾部）。

操作流程

查询：若数据存在，将其移动到链表头部（表示最近使用），返回数据。
新增/更新：若数据已存在，更新值并移动到头部；若不存在，在头部插入新节点。当缓存满时，先淘汰尾部节点再插入。

#include <list>
#include <unordered_map>class LRUCache {
private:int capacity;std::list<std::pair<int, int>> cache; // {key, value}// map 保存的是value的迭代器（实际数据存储在 cache 中），方便使用std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;public:LRUCache(int cap) : capacity(cap) {}int get(int key) {// map 统计 key 数量，不存在则返回空；if(!map.count(key)) return -1;auto it = map[key];// it 就是 cache 的迭代器，将其移动到 begin 位置cache.splice(cache.begin(), cache, it); // 移到头部return it->second;}void put(int key, int value) {// 若已存在数据，则更新 value，并移动到头部if(map.count(key)) {auto it = map[key];it->second = value;cache.splice(cache.begin(), cache, it);return;}// 若塞满了，则删除末尾的缓存valueif(cache.size() == capacity) {int del_key = cache.back().first;cache.pop_back();map.erase(del_key);}// 在 cache 头部直接构造 value 对象并插入，避免了重复创建 value 对象cache.emplace_front(key, value);map[key] = cache.begin();}
};

基本特征

优点：

对热点数据友好，能有效利用访问历史。
实现高效（哈希表+双向链表可实现O(1)操作）。

缺点：

偶发性批量操作（如全表扫描）可能污染缓存，淘汰真正热点数据。
链表指针占用额外内存。

适用场景：通用缓存场景（如网页缓存、数据库查询缓存）。

二、LFU（最不常使用）

工作原理

LFU （Least Frequently Used）策略根据数据的历史访问频率淘汰数据。它记录每个数据的访问次数，当缓存满时淘汰访问频率最低的数据。若频率相同，则淘汰其中最久未使用的数据（解决旧频率堆积问题）。

操作流程

查询：若数据存在，增加其访问频率，并根据新频率调整位置（如移到更高频率链表的头部）。
新增/更新：新数据初始频率为1。若缓存满，淘汰最低频率链表中的尾部节点（同频最久未用）。

#include <list>
#include <unordered_map>class LFUCache {
private:struct Node {int key, val, freq;Node(int k, int v, int f) : key(k), val(v), freq(f) {}};int capacity, minFreq;// key-valuestd::unordered_map<int, std::list<Node>::iterator> keyMap;// 频率-valuestd::unordered_map<int, std::list<Node>> freqMap;void updateFreq(std::list<Node>::iterator it) {int curFreq = it->freq;freqMap[curFreq].erase(it);/*minFreq是当前缓存中最小的频率。当某个频率的链表变空后，说明没有节点再使用这个频率了，保留它在 freqMap 中是没有意义的，删除它，避免占用不必要的内存。*/if(freqMap[curFreq].empty()) {freqMap.erase(curFreq);// 如果这个频率就是当前的 minFreq，那么我们需要更新 minFreq 到下一个更小的频率（比如 minFreq + 1）if(minFreq == curFreq) minFreq++;}it->freq++;// 更新频率后插入同频率链表头部freqMap[it->freq].push_front(*it);keyMap[it->key] = freqMap[it->freq].begin();}public:LFUCache(int cap) : capacity(cap), minFreq(1) {}// 根据 key 快速查找 value，并更新其使用频率int get(int key) {if(!keyMap.count(key)) return -1;auto it = keyMap[key];int val = it->val;updateFreq(it);return val;}void put(int key, int value) {if(capacity <= 0) return;// 若已存在同 key 的数据，则更新 value 与频率；if(keyMap.count(key)) {auto it = keyMap[key];it->val = value;updateFreq(it);return;}// 缓存满了之后，获取最小使用频率中的链表，并删除末尾的 value 节点；if(keyMap.size() >= capacity) {auto& minList = freqMap[minFreq];int del_key = minList.back().key;minList.pop_back();keyMap.erase(del_key);}// 新的 （key、value）插入频率为 1 的链表头部；freqMap[1].emplace_front(key, value, 1);// 写入缓存keyMap[key] = freqMap[1].begin();// 更新最小频率为 1minFreq = 1;}
};

基本特征

优点：

长期保护高频数据，不受偶发操作影响。

缺点：

新数据因频率低易被淘汰（“缓存冷启动”问题）。
频率计数需长期存储，内存开销大。
实现复杂（需双层结构：频率哈希表+节点链表）。

适用场景：长期热点数据缓存（如电商商品详情页、视频热门排行榜）。

三、ARC 自适应

工作原理

ARC 是一种自适应的缓存淘汰算法，通过动态平衡 LRU 和 LFU 策略来适应不同的访问模式。

ARC算法通过维护两个LRU链表和两个幽灵（ghost）链表来实现自适应：

两个实际缓存链表：

T1：存储最近被访问的项（类似于LRU）。
T2：存储被访问多次的项（类似于LFU中的频繁访问项）。

两个幽灵链表：

B1：存储从T1中被淘汰的项的键（只存储键，不存储数据）。
B2：存储从T2中被淘汰的项的键。

自适应参数 p：

T1 实际容量 = p
T2 实际容量 = capacity - p

操作	p值变化	T1空间变化	T2空间变化	实际效果
访问B1	增大	增加	减少	强化LRU特性（保留新访问数据）
访问B2	减小	减少	增加	强化LFU特性（保留热点数据）

操作流程

读操作：

如果数据在 T1 或 T2 中（缓存命中），则将该项移动到 T2 的 MRU（最近使用）端。
如果数据在 B1 中（幽灵链表），说明最近被淘汰的项又被访问了，此时增加 T1 的大小（即增加 p），强化 LRU 特性。然后从存储中加载数据到 T2 的 MRU 端，并从 B1 中移除该项。
如果数据在 B2 中，则增加 T2 的大小（即减少 p），强化 LFU 特性。然后从存储中加载数据到 T2 的 MRU 端，并从 B2 中移除该项。
如果都不在（缓存未命中），则从存储中加载数据，并放入 T1 的 MRU 端。

写操作：通常与读操作类似，但需要考虑写策略（如写回或写穿）。在缓存中，写操作通常也会更新缓存项的位置（类似于读操作），并将数据标记为脏（如果使用写回策略）。

#include <list>
#include <unordered_map>
#include <optional>template <typename K, typename V>
class ARCCache {size_t capacity;size_t p = 0;  // 自适应参数// 主缓存std::list<std::pair<K, V>> t1;std::list<std::pair<K, V>> t2;// 幽灵缓存（仅存储键）std::list<K> b1;std::list<K> b2;// 快速查找表std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> t1_map;std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> t2_map;std::unordered_map<K, typename std::list<K>::iterator> b1_map;std::unordered_map<K, typename std::list<K>::iterator> b2_map;void evict() {// 根据p值决定淘汰策略，t1 容量等于 pif (t1.size() > std::max(size_t(1), p)) {// 淘汰T1尾部auto [key, val] = t1.back();t1_map.erase(key);b1.push_front(key);b1_map[key] = b1.begin();t1.pop_back();} else {// 淘汰T2尾部auto [key, val] = t2.back();t2_map.erase(key);b2.push_front(key);b2_map[key] = b2.begin();t2.pop_back();}}public:ARCCache(size_t cap) : capacity(cap) {}std::optional<V> get(const K& key) {// 在T1中找到if (auto it = t1_map.find(key); it != t1_map.end()) {t2.splice(t2.begin(), t1, it->second);  // 移动到T2头部t2_map[key] = t2.begin();t1_map.erase(key);return t2.front().second;}// 在T2中找到if (auto it = t2_map.find(key); it != t2_map.end()) {t2.splice(t2.begin(), t2, it->second);  // 移动到头部return t2.front().second;}// 在B1中找到（幽灵缓存）if (auto it = b1_map.find(key); it != b1_map.end()) {p = std::min(capacity, p + std::max(b2.size() / b1.size(), size_t(1)));replace();put(key, load_from_disk(key));  // 实际需替换为数据加载b1_map.erase(key);b1.erase(it->second);return get(key);  // 递归获取}// 在B2中找到（幽灵缓存）if (auto it = b2_map.find(key); it != b2_map.end()) {p = std::max(size_t(0), p - std::max(b1.size() / b2.size(), size_t(1)));replace();put(key, load_from_disk(key));b2_map.erase(key);b2.erase(it->second);return get(key);}return std::nullopt;  // 未命中}void put(const K& key, const V& value) {// 如果已在缓存中，更新位置if (get(key).has_value()) return;// 需要淘汰旧数据if (t1.size() + t2.size() >= capacity) {evict();}// 新数据加入T1t1.emplace_front(key, value);t1_map[key] = t1.begin();}// 模拟从磁盘加载数据V load_from_disk(const K& key) { /* ... */ }
};

基本特征

✅ 优点：

自适应不同访问模式（时间局部性/频率局部性）
抵抗缓存扫描攻击
幽灵列表提供历史信息且内存占用小
常数时间操作（O(1)）
综合性能优于 LRU/LFU

❌ 缺点：

实现复杂度较高（需维护4个链表）
幽灵列表需要额外内存
参数 p 的调整需要精细控制
对极端访问模式适应性有限

✅ 适用场景

数据库缓存系统（如 Oracle, PostgreSQL）
操作系统页面缓存
CDN 内容缓存
大规模键值存储系统
需要高命中率的缓存场景

四、TTL（生存时间）

工作原理

TTL 策略为每个数据设置一个过期时间（如30秒）。数据过期后自动淘汰，无论其是否被访问。淘汰机制分为两种：

惰性删除：访问时检查过期则删除。
主动清理：后台线程定期扫描过期数据。

操作流程

查询：检查数据是否过期，过期则删除并返回空。
新增/更新：写入时设置过期时间戳。
淘汰：由访问触发（惰性）或定时任务触发（主动）。

#include <unordered_map>
#include <queue>
#include <chrono>class TTLValue {
public:int value;std::chrono::system_clock::time_point expire;TTLValue(int v, int ttl_ms) : value(v) {expire = std::chrono::system_clock::now() + std::chrono::milliseconds(ttl_ms);}bool expired() const {return std::chrono::system_clock::now() > expire;}
};class TTLCache {
private:std::unordered_map<int, TTLValue> cache;public:void put(int key, int value, int ttl_ms) {cache[key] = TTLValue(value, ttl_ms);}int get(int key) {if(!cache.count(key)) return -1;if(cache[key].expired()) {cache.erase(key);return -1;}return cache[key].value;}// 主动清理（示例）void cleanExpired() {for(auto it = cache.begin(); it != cache.end(); ) {if(it->second.expired()) it = cache.erase(it);else ++it;}}
};

基本特征

优点：

保证数据新鲜度，避免使用过时数据。
实现简单（仅需存储过期时间）。

缺点：

可能提前删除仍有价值的数据（如过期但频繁访问）。
主动清理需额外CPU开销。

适用场景：时效性敏感数据（如用户会话Token、验证码、新闻缓存）。

五、FIFO

工作原理

FIFO 策略按数据进入缓存的顺序淘汰，类似队列。最早进入的数据最先被淘汰，与访问频率无关。

操作流程

查询：返回数据，不改变任何顺序。
新增/更新：新数据加入队列尾部。若缓存满，淘汰队列头部数据。

#include <queue>
#include <unordered_map>class FIFOCache {
private:int capacity;std::queue<int> entryQueue;std::unordered_map<int, int> cache;public:FIFOCache(int cap) : capacity(cap) {}int get(int key) {if(!cache.count(key)) return -1;return cache[key]; // 不改变队列顺序}void put(int key, int value) {if(cache.size() >= capacity) {int del_key = entryQueue.front();entryQueue.pop();cache.erase(del_key);}cache[key] = value;entryQueue.push(key);}
};

基本特征

优点：

实现极其简单（队列+哈希表）。
无额外计算开销。

缺点：

无视访问模式，可能淘汰热点数据。

适用场景：顺序无关的低价值缓存（如日志临时缓存、下载缓冲池）。

六、Random

工作原理

随机策略在缓存满时随机选择一个数据淘汰。

操作流程

查询：直接返回数据。
新增/更新：若缓存满，随机选择一个键删除，再插入新数据。

#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <ctime>class RandomCache {
private:int capacity;std::vector<int> keys;std::unordered_map<int, int> cache;public:RandomCache(int cap) : capacity(cap) { srand(time(0)); }int get(int key) {return cache.count(key) ? cache[key] : -1;}void put(int key, int value) {if(cache.size() >= capacity) {int idx = rand() % keys.size();int del_key = keys[idx];keys[idx] = keys.back(); // 交换到末尾keys.pop_back();cache.erase(del_key);}cache[key] = value;keys.push_back(key);}
};

基本特征

优点：

实现简单，零维护成本。
无任何排序开销。

缺点：

结果不可控，可能淘汰重要数据。

适用场景：对性能要求极高且数据价值均匀的场景（如内存紧张的低优先级缓存）。

七、使用建议

特性	LRU	LFU	TTL	FIFO	Random
排序依据	访问时间	访问频率	过期时间	进入顺序	无
实现复杂度	中	高	低	极低	极低
热点保护	★★★★	★★★★★	★★	★	★
时效保证	✘	✘	★★★★★	✘	✘
内存开销	中	高	低	低	低
适用场景	通用缓存	长期热点	时效数据	流水数据	临时缓存