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