緩存系統-淘汰策略

一、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
排序依據	訪問時間	訪問頻率	過期時間	進入順序	無
實現復雜度	中	高	低	極低	極低
熱點保護	★★★★	★★★★★	★★	★	★
時效保證	?	?	★★★★★	?	?
內存開銷	中	高	低	低	低
適用場景	通用緩存	長期熱點	時效數據	流水數據	臨時緩存