手寫LRU緩存算法這個(gè)話題網(wǎng)上已經(jīng)有很多版本了但大部分都停在用LinkedHashMap重寫一個(gè)removeEldestEntry的程度。我能理解面試或者日常開發(fā)里碰到緩存淘汰需求第一反應(yīng)就是找個(gè)現(xiàn)成的輪子。但如果你真的打算手寫一版LRU并且想把它寫明白、寫對、寫到能在生產(chǎn)環(huán)境里扛住壓力那這篇文章應(yīng)該能幫到你。我會從最基礎(chǔ)的場景說起講到HashMap加雙向鏈表的經(jīng)典實(shí)現(xiàn)再深入到幾個(gè)真正會讓人翻車的細(xì)節(jié)最后聊一些面試和工作里更進(jìn)階的思考比如熱點(diǎn)數(shù)據(jù)污染、多級緩存和并發(fā)安全。全程都是我自己寫過的代碼、踩過的坑不繞彎子。1. LRU緩存到底在解決什么問題1.1 一個(gè)真實(shí)場景緩存失效帶來的連鎖反應(yīng)先來說個(gè)實(shí)際場景。假設(shè)你在維護(hù)某個(gè)訂單查詢接口數(shù)據(jù)庫里存著幾千萬訂單數(shù)據(jù)用戶端會高頻查詢最近半小時(shí)的訂單狀態(tài)。最開始你直接查庫QPS一上去數(shù)據(jù)庫連接池就告警了慢查詢?nèi)罩纠锶峭粭lSQL。然后你引入了緩存把最近查過的訂單放進(jìn)去。緩存一上接口P99從800ms降到了50ms效果立竿見影。但問題來了緩存空間是有限的不可能把所有訂單都放在內(nèi)存里。當(dāng)緩存滿了新數(shù)據(jù)要進(jìn)來就得有人出去。誰出去這就是淘汰策略的職責(zé)。最樸素的思路是先進(jìn)先出FIFO誰先進(jìn)來誰先走。但你很快發(fā)現(xiàn)這有問題某個(gè)訂單雖然是很早之前查過一次但它其實(shí)仍然在被高頻查詢只是查詢頻率是間歇性的。如果它進(jìn)來了卻被FIFO無情淘汰下一次訪問就會再次穿透到數(shù)據(jù)庫。LRULeast Recently Used最近最少使用的思路就是當(dāng)一個(gè)數(shù)據(jù)被訪問過就把它標(biāo)記為最近使用當(dāng)緩存滿優(yōu)先淘汰那些最久沒被訪問的數(shù)據(jù)。它解決的核心問題是把有限的內(nèi)存資源優(yōu)先留給那些近期活躍的數(shù)據(jù)。1.2 怎樣理解最近最少使用這個(gè)定義LRU的淘汰依據(jù)不是使用次數(shù)而是距離現(xiàn)在的時(shí)間間隔。你可以把它想象成一個(gè)原始的登記表每個(gè)數(shù)據(jù)進(jìn)來時(shí)在表上蓋一個(gè)時(shí)間戳每次被訪問時(shí)間戳刷新成當(dāng)前時(shí)間淘汰時(shí)掃描整張表找到時(shí)間戳最舊的那條刪掉。這個(gè)邏輯用直覺就能理解但如果真用每次訪問都更新時(shí)間戳、淘汰時(shí)全表掃描的方式實(shí)現(xiàn)性能會非常糟糕。訪問一次的時(shí)間復(fù)雜度是O(n)緩存越大越慢根本扛不住高并發(fā)。所以工程上幾乎不會用時(shí)間戳方案。真正普遍采用的數(shù)據(jù)結(jié)構(gòu)組合是哈希表加雙向鏈表哈希表負(fù)責(zé)O(1)地定位數(shù)據(jù)是否存在、數(shù)據(jù)在鏈表哪個(gè)節(jié)點(diǎn)雙向鏈表負(fù)責(zé)維護(hù)訪問時(shí)間順序最近訪問的節(jié)點(diǎn)在鏈表頭部最久未訪問的在尾部。你的每一次訪問核心動作就兩個(gè)把被訪問的節(jié)點(diǎn)摘下來、再掛到鏈表頭部。淘汰時(shí)直接刪除鏈表尾部節(jié)點(diǎn)就行。全部操作都是O(1)。這個(gè)組合是整個(gè)LRU實(shí)現(xiàn)的靈魂也是手寫時(shí)最應(yīng)該先想清楚的部分。2. 最容易跑偏的初版實(shí)現(xiàn)為什么能用不等于夠用2.1 用數(shù)組維護(hù)訪問時(shí)間的版本很多第一次手寫LRU的人都會先寫一個(gè)直觀版用一個(gè)Map存key和value用一個(gè)數(shù)組或者List存key的訪問順序。訪問某個(gè)key時(shí)先把key從數(shù)組里刪掉再把它放到數(shù)組末尾淘汰時(shí)取數(shù)組第一個(gè)元素刪掉。這樣寫起來確實(shí)很快二十分鐘就能跑通功能。如果面試官只問講講你LRU怎么實(shí)現(xiàn)的這個(gè)版本勉強(qiáng)也能說。但一旦被問到get和put的時(shí)間復(fù)雜度是多少就露餡了。從數(shù)組中間刪除一個(gè)元素需要把后續(xù)元素全部往前移動一位這是O(n)。當(dāng)緩存容量是幾千甚至幾萬時(shí)刪除操作會變成性能瓶頸。我見過有人用ArrayList然后調(diào)remove(key)在容量1萬、每秒幾百次寫操作的情況下接口RT直接翻了好幾倍。另一個(gè)隱蔽問題是并發(fā)。ArrayList本身線程不安全如果同一個(gè)緩存實(shí)例被多個(gè)線程同時(shí)訪問刪除和插入操作會造成數(shù)據(jù)覆蓋、元素丟失甚至ArrayIndexOutOfBounds。網(wǎng)上很多demo級別代碼根本不考慮這個(gè)但你在真實(shí)項(xiàng)目里敢這么用線上遲早會給你顏色看。2.2 為什么能用和夠用差距那么大手寫LRU很容易寫出功能正確但性能不合格的版本問題就出在對操作復(fù)雜度的理解上。你需要對每個(gè)操作都問一句它是不是O(1)查詢一個(gè)key是否存在O(1)用HashMap。把一個(gè)節(jié)點(diǎn)從當(dāng)前位置移到鏈表頭部O(1)前提是你直接持有這個(gè)節(jié)點(diǎn)的引用而不是遍歷鏈表去找它。淘汰最久未使用的節(jié)點(diǎn)O(1)刪除尾部節(jié)點(diǎn)本身很快關(guān)鍵是能O(1)地拿到這個(gè)節(jié)點(diǎn)對應(yīng)的key從而同步刪除HashMap里的映射。第二條是重點(diǎn)。很多實(shí)現(xiàn)里把節(jié)點(diǎn)移到頭部靠的是先刪除再重新遍歷鏈表這就是O(n)的來源。正確做法是用HashMap記錄key到節(jié)點(diǎn)Node的映射節(jié)點(diǎn)持有prev和next兩個(gè)指針。拿到引用之后摘除和插入都是指針操作沒有任何遍歷。這個(gè)設(shè)計(jì)理念可以延伸到很多場景。比如你做熱更新配置、做任務(wù)調(diào)度器的超時(shí)管理凡是需要快速定位某個(gè)元素 按順序淘汰的組合幾乎都可以套用哈希表加鏈表的結(jié)構(gòu)。LRU手寫一遍真正練的是這種思考方式而不僅僅是背一道面試題。3. HashMap加雙向鏈表的經(jīng)典組合核心實(shí)現(xiàn)拆解3.1 數(shù)據(jù)結(jié)構(gòu)選型背后的邏輯在動手寫代碼前先把三個(gè)角色想清楚Cache接口對外暴露get和put兩個(gè)方法。Node節(jié)點(diǎn)鏈表的基本單元包含key、value、prev、next四個(gè)字段。LRUCache類內(nèi)部持有一個(gè)HashMap和一個(gè)雙向鏈表HashMap的value類型直接設(shè)置為Node節(jié)點(diǎn)。為什么要用雙向鏈表而不是單向鏈表未經(jīng)深思熟慮的選擇——如果用一個(gè)HashMap維護(hù)key到節(jié)點(diǎn)的映射那么把某個(gè)節(jié)點(diǎn)移到頭部時(shí)按照單向鏈表你要把它的前驅(qū)節(jié)點(diǎn)的next指針指向當(dāng)前節(jié)點(diǎn)的next。問題是單向鏈表不知道前驅(qū)是誰你得從頭遍歷才能找到前驅(qū)。雙向鏈表天生就能通過node.prev拿到前驅(qū)摘除節(jié)點(diǎn)這一步就變成了O(1)。這是雙向鏈表在手寫LRU中幾乎不可替代的原因。3.2 逐段拆解一個(gè)可直接運(yùn)行的版本以下是Java實(shí)現(xiàn)。不用第三方依賴純JDK就能跑。import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { private static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; Node(K key, V value) { this.key key; this.value value; } } private final int capacity; private final MapK, NodeK, V map; private final NodeK, V head; private final NodeK, V tail; public LRUCache(int capacity) { if (capacity 1) { throw new IllegalArgumentException(capacity must be positive); } this.capacity capacity; this.map new HashMap(capacity); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } // 訪問過的節(jié)點(diǎn)移到鏈表頭部 moveToHead(node); return node.value; } public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() capacity) { NodeK, V tailNode removeTail(); map.remove(tailNode.key); } } private void addToHead(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, V result tail.prev; removeNode(result); return result; } }這段代碼是我在實(shí)際項(xiàng)目里用過的精簡版。邏輯核心就是四段初始化虛擬節(jié)點(diǎn)、get時(shí)移動、put時(shí)插頭、容量超限時(shí)刪尾。3.3 為什么引入虛擬頭尾節(jié)點(diǎn)這里有個(gè)很實(shí)用的細(xì)節(jié)在雙向鏈表里聲明兩個(gè)哨兵節(jié)點(diǎn)head和tail。一個(gè)表示鏈表頭部一個(gè)表示鏈表尾部但實(shí)際上它們不存儲任何業(yè)務(wù)數(shù)據(jù)。哨兵節(jié)點(diǎn)的好處是不管鏈表是空的、只有一個(gè)節(jié)點(diǎn)、還是有很多節(jié)點(diǎn)頭部插入和尾部刪除的指針操作代碼都完全一樣。不需要再寫特判邏輯來處理如果鏈表為空怎么辦這類分支。如果沒有哨兵節(jié)點(diǎn)頭插和尾刪都得判斷head、tail是否為null代碼會多出一堆分支不說還特別容易在邊界狀態(tài)下出錯(cuò)。我見過不少初版實(shí)現(xiàn)最后崩潰都發(fā)生在緩存里只有一個(gè)元素的時(shí)候。哨兵節(jié)點(diǎn)直接把這個(gè)坑填平了。4. 手寫過程中最容易翻車的幾個(gè)細(xì)節(jié)4.1 容量邊界的差一錯(cuò)誤容量邊界是手寫LRU時(shí)最經(jīng)典的問題。核心判斷是map.size() capacity還是map.size() capacity還是一次寫入時(shí)要先插后刪還是先刪后插假設(shè)容量是3當(dāng)前map里已經(jīng)有3個(gè)元素?，F(xiàn)在put一個(gè)新key。如果寫的是if (map.size() capacity) { removeTail(); }那就意味著只要達(dá)到容量上限就先刪一個(gè)再插入。表面看沒什么問題但如果你剛開始緩存還不滿比如現(xiàn)在只有2個(gè)元素put第3個(gè)時(shí)map.size() capacity成立會把最老的還沒被淘汰的節(jié)點(diǎn)刪掉再插新節(jié)點(diǎn)。結(jié)果容量永遠(yuǎn)用不滿。正確做法是先插入后判斷是否超容量判斷條件用map.size() capacity只刪多出來的那一個(gè)。這也是上面代碼里的寫法。如果先把某個(gè)節(jié)點(diǎn)刪掉再插入也是一樣的結(jié)果只是要小心刪除之前別忘了把對應(yīng)的map映射也刪掉。4.2 更新已有key時(shí)的順序問題當(dāng)put一個(gè)已經(jīng)存在的key時(shí)有兩個(gè)動作要做更新value、把節(jié)點(diǎn)移到頭部。我見過有人寫先刪掉舊節(jié)點(diǎn)再new一個(gè)新節(jié)點(diǎn)重新插入。這樣做功能沒問題但白白多了一次節(jié)點(diǎn)對象分配和一次指針摘除操作在高頻更新場景下會產(chǎn)生不必要的GC壓力。更優(yōu)雅的方式直接復(fù)用原節(jié)點(diǎn)找到節(jié)點(diǎn)修改value然后移動節(jié)點(diǎn)位置。整個(gè)過程中節(jié)點(diǎn)在鏈表里的鄰居關(guān)系不變只是當(dāng)前節(jié)點(diǎn)被摘除再插到頭部。對應(yīng)的更新value之后不需要重新put到map因?yàn)閙ap里存的引用本來就是同一個(gè)節(jié)點(diǎn)對象value是節(jié)點(diǎn)內(nèi)部的字段。有人會問如果我把value改成新值但map里沒動會不會出現(xiàn)map里的node和鏈表里的node不是同一個(gè)在正確實(shí)現(xiàn)中不會。map的value就是鏈表節(jié)點(diǎn)的引用兩者始終指向同一個(gè)對象。如果你在任何一處重新new了Node而忘記更新map就會出現(xiàn)這種幽靈節(jié)點(diǎn)——鏈表里有個(gè)節(jié)點(diǎn)但map根本查不到它或者map指向的節(jié)點(diǎn)已經(jīng)不在鏈表里了。4.3 鏈表自環(huán)與引用丟失還有一個(gè)特別隱蔽的bug在removeNode和addToHead里如果指針更新的順序不對鏈表會自環(huán)。比如在addToHead里如果你先執(zhí)行head.next node再執(zhí)行head.next.prev node此時(shí)head.next已經(jīng)變成新節(jié)點(diǎn)了所以node.prev指向了node自己。沒錯(cuò)節(jié)點(diǎn)自己指向自己鏈表直接死循環(huán)。正確順序是先處理新節(jié)點(diǎn)自己的prev和next再更新前驅(qū)和后繼的指針。也就是node.prev head; node.next head.next; head.next.prev node; head.next node;這個(gè)順序的要點(diǎn)是先把新節(jié)點(diǎn)的指針都安排好再去碰鏈條上的其他節(jié)點(diǎn)。一旦你動了head.next后面引用head.next.prev時(shí)拿到的是新節(jié)點(diǎn)自己而不是原來的第一個(gè)業(yè)務(wù)節(jié)點(diǎn)。這類bug在功能測試階段很難暴露因?yàn)殒湵碜原h(huán)后正常的插入、查詢、淘汰流程可能還能跑一陣子直到某個(gè)操作遍歷到死循環(huán)才會卡住。想快速定位的話調(diào)試時(shí)直接打印鏈表長度發(fā)現(xiàn)它和map.size()對不上基本就鎖定問題在指針操作上。5. 進(jìn)階思考一只保留訪問順序還不夠如何防止緩存被熱點(diǎn)污染5.1 LRU的固有短板LRU雖然經(jīng)典但有明顯的短板它只關(guān)注最近是否被訪問不關(guān)注被訪問的頻率。極端情況下一個(gè)熱點(diǎn)key在短時(shí)間內(nèi)被高頻訪問之后就不再訪問了而另一個(gè)key訪問頻率不高但一直穩(wěn)定地每隔一會訪問一次。在LRU的視角里熱點(diǎn)key因?yàn)樽罱辉L問過會一直留在緩存里而那個(gè)穩(wěn)定的低頻key反而可能被淘汰。這在業(yè)務(wù)上有個(gè)很直觀的場景某個(gè)秒殺活動開始后活動商品id被瞬間刷爆大量進(jìn)入緩存活動結(jié)束這些商品再也不被訪問但它們霸占了緩存空間把其他正常業(yè)務(wù)的緩存全擠出去了。這就是緩存污染問題。緩存的命中率會明顯下降數(shù)據(jù)庫壓力反而上升。針對這個(gè)場景最簡單的策略之一是給緩存項(xiàng)設(shè)置過期時(shí)間而且這個(gè)過期時(shí)間不能用固定值而是要根據(jù)業(yè)務(wù)類型分成幾檔。比如熱點(diǎn)數(shù)據(jù)給30秒普通數(shù)據(jù)給5分鐘。再配合LRU本身容量淘汰可以緩解大部分污染問題。5.2 LFU和LRU的取舍LFULeast Frequently Used最近最不常使用用訪問次數(shù)代替訪問時(shí)間作為淘汰依據(jù)。對于上面秒殺場景LFU可能表現(xiàn)更好因?yàn)樵L問頻率高的key會一直待著。但LFU也有自己的問題一個(gè)key曾經(jīng)被猛烈訪問過之后冷下來了但因?yàn)闅v史計(jì)數(shù)很高它會一直賴在緩存里不走。LRU天然會把它洗掉LFU卻不一定。所以在實(shí)際系統(tǒng)里L(fēng)RU和LFU都不是銀彈。很多框架會做折中比如Redis的近似LRU加上volatile-lfu策略允許用戶根據(jù)場景選擇。在你手寫算法時(shí)也要想清楚時(shí)間維度和頻率維度哪種更適合你的業(yè)務(wù)流量特征。5.3 LRU-K的近似實(shí)現(xiàn)思路如果面試被問到如何改進(jìn)LRU一個(gè)很好的回答方向是LRU-K。簡單說LRU-K記錄每個(gè)key的最近K次訪問時(shí)間只有當(dāng)訪問次數(shù)達(dá)到K次才把key放進(jìn)真正的LRU緩存。這樣偶爾一兩次的冷訪問不會立刻把數(shù)據(jù)帶進(jìn)緩存能有效過濾掉低質(zhì)量的訪問流量。而一個(gè)真正會被高頻訪問的數(shù)據(jù)會盡快通過K次閾值進(jìn)入緩存。實(shí)現(xiàn)LRU-K并不需要完整再寫一套?？梢圆鸪蓛蓚€(gè)階段第一階段是歷史訪問記錄用一個(gè)容量小得多的LRU只記錄key和時(shí)間不存value第二階段才是真正的緩存放value。當(dāng)?shù)谝浑A段某個(gè)key被訪問超過K次就把value寫入第二階段。這個(gè)方案對內(nèi)存的額外開銷很小但能明顯提升緩存命中率適合讀多寫少、訪問模式相對穩(wěn)定的業(yè)務(wù)。6. 進(jìn)階思考二工程落地時(shí)的并發(fā)、一致性與成本6.1 并發(fā)安全從加鎖到分段鎖上面那段代碼嚴(yán)格來說是單線程版本。真實(shí)項(xiàng)目里緩存必然被多個(gè)線程共享。最簡單的做法是給get和put加synchronized但這樣會引入全局鎖競爭。當(dāng)一個(gè)線程正在執(zhí)行耗時(shí)較長的淘汰操作時(shí)其他所有線程的get都得排隊(duì)。更好的思路是使用ConcurrentHashMap來存儲映射再配合一個(gè)顯式鎖來保護(hù)鏈表的修改操作。因?yàn)間et操作需要修改鏈表移動到頭部所以不能只靠ConcurrentHashMap自身保證線程安全還是需要鎖但鎖的粒度可以細(xì)一些。我見過一種工程上比較平衡的做法使用ReentrantReadWriteLock讀操作get獲取讀鎖寫操作put獲取寫鎖。在讀多寫少的緩存場景中讀鎖可以并發(fā)持有只有put才串行性能比全局synchronized好不少。代價(jià)是代碼復(fù)雜度上升鎖的獲取與釋放要格外小心避免死鎖。6.2 緩存與數(shù)據(jù)庫的一致性問題手寫LRU只是解決了緩存里放什么、滿了淘汰誰的問題但還有一個(gè)更難的問題淘汰之后如果緩存再被訪問怎么保證拿到的是最新的數(shù)據(jù)常見做法是旁路緩存Cache-Aside模式讀時(shí)先查緩存未命中再查數(shù)據(jù)庫并把結(jié)果寫入緩存寫時(shí)先更新數(shù)據(jù)庫再刪除緩存。刪除不是直接更新緩存是很多團(tuán)隊(duì)踩過坑之后總結(jié)出來的經(jīng)驗(yàn)——直接更新緩存會有并發(fā)寫導(dǎo)致的數(shù)據(jù)不一致刪除緩存則會強(qiáng)迫下一次讀去數(shù)據(jù)庫拉最新值。這里面還有一個(gè)坑刪除緩存失敗怎么辦很多系統(tǒng)引入消息隊(duì)列做異步重試在數(shù)據(jù)庫寫完binlog后由消費(fèi)端去刪除對應(yīng)緩存。如果binlog消費(fèi)有延遲可能會短暫出現(xiàn)緩存里還是舊值的情況。這個(gè)問題沒有銀彈只能在實(shí)時(shí)性和一致性之間做取舍。6.3 多級緩存與淘汰策略的成本權(quán)衡最后聊一點(diǎn)工程視野。真正的生產(chǎn)環(huán)境通常不是單層緩存。CPU有L1/L2/L3本地有堆內(nèi)緩存下面還有Redis這一類集中式緩存再下面才是數(shù)據(jù)庫。每一層都有不同的訪問速度和容量成本淘汰策略的選擇也不一樣。在堆內(nèi)緩存這一層我們可以用LRU或者LRU-K控制內(nèi)存占用容量一般很小幾十到幾百M(fèi)B級在Redis這一層雖然容量更大但仍然有限需要配置maxmemory和淘汰策略。不同數(shù)據(jù)的重要性和訪問QPS差異很大因此還可以在業(yè)務(wù)代碼里給緩存項(xiàng)設(shè)置不同的等級等級高的用獨(dú)立緩存實(shí)例或獨(dú)立Redis避免被其他數(shù)據(jù)擠掉。有意思的是在Java生態(tài)里L(fēng)inkedHashMap本身就實(shí)現(xiàn)了LRU的大部分能力它內(nèi)部維護(hù)了雙向鏈表accessOrder設(shè)為true時(shí)每次get會觸發(fā)afterNodeAccess把節(jié)點(diǎn)移到鏈表尾部。你只需要重寫removeEldestEntry就能得到一個(gè)可用的LRU。但真正的面試題往往要求你手動實(shí)現(xiàn)原因就是考察你對指針操作、邊界條件、復(fù)雜度分析的掌握程度。把這些基本功練扎實(shí)了寫一遍LRU再去做緩存框架的二次開發(fā)或者去閱讀Redis、Caffeine這類優(yōu)秀開源項(xiàng)目的源碼會順暢很多。我在實(shí)際寫這一段代碼并拿去壓測時(shí)最大的體會是LRU看著簡單但要寫得有質(zhì)量核心不在于鏈表操作本身而在于對每一個(gè)操作復(fù)雜度的敏感度以及對緩存策略選擇背后業(yè)務(wù)語義的理解。如果你也被要求寫一個(gè)LRU別急著背代碼先想想業(yè)務(wù)方到底需要什么訪問模式再來設(shè)計(jì)你的數(shù)據(jù)結(jié)構(gòu)——這樣寫出來的才不是一個(gè)玩具。