一、引言

在日常開發(fā)使用中，我們經(jīng)常會使用key-value，也就是hash的數(shù)據(jù)結(jié)構(gòu)，在java中我們用的HashMap通常是沒有淘汰策略的，大小在超過我們設(shè)定的值之后會自動擴容。而我們在使用緩存的場景下，其大小通常是有限制的，在容量有限的情況下，怎么合理的淘汰沒有價值的內(nèi)存，提高緩存的命中率是一門優(yōu)雅的藝術(shù)。

二、常見的淘汰策略算法

首先要定義怎樣的數(shù)據(jù)才算是“低價值”？由于緩存的通用性，這個問題的答案必須是與具體業(yè)務(wù)邏輯是無關(guān)的。我們從何種維度、如何定義數(shù)據(jù)的價值高低，其實也就決定了我們要使用什么樣的緩存淘汰策略。我們最常見的緩存淘汰策略有:FIFO(First In First Out)、LRU(Least Recent Used),LFU（Least Frequently Used）下面我們依次講解這幾種淘汰策略的實現(xiàn)原理及其實現(xiàn)。

FIFO:

先淘汰最早進入被緩存的數(shù)據(jù)。FIFO 實現(xiàn)十分簡單，但一般來說它并不是優(yōu)秀的淘汰策略，越是頻繁被用到的數(shù)據(jù)，往往會越早被存入緩存之中。如果采用這種淘汰策略，很可能會大幅降低緩存的命中率。

LRU（The Least Recently Used）:

優(yōu)先淘汰最近最久未被使用訪問過的數(shù)據(jù)。在計算機科學(xué)中，通常認(rèn)為越是最近經(jīng)常訪問的數(shù)據(jù)，越是將要被訪問到，從這個角度看，那么越久沒有被訪問到的數(shù)據(jù)，越是應(yīng)該被優(yōu)先淘汰掉。下面我來看看一下具體的實現(xiàn)。
首先具體的操作大致有兩個，一個是put操作儲存元素，另一個是get操作獲取元素值。
為了使獲取數(shù)據(jù)的時間復(fù)雜度盡可能低，我們優(yōu)先使用的是hash的數(shù)據(jù)結(jié)構(gòu)，但是想要實現(xiàn)優(yōu)先淘汰最近最久沒有被訪問的數(shù)據(jù)，那么我們首先想到可以存數(shù)據(jù)的訪問時間，在容量到達閾值時，根據(jù)根據(jù)訪問時間來判斷，但是這顯然不是最優(yōu)解。另一種辦法是我們維護一個鏈表，最久沒有訪問過的數(shù)據(jù)放在尾部，最近訪問過的數(shù)據(jù)放在頭部，這樣我們淘汰數(shù)據(jù)時，就可以直接刪除鏈表尾部的數(shù)據(jù)，其時間復(fù)雜度是O（1）。而且插入數(shù)據(jù)時，我們需要維護鏈表元素的順序性時，移動元素的時間復(fù)雜也可以達到O(1)。這樣我們基本就確定了要使用 hash 和 鏈表的數(shù)據(jù)結(jié)構(gòu)，具體兩種數(shù)據(jù)結(jié)構(gòu)定義，我們可以從思考兩種操作如何實現(xiàn)上來得到答案。

實現(xiàn)邏輯

首先put操作：存儲元素時，需要判斷元素是否已經(jīng)存在，
1、如果元素已經(jīng)存在，則更新map中key對應(yīng)的value值，并且將鏈表中的這個元素的節(jié)點移動到鏈表的頭部。
2、 如果不存在則map和鏈表中直接新增元素。在map中新增元素時，需要判斷容量是否已滿，如果容量已滿，我們需要先淘汰元素，然后需要在map和List中都新增一個元素；如果容量未滿，則直接在map和鏈表中新增。
get操作：
如果元素不存在，直接返回null，如果元素存在，則需要移動鏈表中的節(jié)點至頭部，然后返回key對應(yīng)的value值。

根據(jù)以上操作，我們定義一個LRUCache類，這個LURCache中肯定有一個 cacheMap，map中的value存的肯定不能是key對應(yīng)的value值，而應(yīng)該是一個鏈表中的一個節(jié)點Node。因為我們在put和get操作中都需要移動鏈表節(jié)點，這個節(jié)點是從map中取出來的。那Node節(jié)點應(yīng)該包含哪些屬性呢，首先value值肯定有，因為get操作我們需要返回value值。其次還需要 prev 和 next屬性，也就是這個鏈表是一個雙向鏈表，因為在刪除和移動節(jié)點的過程中需要訪問節(jié)點的前置和后置。Node中key也需要，因為刪除節(jié)點時，map中是根據(jù)key刪除的。為了方便操作雙向鏈表，使得刪除（刪除尾節(jié)點）和插入（插入頭結(jié)點）操作時間復(fù)雜度尾O(1),LRUCache 中還需要 head 節(jié)點 和 tail 尾節(jié)點。 最后還需要有個 capital容量的屬性，判斷map中元素是否達到閾值。那么至此，LRUCache類的數(shù)據(jù)結(jié)構(gòu)就出來了

class LRUCache {
     private ListNode head ;
    private ListNode tail ;
    private Map<Integer,ListNode> lruMap ;
    private int capacity = 65535;

    public LRUCache(int capacity){
        this.capacity = capacity;
        head = new ListNode(null,0,0,null);
        tail = new ListNode(head,0,0,null);
        head.next = tail;
        lruMap = new HashMap<>();
    }
    
    public void put(Integer key,Integer value){
     ...
    }

    public Integer get(Integer key){
     ...
    }


   class ListNode{
        Integer key;
        Integer val;
        ListNode pre;
        ListNode next;

        public ListNode(ListNode pre,Integer key,Integer val,ListNode next){
            this.key = key;
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    }
}

LRU算法相比FIFO雖然已經(jīng)能夠顯著提高緩存的命中率，但是從另外一個角度來看，還是存在一些問題，比如一些熱點數(shù)據(jù)在系統(tǒng)中經(jīng)常被頻繁訪問，但最近一段時間因為某種原因未被訪問過（周期性熱點數(shù)據(jù)），此時這些熱點數(shù)據(jù)依然要面臨淘汰的命運，LRU 依然可能錯誤淘汰價值更高的數(shù)據(jù)。

LFU（The Least Frequently Used）:

優(yōu)先淘汰最不經(jīng)常使用的數(shù)據(jù)。如果定義一個數(shù)據(jù)會不會經(jīng)常被使用呢，可能就需要給這個元素定義一個訪問計數(shù)器， 根據(jù)訪問計數(shù)器的大小來判斷，訪問得越少，就優(yōu)先淘汰。下面我們來思考怎么實現(xiàn)。
淘汰數(shù)據(jù)時要根據(jù)元素訪問計數(shù)器的大小，怎么判斷訪問計數(shù)器大小有兩種方式，一種是在元素淘汰時，先把所有元素取出來對比一下，找到最小的淘汰，這種時間復(fù)雜度要O(N)，通常不采用。另外一種是在元素插入時，就按照其大小排列好，可以采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)，時間復(fù)雜度可以達到logN，這種顯然要更優(yōu)。
基于上面所說，基本數(shù)據(jù)結(jié)構(gòu)就出來了，采用Map 和 TreeSet的數(shù)據(jù)結(jié)構(gòu)。

public class LFUCache<K,V> {

    /**
     * 存對象key，Node
     */
    private Map<K,LFUNode<K,V>> cacheMap = new HashMap<K,LFUNode<K,V>>();

    /**
     * 排序的set，根據(jù)活躍數(shù)
     */
    private TreeSet<LFUNode> activeSet;

    private Integer capital = 65535;

    public LFUCache(Integer capital) {
        this.capital = capital;
    }

    public V get(K key) {
       ...
    }

    public void put(K key,V value) {
     ...
    }

    class LFUNode<K,V> implements Comparable<LFUNode>{
        private K key;

        private V value;

        private Integer activeCount;

        public LFUNode(K key,V value,Integer activeCount) {
            this.key = key;
            this.value = value;
            this.activeCount = activeCount;
        }

        @Override
        public int compareTo(LFUNode o) {
            return activeCount - o.activeCount;
        }
    }
}

實現(xiàn)邏輯

首先put操作：存儲元素時，需要判斷元素是否已經(jīng)存在，
1、如果元素已經(jīng)存在，則更新map中key對應(yīng)元素的value值，并且元素訪問計數(shù)器+1，treeSet中刪除此key對應(yīng)的元素，并將更新后的元素添加到treeSet。
2、 如果不存在則map和set中直接新增元素。在map中新增元素時，需要判斷容量是否已滿，如果容量已滿，我們需要先淘汰treeSet中的第一個元素（默認(rèn)訪問計數(shù)器升序排列），然后再在map和TreeSet中新增一個元素；如果容量未滿，則直接在map和TreeSet中新增一個元素。
get操作：
如果元素不存在，直接返回null，如果元素存在，從map中取出key對應(yīng)元素，元素訪問計數(shù)器+1，treeSet中刪除此key對應(yīng)的元素，并將更新后的元素添加到treeSet，最后返回元素的valuie值

優(yōu)化升級版的LFU

以上的實現(xiàn)我們上文提到我們在像treeSet中添加元素或者刪除元素時的時間復(fù)雜度都是logn，那有沒有更優(yōu)解呢，比如把時間復(fù)雜度降低為O(1)呢。在計算機科學(xué)中，還有一種常見的做法，當(dāng)我們要追求時間上的極致性能時，往往要犧牲空間上的性能，也就是以空間換時間。
使用的數(shù)據(jù)結(jié)構(gòu)：

比如我們可以建一個freqMap，key用來存訪問次數(shù)，value則使用LinkedHashSet來存儲Node節(jié)點，之所以使用LinkedHashSet，而不用List，是因為首先刪除元素操作是常數(shù)階的時間復(fù)雜度，另外， 同一個訪問次數(shù)可能對應(yīng)多個元素，需要保證這些元素是有序的，這樣我們就可以在同一個訪問次數(shù)的情況下，先刪除set中的第一個元素（也就是最久未使用的元素）。另外，我們還需要維護一個min，用來表示當(dāng)前最小訪問次數(shù)。這樣在容量超過閾值時，我們就可以直接刪除這個訪問次數(shù)的節(jié)點元素。

min的維護

具體min 怎么維護呢，我們新增元素時，min = 1。另外刪除元素時，有兩個場景，一個是cache中已經(jīng)存在此元素，這個時候，freqMap中需要刪除這個元素訪問次數(shù)中set對應(yīng)的元素節(jié)點，刪除完了之后，需要判斷一下當(dāng)前set中是否還有元素，如果沒有元素，說明當(dāng)前訪問次數(shù)中的元素訪問次數(shù)全部升級了。那么如果當(dāng)前訪問次數(shù) = min，那么min就需要+1； 還有一個場景是cache中元素已經(jīng)滿了的情況下，需要刪除min對應(yīng)set中的第一個元素，刪除之后，如果set中沒有數(shù)據(jù)，同樣需要對 min進行+1；
具體的put操作和get操作的實現(xiàn)邏輯此處不再贅述，下面只列出相關(guān)的數(shù)據(jù)結(jié)構(gòu)。

class LFUCache {
    Map<Integer, Node> cache;  // 存儲緩存的內(nèi)容
    Map<Integer, LinkedHashSet<Node>> freqMap;
    int size;
    int capacity;
    int min; // 存儲當(dāng)前最小頻次

    public LFUCache(int capacity) {
        cache = new HashMap<> (capacity);
        freqMap = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
     ...
    }
    
    public void put(int key, int value) {
        .....
    }
}

class Node {
    int key;
    int value;
    int freq = 1;

    public Node() {}
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

LFU可以解決LRU周期性的熱點數(shù)據(jù)問題，但是同樣也存在以下幾個問題：一是我們需要維護好每個元素的訪問計數(shù)器，這個維護帶來的成本是高昂的。另一個是有些數(shù)據(jù)曾經(jīng)被頻繁訪問過，但是最近不需要了，這些數(shù)據(jù)就很難被清除。比如對突發(fā)性的局部熱點數(shù)據(jù)/稀疏流量無法被淘汰，就會導(dǎo)致算法中緩存的命中率急劇下降，這個是它最大弊端。

TinyLFU

這么看來，其實LRU和LFU各有優(yōu)缺點，LRU使用于突發(fā)性流量的場景，而LFU使用于局部周期性流量。那么，有沒有一種緩存淘汰算法，能夠兼容他們兩個的優(yōu)點呢？TinyLFU算法出現(xiàn)了，顧名思義，TinyLFU是一種LFU算法，只不過在LFU算法的基礎(chǔ)上，它又對LFU面臨的兩個問題給予了解決。
首先，在第一個問題上，對每個元素的維護上帶來的時間和空間上的開銷，首先對于每個元素的維護時間上的開銷，采用了異步的方式，而不是在put或者get的時候直接取維護，而是采用了類似數(shù)據(jù)庫的基于日志提交再去處理的方式。此外，對于在維護每個元素的訪問計數(shù)所占用的空間問題上，采用了 Count–Min Sketch算法（類似布隆過濾器的原理去降低存儲的空間開銷）。最后在局部熱點數(shù)據(jù)無法被淘汰的問題上，TinyLFU采用了熱度衰減機制，就是當(dāng)整體的統(tǒng)計計數(shù)（當(dāng)前所有記錄的頻率統(tǒng)計之和，這個數(shù)值內(nèi)部維護）達到某一個值時，那么所有記錄的統(tǒng)計計數(shù)除以 2。
下面我們詳細(xì)說一下Count–Min Sketch算法的具體原理

Count–Min Sketch

W-TinyLFU

W-TinyLFU 又是 TinyLFU 的改進版本。TinyLFU 在實現(xiàn)減少計數(shù)器維護頻率的同時，也帶來了無法很好地應(yīng)對稀疏突發(fā)訪問的問題，所謂稀疏突發(fā)訪問是指有一些絕對頻率較小，但突發(fā)訪問頻率很高的數(shù)據(jù)，譬如某些運維性質(zhì)的任務(wù)，也許一天、一周只會在特定時間運行一次，其余時間都不會用到，此時 TinyLFU 就很難讓這類元素通過 Sketch 的過濾，因為它們無法在運行期間積累到足夠高的頻率。應(yīng)對短時間的突發(fā)訪問是 LRU 的強項，W-TinyLFU 就結(jié)合了 LRU 和 LFU 兩者的優(yōu)點，從整體上看是它是 LFU 策略，從局部實現(xiàn)上看又是 LRU 策略。具體做法是將新記錄暫時放入一個名為 Window Cache 的前端 LRU 緩存里面，讓這些對象可以在 Window Cache 中累積熱度，如果能通過 TinyLFU 的過濾器，再進入名為 Main Cache 的主緩存中存儲，主緩存根據(jù)數(shù)據(jù)的訪問頻繁程度分為不同的段（LFU 策略，實際上 W-TinyLFU 只分了兩段），但單獨某一段局部來看又是基于 LRU 策略去實現(xiàn)的（稱為 Segmented LRU）。每當(dāng)前一段緩存滿了之后，會將低價值數(shù)據(jù)淘汰到后一段中去存儲，直至最后一段也滿了之后，該數(shù)據(jù)就徹底清理出緩存。
僅靠以上簡單的、有限的介紹，你不一定能完全理解 TinyLFU 和 W-TinyLFU 的工作原理，但肯定能看出這些改進算法比起原來基礎(chǔ)版本的 LFU 要復(fù)雜了許多。有時候為了取得理想的效果，采用較為復(fù)雜的淘汰策略是不得已的選擇。如果對具體的實現(xiàn)原理感興趣，可以看一下這篇 caffeine的緩存設(shè)計，里面有詳細(xì)的原理解析。