緩存淘汰算法LRU和LFU

2020-10-13 阿毛雜記

前言

LRU算法和LFU算法是屬於頁面置換的一種算法，或者更通俗的說，就是緩存如何淘汰的一種策略。

我們通常在設計一個系統的時候，由於資料庫的讀取速度遠小於內存的讀取速度，所以為了加快讀取速度，會將一部分數據放到內存中，稱為緩存。

但是內存容量是有限的，當你要緩存的數據超出容量，就得有部分數據刪除，這時候哪些數據刪除，哪些數據保留，就是LRU算法和LFU算法要幹的事。

什麼是LRU算法

LRU算法，全稱Least recently used，即最近最少使用。LRU算法的思想是如果數據最近被訪問過，那麼將來被訪問的概率也會很高。

根據這個思想，我們可以想到，實現LRU算法肯定會用到列表/鍊表，目的是保證有序；還有一個是用到哈希表，這是因為緩存經常是key-value鍵值對的形式。

比較簡單的做法是使用列表+哈希表，但是這種方式查詢和插入的時間複雜度都是O(n)，還有一種做法是使用雙向鍊表+哈希表，查詢和插入的時間複雜度都是O(1)，但是耗費的空間資源比較多。

列表+哈希表的實現

如上圖，假設我們使用頭插法，即最近訪問的元素放在最前面，最晚的元素放在最後面，則實現LRU算法的步驟如下：

  • 1.初始化一個空列表，如上圖，其容器為5。
  • 2.當執行查找（GET）操作時，需要遍歷整個列表，找到key相同的元素，時間複雜度為O(n)
  • 3.當執行插入（PUT）操作時，有三種情況：
  • 3.1 遍歷列表，如果元素的key存在，更新value的值，並把這個元素放到列表的最前面，從而保證最後面的元素是最晚訪問的。
  • 3.2 遍歷列表，如果元素的key不存在，且列表的容量未滿，則把這個元素放到列表的最前面
  • 3.3 遍歷列表，如果元素的key不存在，且列表的容量已滿，刪除最後的元素，並把新元素放到最前面

雙向鍊表+哈希表的實現

這應該是面試比較常考的點，面試官可能會問你，如果實現一個時間複雜度為O(1)的LRU緩存？

這種實現的結構如下：

上述LRUCache的m其實就是上圖左邊的HashMap，它的目的是為了實現查找的時間複雜度為O(1)。

如果沒有這個m，則查找元素的時候，需要遍歷雙向鍊表，時間複雜度為O(n)。

而使用雙向鍊表的原因主要是為了實現節點插入/刪除的時間複雜度為O(1)。

那使用單鍊表不行嗎？

如上，使用單鍊表的話，可以實現頭部快速插入新節點，尾部快速刪除舊節點，時間複雜度都是O(1)。

但是對於中間節點，比如我需要節點1的值由2更新為4，這時候除了更新值，還需要將其移動到最前面，而對於單鍊表，它只知道下一個元素，並不知道上一個元素，為了得到上一個元素，它必須遍歷一次鍊表才知道，時間複雜度為O(n)，這就是為什麼要用雙向鍊表的原因。

關於這種方式的源碼實現，可以查看Leetcode LRU雙向鍊表實現

什麼是LFU算法

LFU算法，全稱Least frequently used，即最不經常使用。LFU算法的思想是一定時期內被訪問次數最少的節點，在將來被訪問到的機率也是最小的。

由此可以看到，LFU強調的是訪問次數，而LRU強調的是訪問時間。

LFU有兩種實現方式，一是哈希表+平衡二叉樹，二是雙哈希表，下面以雙哈希表為例，說明LFU具體的步驟：

雙哈希表的實現

雙哈希表的實現如下圖：

如上，雙哈希表需要維護兩個哈希表以及一個最少頻次使用的計數minFreq。

第一個哈希表是 freq_table，它的key是訪問的頻次，它的value是一個雙向鍊表，雙向鍊表的每一個節點包含三個元素：key，value，以及count。

第二個哈希表是 key_table，它的key是雙向鍊表中存儲的key，value是對應節點的指針（這樣查找的時間複雜度就是O(1)）。

類比LRU，LFU的步驟如下：

  • 1.假設LFU緩存容量為3，且一開始初始化插入三個鍵值對（1，1），（2，2），（3，3）此時每個鍵值對的頻次都是1，所以它們都在同一個雙向鍊表上，如圖四。
  • 2.假設這時候查找key=1，由於key_table存儲的是節點的指針，所以可以以O(1)的複雜度得到結果。
  • 2.1 注意此時節點1的頻次由1變為2，所以要將節點1移動到頻次為2的鍊表，如圖五
  • 2.2 另外，minFreq也要記得同步更新，不過本次操作不用。
  • 3.假設這時候插入一個新的鍵值對（4，4），由於它的頻次為1，所以對應鍊表1，它會被插入到鍊表1的最前面，而由於這種操作，所以同鍊表的最後一個元素肯定是最晚插入的。
  • 3.1 由於新加的元素導致容量溢出，所以我們要刪除頻次最少，插入時間最晚的，即圖五的（3，3，1）

相關焦點

  • 「Redis源碼分析」Redis中的LRU算法實現
    希望閱讀完可以得到你的一個【三連】，這將是對我最大的鼓勵和支持。LRU是什麼LRU(least recently used)是一種緩存置換算法。即在緩存有限的情況下，如果有新的數據需要加載進緩存，則需要將最不可能被繼續訪問的緩存剔除掉。
  • Redis內存淘汰機制
    從已設置過期時間的數據集中挑選任意 Key淘汰volatile-lfu從已設置過期時間的數據集中挑選最不經常使用的 Key 淘汰allkeys-lru當內存不足寫入新數據時淘汰最近最少使用的 Keyallkeys-random當內存不足寫入新數據時隨機選擇任意 key淘汰allkeys-lfu當內存不足寫入新數據時移除最不經常使用的Keyvolatile為前綴的策略都是從 已過期的數據集
  • 從零開始手寫 redis（九）LRU 緩存淘汰避免緩存汙染
    當緩存使用的空間達到上限後，就需要從已有的數據中淘汰一部分以維持緩存的可用性，而淘汰數據的選擇就是通過LRU算法完成的。LRU算法的基本思想是基於局部性原理的時間局部性：如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。
  • 從零開始手寫 redis（十）緩存淘汰LFU算法詳解
    java從零手寫實現redis（四）添加監聽器java從零手寫實現redis（五）過期策略的另一種實現思路java從零手寫實現redis（六）AOF 持久化原理詳解及實現java從零手寫實現redis（七）LRU 緩存淘汰策略詳解java從零開始手寫 redis（八）樸素 LRU 淘汰算法性能優化本節一起來學習下另一個常用的緩存淘汰算法
  • 你從未了解過的Redis內存淘汰機制
    >3|3LRU 算法概念LRU(Least Recently Used)，最近最少使用，是一種緩存置換算法，其核心思想是：如果一個數據在最近一段時間內沒有被用到LRU 和 近似 LRU 效果對比下圖是常規LRU淘汰策略與Redis隨機樣本取一鍵淘汰策略的對比，淺灰色表示已經刪除的鍵，深灰色表示沒有被刪除的鍵，綠色表示新加入的鍵，越往上表示鍵加入的時間越久。
  • 面試必問：請手寫淘汰算法LRU與LFU
    從Redis看淘汰算法雖然「Redis」有自己的過期策略來刪除過期的數據（惰性刪除和抽樣刪除）。這其中具體的刪除原理本章不做詳細介紹。但是也會存在Redis刪不過來導致內存佔滿的情況。所以「Redis」使用了一些淘汰算法來處理這些來不及刪除的數據。下面我們來說說「LRU」淘汰算法。
  • LRU算法
    LRU算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。當List空間已滿時，將時間戳最大的數據項淘汰。利用一個鍊表來實現，每次新插入數據的時候將新數據插到鍊表的頭部；每次緩存命中（即數據被訪問），則將數據移到鍊表頭部；那麼當鍊表滿的時候，就將鍊表尾部的數據丟棄。利用鍊表和hashmap。
  • Redis5.0數據淘汰策略詳解(最新版本,面試常問)
    作為一個內存資料庫，redis在內存空間不足的時候，為了保證命中率，就會選擇一定的數據淘汰策略，這篇文章主要講解常見的幾種內存淘汰策略。和我們作業系統中的頁面置換算法類似。一、參數設置我們的redis資料庫的最大緩存、主鍵失效、淘汰機制等參數都是通過配置文件來配置的。
  • LRU緩存算法的實現
    ，將最近長時間未使用的頁面淘汰，其實也很簡單，就是要將不受歡迎的頁面及時淘汰，不讓它佔著茅坑不拉shit，浪費資源。常見的頁面置換算法有如下幾種：LRU 最近最久未使用FIFO 先進先出置換算法 類似隊列OPT 最佳置換算法 (理想中存在的)NRU Clock置換算法LFU 最少使用置換算法PBA 頁面緩衝算法
  • 從零開始手寫 redis（八）樸素 LRU 淘汰算法性能優化
    （Least Recently Use），廣泛的應用於緩存機制中。當緩存使用的空間達到上限後，就需要從已有的數據中淘汰一部分以維持緩存的可用性，而淘汰數據的選擇就是通過LRU算法完成的。LRU算法的基本思想是基於局部性原理的時間局部性：如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。
  • 詳解工程師不可不會的LRU緩存淘汰算法
    大家好，歡迎大家來到算法數據結構專題，今天我們和大家聊一個非常常用的算法，叫做LRU。LRU的英文全稱是Least Recently Used，也即最不經常使用。我們看著好像挺迷糊的，其實這個含義要結合緩存一起使用。對於工程而言，緩存是非常非常重要的機制，尤其是在當下的網際網路應用環境當中，起到的作用非常重要。
  • LRU(Least Recently Used)緩存算法的實現
    作者：LuckDay 來源：JavaScript忍者秘籍LRU就是Least Recently Used，即最近最少使用，是一種常用的頁面置換算法，將最近長時間未使用的頁面淘汰，其實也很簡單，就是要將不受歡迎的頁面及時淘汰，不讓它佔著茅坑不拉shit，浪費資源。
  • LRU原理和Redis實現——一個今日頭條的面試題
    但是如果讓我們自己設計一個基於 LRU 的緩存，這樣設計可能問題很多，這段內存按照訪問時間進行了排序，會有大量的內存拷貝操作，所以性能肯定是不能接受的。那麼如何設計一個LRU緩存，使得放入和移除都是 O(1) 的，我們需要把訪問次序維護起來，但是不能通過內存中的真實排序來反應，有一種方案就是使用雙向鍊表。
  • 地鐵五分鐘理解LRU算法
    LRU（Least recently used，最近最少使用）算法作為內存管理的一種有效算法，其含義是在內存有限的情況下，當內存容量不足時，為了保證程序的運行，這時就不得不淘汰內存中的一些對象，釋放這些對象佔用的空間，那麼選擇淘汰哪些對象呢？
  • 了解常用緩存淘汰算法,這就夠了
    如果查詢一個數據，這個數據剛好在緩存裡，我們稱之為命中緩存，顯而易見，命中率，是衡量一個緩存的重要指標。淘汰算法因為需要淘汰掉數據，所以需要設計淘汰算法，總不能跟機器說，幫我淘汰掉沒價值的，那樣估計程式設計師們就要失業了，常用的淘汰算法有哪些呢？
  • 手寫一下 LRU 代碼實現？
    redis 是緩存，你給當存儲了是吧？啥叫緩存？用內存當緩存。內存是無限的嗎，內存是很寶貴而且是有限的，磁碟是廉價而且是大量的。可能一臺機器就幾十個 G 的內存，但是可以有幾個 T 的硬碟空間。redis 主要是基於內存來進行高性能、高並發的讀寫操作的。那既然內存是有限的，比如 redis 就只能用 10G，你要是往裡面寫了 20G 的數據，會咋辦？
  • 以及訂閱模式、LRU
    使用場景就是搞促銷活動時，會做預緩存，會往緩存裡放大批數據，如果直接放的話那麼會很慢，怎麼能提高效率呢？Redis的批量操作-管道（pipeline）首先Redis的管道（pipeline）並不是Redis服務端提供的功能，而是Redis客戶端為了減少網絡交互而提供的一種功能。