1. 從緩存淘汰說起LRU 到底解決的是什么問題聊 LRU 之前我先講個(gè)特別接地氣的場(chǎng)景。你家里有個(gè)鞋柜只能放十雙鞋但你有一百雙鞋。每次出門穿哪雙脫下來就往柜子里塞。塞滿了怎么辦要么把最久沒穿過的那雙扔了要么把最近剛穿過的扔掉。正常人都會(huì)做第一個(gè)選擇——把最久沒碰過的清出去因?yàn)槟请p鞋大概率你近期也不需要了。LRU 算法Least Recently Used最近最少使用干的就是這么回事只不過它管的不是鞋是內(nèi)存里的數(shù)據(jù)。在計(jì)算機(jī)系統(tǒng)里內(nèi)存和緩存永遠(yuǎn)不夠用。CPU 有寄存器、L1/L2/L3 緩存容量一級(jí)比一級(jí)小、速度一級(jí)比一級(jí)快。操作系統(tǒng)管理物理內(nèi)存的時(shí)候不可能把所有進(jìn)程的數(shù)據(jù)都同時(shí)塞進(jìn)內(nèi)存條。數(shù)據(jù)庫查詢熱數(shù)據(jù)的時(shí)候也不可能把整張表都常駐內(nèi)存。這就必然引出一個(gè)問題當(dāng)緩存空間滿了新的數(shù)據(jù)要進(jìn)來得請(qǐng)誰出去這就是所謂的淘汰策略而 LRU 是這里面應(yīng)用最廣、也最經(jīng)得起實(shí)戰(zhàn)考驗(yàn)的一種。1.1 為什么是最近最少使用而不是別的淘汰策略其實(shí)有好幾種比較常見的還有 FIFO先進(jìn)先出和 LFU最不經(jīng)常使用。FIFO 顧名思義誰先進(jìn)來的誰先滾蛋簡單粗暴但它有個(gè)致命缺陷它不考慮數(shù)據(jù)的使用頻率。想象一個(gè)場(chǎng)景你在做一個(gè)網(wǎng)頁服務(wù)首頁的配置數(shù)據(jù)是訪問最頻繁的但它在系統(tǒng)啟動(dòng)時(shí)是最早加載的那批。如果按 FIFO 淘汰這個(gè)最熱的配置數(shù)據(jù)反而會(huì)最先被踢出去然后下次訪問又要重新加載然后又最早進(jìn)來又被最早踢出去——循環(huán)往復(fù)簡直災(zāi)難。LFU 是按訪問次數(shù)來淘汰聽起來更科學(xué)但它的問題在于歷史包袱。一個(gè)數(shù)據(jù)可能曾經(jīng)被訪問過一萬次但現(xiàn)在早就不用了LFU 還是會(huì)把它當(dāng)寶貝供著因?yàn)樗螖?shù)高。而且 LFU 需要給每個(gè)數(shù)據(jù)維護(hù)一個(gè)計(jì)數(shù)器開銷也不小。LRU 的哲學(xué)就很有意思了它賭的是局部性原理。什么意思就是如果一個(gè)數(shù)據(jù)剛剛被訪問過那么它在不久的將來被再次訪問的概率非常高。反過來如果一個(gè)數(shù)據(jù)很久沒被碰過了那它未來被訪問的概率就很低。這個(gè)假設(shè)在很多真實(shí)場(chǎng)景下都成立——你看視頻剛看過的片段可能還要回看你查數(shù)據(jù)庫同一批熱點(diǎn)商品數(shù)據(jù)會(huì)被反復(fù)查詢。所以 LRU 淘汰最久沒用過的實(shí)際上是在用最小代價(jià)保住最可能被用到的數(shù)據(jù)。注意LRU 的核心假設(shè)是訪問的時(shí)間局部性它不保證絕對(duì)最優(yōu)。如果你的訪問模式是隨機(jī)的、沒有局部性LRU 的命中率可能還不如一些更簡單的策略。所以在選型前先想清楚你的業(yè)務(wù)訪問模式。1.2 LRU 在真實(shí)系統(tǒng)里的位置你平時(shí)可能沒直接寫過 LRU但你幾乎每天都在用它。操作系統(tǒng)的頁面置換Linux 內(nèi)核里那一套 active/inactive 鏈表本質(zhì)就是 LRU 的變體MySQL 的 InnoDB Buffer Pool 用的近似 LRU通過分代優(yōu)化來避免全表掃描污染緩存Redis 的maxmemory-policy里就有allkeys-lru和volatile-lru兩種模式各種 HTTP 客戶端、CDN、瀏覽器緩存背后也都有 LRU 的影子。所以當(dāng)面試官問你手寫一個(gè) LRU的時(shí)候他不是在考你背書他是在看你對(duì)數(shù)據(jù)結(jié)構(gòu) 緩存思想的理解深度。這個(gè)題之所以經(jīng)典是因?yàn)樗浦阍跁r(shí)間復(fù)雜度和空間復(fù)雜度之間做權(quán)衡而做權(quán)衡恰恰是工程的核心。2. 核心設(shè)計(jì)拆解為什么必須是哈希表 雙向鏈表很多人第一次面對(duì)設(shè)計(jì)一個(gè) O(1) 的 LRU時(shí)會(huì)懵。直覺上我需要兩件事第一我要能快速找到某個(gè) key 對(duì)應(yīng)的數(shù)據(jù)在哪里查找快第二我要能快速知道誰是最久沒用的并且能快速把它刪掉、把新來的加進(jìn)去更新快。單靠一個(gè)數(shù)組不行刪除中間元素要移動(dòng)后面所有元素O(n)。單靠一個(gè)單向鏈表也不行你找到某個(gè)節(jié)點(diǎn)之后想把它移到鏈表頭但單向鏈表拿不到它的前驅(qū)節(jié)點(diǎn)還是要從頭遍歷O(n)。單靠一個(gè)哈希表更不行哈希表能讓你 O(1) 找到數(shù)據(jù)但它沒法告訴你誰最久沒用。所以答案就是組合拳哈希表負(fù)責(zé)找得到雙向鏈表負(fù)責(zé)排得序。2.1 哈希表在這里扮演什么角色哈希表在 Java 里是 HashMapPython 里是 dictC 里是 unordered_map存的是 key 到鏈表節(jié)點(diǎn)的映射。這里有個(gè)細(xì)節(jié)新手容易踩坑哈希表里存的 value 不是數(shù)據(jù)本身而是指向雙向鏈表節(jié)點(diǎn)的引用指針。為什么要這么設(shè)計(jì)因?yàn)楫?dāng)你要訪問某個(gè) key 的時(shí)候你希望 O(1) 就能定位到它在鏈表里的那個(gè)節(jié)點(diǎn)然后直接把這個(gè)節(jié)點(diǎn)從當(dāng)前位置摘下來移到鏈表頭部標(biāo)記為最近使用。如果你存的是數(shù)據(jù)值而不是節(jié)點(diǎn)引用你就得拿著 key 再去鏈表里遍歷找節(jié)點(diǎn)那又退化成 O(n) 了。實(shí)操心得很多教程圖省事哈希表直接存 value然后在淘汰時(shí)遍歷鏈表找最舊的那個(gè)——這在小數(shù)據(jù)量下看著沒問題一旦數(shù)據(jù)量上來性能直接崩盤。LRU 的精髓就在這個(gè)節(jié)點(diǎn)引用別省這一步。2.2 雙向鏈表為什么不是單向鏈表雙向鏈表在這里的職責(zé)是維護(hù)使用順序。我們約定靠近頭部的節(jié)點(diǎn)是最近使用的靠近尾部的節(jié)點(diǎn)是最久未使用的。訪問一個(gè)數(shù)據(jù)把對(duì)應(yīng)節(jié)點(diǎn)移到頭部。淘汰數(shù)據(jù)把尾部節(jié)點(diǎn)刪掉。插入新數(shù)據(jù)放到頭部。這里面有個(gè)關(guān)鍵動(dòng)作叫把任意節(jié)點(diǎn)移到頭部。如果鏈表是單向的你要?jiǎng)h除一個(gè)節(jié)點(diǎn)必須知道它的前驅(qū)節(jié)點(diǎn)而單向鏈表只能從頭往后找這就是 O(n) 的根源。雙向鏈表每個(gè)節(jié)點(diǎn)都有prev和next兩個(gè)指針不管這個(gè)節(jié)點(diǎn)在哪個(gè)位置你都能直接拿到它的前驅(qū)和后繼摘除和插入都是常數(shù)時(shí)間。為了代碼寫起來不惡心工業(yè)實(shí)現(xiàn)里通常會(huì)引入虛擬頭節(jié)點(diǎn)dummy head和虛擬尾節(jié)點(diǎn)dummy tail。這兩個(gè)節(jié)點(diǎn)不存真實(shí)數(shù)據(jù)只是哨兵。好處是你永遠(yuǎn)不用判斷是不是空鏈表是不是在頭部插入是不是在尾部刪除這些邊界情況所有操作都能用統(tǒng)一的邏輯處理代碼會(huì)干凈很多bug 也少很多。2.3 各操作的時(shí)間復(fù)雜度賬我們把賬算清楚操作做法時(shí)間復(fù)雜度查找 key哈希表定位O(1)訪問數(shù)據(jù)哈希表定位 鏈表節(jié)點(diǎn)移到頭部O(1)插入新數(shù)據(jù)存入哈希表 插入鏈表頭部O(1)淘汰數(shù)據(jù)刪除鏈表尾部節(jié)點(diǎn) 刪哈希表項(xiàng)O(1)空間復(fù)雜度哈希表 O(n) 鏈表 O(n)O(n)這就是 LRU 的精髓所在用額外的 O(n) 空間換取所有核心操作 O(1) 的時(shí)間。在緩存這個(gè)場(chǎng)景里空間本來就是要用來存數(shù)據(jù)的所以這份額外開銷哈希表存指針、鏈表節(jié)點(diǎn)存指針完全可以接受。2.4 為什么不用現(xiàn)成的有序結(jié)構(gòu)有人會(huì)問Java 里不是有LinkedHashMap嗎它可以設(shè)置accessOrdertrue天生就是 LRU。沒錯(cuò)LinkedHashMap底層就是哈希表 雙向鏈表和我們手寫的結(jié)構(gòu)一模一樣。那手寫還有什么意義第一你得理解它否則遇到需要定制版本比如加過期時(shí)間、加權(quán)重、加分段的時(shí)候你就抓瞎。第二LinkedHashMap的 LRU 是全局鎖的高并發(fā)下性能很差真到生產(chǎn)環(huán)境你往往需要自己實(shí)現(xiàn)一套帶分片加鎖或者無鎖的結(jié)構(gòu)。第三面試和筆試它是剛需躲不掉。所以我一直建議先手寫一遍理解原理再在合適的場(chǎng)景用現(xiàn)成實(shí)現(xiàn)需要性能時(shí)自己優(yōu)化。3. 手寫實(shí)現(xiàn)從零到可運(yùn)行的完整代碼光說不練假把式。我用 Python 寫一版最清晰的再給一版 C 的最后給一版 Java 用LinkedHashMap的極簡版方便不同語言的讀者直接抄作業(yè)。3.1 雙向鏈表節(jié)點(diǎn)的定義節(jié)點(diǎn)是基礎(chǔ)。我們把它設(shè)計(jì)得簡單點(diǎn)class Node: def __init__(self, key0, value0): self.key key # 存 key 是為了淘汰時(shí)能反查哈希表 self.value value self.prev None self.next None這里有個(gè)容易被忽略的細(xì)節(jié)節(jié)點(diǎn)里為什么要存 key因?yàn)樘蕴膊抗?jié)點(diǎn)的時(shí)候我們不僅要把這個(gè)節(jié)點(diǎn)從鏈表刪掉還要把哈希表里對(duì)應(yīng)的映射刪掉否則哈希表就會(huì)泄漏。要?jiǎng)h哈希表你就得有 key而尾部節(jié)點(diǎn)只有 value 沒有 key你就找不到哈希表里那項(xiàng)。所以節(jié)點(diǎn)必須存 key。這是新手最常踩的坑之一代碼跑起來發(fā)現(xiàn)數(shù)據(jù)對(duì)不上八成就是這里出了問題。3.2 完整 LRU 實(shí)現(xiàn)Python 版class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache {} # key - Node # 虛擬頭尾節(jié)點(diǎn)簡化邊界處理 self.head Node() self.tail Node() self.head.next self.tail self.tail.prev self.head def _remove(self, node): 把節(jié)點(diǎn)從鏈表中摘除 node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): 把節(jié)點(diǎn)插入到頭部最近使用的位置 node.next self.head.next node.prev self.head self.head.next.prev node self.head.next node def _move_to_head(self, node): self._remove(node) self._add_to_head(node) def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) return node.value def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) else: node Node(key, value) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: # 淘汰尾部節(jié)點(diǎn)最久未使用 lru self.tail.prev self._remove(lru) del self.cache[lru.key]這段代碼我建議你對(duì)著敲一遍尤其是_remove和_add_to_head這兩個(gè)操作里指針的順序。指針操作是 LRU 實(shí)現(xiàn)里最容易出 bug 的地方順序錯(cuò)了就會(huì)形成環(huán)或者斷鏈。操作禁忌寫指針操作的時(shí)候一定要遵循先接后斷的原則——先把新指針接好再斷開舊指針。上面_add_to_head里先設(shè)置node.next和node.prev再修改self.head.next.prev和self.head.next這個(gè)順序不能亂否則會(huì)丟失節(jié)點(diǎn)引用。3.3 關(guān)鍵步驟的現(xiàn)場(chǎng)推演我拿一組具體數(shù)據(jù)帶你把流程走一遍容量設(shè)為 2。初始狀態(tài)鏈表空head - tail。put(1, 1)新建節(jié)點(diǎn)1掛到頭部。鏈表變成head - 1 - tail哈希表{1: node1}。put(2, 2)新建節(jié)點(diǎn)2掛到頭部。鏈表變成head - 2 - 1 - tail哈希表{1: node1, 2: node2}。get(1)命中把節(jié)點(diǎn)1移到頭部。鏈表變成head - 1 - 2 - tail。返回 1。注意現(xiàn)在節(jié)點(diǎn)2變成了尾部也就是最舊的。put(3, 3)新建節(jié)點(diǎn)3此時(shí) size 會(huì)變成 3超過容量 2。先掛節(jié)點(diǎn)3到頭部鏈表變成head - 3 - 1 - 2 - tail然后淘汰尾部節(jié)點(diǎn)2刪鏈表和哈希表。最終head - 3 - 1 - tail哈希表{1: node1, 3: node3}。get(2)不在哈希表里返回 -1。正確因?yàn)?已經(jīng)被淘汰了。你把這幾步在紙上畫一畫整個(gè) LRU 的動(dòng)態(tài)就活了。很多人看代碼覺得懂了一畫圖發(fā)現(xiàn)理解是錯(cuò)的這就是為什么要?jiǎng)邮帧?.4 C 版本的核心骨架C 里用std::list和std::unordered_map組合最省事因?yàn)閟td::list天然支持 O(1) 的任意位置刪除和轉(zhuǎn)移。class LRUCache { private: int cap; std::liststd::pairint, int lst; // 頭部最新尾部最舊 std::unordered_mapint, std::liststd::pairint, int::iterator mp; public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { auto it mp.find(key); if (it mp.end()) return -1; // 把命中的節(jié)點(diǎn) splice 到頭部 lst.splice(lst.begin(), lst, it-second); return it-second-second; } void put(int key, int value) { auto it mp.find(key); if (it ! mp.end()) { it-second-second value; lst.splice(lst.begin(), lst, it-second); return; } if ((int)lst.size() cap) { int oldKey lst.back().first; lst.pop_back(); mp.erase(oldKey); } lst.emplace_front(key, value); mp[key] lst.begin(); } };這里splice是std::list的殺手锏它能把一個(gè)節(jié)點(diǎn)從鏈表的一個(gè)位置剪切到另一個(gè)位置而且不涉及內(nèi)存分配和拷貝純指針操作效率極高。很多人不知道這個(gè)函數(shù)用erase push_front雖然也對(duì)但多了一次節(jié)點(diǎn)構(gòu)造和析構(gòu)性能上有差距。實(shí)操心得C 的std::list迭代器在splice之后依然有效只要節(jié)點(diǎn)沒被銷毀所以哈希表里存的迭代器不用更新。這個(gè)特性是很多面試官想考察的點(diǎn)答對(duì)了加分。3.5 Java 一行搞定的方式如果你只是想快速用Java 的LinkedHashMap是標(biāo)準(zhǔn)答案重寫removeEldestEntry即可class LRUCache extends LinkedHashMapInteger, Integer { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder true 開啟 LRU 排序 this.capacity capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }注意構(gòu)造函數(shù)第三個(gè)參數(shù)accessOrder必須傳true默認(rèn)是false插入順序。這一點(diǎn)坑過無數(shù)人跑出來的行為是 FIFO 而不是 LRU還找不到原因。4. 進(jìn)階優(yōu)化真實(shí)生產(chǎn)環(huán)境里的 LRU 長什么樣標(biāo)準(zhǔn) LRU 在教科書里很美好但到了生產(chǎn)環(huán)境它有幾個(gè)硬傷。這一章我講講怎么把它改造成能扛住真實(shí)業(yè)務(wù)的版本這些內(nèi)容在普通教程里基本看不到。4.1 并發(fā)環(huán)境下的加鎖問題單線程 LRU 沒問題但 Redis 那種高并發(fā)場(chǎng)景多個(gè)線程同時(shí)讀寫鏈表不加鎖必崩。最粗暴的方案是給整個(gè) LRU 加一把大鎖但這樣所有讀操作都串行化吞吐量上不去。工業(yè)界的做法通常是分段鎖sharding把一個(gè)大的 LRU 拆成 N 個(gè)小 LRU每個(gè)小 LRU 一把鎖訪問時(shí)用 key 的哈希值決定去哪個(gè)分片。import threading class ShardedLRUCache: def __init__(self, capacity, shard_count16): self.shards [ (LRUCache(capacity // shard_count), threading.Lock()) for _ in range(shard_count) ] self.shard_count shard_count def get(self, key): idx hash(key) % self.shard_count cache, lock self.shards[idx] with lock: return cache.get(key) def put(self, key, value): idx hash(key) % self.shard_count cache, lock self.shards[idx] with lock: cache.put(key, value)這樣做的好處是只要 key 分布均勻并發(fā)沖突概率大大降低。代價(jià)是每個(gè)分片獨(dú)立淘汰整體上不是嚴(yán)格的 LRU但在這個(gè)量級(jí)下誤差可以忽略性能收益是值得的。注意分片數(shù)不是越多越好。分片太多鎖競爭是小了但內(nèi)存碎片、緩存局部性、管理開銷都會(huì)上升。實(shí)踐中一般取 2 的冪次16 或 32 是比較穩(wěn)的起點(diǎn)。4.2 近似 LRURedis 為什么不用嚴(yán)格 LRURedis 官方文檔里說得很清楚它用的是近似 LRUApproximate LRU。為什么因?yàn)榫S護(hù)一個(gè)嚴(yán)格的全局 LRU 鏈表每次訪問都要修改指針在高頻讀寫場(chǎng)景下這個(gè)鏈表操作本身就是巨大的開銷而且嚴(yán)重限制并發(fā)。Redis 的做法是每個(gè)對(duì)象存一個(gè)lru_clock時(shí)間戳精度是秒級(jí)或毫秒級(jí)淘汰的時(shí)候隨機(jī)采樣若干個(gè) key從中挑出最久未使用的那個(gè)淘汰。這樣不需要維護(hù)鏈表淘汰時(shí)也不影響讀寫主流程。采樣數(shù)量默認(rèn)是 5可以通過maxmemory-samples配置。采樣 5 個(gè)聽起來很粗糙但 Redis 官方做過壓測(cè)采樣 10 個(gè)的時(shí)候近似 LRU 的效果已經(jīng)和嚴(yán)格 LRU 非常接近了。這就是工程上的經(jīng)典取舍——用一點(diǎn)點(diǎn)精確性換來了巨大的性能提升和并發(fā)能力。4.3 LRU-K 與 2Q解決緩存污染標(biāo)準(zhǔn) LRU 有個(gè)著名的問題叫緩存污染cache pollution。舉個(gè)例子你做數(shù)據(jù)庫緩存突然來了一次全表掃描大量數(shù)據(jù)一次性涌入瞬間把原本熱點(diǎn)的數(shù)據(jù)全擠出去了。等全表掃描結(jié)束熱點(diǎn)數(shù)據(jù)全沒了緩存命中率斷崖式下跌。解決方案之一是LRU-K。它的思路是記錄每個(gè)數(shù)據(jù)最近的第 K 次訪問時(shí)間只有當(dāng)訪問次數(shù)達(dá)到 K 次時(shí)才認(rèn)為它是熱數(shù)據(jù)才允許進(jìn)入主緩存。這樣偶爾訪問一次的數(shù)據(jù)比如全表掃描的數(shù)據(jù)根本進(jìn)不來污染不了。2QTwo Queues是另一個(gè)思路維護(hù)兩個(gè)隊(duì)列一個(gè) FIFO 隊(duì)列用于過濾冷數(shù)據(jù)和一個(gè) LRU 隊(duì)列存熱數(shù)據(jù)。數(shù)據(jù)先進(jìn) FIFO被第二次訪問才移到 LRU。原理和 LRU-K 類似實(shí)現(xiàn)更簡單。算法核心思想適用場(chǎng)景代價(jià)標(biāo)準(zhǔn) LRU淘汰最久未使用訪問局部性強(qiáng)易被偶發(fā)大量訪問污染LRU-K訪問達(dá) K 次才入主緩存有明顯熱點(diǎn)、抗污染需維護(hù)訪問計(jì)數(shù)K 值難調(diào)2QFIFO 過濾 LRU 留存抗掃描污染結(jié)構(gòu)復(fù)雜內(nèi)存開銷大近似 LRU采樣淘汰高并發(fā)、海量 key精度略降實(shí)操心得K 值怎么選沒有萬能公式。太小比如 2過濾能力弱太大比如 5會(huì)導(dǎo)致新熱點(diǎn)遲遲進(jìn)不來。我一般從 2 開始試看命中率曲線找到拐點(diǎn)。這東西必須靠業(yè)務(wù)數(shù)據(jù)調(diào)別迷信理論值。4.4 給緩存加過期時(shí)間和權(quán)重真實(shí)業(yè)務(wù)里光有 LRU 不夠經(jīng)常還要疊加 TTL生存時(shí)間和權(quán)重。TTL 好理解每個(gè)節(jié)點(diǎn)加個(gè)過期時(shí)間戳get的時(shí)候先檢查是否過期過期就當(dāng)作未命中。但要注意TTL 的清理策略也有講究惰性刪除訪問時(shí)才檢查省 CPU 但浪費(fèi)內(nèi)存定期刪除后臺(tái)線程掃描占 CPU 但內(nèi)存干凈。Redis 用的是兩者結(jié)合。權(quán)重是另一個(gè)維度。假設(shè)你的緩存里既有小對(duì)象幾 KB又有大對(duì)象幾 MB單純按個(gè)數(shù)淘汰一個(gè)大對(duì)象可能占著很多空間卻只算一個(gè)名額這不合理。所以有些系統(tǒng)會(huì)引入基于大小的淘汰GDSF 等讓大對(duì)象在淘汰時(shí)權(quán)重大更容易被清出去。這些改造在校招面試?yán)锘静粫?huì)問但一旦你工作兩三年負(fù)責(zé)一個(gè)真實(shí)的緩存層這些就是你必須考慮的東西。我見過太多項(xiàng)目一開始用最簡單的 LRU跑著跑著內(nèi)存爆了、命中率崩了回過頭來才發(fā)現(xiàn)是沒考慮這些。5. 常見問題排查與踩坑實(shí)錄這一章是我自己這些年踩過的坑還有幫別人看代碼時(shí)遇到的典型問題。LRU 本身不難但細(xì)節(jié)特別多一不留神就翻車。5.1 高頻 Bug 速查表現(xiàn)象可能原因排查方向淘汰后數(shù)據(jù)還能查到淘汰時(shí)忘了刪哈希表 / 節(jié)點(diǎn)沒存 key檢查put里的 cleanup 邏輯命中率異常低accessOrder 沒開退化成 FIFO檢查構(gòu)造參數(shù)鏈表出現(xiàn)環(huán)死循環(huán)指針操作順序錯(cuò)誤檢查_remove和_add順序get之后淘汰錯(cuò)了對(duì)象沒有把命中節(jié)點(diǎn)移到頭部檢查get是否調(diào)用_move_to_head容量為 0 時(shí)報(bào)錯(cuò)沒處理邊界情況特判 capacity 0更新已存在的 key 沒生效只更新了哈希表沒更新節(jié)點(diǎn)檢查put的更新分支5.2 一個(gè)我真實(shí)踩過的坑節(jié)點(diǎn)沒存 key剛工作那會(huì)兒我寫了個(gè) LRU 用在接口緩存上測(cè)試環(huán)境跑得好好的一上預(yù)發(fā)就出問題緩存里已經(jīng)有 100 條了還在往里加看起來容量限制完全沒生效。查了半天才發(fā)現(xiàn)我淘汰尾部節(jié)點(diǎn)的時(shí)候只刪了鏈表節(jié)點(diǎn)沒刪哈希表里的映射。而判斷是否超容量是看哈希表大小所以哈希表一直在漲鏈表縮了但計(jì)數(shù)沒減兩邊對(duì)不上。這個(gè)坑的教訓(xùn)就是哈希表和鏈表是兩份必須同步的數(shù)據(jù)結(jié)構(gòu)任何一方的增刪都必須同步到另一方。后來我養(yǎng)成一個(gè)習(xí)慣把刪鏈表 刪哈希表封裝成一個(gè)原子方法永遠(yuǎn)成對(duì)調(diào)用不再分開寫。這個(gè)小重構(gòu)之后再?zèng)]犯過類似的錯(cuò)。5.3 命中率上不去的排查思路如果你發(fā)現(xiàn) LRU 命中率遠(yuǎn)低于預(yù)期別急著換算法先按這個(gè)順序排查第一確認(rèn)訪問模式有沒有局部性。如果業(yè)務(wù)本身就是隨機(jī)訪問海量 key那 LRU 天生就不適合換什么算法都白搭得考慮用別的方案或者加大容量。第二看有沒有緩存污染。抓一段時(shí)間的訪問日志看看是不是有周期性的批量掃描把熱點(diǎn)沖掉了。如果是上 LRU-K 或 2Q。第三檢查容量設(shè)置是否合理。容量太小怎么淘汰都不夠用。一般有個(gè)經(jīng)驗(yàn)值熱點(diǎn)數(shù)據(jù)的總大小乘以 1.5 到 2 倍是比較舒服的容量。第四確認(rèn) key 的粒度。有時(shí)候一個(gè)大 key 里塞了幾百個(gè)小字段訪問其中一個(gè)字段也要整個(gè)換入換出命中率自然低。這時(shí)候應(yīng)該考慮把 key 拆細(xì)。5.4 面試答題的加分點(diǎn)如果你是在準(zhǔn)備面試除了能寫出 O(1) 的代碼我建議你主動(dòng)聊這幾點(diǎn)面試官會(huì)覺得你真的理解而不是背題主動(dòng)說明為什么要用雙向鏈表而不是單向鏈表點(diǎn)出前驅(qū)指針的必要性。提一句虛擬頭尾節(jié)點(diǎn)簡化邊界處理。說出 LRU 基于時(shí)間局部性原理并說明它的局限。如果能順帶提到 Redis 用近似 LRU、MySQL 用分代 LRU那就是明顯加分。被問如果并發(fā)怎么辦答分段鎖并說明取舍。這些點(diǎn)我在面試別人的時(shí)候特別看重能把標(biāo)準(zhǔn)答案背出來的人很多能講清楚為什么這么設(shè)計(jì)什么場(chǎng)景不適用的人很少。最后再分享一個(gè)我自己調(diào) LRU 的小技巧加個(gè)命中率監(jiān)控埋點(diǎn)定期打日志。很多問題不是代碼錯(cuò)了是業(yè)務(wù)訪問模式變了而你還不知道。有了命中率曲線你就能第一時(shí)間發(fā)現(xiàn)異常早發(fā)現(xiàn)早處理比事后救火強(qiáng)太多。