在記憶體資源有限的系統中，快取的大小永遠無法無限膨脹。當快取容量達到上限時，必須有一套智慧演算法來決定：「當新資料進入時，哪一條舊資料應該被立即驅逐（Evict）？」
快取淘汰演算法的良窳，直接決定了快取的命中率（Hit Ratio）。在海量高併發場景下，快取命中率從 90% 提升至 99%，意味著穿透到底層資料庫的流量被瞬間壓低了整整 10 倍！
然而，經典的 LRU 面臨突發全表掃描的快取污染危機，而 LFU 則受限於歷史頻率殘留與巨大的記憶體開銷。
本文將從資料結構、時間與空間複雜度出發，深度剖析從 LRU、LFU、ARC 到現代 Java / Go 生產級快取（如 Caffeine、Ristretto）普遍採用的 W-TinyLFU。
1. 四大快取淘汰演算法全景對決
| 評估維度 | LRU（最近最少使用） | LFU（最不常使用） | ARC（自適應替換） | W-TinyLFU（視窗微 LFU） |
|---|---|---|---|---|
| 核心判斷維度 | 僅考慮時間衰減（Recency） | 僅考慮存取次數（Frequency） | 動態自適應 Recency + Frequency | 準入過濾 + 分段衰減 |
| 突發掃描污染防禦 | 極差（全量掃描沖刷熱點） | 良好（熱點不易被剔除） | 極佳（動態調整邊界） | 完美防禦（基於準入頻率 PK） |
| 歷史過期頻率適應性 | 良好（新資料隨時間上位） | 差（舊熱點長期佔用） | 良好 | 完美（週期性計數減半衰減） |
| 元數據記憶體開銷 | 每個項目 2 個指標（雙向鏈表） | 需維護計數器或 Min-Heap | 需維護 4 條鏈表（2x 開銷） | 極微（每個 Key 僅需 4 bits） |
| 時間複雜度 (Get/Put) | O(1) | O(1) 或 O(log N) | O(1) | O(1) |
| 工業級代表實踐 | Redis（近似 LRU） | Redis LFU | ZFS 檔案系統 | Caffeine（Java）、Ristretto（Go） |
2. 經典 LRU 的原理與突發掃描污染危機
2.1 LRU 資料結構：HashMap + 雙向鏈表
鏈表頭部：最新被存取節點
無論新寫入或舊資料被讀取，一律以 O(1) 移至 Head。處於最安全防禦區，永不優先淘汰。
中間資料節點 (Node A / B ...)
維護前後節點雙向記憶體指標，被命中時透過 HashMap O(1) 摘除並重新插回 Head。
鏈表尾部：最舊存取 (驅逐目標)
長時間未被存取的資料逐漸沉降至 Tail；當快取容量超過上限時，直接從尾部驅逐拋棄。
HashMap O(1) 直達索引
底層雜湊表直接映射 Key 到鏈表節點指標，擺脫 O(N) 遍歷開銷，保證讀寫均為 O(1)。
- 每次存取或寫入某個 Key 時，將該節點從雙向鏈表中摘下，重新插入到鏈表頭部（Head）。
- 容量滿時，直接將鏈表尾部（Tail）的節點移除。
2.2 致命缺陷：突發全表掃描污染（Scan Resistance Failure）
假設某後台程式在凌晨發起了一次全庫匯出（遍歷 100 萬筆只會被存取一次的冷資料）：
- 這 100 萬筆冷資料會瞬間湧入 LRU 鏈表頭部，將所有正在高頻存取的線上熱點商品全部強制擠出尾部！
- 匯出結束後，原本命中率高達 99% 的快取瞬間暴跌至 0%，引發毀滅性的資料庫連鎖崩潰。
3. LFU 的原理與歷史頻率殘留陷阱
LFU（Least Frequently Used）根據每個資料項目的歷史存取次數進行排序，優先淘汰存取次數最少的資料。
3.1 致命缺陷：歷史熱點殭屍化（Frequency Pollution）
- 假設某篇新聞在昨天被瘋狂點擊了 10 萬次，其頻率計數高達 100,000。
- 到了今天，該新聞熱度歸零，再無人問津；但因為其計數高達 10 萬，任何今天新發布的爆款新聞（計數只有 1~5 次）在快取滿時都會被無情拒絕或立即淘汰，而這篇殭屍新聞將長期霸佔快取空間。
4. 現代顛覆者：Window TinyLFU (W-TinyLFU)
為了徹底結合 LRU 對時間衰減的敏感度與 LFU 對長期頻率的精確判斷，Ben Manes 在 Caffeine 快取 中設計了 W-TinyLFU 演算法。
新資料緩衝區 (容量佔比 1%)
未命中資料優先載入小容量 Window LRU，捕捉短暫的高頻突發請求；當突發全表掃描發生時，冷資料僅在此處流轉，絕不直接衝擊主快取。
Count-Min Sketch 頻率對決
採用 4-bit 概率計數矩陣估算存取頻率（每項僅 4 bits 開銷），搭配定期折半衰減避免殭屍熱點；將 Window 淘汰者與主快取末尾者進行頻率 PK。
晉升 Segmented LRU (佔比 99%)
挑戰成功的熱點進入 20% 試用區（Probationary），若再次被讀取則升入 80% 保護區（Protected），確保高頻核心熱點長效存留。
頻率不足：直接丟棄
無法勝過主快取末尾項的冷資料直接被驅逐，從根源徹底免疫突發冷資料的全表掃描污染。
4.1 核心三大創新機制
- TinyLFU 準入策略（Admission Policy）：
- 當新資料被擠出 Window LRU 時，它不能直接進入主快取，而是作為「挑戰者」與主快取中即將被淘汰的「守擂者」進行頻率 PK。
- 只有挑戰者的存取頻率大於守擂者時，才允許其晉升進入主快取，否則直接拒絕。這從根本上免疫了突發全表掃描對快取的污染！
- Count-Min Sketch 空間極限壓縮：
- 如果為每個 Key 保存一個 32 位元或 64 位元的計數器，快取中元數據的體積將超過資料本身。
- TinyLFU 採用 4-bit Count-Min Sketch（基於 Bloom Filter 思想的概率計數矩陣），每個 Key 僅需 4 bits（最大計數到 15），即能以極小的記憶體開銷精確估算頻率。
- 週期性衰減（Reset / Aging Mechanism）：
- 當累積存取次數達到樣本總量上限時，TinyLFU 會將所有計數器的值除以 2（右移 1 位元）。
- 讓歷史熱點的權重隨時間自動減半衰退，完美解決了傳統 LFU 的殭屍資料問題！
5. 架構選型總結
- Java 應用本地快取：一律強制採用 Caffeine（內建 W-TinyLFU），其吞吐量與命中率在所有 Benchmark 中均全面碾壓 Guava Cache 與 Ehcache。
- Go 語言本地快取：採用 Ristretto（Dgraph 團隊基於 TinyLFU 打造）。
- 分散式 Redis：生產環境推薦配置
volatile-lru或allkeys-lfu，結合合理記憶體上限進行平滑淘汰。