快取淘汰演算法

引言：「行李箱滿載」問題

記憶體是昂貴的。妳無法將所有內容都存入快取（如 Redis、Memcached 或本地 RAM）。當妳的「行李箱」滿了，又有一個新項進來時，妳必須決定扔掉哪個舊項。

快取淘汰 (Cache Eviction) 就是做出這個決定的演算法。一個好的演算法會保留「熱數據」（妳很快就會用到的），並丟棄「冷數據」。

核心演算法

1. LRU (最近最少使用)

• 邏輯： 扔掉那個最長時間沒被訪問過的項。
• 工作原理： 雜湊表 + 雙向鏈表。每次訪問一個項，就把它移到鏈表頭部。鏈表尾部的項就是待淘汰的犧牲品。
• 優點： 非常簡單，適用於大多數基於「時間局部性」的場景。
• 缺點： 容易受「稀疏掃描」影響。如果一個腳本一次性讀取了 100 萬條舊數據，她會沖掉妳原本頻繁訪問的所有熱數據。

2. LFU (最不經常使用)

• 邏輯： 扔掉訪問次數最少的項。
• 工作原理： 為每個項維護一個訪問計數器。
• 優點： 適用於基於「頻率」的場景（例如一個始終很受歡迎的靜態首頁）。
• 缺點： 實現 $O(1)$ 複雜度較難。而且，一個 1 小時前很火但現在已經沒人看的項，可能會因為高計數而在快取中「殭死」很久。

3. W-TinyLFU

• 邏輯： 一種混合方法，使用一個小型的「准入窗口」和一個類似布隆過濾器的 Sketch 來追蹤頻率。
• 地位： 這是 Caffeine (Java) 和 Ristretto (Go) 使用的演算法。她提供了接近完美的命中率，並且能有效抵抗稀疏掃描。

典型業務場景

• ✅ Session 儲存： 使用 LRU。如果使用者 30 分鐘沒動，淘汰他的 Session 是安全的。
• ✅ 商品目錄： 使用 W-TinyLFU。有些商品是常青樹（頻率），有些則是當下的爆款（最近性）。
• ✅ 資料庫緩衝池： MySQL 和 Postgres 使用改良版的 LRU（如 LRU-2），以防止全表掃描毀掉整個快取。

性能與複雜度總結

• LRU： get 和 put 均為 $O(1)$。
• W-TinyLFU： 也是 $O(1)$，但需要更複雜的邏輯和頻率估算器 (Count-Min Sketch)。

小結：一句話記住它

「LRU 是行業默認選擇，因為她簡單且快。但如果妳的系統面臨不可預測的流量激增或大範圍掃描，請升級到 W-TinyLFU 以保持高快取命中率。」