緩存置換：用c++實現最近最少使用（LRU）算法

? ? ? ?在計算機的世界里，緩存就像一個“快速倉庫”，它存儲著我們頻繁訪問的數據，大大提升了數據的讀取速度。但這個 “倉庫” 空間有限，當它被裝滿時，就得決定舍棄一些數據，為新數據騰出位置，這個決策過程就由緩存置換算法來掌控。今天，就讓我們探索常見的緩存置換算法中的最近最少使用算法（LRU），并使用c++實現它。

一、LRU 算法原理

? ? ? ? LRU 算法的核心思想非常簡單：當緩存已滿，需要淘汰數據時，優先淘汰那些最近最少使用的數據。想象一下你在整理書架，那些很久都沒被翻閱過的書籍（最近最少使用的數據），往往會被你放到更靠后的位置，甚至在書架空間不足時，你會優先選擇將它們清理出去，以便為新的書籍騰出空間。LRU 算法就是基于這樣的邏輯，確保緩存中始終保留最有可能被再次訪問的數據。

? ? ? ? 為了實現這一目標，LRU 算法需要記錄每個數據的訪問時間或者訪問順序。每當訪問一個數據時，它就會被標記為 “最近使用”，而那些長時間沒有被訪問的數據則會逐漸成為 “最近最少使用” 的數據。當緩存空間不足時，這些數據就會被替換掉。

二、實現 LRU 算法的數據結構選擇

? ? ? ? 要實現 LRU 算法，選擇合適的數據結構至關重要。通常，我們會結合雙向鏈表和哈希表來實現 LRU 緩存。

（一）雙向鏈表

? ? ? ? ?雙向鏈表用于維護數據的訪問順序。鏈表中的每個節點代表一個緩存數據，鏈表的尾部表示最近使用的數據，頭部表示最近最少使用的數據。當訪問一個數據時，對應的節點會被移動到鏈表尾部；當需要淘汰數據時，直接刪除鏈表頭部的節點即可。雙向鏈表的優勢在于，插入和刪除操作的時間復雜度都是?O(1)?，這對于頻繁的緩存操作來說非常高效。例如，在一個頻繁讀寫的數據庫緩存中，數據的插入和刪除操作會經常發生，雙向鏈表的這種特性可以保證緩存操作的快速執行。

（二）哈希表

? ? ? ? 哈希表則用于快速定位數據在雙向鏈表中的位置。它以數據的鍵作為索引，存儲對應數據在雙向鏈表中的節點指針。這樣，在查找數據時，通過哈希表可以在?O(1)?的時間復雜度內找到對應的數據節點，然后根據節點指針在雙向鏈表中進行操作。例如，在一個基于鍵值對存儲的內存緩存中，通過哈希表可以快速找到特定鍵對應的數據，提高緩存的查詢效率。

? ? ? ? 不清楚哈希表的可以看我以前的文章c++ 手寫STL篇（三）實現hashtable

? ? ? ? 結合雙向鏈表和哈希表，我們可以在?O(1)?的時間復雜度內完成數據的查找、插入和刪除操作，滿足 LRU 算法高效性的要求。

三、LRU 算法的操作流程

? ? ? ? 下面詳細介紹 LRU 算法在緩存操作中的具體流程。

（一）查詢操作

? ? ? ? 當進行查詢操作時，首先根據數據的鍵在哈希表中查找對應的節點。如果找到了，說明數據在緩存中，將該節點從雙向鏈表中移除，并插入到鏈表尾部，表示該數據是最近使用的；如果在哈希表中未找到，則說明數據不在緩存中，需要從其他數據源獲取數據（例如從磁盤讀取數據），然后將數據插入到緩存鏈表尾部。

（二）插入操作

? ? ? ? 插入操作分為兩種情況。如果緩存未滿，直接將數據插入到雙向鏈表頭部，并在哈希表中記錄數據的鍵和對應的節點指針；如果緩存已滿，則先刪除雙向鏈表頭部的節點（即最近最少使用的數據），同時在哈希表中刪除對應的鍵值對，然后再將新數據插入到雙向鏈表尾部，并更新哈希表。

四、LRU 算法的應用場景

? ? ? ? LRU 算法在許多實際場景中都發揮著重要作用，以下是一些常見的應用場景。

操作系統內存管理：以 Ubuntu 系統為例，在其內存管理中，LRU 算法發揮著重要作用。Ubuntu 基于 Linux 內核，系統會將常用的數據和程序頁面緩存到物理內存中，以提升訪問速度。當物理內存不足時，就需要淘汰部分頁面。此時，LRU 算法會優先淘汰那些最近最少使用的頁面。假設用戶在 Ubuntu 系統上同時運行多個程序，如瀏覽器、文本編輯器和音樂播放器。一段時間內，用戶頻繁操作瀏覽器，而文本編輯器和音樂播放器處于后臺且較少被使用。那么，根據 LRU 算法，文本編輯器和音樂播放器相關的內存頁面（如果長時間未被訪問）就更有可能被淘汰，從而為其他更活躍的程序騰出內存空間，保證系統的穩定運行和高效性能。
瀏覽器緩存優化：主流瀏覽器如 Chrome、Firefox 等均采用 LRU 算法管理緩存。當用戶瀏覽網頁時，瀏覽器會將網頁的 HTML、CSS、圖片等資源緩存起來。以在 Ubuntu 系統上使用 Chrome 瀏覽器訪問網頁為例，當用戶再次訪問相同或相關頁面時，若資源在緩存中，瀏覽器可直接從緩存讀取，減少網絡請求，加快頁面加載速度（背過八股文的應該清楚這一部分）。隨著用戶瀏覽的網頁增多，緩存空間會逐漸被占滿。此時，LRU 算法會將最近最少訪問的網頁資源淘汰，確保緩存中始終保留最有可能再次被訪問的內容。比如，用戶之前瀏覽過多個新聞頁面，一段時間后又頻繁訪問購物網站，那么那些較早瀏覽且長時間未再次訪問的新聞頁面緩存資源就可能被 LRU 算法淘汰，為購物網站的緩存資源騰出空間。
CPU 緩存協同工作：在計算機硬件層面，CPU 緩存同樣應用了 LRU 算法或類似策略。CPU 緩存用于存儲 CPU 頻繁訪問的數據和指令，分為一級緩存（L1 Cache）、二級緩存（L2 Cache）和三級緩存（L3 Cache）（關于cpu的三級緩沖可以參考這篇文章：小林coding 圖解系統）。當 CPU 需要讀取數據或指令時，首先在緩存中查找。若緩存命中，則快速獲取數據；若緩存未命中，則從主內存讀取，并將數據存入緩存。由于緩存容量有限，當新數據需要存入緩存時，會根據類似 LRU 的算法淘汰最近最少使用的數據。比如在 Ubuntu 系統上運行復雜的圖像渲染程序，CPU 需要頻繁讀取圖像數據和相關指令。隨著程序的運行，緩存中的數據不斷更新，那些近期較少被使用的圖像數據和指令就會被淘汰，為新的數據騰出空間，確保 CPU 能夠快速訪問到最需要的數據，提高圖像渲染的效率。

五、LRU 算法的優缺點

（一）優點

簡單高效：LRU 算法的原理和實現相對簡單，并且在許多場景下都能表現出良好的性能。它能夠快速地淘汰最近最少使用的數據，保證緩存中始終保留最有價值的數據，從而提高系統的整體性能。
符合局部性原理：在計算機系統中，數據訪問往往具有局部性特征，即最近訪問過的數據在未來一段時間內再次被訪問的概率較高。LRU 算法正好符合這一原理，通過優先保留最近使用的數據，能夠有效地提高緩存命中率，減少數據的重復讀取。

（二）缺點

無法準確預測未來訪問模式：LRU 算法僅僅根據過去的數據訪問歷史來決定淘汰哪些數據，而不能準確預測未來的數據訪問模式。在某些情況下，一次性遍歷大量不重復數據（或者突然訪問大量冷數據），可能會將真正的熱點數據清空（緩存污染），導致命中率低。
實現成本較高：雖然 LRU 算法的基本思想簡單，但要實現一個高效的 LRU 緩存，需要結合雙向鏈表和哈希表等數據結構，這增加了代碼的復雜性和實現成本。此外，在高并發環境下，還需要考慮數據結構的線程安全性，進一步增加了實現的難度，同時鎖的加入會在高并發下消耗大量資源用于線程的同步等待。

六、c++實現LRU

? ? ? ? LRU 緩存置換算法是一種經典且實用的算法，在眾多領域都有廣泛的應用。通過深入理解其原理、數據結構選擇、操作流程以及應用場景，我們可以更好地將其應用到實際項目中，提升系統的性能。接下來，我們將通過手撕代碼的方式，詳細展示如何實現一個 LRU 緩存。

代碼參考自：https://github.com/youngyangyang04/KamaCache

接口類，對緩存置換算法設計統一接口實現隔離?：

#ifndef CACHEPOLICY_H
#define CACHEPOLICY_Htemplate<typename Key, typename Value>
class CachePolicy
{
public:virtual ~CachePolicy() {};virtual void put(Key key, Value value) = 0;virtual bool get(Key key,Value& value) = 0;virtual Value get(Key key) = 0;
};#endif

?節點類，LRU中的雙向鏈表，每個節點保存緩存數據的鍵值對、訪問次數和前后節點指針，同時封裝類方法用于訪問和修改私有成員變量

//前置聲明LRU類，具體實現看下文
template<typename Key, typename Value> class LruCache;template<typename Key, typename Value>
class LruNode
{
private:Key key_;Value value_;size_t accessCount_;std::shared_ptr<LruNode<Key,Value>> next_;std::shared_ptr<LruNode<Key,Value>> prev_;public://初始化列表方法對類成員變量賦初值LruNode(Key key, Value value):key_(key),value_(value),accessCount_(0),next_(nullptr),prev_(nullptr) {}Key getKey() const {return key_;}//const聲明方法不對成員變量修改Value getValue() const {return value_;}void setValue(const Value& value) {value_ = value;}size_t getAccexxCount() const {return accessCount_;}void incrementAccessCount() {++accessCount_;}//LRU類作為節點類友元，用于在LRU類中訪問節點類的私有成員friend class LruCache<Key, Value>;
};

LRU類，其內部包含鏈表虛擬頭節點（虛擬頭節點的下一個節點就是最不經常使用節點）指針，虛擬尾節點（虛擬尾節點的上一個節點最近訪問過的節點）指針。使用unordered_map作為哈希表（unordered_map底層是哈希表實現，不清楚哈希表的可以看我以前的文章c++ 手寫STL篇（三）實現hashtable）。

template<typename Key, typename Value> 
class LruCache : public CachePolicy<Key,Value>
{
public:	using LruNodeType = LruNode<Key,Value>;using NodePtr = std::shared_ptr<LruNodeType>;using NodeMap = std::unordered_map<Key,NodePtr>;LruCache(int capacity): capacity_ (capacity){initializeList();}~LruCache() override = default;void put(Key key, Value value) override {if(capacity_ <= 0) return;std::lock_guard<std::mutex> lock(mutex_);//互斥鎖，避免臨界區競爭//先使用哈希表查找緩存中是否存在key，//存在則將節點取出，并插入鏈表尾部，//不存在則新建節點并插入鏈表尾部auto it = nodeMap_.find(key);if(it != nodeMap_.end()){updateExistingNode(it->second, value);return ;}addNewNode(key,value);}bool get(Key key,Value& value) override{std::lock_guard<std::mutex> lock(mutex_);
//先查找是否存在，存在則把節點移到鏈表尾部，不存在直接返回falseauto it = nodeMap_.find(key);if(it != nodeMap_.end()){moveToMostRecent(it->second);value = it->second->getValue();return true;}return false;}//get的重載Value get(Key key) override{Value value{};get(key,value);return value;}void remove(Key key){std::lock_guard<std::mutex> lock(mutex_);auto it = nodeMap_.find(key);if(it != nodeMap_.end()){removeNode(it->second);nodeMap_.erase(it);}}private://初始化就是構建虛擬頭節點和虛擬尾節點，然后頭尾相連void initializeList(){dummyHead_ = std::make_shared<LruNodeType>(Key(),Value());dummyTail_ = std::make_shared<LruNodeType>(Key(),Value());dummyHead_->next_ = dummyTail_;dummyTail_->prev_ = dummyHead_;}//修改節點值，然后移動到鏈表尾部void updateExistingNode(NodePtr node, const Value& value){node->setValue(value);moveToMostRecent(node);}//新增節點，這里會判斷緩存容量是否已滿，滿了刪除最不經常使用的節點（頭部節點）void addNewNode(const Key& key, const Value& value){if(nodeMap_.size() >= capacity_){evictLeastNode();}NodePtr newNode = std::make_shared<LruNodeType>(key,value);insertNode(newNode);nodeMap_[key] = newNode;}//節點移動到鏈表尾部（刪除-》插入）void moveToMostRecent(NodePtr node){removeNode(node);insertNode(node);}void removeNode(NodePtr node){node->prev_->next_ = node->next_;node->next_->prev_ = node->prev_;}void insertNode(NodePtr node){node->next_ = dummyTail_;node->prev_ = dummyTail_->prev_;dummyTail_->prev_->next_ = node;dummyTail_->prev_ = node;}//刪除最不經常使用節點（頭部節點）void evictLeastNode(){NodePtr leastRecent = dummyHead_->next_;removeNode(leastRecent);nodeMap_.erase(leastRecent->getKey());}private:int capacity_;//容量NodeMap nodeMap_;//哈希表NodePtr dummyHead_;//虛擬頭節點，它的next指向真正的頭節點（最不經常使用節點）NodePtr dummyTail_;//虛擬尾節點，它的prev指向真正的為尾節點（最近使用過的節點）std::mutex mutex_;//互斥鎖
};

? ? ? ? 通過以上代碼不難看出，鎖的粒度很大，這樣的話高并發下會消耗大量資源用于線程同步等待，這個問題怎么解決呢？其實可以把一個大的緩存池分成幾個小的緩存池，就好比多個人都要從一個倉庫取貨，但倉庫每次只能進一個人，如果多個人要取貨那就必須得排隊等待，哪怕每個人要取的貨物不同，既然這樣那不如把一個大倉庫分成若干個小倉庫，每個人取得貨物可能分布在不同倉庫內，哪怕仍然有好幾個人要的貨物碰巧在同一個倉庫，那隊伍也不會排的像原先那么長。這樣就實現了分流。

template<typename Key, typename Value>
class HashLruCaches
{
public:	//把lurcache進行分片，計算每一個小的cache容量大小HashLruCaches(size_t capacity, int sliceNum):	capacity_(capacity),sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency()){size_t sliceSize = std::ceil(capacity / static_cast<double>(sliceNum_));for(int i = 0; i < sliceNum_; i++){lruSliceCaches_.emplace_back(new LruCache<Key,Value>(sliceSize));}}//使用哈希函數計算要找的節點在哪一個cache中void put(Key key,Value value){size_t sliceIndex = Hash(key) % sliceNum_;return lruSliceCaches_[sliceIndex]->put(key, value);}bool get(Key key, Value& value){size_t sliceIndex = Hash(key) % sliceNum_;return lruSliceCaches_[sliceIndex]->get(key, value);}Value get(Key key){Value value{};memset(&value, 0, sizeof(Value));get(key, value);return value;}private:size_t Hah(Key key){std::hash<Key> hashFunc;return hashFunc(key);}private:size_t capacity_;int sliceNum_;std::vector<std::unique_ptr<LruCache<Key,Value>>> lruSliceCaches_;
};