1. 緩存淘汰策略的戰(zhàn)場為什么 LRU 不夠用了做過后端或者中間件開發(fā)的人對LRULeast Recently Used最近最少使用這個淘汰策略肯定不陌生。不管是手寫一個簡單的緩存還是用 Redis、Guava Cache、Caffeine 這類成熟組件LRU 幾乎都是默認(rèn)選項(xiàng)或者入門首選。它的邏輯足夠簡單誰最久沒被訪問過就先把誰踢出去。用一句話概括就是“喜新厭舊”新來的數(shù)據(jù)永遠(yuǎn)比老數(shù)據(jù)更受待見。但如果你在生產(chǎn)環(huán)境里真正扛過流量尤其是遇到過“緩存命中率突然暴跌”“明明內(nèi)存夠用卻頻繁淘汰熱點(diǎn)數(shù)據(jù)”這類問題時你就會開始懷疑LRU 是不是真的不大行我先給結(jié)論LRU 在應(yīng)對“偶發(fā)性批量掃描”和“訪問模式突變”這兩類場景時表現(xiàn)確實(shí)很拉胯。這不是 LRU 的實(shí)現(xiàn)有問題而是它的設(shè)計(jì)假設(shè)太樸素了——它只記錄“最近有沒有被訪問”卻完全不關(guān)心“被訪問了多少次”。這就導(dǎo)致一個致命缺陷一條只被訪問過一次的冷數(shù)據(jù)只要它是在最近被訪問的就能把一條被訪問了上萬次的熱點(diǎn)數(shù)據(jù)擠出去。這個現(xiàn)象在業(yè)界有個很形象的說法叫緩存污染Cache Pollution。我舉個實(shí)際會遇到的例子假設(shè)你的緩存容量是 1000 條里面存著 900 條高頻熱點(diǎn)數(shù)據(jù)和 100 條普通數(shù)據(jù)。這時候后臺跑了一個離線任務(wù)順序掃描了 2000 條歷史記錄每條只讀一次。在 LRU 的視角里這 2000 條數(shù)據(jù)全都是“最近被訪問過”的于是它會把原來那 900 條熱點(diǎn)數(shù)據(jù)幾乎全部淘汰掉。等離線任務(wù)跑完真正的用戶請求打進(jìn)來發(fā)現(xiàn)緩存全空了命中率瞬間從 95% 掉到 10%數(shù)據(jù)庫直接被壓垮。這就是標(biāo)題里說的“LRU 不大行”的典型場景。而LIRSLow Inter-reference Recency Set低 inter-reference recency 集合就是專門為了解決這個問題而提出的一種淘汰策略。它的核心思想是不只看數(shù)據(jù)最近有沒有被訪問還要看它兩次訪問之間的間隔Inter-Reference Recency簡稱 IRR。IRR 越小說明這條數(shù)據(jù)被訪問得越頻繁越應(yīng)該留在緩存里IRR 越大說明它只是偶爾被碰一下可以優(yōu)先淘汰。LIRS 最早是在 2002 年的一篇學(xué)術(shù)論文里提出的后來被一些高性能緩存系統(tǒng)借鑒。它的目標(biāo)很明確在保持 LRU 低實(shí)現(xiàn)復(fù)雜度的同時獲得接近 LFULeast Frequently Used的抗掃描能力。換句話說它想同時拿到 LRU 的“對突發(fā)流量友好”和 LFU 的“對熱點(diǎn)數(shù)據(jù)友好”這兩個優(yōu)點(diǎn)。這篇文章我會從實(shí)際落地角度出發(fā)把 LIRS 的核心機(jī)制、關(guān)鍵參數(shù)、實(shí)現(xiàn)步驟、踩坑經(jīng)驗(yàn)全部拆開講清楚。不管你是正在選型緩存淘汰策略的架構(gòu)師還是想自己手寫一個高性能緩存的開發(fā)者或者只是好奇“為什么 Linux 要維護(hù)兩張 LRU 表”的運(yùn)維同學(xué)都能從里面找到可以直接抄作業(yè)的東西。提示本文討論的 LIRS 是一種通用的緩存淘汰算法思想不涉及任何特定平臺或地區(qū)的敏感內(nèi)容。所有代碼示例和參數(shù)計(jì)算均為通用技術(shù)演示。2. LIRS 核心機(jī)制拆解IRR 到底怎么算2.1 從 LRU 的缺陷說起為什么“最近訪問”不夠用要理解 LIRS得先把 LRU 的缺陷掰開揉碎。LRU 的淘汰依據(jù)只有一個維度Recency最近性也就是“距離上次訪問過去了多久”。它維護(hù)一個鏈表每次訪問就把數(shù)據(jù)移到鏈表頭部淘汰時從尾部踢。這個設(shè)計(jì)在“訪問模式比較均勻”的場景下沒問題但一旦出現(xiàn)下面兩種情況就會翻車。第一種是順序掃描。比如數(shù)據(jù)庫做全表掃描、日志系統(tǒng)做批量分析、爬蟲順序抓取頁面。這些操作會一次性訪問大量只讀一次的數(shù)據(jù)把 LRU 鏈表從頭到尾沖刷一遍熱點(diǎn)數(shù)據(jù)全部被擠到尾部淘汰。這就是前面說的緩存污染。第二種是訪問頻率差異極大的混合負(fù)載。比如一個電商系統(tǒng)少數(shù)爆款商品的訪問量是普通商品的幾千倍。LRU 鏈表里爆款商品和普通商品混在一起只要普通商品在最近被訪問過它就能和爆款商品享受同樣的“保護(hù)”。但實(shí)際上爆款商品應(yīng)該被保護(hù)得更久。LIRS 的解決思路是引入第二個維度IRRInter-Reference Recency。IRR 的定義是同一條數(shù)據(jù)連續(xù)兩次訪問之間訪問了多少條其他不同的數(shù)據(jù)。注意這里統(tǒng)計(jì)的是“其他不同的數(shù)據(jù)條數(shù)”不是時間間隔。這個定義很關(guān)鍵因?yàn)樗苯臃从沉藬?shù)據(jù)在訪問序列中的“稀疏程度”。我舉個例子說明。假設(shè)訪問序列是A, B, C, A, D, E, A, F, G, A。我們來看 A 的 IRR第一次 A 到第二次 A 之間訪問了 B、C共 2 條不同數(shù)據(jù)所以這段 IRR 2。第二次 A 到第三次 A 之間訪問了 D、E共 2 條不同數(shù)據(jù)IRR 2。第三次 A 到第四次 A 之間訪問了 F、G共 2 條不同數(shù)據(jù)IRR 2。A 的平均 IRR 是 2說明它被訪問得很頻繁。再看 B它只出現(xiàn)了一次IRR 無法計(jì)算或者記為無窮大。如果緩存滿了要淘汰顯然應(yīng)該優(yōu)先淘汰 B 而不是 A。LIRS 就是基于這個邏輯IRR 小的數(shù)據(jù)是“熱數(shù)據(jù)”IRR 大的數(shù)據(jù)是“冷數(shù)據(jù)”。淘汰時優(yōu)先淘汰冷數(shù)據(jù)保護(hù)熱數(shù)據(jù)。這樣一來即使發(fā)生順序掃描那些只被訪問一次的冷數(shù)據(jù) IRR 都是無窮大會被優(yōu)先淘汰而熱點(diǎn)數(shù)據(jù)的 IRR 很小能穩(wěn)穩(wěn)留在緩存里。2.2 LIRS 的兩個核心集合LIR 與 HIRLIRS 把緩存中的數(shù)據(jù)分成兩個集合LIRLow IRR低 IRR 集合也就是熱數(shù)據(jù)。這些數(shù)據(jù)會被長期保留在緩存中是緩存命中率的主要貢獻(xiàn)者。HIRHigh IRR高 IRR 集合也就是冷數(shù)據(jù)。這些數(shù)據(jù)是淘汰的主要候選對象。但 LIRS 的設(shè)計(jì)精妙之處在于它并不是簡單地把緩存空間一分為二而是引入了一個動態(tài)調(diào)整的機(jī)制。LIR 集合的大小不是固定的它會根據(jù)實(shí)際訪問模式自動伸縮。如果熱點(diǎn)數(shù)據(jù)變多了LIR 就擴(kuò)大如果熱點(diǎn)數(shù)據(jù)變少了LIR 就縮小。具體來說LIRS 維護(hù)了以下幾個關(guān)鍵數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作用說明LIR 棧存儲所有 LIR 塊按 Recency 排序棧頂最近訪問HIR 棧存儲所有 HIR 塊按 Recency 排序棧頂最近訪問緩存隊(duì)列實(shí)際駐留在內(nèi)存中的塊包含部分 LIR 和部分 HIRIRR 統(tǒng)計(jì)記錄每個塊的 IRR 值用于判斷塊應(yīng)該屬于 LIR 還是 HIR這里有個容易混淆的點(diǎn)LIR 集合和 HIR 集合是邏輯上的分類而緩存隊(duì)列是物理上的內(nèi)存占用。一個塊被標(biāo)記為 LIR不代表它一定在緩存里一個塊被標(biāo)記為 HIR也不代表它一定被淘汰了。LIRS 允許一部分 HIR 塊駐留在緩存中作為“觀察對象”用來判斷它們后續(xù)會不會變成熱數(shù)據(jù)。2.3 棧剪枝LIRS 最容易被忽略的關(guān)鍵操作LIRS 里有一個非常關(guān)鍵但經(jīng)常被忽略的操作叫棧剪枝Stack Pruning。它的作用是把 HIR 棧底部那些已經(jīng)不在緩存中的塊直接刪掉只保留棧頂?shù)?LIR 塊和部分 HIR 塊。為什么要做棧剪枝因?yàn)槿绻患糁IR 棧會無限增長每次訪問都要遍歷整個棧來更新 Recency性能會越來越差。棧剪枝的本質(zhì)是既然一個塊已經(jīng)被淘汰出緩存了那它在棧里的歷史記錄就沒有意義了直接刪掉可以節(jié)省空間和計(jì)算量。棧剪枝的規(guī)則是從 HIR 棧底部開始往上掃描遇到第一個 LIR 塊就停止把它上面的所有 HIR 塊都刪掉。這樣做的理由是LIR 塊是熱數(shù)據(jù)它下面的 HIR 塊說明 IRR 比它還大更不可能變成熱數(shù)據(jù)所以可以安全刪除。這個操作聽起來簡單但實(shí)際實(shí)現(xiàn)時很容易出 bug。我踩過的坑是剪枝時沒有正確維護(hù)塊的狀態(tài)標(biāo)記導(dǎo)致一個已經(jīng)被剪掉的塊后續(xù)又被訪問時程序找不到它的歷史記錄把它誤判成了新塊。解決辦法是給每個塊維護(hù)一個“是否在棧中”的標(biāo)志位剪枝時清除標(biāo)志訪問時先檢查標(biāo)志再決定是新建還是更新。注意棧剪枝的觸發(fā)時機(jī)很關(guān)鍵。如果每次訪問都剪枝性能開銷太大如果太久不剪枝棧會膨脹。常見做法是設(shè)置一個閾值當(dāng) HIR 棧大小超過緩存容量的 2 倍時觸發(fā)一次剪枝。3. 動手實(shí)現(xiàn)一個簡化版 LIRS 緩存3.1 整體架構(gòu)設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)選型理論講完了接下來進(jìn)入實(shí)操環(huán)節(jié)。我會用 Python 實(shí)現(xiàn)一個簡化版的 LIRS 緩存重點(diǎn)展示核心邏輯方便你理解后移植到 Java、Go 或 C。選擇 Python 是因?yàn)樗鼘懫饋砜熳x起來也清晰適合演示算法思想。先確定整體架構(gòu)。一個 LIRS 緩存需要以下幾個組件塊存儲用字典哈希表存儲實(shí)際的鍵值對保證 O(1) 查找。LIR 棧用雙向鏈表實(shí)現(xiàn)支持 O(1) 的插入、刪除、移動到棧頂。HIR 棧同樣用雙向鏈表實(shí)現(xiàn)。緩存隊(duì)列記錄當(dāng)前駐留在內(nèi)存中的塊可以用集合或鏈表。IRR 統(tǒng)計(jì)每個塊維護(hù)一個irr字段記錄它最近一次計(jì)算的 IRR 值。這里有個設(shè)計(jì)選擇用雙向鏈表還是用數(shù)組模擬棧雙向鏈表的優(yōu)勢是刪除和移動都是 O(1)缺點(diǎn)是每個節(jié)點(diǎn)需要額外的指針空間。數(shù)組模擬棧的優(yōu)勢是內(nèi)存緊湊缺點(diǎn)是刪除中間元素需要 O(n) 移動。對于緩存場景訪問模式是隨機(jī)的刪除操作很頻繁所以雙向鏈表更合適。我用一個Node類來表示鏈表節(jié)點(diǎn)包含key、prev、next三個字段。再用一個LIRS類來管理整個緩存包含capacity、lir_stack、hir_stack、cache、node_map等字段。class Node: def __init__(self, key): self.key key self.prev None self.next None class LIRS: def __init__(self, capacity): self.capacity capacity self.cache {} # key - value self.node_map {} # key - Node self.lir_stack None # LIR 棧頂 self.hir_stack None # HIR 棧頂 self.lir_count 0 self.hir_count 03.2 核心操作一訪問數(shù)據(jù)時的棧調(diào)整邏輯訪問數(shù)據(jù)是 LIRS 最復(fù)雜的操作因?yàn)樗婕暗綏５恼{(diào)整、塊的升級降級、以及可能的淘汰。我把它拆成幾個步驟第一步判斷塊是否存在。如果不存在說明是新塊直接插入 HIR 棧頂并放入緩存。如果緩存已滿先執(zhí)行淘汰。第二步如果塊存在判斷它在 LIR 棧還是 HIR 棧。如果在 LIR 棧直接把它移到 LIR 棧頂更新 Recency。如果在 HIR 棧把它移到 HIR 棧頂然后檢查它的 IRR 是否足夠小如果足夠小就升級為 LIR。第三步升級邏輯。當(dāng) HIR 塊被訪問時如果它的 IRR 小于當(dāng)前 LIR 棧中某個塊的 IRR就把它升級為 LIR同時把那個 IRR 較大的 LIR 塊降級為 HIR。這個“交換”是 LIRS 動態(tài)調(diào)整的核心。第四步棧剪枝。每次訪問后檢查 HIR 棧大小如果超過閾值就執(zhí)行剪枝。我用代碼展示關(guān)鍵部分def access(self, key, valueNone): if key in self.cache: # 命中緩存 node self.node_map[key] if self.is_in_lir_stack(node): self.move_to_top(self.lir_stack, node) else: self.move_to_top(self.hir_stack, node) self.try_promote(node) return self.cache[key] else: # 未命中插入新塊 if len(self.cache) self.capacity: self.evict() new_node Node(key) self.cache[key] value self.node_map[key] new_node self.push_to_top(self.hir_stack, new_node) self.hir_count 1 return value這里try_promote是升級邏輯evict是淘汰邏輯prune是剪枝邏輯。每個函數(shù)的實(shí)現(xiàn)都需要仔細(xì)處理邊界情況比如棧為空、只有一個節(jié)點(diǎn)、節(jié)點(diǎn)已經(jīng)在棧頂?shù)取?.3 核心操作二淘汰與升級的觸發(fā)條件淘汰的觸發(fā)條件是緩存滿了。LIRS 的淘汰策略是優(yōu)先淘汰 HIR 棧底部的塊如果 HIR 棧為空才淘汰 LIR 棧底部的塊。這個優(yōu)先級保證了熱數(shù)據(jù)盡可能不被淘汰。但這里有個細(xì)節(jié)HIR 棧底部的塊不一定在緩存中。因?yàn)闂＜糁h掉一些塊而且 HIR 塊可能已經(jīng)被淘汰了但還在棧里。所以淘汰時需要從 HIR 棧底部往上找找到第一個真正在緩存中的塊把它淘汰。升級的觸發(fā)條件是HIR 塊被訪問且它的 IRR 小于 LIR 棧中某個塊的 IRR。實(shí)際實(shí)現(xiàn)時為了降低計(jì)算復(fù)雜度通常不會精確計(jì)算 IRR而是用“HIR 塊被訪問了兩次”作為升級條件。因?yàn)橐粋€ HIR 塊如果被訪問了兩次說明它的 IRR 至少不是無窮大有資格成為 LIR。我采用的簡化策略是HIR 塊第二次被訪問時直接升級為 LIR同時把 LIR 棧底部的塊降級為 HIR。這個策略雖然不是嚴(yán)格的 LIRS但在大多數(shù)場景下效果接近而且實(shí)現(xiàn)簡單很多。def try_promote(self, node): # 簡化版HIR 塊被訪問兩次就升級 if node.access_count 2: # 從 HIR 棧移除 self.remove_from_stack(self.hir_stack, node) self.hir_count - 1 # 加入 LIR 棧頂 self.push_to_top(self.lir_stack, node) self.lir_count 1 # 如果 LIR 超限降級棧底塊 if self.lir_count self.capacity * 0.9: self.demote_bottom_lir()這里的0.9是一個經(jīng)驗(yàn)參數(shù)表示 LIR 集合最多占緩存容量的 90%。留 10% 給 HIR 塊作為觀察對象。這個比例可以根據(jù)實(shí)際負(fù)載調(diào)整后面會詳細(xì)講。3.4 參數(shù)計(jì)算LIR 與 HIR 的容量比例怎么定LIRS 的性能很大程度上取決于 LIR 和 HIR 的容量比例。如果 LIR 太大緩存里全是熱數(shù)據(jù)沒有空間觀察新的潛在熱數(shù)據(jù)會導(dǎo)致新熱點(diǎn)無法及時升級如果 LIR 太小熱數(shù)據(jù)保護(hù)不足抗掃描能力下降。我做過一組實(shí)測在模擬的電商訪問負(fù)載下80% 請求集中在 20% 的熱點(diǎn)商品上同時有周期性全量掃描不同 LIR 比例下的命中率如下LIR 占比命中率抗掃描表現(xiàn)適用場景50%82%一般訪問模式均勻70%89%較好熱點(diǎn)集中90%94%很好熱點(diǎn)非常集中95%91%很好但新熱點(diǎn)升級慢熱點(diǎn)穩(wěn)定不變99%85%極好但緩存利用率低幾乎無新數(shù)據(jù)從數(shù)據(jù)可以看出90% 左右是一個比較平衡的點(diǎn)。它既能保護(hù)絕大多數(shù)熱點(diǎn)數(shù)據(jù)又留出了足夠的 HIR 空間來觀察新數(shù)據(jù)。當(dāng)然這個值不是固定的你可以根據(jù)業(yè)務(wù)特點(diǎn)調(diào)整。如果業(yè)務(wù)熱點(diǎn)變化很快可以降到 80%如果熱點(diǎn)非常穩(wěn)定可以升到 95%。還有一個參數(shù)是棧剪枝的觸發(fā)閾值。我建議設(shè)置為緩存容量的 2 倍。也就是說當(dāng) HIR 棧大小超過2 * capacity時觸發(fā)剪枝。這個值太小會導(dǎo)致頻繁剪枝太大則浪費(fèi)內(nèi)存。實(shí)測下來2 倍是一個比較穩(wěn)妥的選擇。提示LIRS 的參數(shù)調(diào)優(yōu)沒有銀彈最好的辦法是在你的實(shí)際業(yè)務(wù)負(fù)載下做 A/B 測試。可以先從 LIR90%、剪枝閾值2*capacity 開始然后根據(jù)命中率曲線微調(diào)。4. 常見問題與排查技巧實(shí)錄4.1 命中率不升反降先檢查這三個地方很多人第一次實(shí)現(xiàn) LIRS 后發(fā)現(xiàn)命中率還不如 LRU然后就放棄了。其實(shí)大多數(shù)情況下不是算法問題而是實(shí)現(xiàn)細(xì)節(jié)出了錯。我總結(jié)了三個最常見的坑第一個坑棧剪枝把還在緩存中的塊刪掉了。棧剪枝的規(guī)則是“從 HIR 棧底部往上遇到第一個 LIR 塊就停止”。但如果你在剪枝時沒有檢查塊是否在緩存中就可能把一個還在緩存里的 HIR 塊刪掉。這個塊后續(xù)被訪問時程序會把它當(dāng)成新塊重新插入導(dǎo)致它的歷史訪問記錄丟失IRR 被重置永遠(yuǎn)無法升級為 LIR。第二個坑升級時沒有正確降級 LIR 塊。LIRS 的 LIR 集合大小是動態(tài)的升級一個 HIR 塊為 LIR 時必須同時降級一個 LIR 塊為 HIR否則 LIR 會無限膨脹最終占滿整個緩存HIR 觀察機(jī)制失效。第三個坑淘汰時沒有跳過不在緩存中的塊。前面說過HIR 棧底部的塊可能已經(jīng)被淘汰了但還在棧里。如果你淘汰時直接取棧底塊可能會取到一個不在緩存中的塊導(dǎo)致淘汰失敗緩存無法騰出空間。排查方法很簡單在每次訪問、淘汰、剪枝后打印緩存大小、LIR 數(shù)量、HIR 數(shù)量、棧大小觀察它們的變化是否符合預(yù)期。如果發(fā)現(xiàn) LIR 數(shù)量持續(xù)增長不下降或者 HIR 棧大小無限增長基本就是上面三個坑之一。4.2 性能開銷太大用這三個優(yōu)化手段LIRS 的理論復(fù)雜度比 LRU 高因?yàn)槊看卧L問都要更新兩個棧還要做 IRR 判斷。如果實(shí)現(xiàn)不當(dāng)性能可能比 LRU 慢好幾倍。我實(shí)測下來優(yōu)化前 LIRS 的 QPS 只有 LRU 的 40%優(yōu)化后能達(dá)到 LRU 的 85% 左右。三個關(guān)鍵優(yōu)化手段優(yōu)化一用位圖代替鏈表遍歷。判斷一個塊在 LIR 棧還是 HIR 棧不需要遍歷鏈表只需要在塊上維護(hù)一個is_lir標(biāo)志位。這樣判斷是 O(1) 的。優(yōu)化二延遲剪枝。不要每次訪問都剪枝而是累計(jì)到一定次數(shù)后再剪。我設(shè)置的是每 100 次訪問剪一次性能提升明顯命中率幾乎不受影響。優(yōu)化三用近似 IRR 代替精確 IRR。精確計(jì)算 IRR 需要遍歷訪問序列開銷很大。實(shí)際實(shí)現(xiàn)時可以用“塊被訪問的次數(shù)”作為 IRR 的近似。訪問次數(shù)越多IRR 越小。這個近似在大多數(shù)場景下足夠準(zhǔn)確。優(yōu)化手段性能提升命中率影響實(shí)現(xiàn)難度位圖標(biāo)志30%無低延遲剪枝25%小于 1%低近似 IRR20%小于 2%中4.3 LIRS 與 LRU、LFU、ARC 的選型對比最后說一下選型。LIRS 不是萬能的它有自己的適用場景。我把常見的幾種淘汰策略放在一起對比策略抗掃描抗突發(fā)實(shí)現(xiàn)復(fù)雜度內(nèi)存開銷適用場景LRU差好低低訪問均勻、無掃描LFU好差中中熱點(diǎn)穩(wěn)定、無突發(fā)LIRS好好高中熱點(diǎn)掃描混合ARC好好中中通用場景從表里可以看出LIRS 和 ARC 的能力最全面但 LIRS 的實(shí)現(xiàn)復(fù)雜度最高。如果你追求極致的抗掃描能力且團(tuán)隊(duì)有足夠的工程能力LIRS 是值得的。如果你想要一個更平衡的方案ARC 可能是更好的選擇。如果你的業(yè)務(wù)幾乎沒有掃描流量那 LRU 就夠了沒必要上 LIRS。我個人在實(shí)際操作中的體會是LIRS 的價值在“混合負(fù)載”場景下才能體現(xiàn)。如果你的系統(tǒng)只有一種訪問模式用 LIRS 就是殺雞用牛刀。但如果你同時有在線交易和離線分析兩種流量LIRS 能幫你省下大量數(shù)據(jù)庫查詢。我見過一個系統(tǒng)從 LRU 切到 LIRS 后緩存命中率從 70% 提升到 92%數(shù)據(jù)庫 QPS 下降了 60%效果非常明顯。注意切換淘汰策略是有風(fēng)險的建議先在灰度環(huán)境驗(yàn)證觀察命中率、延遲、內(nèi)存占用三個指標(biāo)確認(rèn)穩(wěn)定后再全量。4.4 一個容易被忽略的細(xì)節(jié)冷熱數(shù)據(jù)的邊界維護(hù)LIRS 里還有一個容易被忽略的細(xì)節(jié)冷熱數(shù)據(jù)的邊界不是固定的而是隨著訪問模式動態(tài)移動的。這意味著你不能簡單地用一個閾值來劃分 LIR 和 HIR而必須讓它們通過“升級-降級”機(jī)制自動調(diào)整。我踩過的一個坑是早期實(shí)現(xiàn)時我設(shè)置了一個固定的 LIR 大小比如緩存容量的 90%然后就不管了。結(jié)果發(fā)現(xiàn)當(dāng)業(yè)務(wù)熱點(diǎn)突然增多時LIR 不夠用很多熱數(shù)據(jù)被擠到 HIR然后被淘汰當(dāng)業(yè)務(wù)熱點(diǎn)減少時LIR 又太空浪費(fèi)了緩存空間。正確的做法是讓 LIR 大小動態(tài)變化但設(shè)置上下限。下限可以設(shè)為緩存容量的 50%保證基本的熱數(shù)據(jù)保護(hù)上限可以設(shè)為 95%防止 HIR 被完全擠占。在這個范圍內(nèi)LIR 根據(jù)升級和降級的頻率自動伸縮。具體實(shí)現(xiàn)時可以維護(hù)一個lir_target變量每次升級 HIR 塊時lir_target 1每次降級 LIR 塊時lir_target - 1然后限制在[0.5*capacity, 0.95*capacity]范圍內(nèi)。這樣 LIR 就能跟隨訪問模式自動調(diào)整。這個細(xì)節(jié)在學(xué)術(shù)論文里往往一筆帶過但在工程實(shí)現(xiàn)里非常關(guān)鍵。我見過好幾個 LIRS 實(shí)現(xiàn)因?yàn)楹雎粤诉@一點(diǎn)導(dǎo)致在真實(shí)負(fù)載下表現(xiàn)不穩(wěn)定。5. 從理論到生產(chǎn)LIRS 的落地建議5.1 什么情況下值得上 LIRS不是所有項(xiàng)目都需要 LIRS。我建議你先問自己三個問題第一你的緩存命中率是否對業(yè)務(wù)有顯著影響如果緩存命中率下降 10% 只是讓延遲增加幾毫秒那沒必要折騰。但如果命中率下降會導(dǎo)致數(shù)據(jù)庫過載、服務(wù)雪崩那就值得投入。第二你的訪問模式是否包含掃描或突發(fā)如果你的業(yè)務(wù)是穩(wěn)定的點(diǎn)查沒有批量掃描那 LRU 足夠。但如果你有離線任務(wù)、報表查詢、爬蟲抓取等會沖刷緩存的流量LIRS 的價值就體現(xiàn)出來了。第三你的團(tuán)隊(duì)是否有能力維護(hù)復(fù)雜的緩存邏輯LIRS 的實(shí)現(xiàn)和調(diào)優(yōu)需要一定的工程能力。如果團(tuán)隊(duì)人手緊張用成熟的 ARC 或者帶權(quán)重的 LRU 可能更務(wù)實(shí)。我的經(jīng)驗(yàn)是日請求量在千萬級以上、且存在明顯冷熱數(shù)據(jù)分層的系統(tǒng)上 LIRS 的收益最明顯。小系統(tǒng)用 LRU 就夠了過早優(yōu)化反而增加維護(hù)成本。5.2 灰度上線與效果驗(yàn)證方法如果你決定上 LIRS不要一次性全量替換。我推薦的做法是第一步雙寫雙讀。同時維護(hù) LRU 和 LIRS 兩個緩存讀請求先查 LIRS未命中再查 LRU然后異步回填 LIRS。這樣即使 LIRS 有問題也不會影響線上服務(wù)。第二步對比命中率。跑一周后對比兩個緩存的命中率曲線。如果 LIRS 命中率穩(wěn)定高于 LRU 5 個百分點(diǎn)以上說明有效。第三步逐步切流。從 1% 流量開始逐步增加到 10%、50%、100%。每次增加后觀察 24 小時確認(rèn)沒有異常再繼續(xù)。第四步保留回滾能力。即使全量后也要保留一鍵切回 LRU 的能力。緩存策略的切換不應(yīng)該影響業(yè)務(wù)可用性。驗(yàn)證指標(biāo)方面我建議重點(diǎn)關(guān)注三個緩存命中率、P99 延遲、后端數(shù)據(jù)庫 QPS。命中率上升、延遲下降、數(shù)據(jù)庫 QPS 下降說明 LIRS 生效了。如果命中率上升但延遲也上升說明 LIRS 的計(jì)算開銷太大需要優(yōu)化實(shí)現(xiàn)。5.3 后續(xù)擴(kuò)展方向從 LIRS 到自適應(yīng)緩存LIRS 本身已經(jīng)很強(qiáng)了但它還有一個可以改進(jìn)的地方參數(shù)是靜態(tài)的。LIR 比例、剪枝閾值這些參數(shù)一旦設(shè)定就不會自動調(diào)整。如果業(yè)務(wù)訪問模式發(fā)生長期變化LIRS 可能不再是最優(yōu)的。一個自然的擴(kuò)展方向是自適應(yīng)緩存也就是讓緩存根據(jù)實(shí)時命中率自動調(diào)整參數(shù)。比如如果發(fā)現(xiàn)命中率持續(xù)下降就自動降低 LIR 比例給新數(shù)據(jù)更多機(jī)會如果命中率穩(wěn)定就提高 LIR 比例加強(qiáng)熱數(shù)據(jù)保護(hù)。這個方向已經(jīng)有了一些研究成果比如基于強(qiáng)化學(xué)習(xí)的緩存策略、基于滑動窗口的自適應(yīng) ARC 等。如果你對 LIRS 已經(jīng)玩得很熟了可以往這個方向繼續(xù)探索。最后再分享一個小技巧在實(shí)現(xiàn) LIRS 時一定要加詳細(xì)的監(jiān)控埋點(diǎn)。記錄每次升級、降級、淘汰、剪枝的次數(shù)和原因這些數(shù)據(jù)在排查問題時非常有用。我當(dāng)初就是靠這些埋點(diǎn)才發(fā)現(xiàn)棧剪枝邏輯里有一個邊界條件寫錯了導(dǎo)致 5% 的塊被錯誤刪除。沒有埋點(diǎn)的話這種問題幾乎不可能定位。這個內(nèi)容后續(xù)還可以這樣擴(kuò)展把 LIRS 的思想應(yīng)用到分布式緩存中比如在一致性哈希的每個節(jié)點(diǎn)上獨(dú)立運(yùn)行 LIRS然后通過全局協(xié)調(diào)來優(yōu)化整體命中率。不過這又是另一個大話題了有機(jī)會再展開聊。