1. LRU

• 1.1. 原理
  • LRU（Least recently used誓禁，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。
• 1.2. 實現(xiàn)
  最常見的實現(xiàn)是使用一個鏈表保存緩存數(shù)據(jù)如输，詳細(xì)算法實現(xiàn)如下：

• 1. 新數(shù)據(jù)插入到鏈表頭部；
• 2. 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問）央勒，則將數(shù)據(jù)移到鏈表頭部不见；
• 3. 當(dāng)鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄崔步。

• 1.3. 分析

  • 【命中率】
    • 當(dāng)存在熱點數(shù)據(jù)時脖祈，LRU的效率很好，但偶發(fā)性的刷晋、周期性的批量操作會導(dǎo)致LRU命中率急劇下降盖高，緩存污染情況比較嚴(yán)重。
  • 【復(fù)雜度】
    • 實現(xiàn)簡單眼虱。
  • 【代價】
    • 命中時需要遍歷鏈表喻奥，找到命中的數(shù)據(jù)塊索引，然后需要將數(shù)據(jù)移到頭部捏悬。

2. LRU-K

• 2.1. 原理
  • LRU-K中的K代表最近使用的次數(shù)撞蚕，因此LRU可以認(rèn)為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題过牙，其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴展為“最近使用過K次”甥厦。
• 2.2. 實現(xiàn)
  • 相比LRU，LRU-K需要多維護一個隊列寇钉，用于記錄所有緩存數(shù)據(jù)被訪問的歷史刀疙。只有當(dāng)數(shù)據(jù)的訪問次數(shù)達到K次的時候，才將數(shù)據(jù)放入緩存扫倡。當(dāng)需要淘汰數(shù)據(jù)時谦秧，LRU-K會淘汰第K次訪問時間距當(dāng)前時間最大的數(shù)據(jù)。詳細(xì)實現(xiàn)如下：

• 1. 數(shù)據(jù)第一次被訪問撵溃，加入到訪問歷史列表疚鲤；
• 2. 如果數(shù)據(jù)在訪問歷史列表里后沒有達到K次訪問，則按照一定規(guī)則（FIFO缘挑，LRU）淘汰集歇；
• 3. 當(dāng)訪問歷史隊列中的數(shù)據(jù)訪問次數(shù)達到K次后，將數(shù)據(jù)索引從歷史隊列刪除语淘，將數(shù)據(jù)移到緩存隊列中诲宇，并緩存此數(shù)據(jù)际歼，緩存隊列重新按照時間排序；
• 4. 緩存數(shù)據(jù)隊列中被再次訪問后焕窝，重新排序；
• 5. 需要淘汰數(shù)據(jù)時维贺，淘汰緩存隊列中排在末尾的數(shù)據(jù)它掂，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)。
     LRU-K具有LRU的優(yōu)點溯泣，同時能夠避免LRU的缺點虐秋，實際應(yīng)用中LRU-- 2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高垃沦，但適應(yīng)性差客给，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉。

• 2.3. 分析

  • 【命中率】
    • LRU-K降低了“緩存污染”帶來的問題肢簿，命中率比LRU要高靶剑。
  • 【復(fù)雜度】
    • LRU-K隊列是一個優(yōu)先級隊列，算法復(fù)雜度和代價比較高池充。
  • 【代價】
    • 由于LRU-K還需要記錄那些被訪問過桩引、但還沒有放入緩存的對象，因此內(nèi)存消耗會比LRU要多收夸；當(dāng)數(shù)據(jù)量很大的時候坑匠，內(nèi)存消耗會比較可觀。
    • LRU-K需要基于時間進行排序（可以需要淘汰時再排序卧惜，也可以即時排序）厘灼，CPU消耗比LRU要高。

3. Two queues（2Q）

• 3.1. 原理
  • Two queues（以下使用2Q代替）算法類似于LRU-2咽瓷，不同點在于2Q將LRU-2算法中的訪問歷史隊列（注意這不是緩存數(shù)據(jù)的）改為一個FIFO緩存隊列设凹，即：2Q算法有兩個緩存隊列，一個是FIFO隊列茅姜，一個是LRU隊列围来。
• 3.2. 實現(xiàn)
  • 當(dāng)數(shù)據(jù)第一次訪問時，2Q算法將數(shù)據(jù)緩存在FIFO隊列里面匈睁，當(dāng)數(shù)據(jù)第二次被訪問時监透，則將數(shù)據(jù)從FIFO隊列移到LRU隊列里面，兩個隊列各自按照自己的方法淘汰數(shù)據(jù)航唆。詳細(xì)實現(xiàn)如下：

• 1. 新訪問的數(shù)據(jù)插入到FIFO隊列胀蛮；
• 2. 如果數(shù)據(jù)在FIFO隊列中一直沒有被再次訪問，則最終按照FIFO規(guī)則淘汰糯钙；
• 3. 如果數(shù)據(jù)在FIFO隊列中被再次訪問粪狼，則將數(shù)據(jù)移到LRU隊列頭部退腥；
• 4. 如果數(shù)據(jù)在LRU隊列再次被訪問，則將數(shù)據(jù)移到LRU隊列頭部再榄；
• 5. LRU隊列淘汰末尾的數(shù)據(jù)狡刘。

• 3.3. 分析

  • 【命中率】
    • 2Q算法的命中率要高于LRU。
  • 【復(fù)雜度】
    • 需要兩個隊列困鸥，但兩個隊列本身都比較簡單嗅蔬。
  • 【代價】
    • FIFO和LRU的代價之和。

• 2Q算法和LRU-2算法命中率類似疾就，內(nèi)存消耗也比較接近澜术，但對于最后緩存的數(shù)據(jù)來說，2Q會減少一次從原始存儲讀取數(shù)據(jù)或者計算數(shù)據(jù)的操作猬腰。

4. Multi Queue（MQ）

• 4.1. 原理
  • MQ算法根據(jù)訪問頻率將數(shù)據(jù)劃分為多個隊列鸟废，不同的隊列具有不同的訪問優(yōu)先級，其核心思想是：優(yōu)先緩存訪問次數(shù)多的數(shù)據(jù)姑荷。
• 4.2. 實現(xiàn)
  • MQ算法將緩存劃分為多個LRU隊列盒延，每個隊列對應(yīng)不同的訪問優(yōu)先級。訪問優(yōu)先級是根據(jù)訪問次數(shù)計算出來的鼠冕，例如
    詳細(xì)的算法結(jié)構(gòu)圖如下兰英，Q0，Q1....Qk代表不同的優(yōu)先級隊列供鸠，Q-history代表從緩存中淘汰數(shù)據(jù)畦贸，但記錄了數(shù)據(jù)的索引和引用次數(shù)的隊列：

如上圖，算法詳細(xì)描述如下：

• 1. 新插入的數(shù)據(jù)放入Q0楞捂；
• 2. 每個隊列按照LRU管理數(shù)據(jù)薄坏；
• 3. 當(dāng)數(shù)據(jù)的訪問次數(shù)達到一定次數(shù)，需要提升優(yōu)先級時寨闹，將數(shù)據(jù)從當(dāng)前隊列刪除胶坠，加入到高一級隊列的頭部；
• 4. 為了防止高優(yōu)先級數(shù)據(jù)永遠(yuǎn)不被淘汰繁堡，當(dāng)數(shù)據(jù)在指定的時間里訪問沒有被訪問時沈善，需要降低優(yōu)先級，將數(shù)據(jù)從當(dāng)前隊列刪除椭蹄，加入到低一級的隊列頭部闻牡；
• 5. 需要淘汰數(shù)據(jù)時，從最低一級隊列開始按照LRU淘汰绳矩；每個隊列淘汰數(shù)據(jù)時罩润，將數(shù)據(jù)從緩存中刪除，將數(shù)據(jù)索引加入Q-history頭部翼馆；
• 6. 如果數(shù)據(jù)在Q-history中被重新訪問割以，則重新計算其優(yōu)先級金度，移到目標(biāo)隊列的頭部；
• 7. Q-history按照LRU淘汰數(shù)據(jù)的索引严沥。

• 4.3. 分析

  • 【命中率】
    • MQ降低了“緩存污染”帶來的問題猜极，命中率比LRU要高。
  • 【復(fù)雜度】
    • MQ需要維護多個隊列消玄，且需要維護每個數(shù)據(jù)的訪問時間跟伏，復(fù)雜度比LRU高。
  • 【代價】
    • MQ需要記錄每個數(shù)據(jù)的訪問時間莱找，需要定時掃描所有隊列酬姆，代價比LRU要高嗜桌。

• 注：雖然MQ的隊列看起來數(shù)量比較多奥溺，但由于所有隊列之和受限于緩存容量的大小，因此這里多個隊列長度之和和一個LRU隊列是一樣的骨宠，因此隊列掃描性能也相近浮定。

5. LRU類算法對比

由于不同的訪問模型導(dǎo)致命中率變化較大，此處對比僅基于理論定性分析层亿，不做定量分析桦卒。

• 實際應(yīng)用中需要根據(jù)業(yè)務(wù)的需求和對數(shù)據(jù)的訪問情況進行選擇，并不是命中率越高越好匿又。例如：雖然LRU看起來命中率會低一些方灾，且存在”緩存污染“的問題，但由于其簡單和代價小碌更，實際應(yīng)用中反而應(yīng)用更多裕偿。

• java中最簡單的LRU算法實現(xiàn)，就是利用jdk的LinkedHashMap痛单，覆寫其中的removeEldestEntry(Map.Entry)方法即可.如果你去看LinkedHashMap的源碼可知嘿棘，LRU算法是通過雙向鏈表來實現(xiàn)，當(dāng)某個位置被命中旭绒，通過調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到頭位置鸟妙，新加入的內(nèi)容直接放在鏈表頭，如此一來挥吵，最近被命中的內(nèi)容就向鏈表頭移動重父，需要替換時，鏈表最后的位置就是最近最少使用的位置忽匈。

基于雙鏈表 的LRU實現(xiàn):

• 傳統(tǒng)意義的LRU算法是為每一個Cache對象設(shè)置一個計數(shù)器坪郭，每次Cache命中則給計數(shù)器+1，而Cache用完脉幢，需要淘汰舊內(nèi)容歪沃，放置新內(nèi)容時嗦锐，就查看所有的計數(shù)器，并將最少使用的內(nèi)容替換掉沪曙。

• 它的弊端很明顯奕污，如果Cache的數(shù)量少，問題不會很大液走， 但是如果Cache的空間過大碳默，達到10W或者100W以上，一旦需要淘汰缘眶，則需要遍歷所有計算器嘱根，其性能與資源消耗是巨大的。效率也就非常的慢了巷懈。

• 它的原理： 將Cache的所有位置都用雙連表連接起來该抒，當(dāng)一個位置被命中之后，就將通過調(diào)整鏈表的指向顶燕，將該位置調(diào)整到鏈表頭的位置凑保，新加入的Cache直接加到鏈表頭中。

• 這樣涌攻，在多次進行Cache操作后欧引，最近被命中的，就會被向鏈表頭方向移動恳谎，而沒有命中的芝此，而想鏈表后面移動，鏈表尾則表示最近最少使用的Cache因痛。

• 當(dāng)需要替換內(nèi)容時候婚苹，鏈表的最后位置就是最少被命中的位置，我們只需要淘汰鏈表最后的部分即可婚肆。

  • 上面說了這么多的理論租副， 下面用代碼來實現(xiàn)一個LRU策略的緩存。

  • 我們用一個對象來表示Cache较性，并實現(xiàn)雙鏈表

public class LRUCache {
    /**
     * 鏈表節(jié)點
     * @author Administrator
     *
     */
    class CacheNode {
        CacheNode prev;//前一節(jié)點
        CacheNode next;//后一節(jié)點
        Object value;//值
        Object key;//鍵
        CacheNode() {
        }
    }
    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//緩存容器
    }
    
    /**
     * 獲取緩存中對象
     * @param key
     * @return
     */
    public Object get(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        } else {
            return null;
        }
    }
    
    /**
     * 添加緩存
     * @param key
     * @param value
     */
    public void put(Object key, Object value) {
        CacheNode node = (CacheNode) nodes.get(key);
        
        if (node == null) {
            //緩存容器是否已經(jīng)超過大小.
            if (currentSize >= cacheSize) {
                if (last != null)//將最少使用的刪除
                    nodes.remove(last.key);
                removeLast();
            } else {
                currentSize++;
            }
            
            node = new CacheNode();
        }
        node.value = value;
        node.key = key;
        //將最新使用的節(jié)點放到鏈表頭用僧，表示最新使用的.
        moveToHead(node);
        nodes.put(key, node);
    }
    /**
     * 將緩存刪除
     * @param key
     * @return
     */
    public Object remove(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
            if (last == node)
                last = node.prev;
            if (first == node)
                first = node.next;
        }
        return node;
    }
    public void clear() {
        first = null;
        last = null;
    }
    /**
     * 刪除鏈表尾部節(jié)點
     *  表示 刪除最少使用的緩存對象
     */
    private void removeLast() {
        //鏈表尾不為空,則將鏈表尾指向null. 刪除連表尾（刪除最少使用的緩存對象）
        if (last != null) {
            if (last.prev != null)
                last.prev.next = null;
            else
                first = null;
            last = last.prev;
        }
    }
    
    /**
     * 移動到鏈表頭，表示這個節(jié)點是最新使用過的
     * @param node
     */
    private void moveToHead(CacheNode node) {
        if (node == first)
            return;
        if (node.prev != null)
            node.prev.next = node.next;
        if (node.next != null)
            node.next.prev = node.prev;
        if (last == node)
            last = node.prev;
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null)
            last = first;
    }
    private int cacheSize;
    private Hashtable nodes;//緩存容器
    private int currentSize;
    private CacheNode first;//鏈表頭
    private CacheNode last;//鏈表尾
}

本文轉(zhuǎn)載自 緩存淘汰算法--LRU算法赞咙。

241天以來责循，Java架構(gòu)更新了 602個主題，已經(jīng)有100+位同學(xué)加入攀操。微信掃碼關(guān)注java架構(gòu)院仿，獲取Java面試題和架構(gòu)師相關(guān)題目和視頻。上述相關(guān)面試題答案，盡在Java架構(gòu)中歹垫。