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