了解LRU緩存的實現方法,這就夠了

2021-01-08 沙茶敏碎碎念

在之前的文章，我們介紹過常用緩存淘汰算法（文末有連結）。常見的緩存淘汰算法有先進先出淘汰算法（FIFO），最近最少使用淘汰算法（LSU），最近最久未使用算法（LRU），MRU（最近最常使用算法）。今天我們來討論其中的一種，也是最常用的LRU算法，看看它是如何實現的。

我們使用例子是谷歌開源的kv存儲LevelDB的經典LRUCache實現。LRUCache一般採用雙鏈進行實現，第一個是一個開散列，第二個是雙向鍊表，我們先簡單介紹下這兩個數據結構。首先是開散列。

開散列（Open Hashing）,如果你是個Java開發，那對此肯定不陌生，也就是HashMap。我們先算出一個Key的Hash值，然後在存到對應的列裡面。如果同一個開散列有兩個key的Hash值一樣，我們稱之為衝突。怎麼解決衝突呢？一般我們使用鍊表解決，相同hash值的key在同一列。這裡，我們不難想到一個經典的java面試題，為什麼java的類的hash函數要設計成儘可能不同的類返回不同的值。如果元素的個數大於散列的列數，我們對散列進行擴大一杯，重新哈希，我們稱之為Rehash。好了，這裡我們不難想到另外一個經典的面試題目，為什麼Java開發中，如果已知key的數量，要在在聲明HashMap的時候就把大小傳進去，相信聰明的你現在已經有了答案。

第二個數據結構是雙向鍊表，在我們還在學習數據結構的年代，我們學習了鍊表，雙向鍊表只是鍊表的一個進化版，擁有兩個指針，一個指向前一個節點，一個指向後一個節點。這種數據結果有什麼特點呢？就是在刪除的P的時候，我們只要把P的前置結點的後置結點置為P的後置結點，把P的後置結點置的前置結點置為P的前置結點，就能夠把一個元素刪除。

兩種數據結構的複雜度如下：

雙向列表，查詢比較慢，但是插入很快，而且非常 容易維護先後使用順序。開散列，查詢很快，插入很快，但是很難維護先後順序，需要給每個元素加上時間戳再去遍歷。我們發現當兩種數據結構巧妙結合起來，用雙向鍊表維護最近未使用，用開散列來查詢，並且在開散列的值上面記錄元素在雙向鍊表中的位置，就能能夠大大的降低複雜度。

每次插入的流程如下：

1.當我們插入一個元素的時候，我們首先去開散列中找到這個元素

2.如果這個元素已經存在，則開散列中的值找到元素所在的雙向鍊表的位置，把它提到最新使用。

3.如果這個元素不存在，那麼開散列中插入這個元素，並且判斷是否要重新擴展。雙向鍊表中插入這個元素，並且判斷是否要淘汰掉最舊元素，如果要，那麼同時在開散列中刪除該元素。

好了，今天的內容我們就講到這裡，如果覺得我講的還不錯，歡迎關注我。

相關焦點

  • 從零開始手寫 redis（九）LRU 緩存淘汰避免緩存汙染
    前言java從零手寫實現redis（一）如何實現固定大小的緩存？java從零手寫實現redis（四）添加監聽器java從零手寫實現redis（五）過期策略的另一種實現思路java從零手寫實現redis（六）AOF 持久化原理詳解及實現java從零手寫實現redis（七）LRU 緩存淘汰策略詳解從零開始手寫 redis（八）樸素 LRU 淘汰算法性能優化前兩節我們分別實現了 LRU
  • 「Redis源碼分析」Redis中的LRU算法實現
    希望閱讀完可以得到你的一個【三連】，這將是對我最大的鼓勵和支持。LRU是什麼LRU(least recently used)是一種緩存置換算法。即在緩存有限的情況下，如果有新的數據需要加載進緩存，則需要將最不可能被繼續訪問的緩存剔除掉。
  • LRU原理和Redis實現——一個今日頭條的面試題
    但是如果讓我們自己設計一個基於 LRU 的緩存，這樣設計可能問題很多，這段內存按照訪問時間進行了排序，會有大量的內存拷貝操作，所以性能肯定是不能接受的。那麼如何設計一個LRU緩存，使得放入和移除都是 O(1) 的，我們需要把訪問次序維護起來，但是不能通過內存中的真實排序來反應，有一種方案就是使用雙向鍊表。
  • 10行Java代碼實現最近被使用(LRU)緩存
    10行Java代碼實現最近被使用（LRU）緩存 據我所知，很少有一種程式語言的標準庫中有通用的數據結構能提供上述功能的。這是一種混合的數據結構，我們需要在哈希表的基礎上建立一個鍊表。但是 Java已經為我們提供了這種形式的數據結構-LinkedHashMap！
  • 手寫一下 LRU 代碼實現？
    手寫一下 LRU 代碼實現？面試官心理分析如果你連這個問題都不知道，上來就懵了，回答不出來，那線上你寫代碼的時候，想當然的認為寫進 redis 的數據就一定會存在，後面導致系統各種 bug，誰來負責？常見的有兩個問題：往 redis 寫入的數據怎麼沒了？
  • LRU緩存算法的實現
    這就意味著，如果經常訪問的數據，我們需要讓其能夠快速命中，而不常訪問的數據，我們在容量超出限制內，要將其淘汰。並將該鍵值提到棧頂，若無要put的key，直接入棧棧滿時，若棧中有要put的key，則更新此key對應的value，並將該鍵值提到棧頂;若棧中沒有put的key 時，去掉棧底元素，將put的值入到棧頂解法：維護一個數組，提供 get 和 put 方法
  • LRU算法
    java實現LRU的方式基於LRU的基礎思想，本文整理三種實現方式利用一個鍊表來實現，每次新插入數據的時候將新數據插到鍊表的頭部；每次緩存命中（即數據被訪問），則將數據移到鍊表頭部；那麼當鍊表滿的時候，就將鍊表尾部的數據丟棄。利用鍊表和hashmap。當需要插入新的數據項的時候，如果新數據項在鍊表中存在（一般稱為命中），則把該節點移到鍊表頭部，如果不存在，則新建一個節點，放到鍊表頭部，若緩存滿了，則把鍊表最後一個節點刪除即可。
  • 「日拱一卒」鍊表——如何實現lru
    LRURedis的內存淘汰機制好幾種，如ttl、random、lru。lru（less recently used）即最近最少使用策略，表示在最近一段時間內最少被使用到的Redis鍵，如果遇到內存不足，會有限淘汰這部分鍵來騰出更多空間。
  • 怎麼實現的延時隊列?以及訂閱模式、LRU
    所以這次準備繼續總結，因為第一個問題，Redis的批量操作，是我在面試過程中被真實問到的，當時沒答上來，也是因為確實沒了解過Redis的批量操作。當時的問題，我還記得比較清晰：Redis執行批量操作的功能是什麼？使用場景就是搞促銷活動時，會做預緩存，會往緩存裡放大批數據，如果直接放的話那麼會很慢，怎麼能提高效率呢？
  • 加速函數,每個Python程式設計師都應該了解標準庫的Lru_cache
    隨著輸入數據的增加，等待外部伺服器的響應變得非常費時，這使得ETL進程越來越慢。經過一番調查，我發現與總記錄數（~500k）相比，並沒有太多不同的輸入值（~500）。因此，換句話說，使用相同的參數調用外部服務時，每個參數大約要重複執行1000次。像這樣的情況是使用緩存的主要用例。緩存一個函數意味著無論何時首次計算函數的返回值，都會將其輸入和結果放在字典中。
  • 了解常用緩存淘汰算法,這就夠了
    為什麼需要緩存因為計算機讀取文件（資料庫）的速度相對於讀取內存的數據來說，會比較慢，所以，我們常常使用緩存來加快我們的訪問效率。為什麼需要淘汰數據相對於動則幾T幾T的硬碟來說，內存就要小得多，而且貴得多，現在大部分的伺服器仍是32G/64G內存的，並且類似JAVA這類會有GC問題的語言來說，使用大內存可能引來FullGC問題，可能會造成系統暫停服務一小段時間，得不償失，所以，我們不能把所有的數據都從資料庫放到內存去緩存，只能夠緩存更加有價值的數據。
  • LRU(Least Recently Used)緩存算法的實現
    這就意味著，如果經常訪問的數據，我們需要讓其能夠快速命中，而不常訪問的數據，我們在容量超出限制內，要將其淘汰。put的key，則更新此key對應的value，並將該鍵值提到棧頂，若無要put的key，直接入棧棧滿時，若棧中有要put的key，則更新此key對應的value，並將該鍵值提到棧頂;若棧中沒有put的key 時，去掉棧底元素，將put的值入到棧頂解法：維護一個數組，提供 get 和 put 方法
  • 了解一下高性能緩存資料庫Redis,再去參加面試
    Redis 在內存中對數字進行遞增或遞減的操作實現的非常好。集合（Set）和有序集合（SortedSet）也使得我們在執行這些操作的時候變的非常簡單，Redis 只是正好提供了這兩種數據結構。由於是純內存操作，資料庫容量受到物理內存的限制，不能用作海量數據的高性能讀寫。Redis 適合的場景主要局限在較小數據量的高性能操作和運算上。
  • Redis緩存失效策略思考
    那麼當程序訪問KEY1時，Redis會檢查KEY1是否過期，如果過期則刪除並不返回該值，這就是惰性刪除策略。結合定期刪除和惰性刪除兩種策略，就可以保證過期數據可以被刪除。2 內存淘汰當內存不足時Redis會選擇一些緩存元素進行刪除，那麼哪些緩存元素會被刪除？
  • 從零開始手寫 redis（八）樸素 LRU 淘汰算法性能優化
    前言java從零手寫實現redis（一）如何實現固定大小的緩存？java從零手寫實現redis（四）添加監聽器java從零手寫實現redis（五）過期策略的另一種實現思路java從零手寫實現redis（六）AOF 持久化原理詳解及實現我們前面簡單實現了 redis 的幾個特性，java從零手寫實現redis（一）如何實現固定大小的緩存？ 中實現了先進先出的驅除策略。
  • 2020-09-18：LRU手擼，說下時間複雜度和空間複雜度
    福哥答案2020-09-18：方法：哈希表 + 雙向鍊表。時間複雜度：對於 put 和 get 都是 O(1)。空間複雜度：O(capacity)，因為哈希表和雙向鍊表最多存儲 capacity+1 個元素。
  • 緩存淘汰算法LRU和LFU
    前言LRU算法和LFU算法是屬於頁面置換的一種算法，或者更通俗的說，就是緩存如何淘汰的一種策略。我們通常在設計一個系統的時候，由於資料庫的讀取速度遠小於內存的讀取速度，所以為了加快讀取速度，會將一部分數據放到內存中，稱為緩存。但是內存容量是有限的，當你要緩存的數據超出容量，就得有部分數據刪除，這時候哪些數據刪除，哪些數據保留，就是LRU算法和LFU算法要幹的事。
  • 使用Python的lru_cache秒殺大量動態規劃問題
    1.初步寫法這道題的思路很清晰，當臺階n > 2 時，每次就有兩種做法，即爬1臺階和爬2臺階，我們遞歸回歸調用 climbStairs 就完事了，入參分別 n-1 和 n-2class Solution: def climbStairs(self, n: int) -> int:
  • 緩存穿透、緩存擊穿、緩存雪崩看這篇就夠了
    常用的緩存有單機版的EhCache、分布式版的Memcache和Redis，都屬於K-V類型的存儲，Key與Value一一對應。當然如果較真的話他們也屬於NoSQL範疇，比如Redis彌補了關係數據不能存儲結構數據的缺憾。雖然這些緩存中間件已經非常成熟和穩定，也得到了廣泛的應用，但設計一個良好的緩存系統還是會遇到很多問題需要解決、方案也需要取捨。
  • JAVA實現LRU算法
    題目就是實現一個LRU算法的緩存。外包居然要求也這麼高了，哎。還好，LRU是我大學老師布置的一道題目，當然我用C語言實現的，算法原理那是一清二楚，可是面試的時候就腦子一片空白了。好在，邊敲代碼，邊思考，就慢慢想起來了，下面是我的代碼。