緩存淘汰策略指南：程序員必懂的四種方法
緩存就像快遞站里的臨時貨架：把最常用的包裹放在最顯眼的位置，下次取件時就能省下翻倉庫的時間。但貨架空間有限，到底該淘汰哪些包裹？今天用真實場景拆解程序員必懂的四種緩存淘汰策略。
排隊淘汰法(FIFO)—先來后到的公平策略
原理：就像超市儲物柜，先存入的包裹會被優(yōu)先清理。緩存滿時，第一個存入的數(shù)據(jù)最先被淘汰。
適用場景：
? ?? 短視頻APP的本地草稿箱（用戶一般處理最新草稿）
? ?? 訂單系統(tǒng)的臨時流水號生成（舊流水號過期即失效）
避坑指南：當(dāng)熱門商品（如秒殺活動的爆款）被頻繁訪問時，可能剛存入就被后續(xù)數(shù)據(jù)擠出緩存，導(dǎo)致緩存命中率暴跌。
Java示例：
// 使用LinkedHashMap的天然隊列特性
public class FIFOCache<K,V> extends LinkedHashMap<K,V> {
private final int maxSize;
public FIFOCache(int maxSize) {
super(maxSize, 0.75f, false); // true改為false關(guān)閉訪問排序
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Entry<K,V> eldest) {
return size() > maxSize;
}
}
// 測試：存入4個元素，觀察最早元素被淘汰
FIFOCache<String, Product> cache = new FIFOCache<>(3);
cache.put("P1001", new Product("iPhone15"));
cache.put("P1002", new Product("小米充電寶"));
cache.put("P1003", new Product("華為耳機(jī)"));
cache.put("P1004", new Product("OPPO手表"));
// 此時緩存中只剩P1002/P1003/P1004熱點守護(hù)者(LRU)—讓緩存記住你的喜好
原理：給每個數(shù)據(jù)貼「最后訪問時間」標(biāo)簽，就像瀏覽器歷史記錄，長期不看的頁面會被自動清理。
真實案例：
? 微信朋友圈緩存（最近瀏覽的朋友動態(tài)優(yōu)先保留）
? 電商商品詳情頁緩存（用戶反復(fù)查看的商品常駐內(nèi)存）
性能陷阱：直接使用LinkedHashMap的默認(rèn)實現(xiàn)，在千萬級并發(fā)時鏈表調(diào)整可能導(dǎo)致性能瓶頸。生產(chǎn)環(huán)境建議結(jié)合ConcurrentHashMap改造。
Java示例：
public class ConcurrentLRU<K,V> {
private final ConcurrentHashMap<K,V> map = new ConcurrentHashMap<>();
private final ConcurrentLinkedDeque<K> queue = new ConcurrentLinkedDeque<>();
private final int maxSize;
public void put(K key, V value) {
if (map.size() >= maxSize) {
KoldestKey= queue.poll(); // 并發(fā)安全的隊列操作
map.remove(oldestKey);
}
queue.addLast(key);
map.put(key, value);
}
public V get(K key) {
queue.remove(key); // 先刪除舊位置
queue.addLast(key); // 插入隊列尾部表示最近使用
return map.get(key);
}
}高頻VIP室(LFU)—只為真愛粉保留座位
原理：統(tǒng)計每個數(shù)據(jù)的訪問次數(shù)，像機(jī)場貴賓廳，只允許最頻繁出行的旅客進(jìn)入。
適用場景：
- ? 新聞APP的熱搜榜單緩存（統(tǒng)計點擊量）
- ? 音樂平臺的排行榜數(shù)據(jù)（按播放次數(shù)排序）
致命缺陷：早期的《哈利波特》小說訪問100次后不再打開，會長期霸占緩存空間，而新上架的《三體》可能因初始訪問量低無法進(jìn)入緩存。
優(yōu)化方案：引入訪問次數(shù)衰減機(jī)制：每隔1小時將所有計數(shù)器減半，讓新熱點有機(jī)會進(jìn)入緩存。
Java示例：
import java.util.*;
public class LFUCache<K, V> {
private final int capacity;
// 核心存儲結(jié)構(gòu)：key -> 值和頻率
private final HashMap<K, ValueWrapper> cache;
// 頻率 -> 相同頻率的key集合（使用LinkedHashSet保持插入順序）
private final HashMap<Integer, LinkedHashSet<K>> freqMap;
private int minFrequency;
public LFUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.freqMap = new HashMap<>();
this.minFrequency = 0;
}
public V get(K key) {
ValueWrapper wrapper= cache.get(key);
if (wrapper == null) return null;
// 更新頻率
updateFrequency(key, wrapper);
return wrapper.value;
}
public void put(K key, V value) {
if (capacity <= 0) return;
if (cache.containsKey(key)) {
// 已存在則更新值和頻率
ValueWrapper wrapper= cache.get(key);
wrapper.value = value;
updateFrequency(key, wrapper);
} else {
// 新增元素時的淘汰邏輯
if (cache.size() >= capacity) {
evict();
}
cache.put(key, new ValueWrapper(value, 1));
freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minFrequency = 1;
}
}
// 更新頻率的核心方法
private void updateFrequency(K key, ValueWrapper wrapper) {
int oldFreq= wrapper.frequency;
wrapper.frequency++;
// 從舊頻率集合移除
freqMap.get(oldFreq).remove(key);
if (freqMap.get(oldFreq).isEmpty()) {
freqMap.remove(oldFreq);
if (minFrequency == oldFreq) minFrequency++;
}
// 加入新頻率集合
freqMap.computeIfAbsent(wrapper.frequency, k -> new LinkedHashSet<>()).add(key);
}
// 執(zhí)行淘汰操作
private void evict() {
LinkedHashSet<K> keys = freqMap.get(minFrequency);
K evictKey= keys.iterator().next();
keys.remove(evictKey);
if (keys.isEmpty()) {
freqMap.remove(minFrequency);
}
cache.remove(evictKey);
}
// 測試用例
public static void main(String[] args) {
LFUCache<String, Integer> cache = new LFUCache<>(2);
cache.put("A", 1);
cache.put("B", 2);
cache.get("A"); // 訪問A使頻率變?yōu)?
cache.put("C", 3); // 淘汰B（A頻率2，B頻率1）
System.out.println(cache.get("B")); // 輸出null
}
// 內(nèi)部值包裝類
private class ValueWrapper {
V value;
int frequency;
ValueWrapper(V value, int frequency) {
this.value = value;
this.frequency = frequency;
}
}
}抽獎式淘汰(Random)—簡單粗暴的生存游戲
原理：隨機(jī)選擇犧牲品，像吃雞游戲的毒圈，存活全靠運氣。
使用場景：
? 臨時驗證碼緩存（無論是否使用，5分鐘后強(qiáng)制過期）
? A/B測試時的臨時實驗數(shù)據(jù)存儲
Java示例：
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ThreadLocalRandom;
public class RandomCache<K, V> {
private final Map<K, V> cache = new ConcurrentHashMap<>();
private final List<K> keyList = new ArrayList<>();
private final Object lock=new Object();
public void put(K key, V value) {
synchronized (lock) {
if (!cache.containsKey(key)) {
keyList.add(key);
}
cache.put(key, value);
}
}
public V get(K key) {
return cache.get(key);
}
public void evict() {
synchronized (lock) {
if (!keyList.isEmpty()) {
int randomIndex= ThreadLocalRandom.current().nextInt(keyList.size());
K evictKey= keyList.get(randomIndex);
// 將待刪除元素與最后一個元素交換后刪除
int lastIndex= keyList.size() - 1;
K lastKey= keyList.get(lastIndex);
keyList.set(randomIndex, lastKey);
keyList.remove(lastIndex);
cache.remove(evictKey);
}
}
}
// 測試用例
public static void main(String[] args) {
RandomCache<String, Integer> cache = new RandomCache<>();
cache.put("X", 10);
cache.put("Y", 20);
cache.evict();
System.out.println(cache.get("X")); // 50%概率輸出null
}
}進(jìn)階技巧：
? 混合策略：例如短視頻采用LRU+FIFO組合，新視頻先進(jìn)入FIFO隊列，達(dá)到一定訪問量后晉升到LRU池
? 分級緩存：Redis+L1/L2緩存設(shè)計，熱點數(shù)據(jù)用LRU，長尾數(shù)據(jù)用LFU
? 動態(tài)調(diào)整：例如外賣根據(jù)時段自動切換策略，午高峰用LFU保商家信息，夜間切Random降內(nèi)存消耗
掌握這些策略的組合拳，才能真正讓緩存成為系統(tǒng)性能的加速器。下次設(shè)計緩存模塊時，不妨先畫個業(yè)務(wù)場景象限圖，找到最適合的淘汰策略組合。
