1. 項(xiàng)目概述為什么我們需要LRU Cache在后臺(tái)服務(wù)、數(shù)據(jù)庫(kù)中間件或者高頻訪問(wèn)的Web應(yīng)用中我們經(jīng)常會(huì)遇到一個(gè)經(jīng)典問(wèn)題數(shù)據(jù)訪問(wèn)遵循“二八定律”即80%的請(qǐng)求往往集中在20%的數(shù)據(jù)上。如果每次請(qǐng)求都去訪問(wèn)相對(duì)緩慢的磁盤數(shù)據(jù)庫(kù)或進(jìn)行復(fù)雜的計(jì)算系統(tǒng)的響應(yīng)速度會(huì)急劇下降吞吐量也會(huì)遇到瓶頸。這時(shí)候一個(gè)高效的緩存機(jī)制就成了提升性能的關(guān)鍵。LRU Cache全稱“最近最少使用”緩存就是解決這個(gè)問(wèn)題的利器。它的核心思想非常直觀當(dāng)緩存空間滿了之后淘汰掉那個(gè)最久沒(méi)有被訪問(wèn)過(guò)的數(shù)據(jù)。這就像你書(shū)桌的桌面空間有限你總是把最近正在看的書(shū)放在手邊而把很久沒(méi)碰過(guò)的書(shū)放回書(shū)架。LRU算法完美契合了程序訪問(wèn)的局部性原理在實(shí)踐中被廣泛應(yīng)用從CPU緩存、操作系統(tǒng)頁(yè)面置換到Redis、Memcached等分布式緩存再到瀏覽器緩存都能看到它的身影。今天我們就來(lái)徹底拆解LRU Cache。我不會(huì)只給你一個(gè)干巴巴的原理描述而是會(huì)帶你從零開(kāi)始用C實(shí)現(xiàn)一個(gè)工業(yè)級(jí)強(qiáng)度的LRU緩存。我們會(huì)探討其背后的數(shù)據(jù)結(jié)構(gòu)選擇手把手實(shí)現(xiàn)核心操作并深入分析線程安全、性能優(yōu)化等實(shí)際工程中必須面對(duì)的挑戰(zhàn)。無(wú)論你是正在準(zhǔn)備系統(tǒng)設(shè)計(jì)面試還是希望優(yōu)化手頭的項(xiàng)目性能這篇文章都能給你提供可直接“抄作業(yè)”的解決方案和避坑指南。2. LRU Cache的核心原理與數(shù)據(jù)結(jié)構(gòu)選型2.1 LRU算法的工作機(jī)制LRU算法的行為規(guī)則可以用一句話概括訪問(wèn)提升滿則淘汰最舊。我們來(lái)模擬一下這個(gè)過(guò)程。假設(shè)我們有一個(gè)容量為3的LRU緩存存入 A。緩存[A]最新存入 B。緩存[B, A]B最新A次新訪問(wèn) A。因?yàn)锳被訪問(wèn)了它被提升到最新位置。緩存[A, B]存入 C。緩存[C, A, B]存入 D。此時(shí)緩存已滿容量為3需要淘汰最久未使用的數(shù)據(jù)也就是B。淘汰B后存入D。緩存[D, C, A]這個(gè)“最新”和“最舊”的順序必須被高效地維護(hù)。兩個(gè)核心操作get(key)和put(key, value)必須滿足以下時(shí)間復(fù)雜度要求get(key)如果key存在返回其值并將該key標(biāo)記為“最近使用”。O(1)時(shí)間復(fù)雜度。put(key, value)如果key存在更新其值并標(biāo)記為“最近使用”。如果不存在則插入。插入后若緩存超容則淘汰“最近最少使用”的key。O(1)時(shí)間復(fù)雜度。注意O(1)的時(shí)間復(fù)雜度是LRU緩存高效的關(guān)鍵。如果你用數(shù)組或單鏈表來(lái)維護(hù)順序get或put中的“移動(dòng)元素到最新位置”操作就可能需要O(n)的遍歷時(shí)間這在數(shù)據(jù)量大時(shí)是不可接受的。2.2 為什么是哈希表雙向鏈表要實(shí)現(xiàn)O(1)的查找和O(1)的插入/刪除/移動(dòng)單一的數(shù)據(jù)結(jié)構(gòu)很難勝任。這就需要經(jīng)典的組合拳哈希表HashMap 雙向鏈表Doubly Linked List。哈希表std::unordered_map負(fù)責(zé)實(shí)現(xiàn)O(1)時(shí)間復(fù)雜度的get操作。它通過(guò)key快速定位到對(duì)應(yīng)的緩存節(jié)點(diǎn)。雙向鏈表負(fù)責(zé)維護(hù)緩存項(xiàng)的“訪問(wèn)時(shí)序”。鏈表的頭部Head代表“最近使用”Most Recently Used, MRU尾部Tail代表“最近最少使用”Least Recently Used, LRU。當(dāng)一個(gè)節(jié)點(diǎn)被訪問(wèn)get或put更新時(shí)我們需要將它從鏈表中當(dāng)前位置刪除并重新插入到鏈表頭部。這個(gè)“刪除并插入頭部”的操作必須在O(1)時(shí)間內(nèi)完成。當(dāng)需要淘汰數(shù)據(jù)時(shí)我們直接刪除鏈表尾部的節(jié)點(diǎn)即可同樣是O(1)。這里的關(guān)鍵是哈希表存儲(chǔ)的值并不是簡(jiǎn)單的value而是指向鏈表中對(duì)應(yīng)節(jié)點(diǎn)的迭代器或指針。這樣通過(guò)key在哈希表中找到節(jié)點(diǎn)指針后我們就可以在O(1)時(shí)間內(nèi)操作鏈表節(jié)點(diǎn)了。為什么不使用單鏈表因?yàn)閯h除鏈表中的一個(gè)節(jié)點(diǎn)非頭尾節(jié)點(diǎn)需要知道它的前驅(qū)節(jié)點(diǎn)。單鏈表在只知道當(dāng)前節(jié)點(diǎn)指針的情況下無(wú)法快速找到前驅(qū)節(jié)點(diǎn)除非從頭遍歷。而雙向鏈表則可以直接通過(guò)prev指針找到前驅(qū)從而實(shí)現(xiàn)O(1)的節(jié)點(diǎn)刪除。數(shù)據(jù)結(jié)構(gòu)定義草圖// 鏈表節(jié)點(diǎn)定義 struct DLinkedNode { int key; int value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {} }; class LRUCache { private: std::unordered_mapint, DLinkedNode* cache; // 哈希表 key - 節(jié)點(diǎn)指針 DLinkedNode* head; // 啞巴頭節(jié)點(diǎn)代表MRU側(cè) DLinkedNode* tail; // 啞巴尾節(jié)點(diǎn)代表LRU側(cè) int capacity; int size; // ... 核心操作移動(dòng)節(jié)點(diǎn)到頭部、刪除尾部節(jié)點(diǎn)、添加節(jié)點(diǎn)到頭部等 };3. C實(shí)現(xiàn)詳解從零搭建線程不安全的LRU Cache3.1 類設(shè)計(jì)與初始化我們先實(shí)現(xiàn)一個(gè)基礎(chǔ)版本暫不考慮線程安全。這個(gè)版本已經(jīng)能解決大多數(shù)單線程場(chǎng)景下的問(wèn)題。首先我們使用兩個(gè)啞巴節(jié)點(diǎn)Dummy Node作為鏈表的頭和尾。啞巴節(jié)點(diǎn)不存儲(chǔ)實(shí)際數(shù)據(jù)它們的引入可以極大地簡(jiǎn)化鏈表邊界條件如空鏈表、只有一個(gè)節(jié)點(diǎn)的判斷讓代碼更簡(jiǎn)潔、更不易出錯(cuò)。#include unordered_map class LRUCache { private: struct Node { int key; int value; Node* prev; Node* next; Node(int k 0, int v 0) : key(k), value(v), prev(nullptr), next(nullptr) {} }; std::unordered_mapint, Node* cacheMap; // 哈希表 Node* dummyHead; // 啞巴頭節(jié)點(diǎn) (MRU側(cè)) Node* dummyTail; // 啞巴尾節(jié)點(diǎn) (LRU側(cè)) int cap; int currentSize; // 核心輔助函數(shù) void moveToHead(Node* node) { // 將節(jié)點(diǎn)從當(dāng)前位置斷開(kāi) removeNode(node); // 將節(jié)點(diǎn)插入到啞巴頭節(jié)點(diǎn)之后 addToHead(node); } void removeNode(Node* node) { node-prev-next node-next; node-next-prev node-prev; } void addToHead(Node* node) { // 插入到 dummyHead 和原來(lái)的第一個(gè)真實(shí)節(jié)點(diǎn)之間 node-prev dummyHead; node-next dummyHead-next; dummyHead-next-prev node; dummyHead-next node; } Node* removeTail() { // 要?jiǎng)h除的節(jié)點(diǎn)是 dummyTail 的前一個(gè)節(jié)點(diǎn) Node* node dummyTail-prev; removeNode(node); return node; // 返回被刪除的節(jié)點(diǎn)以便從哈希表中刪除key } public: LRUCache(int capacity) : cap(capacity), currentSize(0) { // 初始化啞巴節(jié)點(diǎn)并讓它們互相指向?qū)Ψ?dummyHead new Node(); dummyTail new Node(); dummyHead-next dummyTail; dummyTail-prev dummyHead; } ~LRUCache() { // 釋放鏈表所有節(jié)點(diǎn)內(nèi)存 Node* curr dummyHead-next; while (curr ! dummyTail) { Node* temp curr; curr curr-next; delete temp; } delete dummyHead; delete dummyTail; } // ... get 和 put 方法見(jiàn)下文 };3.2 get操作的實(shí)現(xiàn)與細(xì)節(jié)get操作需要完成三件事1. 查找key2. 返回value3. 將節(jié)點(diǎn)移動(dòng)到頭部。int get(int key) { // 1. 在哈希表中查找 auto it cacheMap.find(key); if (it cacheMap.end()) { // 未找到按題目要求返回 -1 return -1; } // 2. 找到對(duì)應(yīng)節(jié)點(diǎn) Node* node it-second; // 3. 將該節(jié)點(diǎn)移動(dòng)到鏈表頭部標(biāo)記為最近使用 moveToHead(node); // 4. 返回節(jié)點(diǎn)的值 return node-value; }這里有一個(gè)關(guān)鍵細(xì)節(jié)moveToHead內(nèi)部調(diào)用了removeNode和addToHead。removeNode操作已經(jīng)正確處理了節(jié)點(diǎn)前后指針的更新所以即使這個(gè)節(jié)點(diǎn)已經(jīng)是頭部節(jié)點(diǎn)再次執(zhí)行moveToHead也不會(huì)出錯(cuò)因?yàn)閞emoveNode操作在節(jié)點(diǎn)前后指針指向自己時(shí)邏輯依然成立。這體現(xiàn)了使用啞巴節(jié)點(diǎn)的另一個(gè)好處——代碼健壯性更強(qiáng)。3.3 put操作的完整流程與淘汰邏輯put操作是LRU的核心邏輯相對(duì)復(fù)雜需要處理key存在和不存在兩種情況以及可能觸發(fā)的淘汰機(jī)制。void put(int key, int value) { // 1. 先查找key是否已存在 auto it cacheMap.find(key); if (it ! cacheMap.end()) { // key已存在 Node* node it-second; node-value value; // 更新值 moveToHead(node); // 移動(dòng)到頭部標(biāo)記為最近使用 return; // 完成操作無(wú)需處理淘汰 } // 2. key不存在需要新建節(jié)點(diǎn)并插入 Node* newNode new Node(key, value); cacheMap[key] newNode; // 加入哈希表 addToHead(newNode); // 插入鏈表頭部 currentSize; // 緩存大小增加 // 3. 檢查是否超出容量 if (currentSize cap) { // 緩存已滿需要淘汰LRU節(jié)點(diǎn) Node* tailNode removeTail(); // 刪除鏈表尾部節(jié)點(diǎn) cacheMap.erase(tailNode-key); // 從哈希表中刪除對(duì)應(yīng)的key delete tailNode; // 釋放節(jié)點(diǎn)內(nèi)存 currentSize--; // 緩存大小減少 } }淘汰邏輯的要點(diǎn)淘汰時(shí)機(jī)是在插入新節(jié)點(diǎn)之后判斷。這樣邏輯清晰currentSize始終代表當(dāng)前緩存中的實(shí)際數(shù)據(jù)量。淘汰目標(biāo)removeTail()返回的是dummyTail-prev即鏈表中最舊最久未訪問(wèn)的節(jié)點(diǎn)。清理工作必須完成“三部曲”——從鏈表斷開(kāi)、從哈希表刪除、釋放內(nèi)存。缺少任何一步都會(huì)導(dǎo)致內(nèi)存泄漏或邏輯錯(cuò)誤。3.4 基礎(chǔ)版本的使用示例與測(cè)試我們可以編寫(xiě)簡(jiǎn)單的代碼來(lái)測(cè)試這個(gè)基礎(chǔ)版本。#include iostream int main() { LRUCache cache(2); cache.put(1, 1); // 緩存是 {11} cache.put(2, 2); // 緩存是 {11, 22} std::cout cache.get(1) std::endl; // 返回 1緩存變?yōu)?{22, 11} cache.put(3, 3); // 該操作會(huì)淘汰 key 2緩存變?yōu)?{11, 33} std::cout cache.get(2) std::endl; // 返回 -1 (未找到) cache.put(4, 4); // 該操作會(huì)淘汰 key 1緩存變?yōu)?{33, 44} std::cout cache.get(1) std::endl; // 返回 -1 std::cout cache.get(3) std::endl; // 返回 3 std::cout cache.get(4) std::endl; // 返回 4 return 0; }輸出應(yīng)該為1,-1,-1,3,4。這個(gè)測(cè)試覆蓋了插入、訪問(wèn)更新、淘汰舊數(shù)據(jù)等基本場(chǎng)景。4. 進(jìn)階實(shí)現(xiàn)邁向工業(yè)級(jí)強(qiáng)度基礎(chǔ)版本在單線程下工作良好但在實(shí)際生產(chǎn)環(huán)境中遠(yuǎn)遠(yuǎn)不夠。我們需要考慮線程安全、性能優(yōu)化和資源管理。4.1 線程安全設(shè)計(jì)與鎖的粒度多個(gè)線程同時(shí)調(diào)用get和put會(huì)導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)Data Race。例如線程A正在移動(dòng)一個(gè)節(jié)點(diǎn)到頭部同時(shí)線程B在刪除尾部節(jié)點(diǎn)鏈表的狀態(tài)可能被破壞。最簡(jiǎn)單的解決方案是使用一個(gè)互斥鎖mutex保護(hù)整個(gè)類的所有公共方法。#include mutex class ThreadSafeLRUCache { private: // ... 原有的成員變量cacheMap, dummyHead, dummyTail, cap, size mutable std::mutex mutex_; // 可變互斥鎖用于const成員函數(shù) public: int get(int key) { std::lock_guardstd::mutex lock(mutex_); // ... 原有的get邏輯 } void put(int key, int value) { std::lock_guardstd::mutex lock(mutex_); // ... 原有的put邏輯 } };使用std::lock_guard可以保證在函數(shù)作用域內(nèi)自動(dòng)加鎖和解鎖避免忘記解鎖。mutable關(guān)鍵字允許在const成員函數(shù)如果未來(lái)有的話中修改mutex_。然而全局鎖的代價(jià)是性能。在高并發(fā)場(chǎng)景下所有操作串行化緩存可能成為性能瓶頸。更精細(xì)化的鎖策略例如讀寫(xiě)鎖Read-Write Lock可以允許多個(gè)get操作并發(fā)執(zhí)行因?yàn)間et不修改哈希表和鏈表的結(jié)構(gòu)只修改鏈表節(jié)點(diǎn)順序而put操作則需要獨(dú)占鎖。C17提供了std::shared_mutex。#include shared_mutex class ReadWriteLRUCache { private: // ... mutable std::shared_mutex rw_mutex_; public: int get(int key) { std::shared_lockstd::shared_mutex lock(rw_mutex_); // 共享鎖 // ... get邏輯 } void put(int key, int value) { std::unique_lockstd::shared_mutex lock(rw_mutex_); // 獨(dú)占鎖 // ... put邏輯 } };注意即使使用讀寫(xiě)鎖get操作中的moveToHead仍然修改了鏈表節(jié)點(diǎn)的順序指針。嚴(yán)格來(lái)說(shuō)這屬于“寫(xiě)”操作。但在某些實(shí)現(xiàn)中如果認(rèn)為更新訪問(wèn)順序的優(yōu)先級(jí)低于并發(fā)讀取的性能可以權(quán)衡后仍使用讀寫(xiě)鎖。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ菍⒃L問(wèn)順序更新延遲或使用無(wú)鎖數(shù)據(jù)結(jié)構(gòu)但這會(huì)極大增加復(fù)雜度。4.2 性能優(yōu)化使用STL容器簡(jiǎn)化實(shí)現(xiàn)我們之前手動(dòng)管理雙向鏈表節(jié)點(diǎn)雖然有助于理解原理但代碼量較大且容易出錯(cuò)。實(shí)際上C STL的list雙向鏈表和unordered_map結(jié)合可以極大簡(jiǎn)化實(shí)現(xiàn)。核心思路是unordered_map存儲(chǔ)key - list::iterator而list中存儲(chǔ)的是pairkey, value。list的頭部代表MRU尾部代表LRU。#include list #include unordered_map class LRUCacheSTL { private: int capacity_; // list 存儲(chǔ)實(shí)際的鍵值對(duì)front是MRUback是LRU std::liststd::pairint, int cacheList_; // 哈希表key 映射到 list 中的迭代器 std::unordered_mapint, std::liststd::pairint, int::iterator cacheMap_; public: LRUCacheSTL(int capacity) : capacity_(capacity) {} int get(int key) { auto it cacheMap_.find(key); if (it cacheMap_.end()) return -1; // 將找到的鍵值對(duì)移動(dòng)到list頭部 // splice操作將it-second指向的元素移動(dòng)到cacheList_.begin()之前 cacheList_.splice(cacheList_.begin(), cacheList_, it-second); // 迭代器仍然有效指向同一個(gè)元素 return it-second-second; // 返回value } void put(int key, int value) { auto it cacheMap_.find(key); if (it ! cacheMap_.end()) { // key存在更新value并移動(dòng)到頭部 it-second-second value; // 更新值 cacheList_.splice(cacheList_.begin(), cacheList_, it-second); return; } // key不存在插入新元素到頭部 cacheList_.emplace_front(key, value); // 在頭部構(gòu)造新節(jié)點(diǎn) cacheMap_[key] cacheList_.begin(); // 記錄迭代器 // 檢查容量 if (cacheMap_.size() capacity_) { // 刪除LRU元素list尾部 int lruKey cacheList_.back().first; cacheMap_.erase(lruKey); // 從哈希表刪除 cacheList_.pop_back(); // 從鏈表刪除 } } };這種實(shí)現(xiàn)的優(yōu)勢(shì)代碼簡(jiǎn)潔無(wú)需手動(dòng)管理鏈表節(jié)點(diǎn)內(nèi)存STL容器自動(dòng)處理。安全避免了手動(dòng)操作指針可能帶來(lái)的內(nèi)存錯(cuò)誤。高效list::splice操作是O(1)的用于移動(dòng)元素非常高效。一個(gè)重要的坑在put操作觸發(fā)淘汰時(shí)我們是先cacheMap_.erase(lruKey)再cacheList_.pop_back()。順序很重要如果先pop_back()尾部的迭代器會(huì)失效再通過(guò)lruKey去erase可能會(huì)訪問(wèn)到無(wú)效的迭代器導(dǎo)致未定義行為。4.3 模板化與泛型支持一個(gè)通用的緩存不應(yīng)該只支持int類型的key和value。我們可以使用模板將其泛化。template typename K, typename V class GenericLRUCache { private: size_t capacity_; std::liststd::pairK, V cacheList_; std::unordered_mapK, typename std::liststd::pairK, V::iterator cacheMap_; // 注意上面這行iterator類型需要加上typename關(guān)鍵字因?yàn)樗谝蕾嚹０鍏?shù)K,V public: GenericLRUCache(size_t capacity) : capacity_(capacity) {} V get(const K key) { // 這里需要一種方式表示“未找到”對(duì)于泛型V可以返回默認(rèn)值或使用std::optional // 簡(jiǎn)單起見(jiàn)我們假設(shè)V是指針或可默認(rèn)構(gòu)造的類型這里僅展示邏輯 auto it cacheMap_.find(key); if (it cacheMap_.end()) { return V(); // 返回默認(rèn)值實(shí)際中可能需要更精細(xì)的處理 } cacheList_.splice(cacheList_.begin(), cacheList_, it-second); return it-second-second; } void put(const K key, const V value) { auto it cacheMap_.find(key); if (it ! cacheMap_.end()) { it-second-second value; cacheList_.splice(cacheList_.begin(), cacheList_, it-second); return; } cacheList_.emplace_front(key, value); cacheMap_[key] cacheList_.begin(); if (cacheMap_.size() capacity_) { auto last cacheList_.back(); cacheMap_.erase(last.first); cacheList_.pop_back(); } } };模板化使得我們的LRU緩存可以用于緩存字符串、對(duì)象指針等任何可拷貝的類型實(shí)用性大大增強(qiáng)。5. 生產(chǎn)環(huán)境中的考量與常見(jiàn)問(wèn)題排查5.1 內(nèi)存管理與對(duì)象生命周期當(dāng)緩存的值不是簡(jiǎn)單數(shù)據(jù)類型如int而是大型對(duì)象如字符串、向量、自定義類時(shí)需要特別注意內(nèi)存管理。值拷貝開(kāi)銷put操作中的cacheList_.emplace_front(key, value)可能會(huì)引發(fā)value的拷貝構(gòu)造如果V對(duì)象很大開(kāi)銷會(huì)很高。考慮使用移動(dòng)語(yǔ)義或智能指針。void put(const K key, V value) { // 按值傳遞為移動(dòng)語(yǔ)義創(chuàng)造條件 // ... cacheList_.emplace_front(key, std::move(value)); // 使用移動(dòng)構(gòu)造 // ... }或者存儲(chǔ)std::shared_ptrV這樣緩存中存儲(chǔ)的是輕量級(jí)的指針拷貝開(kāi)銷小。std::liststd::pairK, std::shared_ptrV cacheList_; std::unordered_mapK, decltype(cacheList_)::iterator cacheMap_; void put(const K key, std::shared_ptrV value) { // ... 邏輯類似存儲(chǔ)的是shared_ptr }緩存穿透與雪崩如果get一個(gè)不存在的key我們的實(shí)現(xiàn)直接返回-1或默認(rèn)值。但在實(shí)際系統(tǒng)中這可能意味著需要去后端數(shù)據(jù)庫(kù)加載。如果大量請(qǐng)求同時(shí)查詢一個(gè)不存在或已過(guò)期的key會(huì)導(dǎo)致請(qǐng)求全部穿透緩存壓垮數(shù)據(jù)庫(kù)。解決方案包括布隆過(guò)濾器快速判斷key是否絕對(duì)不存在于緩存避免無(wú)謂的數(shù)據(jù)庫(kù)查詢。空值緩存即使數(shù)據(jù)庫(kù)查不到也將這個(gè)key和一個(gè)特殊的“空值”標(biāo)記存入緩存一小段時(shí)間避免短時(shí)間內(nèi)重復(fù)查詢?；コ怄iMutex per key對(duì)于同一個(gè)key只允許一個(gè)線程去后端加載其他線程等待。這通常需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)支持。5.2 性能監(jiān)控與容量規(guī)劃一個(gè)LRU緩存在線上運(yùn)行你需要監(jiān)控它的效果。命中率Hit Ratioget請(qǐng)求成功從緩存返回的次數(shù) / 總的get請(qǐng)求次數(shù)。這是衡量緩存有效性的核心指標(biāo)。命中率過(guò)低可能意味著容量太小或者數(shù)據(jù)訪問(wèn)模式不符合LRU的假設(shè)。平均訪問(wèn)延遲監(jiān)控get和put操作的平均耗時(shí)確保在高并發(fā)下性能達(dá)標(biāo)。容量規(guī)劃容量capacity設(shè)置多少合適太小則命中率低太大則浪費(fèi)內(nèi)存且可能增加鏈表操作開(kāi)銷。需要通過(guò)壓測(cè)和監(jiān)控歷史命中率來(lái)動(dòng)態(tài)調(diào)整。有些系統(tǒng)支持動(dòng)態(tài)調(diào)整容量。5.3 常見(jiàn)問(wèn)題排查實(shí)錄問(wèn)題1程序運(yùn)行一段時(shí)間后崩潰報(bào)“segmentation fault”或“iterator incompatible”。排查這很可能是迭代器失效問(wèn)題。在STL實(shí)現(xiàn)中當(dāng)對(duì)list進(jìn)行erase或pop_back操作時(shí)指向被刪除元素的迭代器會(huì)失效。但在我們的LRUCacheSTL實(shí)現(xiàn)中我們確保在淘汰元素時(shí)是先通過(guò)迭代器從unordered_map中刪除key再對(duì)list進(jìn)行pop_back。問(wèn)題可能出在其他地方比如在多線程環(huán)境下一個(gè)線程正在使用迭代器另一個(gè)線程刪除了它。解決檢查線程安全。如果沒(méi)有加鎖必須加上。如果使用了讀寫(xiě)鎖確認(rèn)get中的splice操作是否被正確保護(hù)。問(wèn)題2緩存的內(nèi)存占用持續(xù)增長(zhǎng)遠(yuǎn)超capacity設(shè)定值。排查首先檢查capacity的單位和cacheMap_.size()是否一致。其次如果V類型是指針或包含指針緩存中存儲(chǔ)的只是指針而指針指向的實(shí)際數(shù)據(jù)可能在其他地方被修改或泄露。解決確保V類型是能正確反映數(shù)據(jù)大小的。對(duì)于指針考慮使用std::shared_ptr并確保沒(méi)有循環(huán)引用。使用內(nèi)存分析工具如Valgrind檢測(cè)內(nèi)存泄漏。問(wèn)題3在高并發(fā)下即使使用了讀寫(xiě)鎖性能依然不佳。排查全局的讀寫(xiě)鎖可能競(jìng)爭(zhēng)依然激烈。get操作中的splice移動(dòng)鏈表節(jié)點(diǎn)是一個(gè)寫(xiě)操作這迫使get實(shí)際上也需要獲取寫(xiě)鎖如果嚴(yán)格按讀寫(xiě)語(yǔ)義或者導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)如果錯(cuò)誤地用了讀鎖。解決這是一個(gè)經(jīng)典難題。工業(yè)級(jí)解決方案可能包括分段鎖Striped Locking將一個(gè)大緩存分成多個(gè)獨(dú)立的小緩存段shard每個(gè)段有自己的鎖。請(qǐng)求根據(jù)key的哈希值路由到不同的段這樣可以大大降低鎖的競(jìng)爭(zhēng)。近似LRU算法放棄嚴(yán)格的LRU使用性能更好、更易于并發(fā)的算法如Redis使用的“采樣淘汰”方式。無(wú)鎖數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)難度極高但性能最好通常用于對(duì)性能有極致要求的底層系統(tǒng)。實(shí)現(xiàn)一個(gè)正確的LRU Cache是理解緩存系統(tǒng)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的絕佳練習(xí)。從基礎(chǔ)的雙向鏈表哈希表到考慮線程安全、泛型、內(nèi)存管理和性能優(yōu)化每一步都對(duì)應(yīng)著實(shí)際工程中的真實(shí)挑戰(zhàn)。我建議你先掌握基礎(chǔ)版本理解其每一行代碼然后再逐步嘗試引入STL簡(jiǎn)化、模板化和鎖機(jī)制。在真正的項(xiàng)目中使用時(shí)務(wù)必進(jìn)行充分的測(cè)試和性能壓測(cè)并根據(jù)監(jiān)控指標(biāo)持續(xù)調(diào)優(yōu)。緩存雖小卻是構(gòu)建高性能系統(tǒng)不可或缺的基石。