完整倉庫鏈接

1. 背景與概述

1.1 什么是緩存驅逐算法

緩存系統的核心問題是當緩存空間有限時，需要決定哪些數據應該被保留，哪些數據應該被移除。這就是緩存驅逐算法要解決的問題。常見的緩存驅逐算法包括LRU（Least Recently Used，最近最少使用）和LFU（Least Frequently Used，最不經常使用）等。

1.2 W-TinyLFU 的定義與價值

W-TinyLFU（Window Tiny Least Frequently Used）是一種高性能的緩存驅逐算法，旨在以較低的內存開銷實現高緩存命中率。它巧妙地結合了LRU和LFU兩種策略的優點，同時規避了它們各自的缺點。

W-TinyLFU特別適用于需要高性能緩存且內存資源受限的場景，例如CDN、數據庫緩存、Web緩存等。

2. 核心思想與設計理念

W-TinyLFU的核心思想可以概括為以下幾點：

2.1 時間局部性與頻率局部性的結合

• 利用LRU處理新對象和一次性訪問的對象：它認為最近訪問的對象很可能在不久的將來再次被訪問（時間局部性）。
• 利用LFU保護長期流行的對象：它認為訪問頻率高的對象更有價值，應該長時間保留在緩存中（頻率局部性）。

2.2 高效的頻率統計

• 使用極小的內存開銷來近似LFU：傳統的LFU需要為每個緩存項維護一個精確的訪問計數器，內存開銷很大。TinyLFU使用Count-Min Sketch這種概率數據結構來_估計_對象的訪問頻率，極大地降低了內存需求。

2.3 窗口機制的引入

• 結合窗口（Window）機制：W-TinyLFU引入了一個小的"Window"緩存，主要基于LRU策略運行，用于處理新進入的對象和近期訪問的對象。這有助于算法快速適應訪問模式的變化。

3. 架構設計與組件

3.1 整體架構

W-TinyLFU由三個主要組件構成：窗口緩存（Window Cache）、主緩存（Main Cache）和頻率過濾器（TinyLFU Filter）。

3.2 窗口緩存（Window Cache）

窗口緩存是一個相對較小的LRU緩存，通常占據整個緩存空間的約1%。它用于快速接納新對象并捕捉短期熱點數據。

// 窗口緩存 (LRU) 的核心實現
template<typename K, typename V>
class WindowCache {
private:size_t capacity;  // 窗口緩存容量std::list<CacheItem<K, V>> items;  // LRU 列表，最近使用的在前面std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> itemMap;  // 快速查找表public:// 構造函數設置窗口容量explicit WindowCache(size_t cap) : capacity(cap) {}// 獲取緩存項，如果存在則移動到 MRU 位置（最近最常使用）std::optional<V> get(const K& key) {auto it = itemMap.find(key);if (it == itemMap.end()) {return std::nullopt;  // 不存在該鍵}// 找到了，將它移到列表前端（MRU位置）auto listIt = it->second;CacheItem<K, V> item = *listIt;items.erase(listIt);items.push_front(item);itemMap[key] = items.begin();return item.value;  // 返回值}// 添加新的緩存項到MRU位置bool add(const K& key, const V& value) {// 如果已存在，則更新值并移到MRU位置auto it = itemMap.find(key);if (it != itemMap.end()) {auto listIt = it->second;listIt->value = value;items.splice(items.begin(), items, listIt);return false;  // 沒有發生驅逐}// 檢查是否需要驅逐bool evicted = false;if (items.size() >= capacity) {evicted = true;}// 添加新項到MRU位置items.push_front(CacheItem<K, V>(key, value));itemMap[key] = items.begin();return evicted;  // 返回是否需要驅逐}// 驅逐LRU位置的項（最久未使用的）std::optional<CacheItem<K, V>> evict() {if (items.empty()) {return std::nullopt;}// 獲取并移除LRU項CacheItem<K, V> victim = items.back();itemMap.erase(victim.key);items.pop_back();return victim;  // 返回被驅逐的項}// 其他實用方法...bool empty() const { return items.empty(); }void clear() { items.clear(); itemMap.clear(); }size_t size() const { return items.size(); }
};

窗口緩存的主要特點：

• 完全按照LRU策略運行
• 所有新的緩存項首先進入窗口緩存
• 主要作用：
  • 快速接納新對象
  • 捕捉短期熱點
  • 作為進入主緩存的過濾器

3.3 主緩存（Main Cache）

主緩存占據大部分緩存空間（通常約99%），采用分段LRU策略，分為保護段和試用段兩部分。

// 主緩存 (分段 LRU: Protected + Probationary) 的核心實現
template<typename K, typename V>
class MainCache {
private:size_t capacity;  // 總容量size_t protectedRatio;  // Protected段所占比例 (0-100)// Protected段(保護段)和Probationary段(試用段)std::list<CacheItem<K, V>> protectedItems;  // 保護段的LRU列表std::list<CacheItem<K, V>> probationaryItems;  // 試用段的LRU列表// 快速查找表std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> protectedMap;std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> probationaryMap;// 獲取Protected段的最大容量size_t getProtectedCapacity() const {return capacity * protectedRatio / 100;}public:// 構造函數，設置容量和保護段比例MainCache(size_t cap, size_t protRatio = 80) : capacity(cap), protectedRatio(protRatio) {}// 獲取緩存項std::optional<V> get(const K& key) {// 先查找Protected段auto protIt = protectedMap.find(key);if (protIt != protectedMap.end()) {// 找到了，移到Protected段的MRU位置auto listIt = protIt->second;CacheItem<K, V> item = *listIt;protectedItems.erase(listIt);protectedItems.push_front(item);protectedMap[key] = protectedItems.begin();return item.value;}// 再查找Probationary段auto probIt = probationaryMap.find(key);if (probIt != probationaryMap.end()) {// 找到了，從Probationary段移除，提升到Protected段auto listIt = probIt->second;CacheItem<K, V> item = *listIt;probationaryItems.erase(listIt);probationaryMap.erase(key);// 提升到Protected段return promoteItem(item);}return std::nullopt;  // 未找到}// 提升項從Probationary段到Protected段V promoteItem(const CacheItem<K, V>& item) {// 如果Protected段已滿，需要將一個項降級到Probationary段if (protectedItems.size() >= getProtectedCapacity() && !protectedItems.empty()) {// 將Protected段LRU端的項降級到Probationary段的MRU位置CacheItem<K, V> demoted = protectedItems.back();protectedItems.pop_back();protectedMap.erase(demoted.key);probationaryItems.push_front(demoted);probationaryMap[demoted.key] = probationaryItems.begin();}// 將項添加到Protected段的MRU位置protectedItems.push_front(item);protectedMap[item.key] = protectedItems.begin();return item.value;}// 獲取犧牲者（即Probationary段LRU端的項）std::optional<CacheItem<K, V>> getVictim() const {if (probationaryItems.empty()) {return std::nullopt;}return probationaryItems.back();  // 返回試用段最久未使用的項}// 添加新項到緩存（為簡潔起見省略了部分代碼）void add(const K& key, const V& value) {// 檢查是否已在緩存中，如果是則更新// ...// 新項添加到Probationary段的MRU位置probationaryItems.push_front(CacheItem<K, V>(key, value));probationaryMap[key] = probationaryItems.begin();// 確保總容量不超過限制maintainSize();}// 其他方法...
};

主緩存的主要特點：

• 占據大部分緩存空間（通常約99%）
• 采用**分段LRU（Segmented LRU, SLRU）**策略
• 分為兩個段：
  • Protected Segment（保護段）：存放被多次訪問的對象
  • Probationary Segment（試用段）：存放新加入或只被訪問過一次的對象

3.4 頻率過濾器（TinyLFU Filter）

頻率過濾器是實現低開銷頻率統計的核心，使用Count-Min Sketch數據結構來估計對象訪問頻率。

// TinyLFU 頻率估計器，使用 Count-Min Sketch 實現
template<typename K>
class TinyLFU {
private:// Count-Min Sketch 參數static constexpr int HASH_COUNT = 4;       // 哈希函數數量int width;                                 // 每行的計數器數量std::vector<std::vector<uint8_t>> counters; // 計數器矩陣std::vector<uint64_t> seeds;               // 哈希函數種子// 重置窗口，用于處理計數飽和int resetThreshold;int itemCount;// 哈希函數size_t hash(const K& key, int seed) const {size_t h = std::hash<K>{}(key) ^ seed;return h % width;}public:// 構造函數，初始化Count-Min Sketchexplicit TinyLFU(int counterSize) {// 根據預期的緩存容量設置計數器大小width = counterSize * 10;  // 經驗法則：寬度 ≈ 容量的10倍// 初始化 Count-Min Sketchcounters.resize(HASH_COUNT, std::vector<uint8_t>(width, 0));// 初始化哈希函數種子seeds.resize(HASH_COUNT);for (int i = 0; i < HASH_COUNT; i++) {seeds[i] = i * 1099511628211ULL;  // 使用大質數}// 設置重置閾值resetThreshold = width * 10;  // 當觀察到的項達到此閾值時重置itemCount = 0;}// 增加一個鍵的頻率計數void increment(const K& key) {for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);// 避免計數器溢出if (counters[i][index] < 255) {counters[i][index]++;}}// 檢查是否需要重置計數器itemCount++;if (itemCount >= resetThreshold) {reset();}}// 估計一個鍵的頻率uint8_t frequency(const K& key) const {uint8_t min_count = 255;for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);min_count = std::min(min_count, counters[i][index]);}return min_count;}// 周期性重置：所有計數器減半（門限衰減）void reset() {for (auto& row : counters) {for (auto& count : row) {count = count >> 1;  // 除以2（位移操作）}}itemCount = 0;}
};

3.4.1 Count-Min Sketch原理

Count-Min Sketch是一種概率數據結構，用于在有限空間內估計數據流中元素的頻率。其原理如下：

• 結構：它是一個二維數組，配合多個獨立的哈希函數

• 插入操作：

  // 對應increment方法的核心
  for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);  // 計算哈希值counters[i][index]++;  // 增加計數器
  }
  

• 查詢操作：

  // 對應frequency方法的核心
  uint8_t min_count = 255;
  for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);min_count = std::min(min_count, counters[i][index]);  // 取最小值作為估計
  }
  return min_count;
  

• 衰減機制：

  // 對應reset方法的核心
  for (auto& row : counters) {for (auto& count : row) {count = count >> 1;  // 所有計數器除以2}
  }
  

頻率過濾器的主要特點：

• 不存儲實際的對象數據，只存儲頻率計數的估計值
• 使用多個哈希函數減小沖突概率
• 通過周期性衰減來適應訪問模式的變化

4. 工作流程詳解

4.1 緩存訪問（Cache Hit）流程

W-TinyLFU的緩存訪問流程是通過WTinyLFUCache類的get方法實現的：

// 獲取緩存項
std::optional<V> get(const K& key) {// 嘗試從窗口緩存獲取auto windowResult = windowCache.get(key);if (windowResult) {frequencySketch.increment(key);  // 增加頻率計數return windowResult;}// 嘗試從主緩存獲取auto mainResult = mainCache.get(key);if (mainResult) {frequencySketch.increment(key);  // 增加頻率計數return mainResult;}return std::nullopt;  // 不存在于緩存中
}

4.1.1 Window Cache命中

當訪問的數據位于Window Cache中時：

1. 通過windowCache.get(key)找到數據
2. 數據被移動到Window Cache的MRU位置（在WindowCache類內部完成）
3. 通過frequencySketch.increment(key)增加TinyLFU中該數據的頻率計數
4. 返回找到的數據值

WindowCache中的get方法實現了LRU更新：

std::optional<V> get(const K& key) {auto it = itemMap.find(key);if (it == itemMap.end()) {return std::nullopt;  // 不存在}// 移動到 MRU 位置auto listIt = it->second;CacheItem<K, V> item = *listIt;items.erase(listIt);items.push_front(item);  // 放到列表前端（MRU位置）itemMap[key] = items.begin();return item.value;
}

4.1.2 Main Cache命中

當訪問的數據位于Main Cache中（無論是試用段或保護段）時：

1. 通過mainCache.get(key)找到數據
2. 數據移動到對應段的MRU位置（在MainCache類內部完成）
3. 如果數據在試用段，它會被提升到保護段（如果保護段有空間）
4. 通過frequencySketch.increment(key)增加TinyLFU中該數據的頻率計數
5. 返回找到的數據值

MainCache中的get方法實現了SLRU的訪問和提升邏輯：

std::optional<V> get(const K& key) {// 先查找Protected段auto protIt = protectedMap.find(key);if (protIt != protectedMap.end()) {auto listIt = protIt->second;CacheItem<K, V> item = *listIt;// 移動到Protected段的MRU位置protectedItems.erase(listIt);protectedItems.push_front(item);protectedMap[key] = protectedItems.begin();return item.value;}// 再查找Probationary段auto probIt = probationaryMap.find(key);if (probIt != probationaryMap.end()) {auto listIt = probIt->second;CacheItem<K, V> item = *listIt;// 從Probationary段移除probationaryItems.erase(listIt);probationaryMap.erase(key);// 提升到Protected段return promoteItem(item);  // 這里實現了從試用段到保護段的提升}return std::nullopt;  // 不存在
}

4.2 緩存未命中與驅逐決策流程

當緩存中不存在請求的數據時，W-TinyLFU通過put方法處理：

// 添加/更新緩存項
void put(const K& key, const V& value) {// 先嘗試直接獲取(用于更新)if (get(key)) {// 如果在窗口緩存中，更新窗口緩存auto windowResult = windowCache.get(key);if (windowResult) {windowCache.add(key, value);return;}// 如果在主緩存中，更新主緩存mainCache.add(key, value);return;}// 新項，增加頻率frequencySketch.increment(key);// 添加到窗口緩存bool evicted = windowCache.add(key, value);// 如果窗口驅逐了一個項，執行策略決定if (evicted) {auto evictedItem = windowCache.evict();if (evictedItem) {handleWindowEviction(*evictedItem);}}
}

4.2.1 緩存未命中處理

當發生緩存未命中時：

1. 首先增加新數據的頻率計數：frequencySketch.increment(key);
2. 新數據被添加到Window Cache：windowCache.add(key, value);
3. 如果Window Cache已滿，會返回evicted = true
4. 此時需要從Window Cache驅逐一個項：evictedItem = windowCache.evict();
5. 被驅逐的項成為"候選者"，進入驅逐決策流程：handleWindowEviction(*evictedItem);

4.2.2 驅逐決策機制

當Window Cache已滿需要驅逐項時，W-TinyLFU需要決定是否將窗口緩存中驅逐出的候選者接納到主緩存中：

// 處理窗口緩存的驅逐
void handleWindowEviction(const CacheItem<K, V>& candidate) {// 獲取主緩存中的犧牲者（從試用段LRU端）auto victimOpt = mainCache.getVictim();// 如果主緩存沒有犧牲者(空的)，直接添加候選項if (!victimOpt) {mainCache.add(candidate.key, candidate.value);return;}const CacheItem<K, V>& victim = *victimOpt;// 比較候選項與犧牲者的頻率uint8_t candidateFreq = frequencySketch.frequency(candidate.key);uint8_t victimFreq = frequencySketch.frequency(victim.key);// 接納策略：候選項頻率大于犧牲者頻率if (candidateFreq > victimFreq) {// 驅逐犧牲者mainCache.evict(victim.key);// 接納候選項mainCache.add(candidate.key, candidate.value);}// 否則丟棄候選項（不做任何操作）
}

驅逐決策的具體步驟：

1. 從Main Cache的試用段LRU端找到"犧牲者"：victimOpt = mainCache.getVictim();
2. 使用TinyLFU Filter查詢候選者和犧牲者的訪問頻率：

   candidateFreq = frequencySketch.frequency(candidate.key);
   victimFreq = frequencySketch.frequency(victim.key);
   

3. 決策邏輯：
   • 如果候選者頻率 > 犧牲者頻率：接納候選者進入Main Cache，驅逐犧牲者

   if (candidateFreq > victimFreq) {mainCache.evict(victim.key);mainCache.add(candidate.key, candidate.value);
   }
   

   • 如果候選者頻率 ≤ 犧牲者頻率：丟棄候選者，犧牲者保留在緩存中

5. 算法優勢與應用場景

5.1 W-TinyLFU的優勢

• 掃描保護：能有效過濾一次性訪問的數據
• 頻率感知：通過頻率統計保留真正"熱"的數據
• 空間效率：使用概率數據結構降低內存開銷
• 時間效率：主要操作都具有O(1)時間復雜度
• 平衡新舊：在保留熱點數據的同時，為新數據提供機會
• 適應性：通過窗口和衰減機制適應訪問模式變化

5.2 潛在缺點與考慮因素

• 實現復雜度：相較于簡單的LRU，實現更為復雜
• 參數調優：性能受多個參數影響，需要針對具體場景調優
• 概率性：頻率統計是估計值而非精確值，理論上存在誤差可能

5.3 適用場景

• 數據庫緩存層
• 內容分發網絡（CDN）
• Web應用緩存
• 分布式緩存系統
• 任何有明顯訪問模式的大規模緩存應用

6. 實現與接口設計

6.1 核心抽象與API設計

6.1.1 主要緩存接口

template<typename K, typename V>
class WTinyLFUCache {
public:// 獲取緩存項，如果存在返回值，否則返回nullstd::optional<V> get(const K& key);// 存儲一個新的緩存項void put(const K& key, const V& value);// 清空緩存void clear();// 當前緩存大小size_t size() const;// 緩存容量size_t capacity() const;
};

6.1.2 組件接口

• WindowCache: 窗口緩存（LRU）
  • add(key, value): 添加項到窗口
  • evict(): 驅逐項并返回
• MainCache: 主緩存（分段LRU）
  • add(key, value): 添加項到緩存
  • getVictim(): 獲取犧牲者
  • promoteProbationaryItem(key): 提升試用項到受保護區
• TinyLFU: 頻率估計器
  • increment(key): 增加鍵的頻率計數
  • frequency(key): 獲取鍵的估計頻率
  • reset(): 周期性重置計數器

7. 性能考量與優化

7.1 時間復雜度分析

• get操作：平均O(1)時間復雜度
• put操作：平均O(1)時間復雜度
• 驅逐決策：O(1)時間復雜度

7.2 空間復雜度分析

• 緩存項存儲：O(n)，其中n為緩存容量
• TinyLFU過濾器：O(m)，其中m通常遠小于n，Count-Min Sketch結構使用的空間比傳統LFU少得多
• 額外元數據：O(n)用于存儲映射關系和鏈表指針

7.3 實際應用優化建議

• 窗口大小調整：根據工作負載特性調整窗口緩存與主緩存的比例

  // 調整窗口緩存大小的示例
  WTinyLFUCache<std::string, std::string> cache(1000, 0.01);  // 1%窗口大小
  WTinyLFUCache<std::string, std::string> cache(1000, 0.05);  // 5%窗口大小，更適合變化快的負載
  

• 分段比例優化：調整保護段與試用段的容量比例

  // 調整主緩存中保護段大小的示例
  WTinyLFUCache<std::string, std::string> cache(1000, 0.01, 80);  // 保護段80%
  WTinyLFUCache<std::string, std::string> cache(1000, 0.01, 60);  // 保護段60%，更容易接納新項
  

• Count-Min Sketch參數：根據緩存大小調整哈希函數數量和計數器矩陣大小

  // Count-Min Sketch參數調整示例
  class TinyLFU {
  private:static constexpr int HASH_COUNT = 4;  // 調整哈希函數數量// width = counterSize * 10;  // 調整寬度倍數
  };
  

• 衰減周期：根據訪問模式變化頻率調整計數器衰減周期

  // 調整衰減周期示例
  // resetThreshold = width * 10;  // 默認設置
  resetThreshold = width * 5;  // 更頻繁地衰減，適應快速變化的模式
  resetThreshold = width * 20;  // 減少衰減頻率，適應穩定的訪問模式
  

8. 完整實現示例

以下是W-TinyLFU緩存驅逐算法的完整實現：

#include <iostream>
#include <unordered_map>
#include <list>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <memory>
#include <cmath>
#include <optional>// 緩存項結構
template<typename K, typename V>
struct CacheItem {K key;V value;CacheItem(const K& k, const V& v) : key(k), value(v) {}
};// TinyLFU 頻率估計器，使用 Count-Min Sketch 實現
template<typename K>
class TinyLFU {
private:// Count-Min Sketch 參數static constexpr int HASH_COUNT = 4;       // 哈希函數數量int width;                                 // 每行的計數器數量std::vector<std::vector<uint8_t>> counters; // 計數器矩陣std::vector<uint64_t> seeds;               // 哈希函數種子// 重置窗口，用于處理計數飽和int resetThreshold;int itemCount;// 哈希函數size_t hash(const K& key, int seed) const {size_t h = std::hash<K>{}(key) ^ seed;return h % width;}public:explicit TinyLFU(int counterSize) {// 根據預期的緩存容量設置計數器大小width = counterSize * 10;  // 經驗法則：寬度 ≈ 容量的10倍// 初始化 Count-Min Sketchcounters.resize(HASH_COUNT, std::vector<uint8_t>(width, 0));// 初始化哈希函數種子seeds.resize(HASH_COUNT);for (int i = 0; i < HASH_COUNT; i++) {seeds[i] = i * 1099511628211ULL;  // 使用大質數}// 設置重置閾值resetThreshold = width * 10;  // 當觀察到的項達到此閾值時重置itemCount = 0;}// 增加一個鍵的頻率計數void increment(const K& key) {for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);// 避免計數器溢出if (counters[i][index] < 255) {counters[i][index]++;}}// 檢查是否需要重置計數器itemCount++;if (itemCount >= resetThreshold) {reset();}}// 估計一個鍵的頻率uint8_t frequency(const K& key) const {uint8_t min_count = 255;for (int i = 0; i < HASH_COUNT; i++) {size_t index = hash(key, seeds[i]);min_count = std::min(min_count, counters[i][index]);}return min_count;}// 周期性重置：所有計數器減半（門限衰減）void reset() {for (auto& row : counters) {for (auto& count : row) {count = count >> 1;  // 除以2（位移操作）}}itemCount = 0;}
};// 窗口緩存 (LRU)
template<typename K, typename V>
class WindowCache {
private:size_t capacity;std::list<CacheItem<K, V>> items;  // LRU 列表std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> itemMap;  // 查找表public:explicit WindowCache(size_t cap) : capacity(cap) {}// 獲取緩存項，如果存在則移動到 MRU 位置std::optional<V> get(const K& key) {auto it = itemMap.find(key);if (it == itemMap.end()) {return std::nullopt;  // 不存在}// 移動到 MRU 位置auto listIt = it->second;CacheItem<K, V> item = *listIt;items.erase(listIt);items.push_front(item);itemMap[key] = items.begin();return item.value;}// 添加新的緩存項bool add(const K& key, const V& value) {// 如果已存在，則更新auto it = itemMap.find(key);if (it != itemMap.end()) {auto listIt = it->second;listIt->value = value;// 移動到 MRU 位置items.splice(items.begin(), items, listIt);return false;  // 沒有發生驅逐}// 檢查容量bool evicted = false;if (items.size() >= capacity) {evicted = true;}// 添加新項到 MRU 位置items.push_front(CacheItem<K, V>(key, value));itemMap[key] = items.begin();return evicted;}// 驅逐 LRU 項std::optional<CacheItem<K, V>> evict() {if (items.empty()) {return std::nullopt;}// 獲取 LRU 項CacheItem<K, V> victim = items.back();itemMap.erase(victim.key);items.pop_back();return victim;}// 是否為空bool empty() const {return items.empty();}// 清空緩存void clear() {items.clear();itemMap.clear();}// 當前大小size_t size() const {return items.size();}
};// 主緩存 (分段 LRU: Protected + Probationary)
template<typename K, typename V>
class MainCache {
private:size_t capacity;size_t protectedRatio;  // Protected段所占比例 (0-100)// Protected段和Probationary段std::list<CacheItem<K, V>> protectedItems;std::list<CacheItem<K, V>> probationaryItems;// 查找表std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> protectedMap;std::unordered_map<K, typename std::list<CacheItem<K, V>>::iterator> probationaryMap;// 獲取Protected段的最大容量size_t getProtectedCapacity() const {return capacity * protectedRatio / 100;}public:MainCache(size_t cap, size_t protRatio = 80) : capacity(cap), protectedRatio(protRatio) {}// 獲取緩存項std::optional<V> get(const K& key) {// 先查找 Protected 段auto protIt = protectedMap.find(key);if (protIt != protectedMap.end()) {auto listIt = protIt->second;CacheItem<K, V> item = *listIt;// 移動到 Protected MRU 位置protectedItems.erase(listIt);protectedItems.push_front(item);protectedMap[key] = protectedItems.begin();return item.value;}// 再查找 Probationary 段auto probIt = probationaryMap.find(key);if (probIt != probationaryMap.end()) {auto listIt = probIt->second;CacheItem<K, V> item = *listIt;// 從 Probationary 移除probationaryItems.erase(listIt);probationaryMap.erase(key);// 添加到 Protected (如果有空間)return promoteItem(item);}return std::nullopt;  // 不存在}// 添加新的緩存項（總是添加到 Probationary）void add(const K& key, const V& value) {// 檢查是否已在 Protectedauto protIt = protectedMap.find(key);if (protIt != protectedMap.end()) {auto listIt = protIt->second;listIt->value = value;// 移動到 Protected MRUprotectedItems.splice(protectedItems.begin(), protectedItems, listIt);return;}// 檢查是否已在 Probationaryauto probIt = probationaryMap.find(key);if (probIt != probationaryMap.end()) {auto listIt = probIt->second;listIt->value = value;// 移動到 Probationary MRUprobationaryItems.splice(probationaryItems.begin(), probationaryItems, listIt);return;}// 添加到 ProbationaryprobationaryItems.push_front(CacheItem<K, V>(key, value));probationaryMap[key] = probationaryItems.begin();// 確保總容量不超過限制maintainSize();}// 提升 Probationary 項到 ProtectedV promoteItem(const CacheItem<K, V>& item) {// 如果 Protected 已滿，嘗試淘汰一些項if (protectedItems.size() >= getProtectedCapacity() && !protectedItems.empty()) {// 將 Protected LRU 降級到 Probationary MRUCacheItem<K, V> demoted = protectedItems.back();protectedItems.pop_back();protectedMap.erase(demoted.key);probationaryItems.push_front(demoted);probationaryMap[demoted.key] = probationaryItems.begin();}// 添加到 Protected MRUprotectedItems.push_front(item);protectedMap[item.key] = protectedItems.begin();return item.value;}// 獲取犧牲者（Probationary LRU）std::optional<CacheItem<K, V>> getVictim() const {if (probationaryItems.empty()) {return std::nullopt;}return probationaryItems.back();}// 驅逐一個指定的項bool evict(const K& key) {// 嘗試從 Probationary 移除auto probIt = probationaryMap.find(key);if (probIt != probationaryMap.end()) {probationaryItems.erase(probIt->second);probationaryMap.erase(probIt);return true;}// 嘗試從 Protected 移除（不常見）auto protIt = protectedMap.find(key);if (protIt != protectedMap.end()) {protectedItems.erase(protIt->second);protectedMap.erase(protIt);return true;}return false;  // 項不存在}// 確保緩存大小不超過容量void maintainSize() {size_t totalSize = protectedItems.size() + probationaryItems.size();while (totalSize > capacity && !probationaryItems.empty()) {// 從 Probationary LRU 端驅逐K victimKey = probationaryItems.back().key;probationaryItems.pop_back();probationaryMap.erase(victimKey);totalSize--;}// 如果仍然超出容量(罕見情況)，從 Protected 驅逐while (totalSize > capacity && !protectedItems.empty()) {K victimKey = protectedItems.back().key;protectedItems.pop_back();protectedMap.erase(victimKey);totalSize--;}}// 當前大小size_t size() const {return protectedItems.size() + probationaryItems.size();}// 清空緩存void clear() {protectedItems.clear();probationaryItems.clear();protectedMap.clear();probationaryMap.clear();}
};// W-TinyLFU 主緩存類
template<typename K, typename V>
class WTinyLFUCache {
private:size_t totalCapacity;float windowRatio;  // 窗口緩存的比例 (0.0-1.0)WindowCache<K, V> windowCache;MainCache<K, V> mainCache;TinyLFU<K> frequencySketch;public:WTinyLFUCache(size_t capacity, float windowRatio = 0.01, size_t protectedRatio = 80): totalCapacity(capacity), windowRatio(windowRatio),windowCache(static_cast<size_t>(capacity * windowRatio)),mainCache(capacity - static_cast<size_t>(capacity * windowRatio), protectedRatio),frequencySketch(capacity) {}// 獲取緩存項std::optional<V> get(const K& key) {// 嘗試從窗口緩存獲取auto windowResult = windowCache.get(key);if (windowResult) {frequencySketch.increment(key);return windowResult;}// 嘗試從主緩存獲取auto mainResult = mainCache.get(key);if (mainResult) {frequencySketch.increment(key);return mainResult;}return std::nullopt;  // 不存在}// 添加/更新緩存項void put(const K& key, const V& value) {// 先嘗試直接獲取(用于更新)if (get(key)) {// 如果在窗口緩存中，更新窗口緩存auto windowResult = windowCache.get(key);if (windowResult) {windowCache.add(key, value);return;}// 如果在主緩存中，更新主緩存mainCache.add(key, value);return;}// 新項，增加頻率frequencySketch.increment(key);// 添加到窗口緩存bool evicted = windowCache.add(key, value);// 如果窗口驅逐了一個項，執行策略決定if (evicted) {auto evictedItem = windowCache.evict();if (evictedItem) {handleWindowEviction(*evictedItem);}}}// 處理窗口緩存的驅逐void handleWindowEviction(const CacheItem<K, V>& candidate) {// 獲取主緩存中的犧牲者auto victimOpt = mainCache.getVictim();// 如果主緩存沒有犧牲者(空的)，直接添加候選項if (!victimOpt) {mainCache.add(candidate.key, candidate.value);return;}const CacheItem<K, V>& victim = *victimOpt;// 比較候選項與犧牲者的頻率uint8_t candidateFreq = frequencySketch.frequency(candidate.key);uint8_t victimFreq = frequencySketch.frequency(victim.key);// 接納策略：候選項頻率大于犧牲者頻率if (candidateFreq > victimFreq) {// 驅逐犧牲者mainCache.evict(victim.key);// 接納候選項mainCache.add(candidate.key, candidate.value);}// 否則丟棄候選項（不做任何操作）}// 清空緩存void clear() {windowCache.clear();mainCache.clear();}// 當前緩存大小size_t size() const {return windowCache.size() + mainCache.size();}// 緩存容量size_t capacity() const {return totalCapacity;}
};

9. 示例應用：Web頁面緩存

下面是一個使用W-TinyLFU的簡單Web頁面緩存示例：

#include <iostream>
#include <string>
#include <chrono>
#include <thread>// 假設我們已經包含了W-TinyLFU的實現...// 模擬網頁內容
struct WebPage {std::string url;std::string content;long timestamp;WebPage() : timestamp(0) {}WebPage(const std::string& u, const std::string& c) : url(u), content(c), timestamp(std::chrono::system_clock::now().time_since_epoch().count()) {}
};// 模擬從網絡加載頁面（昂貴操作）
WebPage fetchFromNetwork(const std::string& url) {std::cout << "Fetching " << url << " from network..." << std::endl;// 模擬網絡延遲std::this_thread::sleep_for(std::chrono::milliseconds(500));// 返回一個模擬的網頁return WebPage(url, "Content of " + url + " fetched at " + std::to_string(std::chrono::system_clock::now().time_since_epoch().count()));
}int main() {// 創建一個容量為100的W-TinyLFU緩存WTinyLFUCache<std::string, WebPage> pageCache(100);// 模擬訪問模式std::vector<std::string> urls = {"https://example.com/home","https://example.com/about","https://example.com/products","https://example.com/blog/post1","https://example.com/blog/post2"};// 模擬熱點頁面（多次訪問）std::vector<std::string> hotUrls = {"https://example.com/home","https://example.com/products"};// 第一次訪問所有頁面（填充緩存）for (const auto& url : urls) {std::cout << "First visit to " << url << std::endl;// 嘗試從緩存獲取auto cachedPage = pageCache.get(url);if (!cachedPage) {// 緩存未命中，從網絡獲取WebPage page = fetchFromNetwork(url);// 存入緩存pageCache.put(url, page);std::cout << "Page cached: " << url << std::endl;} else {std::cout << "Cache hit for " << url << std::endl;}std::cout << "-------------------" << std::endl;}// 模擬重復訪問熱點頁面（增加頻率）for (int i = 0; i < 5; i++) {for (const auto& url : hotUrls) {std::cout << "Repeated visit to hot page: " << url << std::endl;// 嘗試從緩存獲取auto cachedPage = pageCache.get(url);if (cachedPage) {std::cout << "Cache hit for hot page: " << url << std::endl;} else {// 理論上不應該發生，因為熱點頁面應該在緩存中std::cout << "Unexpected cache miss for hot page: " << url << std::endl;// 重新加載并緩存WebPage page = fetchFromNetwork(url);pageCache.put(url, page);}std::cout << "-------------------" << std::endl;}}// 模擬一次性訪問（掃描模式）for (int i = 0; i < 10; i++) {std::string scanUrl = "https://example.com/scan/page" + std::to_string(i);std::cout << "Scanning: " << scanUrl << std::endl;// 嘗試從緩存獲取auto cachedPage = pageCache.get(scanUrl);if (!cachedPage) {// 緩存未命中，從網絡獲取WebPage page = fetchFromNetwork(scanUrl);// 存入緩存pageCache.put(scanUrl, page);} else {std::cout << "Cache hit for " << scanUrl << " (unlikely)" << std::endl;}std::cout << "-------------------" << std::endl;}// 驗證熱點頁面是否仍在緩存中for (const auto& url : hotUrls) {std::cout << "Final check for hot page: " << url << std::endl;auto cachedPage = pageCache.get(url);if (cachedPage) {std::cout << "SUCCESS: Hot page still in cache: " << url << std::endl;} else {std::cout << "FAILURE: Hot page evicted: " << url << std::endl;}std::cout << "-------------------" << std::endl;}// 驗證掃描頁面是否已被驅逐（隨機選擇幾個）for (int i = 0; i < 3; i++) {std::string scanUrl = "https://example.com/scan/page" + std::to_string(i);std::cout << "Final check for scan page: " << scanUrl << std::endl;auto cachedPage = pageCache.get(scanUrl);if (cachedPage) {std::cout << "Scan page still in cache: " << scanUrl << std::endl;} else {std::cout << "As expected, scan page evicted: " << scanUrl << std::endl;}std::cout << "-------------------" << std::endl;}return 0;
}

10. 參考資料

1. TinyLFU: A Highly Efficient Cache Admission Policy
2. w-TinyLFU: A Cost-efficient, Admission-constrained Cache
3. Caffeine: A Java implementation of W-TinyLFU
4. Count-Min Sketch: An improved data structure for finding frequent elements in data streams
5. W-TinyLFU緩存淘汰策略