一嫌术、引言

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

二浴麻、常見的淘汰策略算法

首先要定義怎樣的數(shù)據(jù)才算是“低價值”得问？由于緩存的通用性，這個問題的答案必須是與具體業(yè)務邏輯是無關的软免。我們從何種維度宫纬、如何定義數(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ù)硼身。在計算機科學中硅急，通常認為越是最近經(jīng)常訪問的數(shù)據(jù)，越是將要被訪問到佳遂，從這個角度看营袜，那么越久沒有被訪問到的數(shù)據(jù)，越是應該被優(yōu)先淘汰掉丑罪。下面我來看看一下具體的實現(xiàn)荚板。
首先具體的操作大致有兩個，一個是put操作儲存元素吩屹，另一個是get操作獲取元素值跪另。
為了使獲取數(shù)據(jù)的時間復雜度盡可能低，我們優(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ù)，其時間復雜度是O（1）蓬衡。而且插入數(shù)據(jù)時喻杈，我們需要維護鏈表元素的順序性時，移動元素的時間復雜也可以達到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對應的value值，并且將鏈表中的這個元素的節(jié)點移動到鏈表的頭部携取。
2攒钳、 如果不存在則map和鏈表中直接新增元素。在map中新增元素時雷滋，需要判斷容量是否已滿不撑，如果容量已滿文兢，我們需要先淘汰元素，然后需要在map和List中都新增一個元素焕檬；如果容量未滿姆坚，則直接在map和鏈表中新增。
get操作：
如果元素不存在实愚，直接返回null兼呵，如果元素存在，則需要移動鏈表中的節(jié)點至頭部爆侣，然后返回key對應的value值萍程。

根據(jù)以上操作，我們定義一個LRUCache類兔仰，這個LURCache中肯定有一個 cacheMap茫负，map中的value存的肯定不能是key對應的value值，而應該是一個鏈表中的一個節(jié)點Node乎赴。因為我們在put和get操作中都需要移動鏈表節(jié)點忍法，這個節(jié)點是從map中取出來的。那Node節(jié)點應該包含哪些屬性呢榕吼，首先value值肯定有饿序，因為get操作我們需要返回value值。其次還需要 prev 和 next屬性羹蚣，也就是這個鏈表是一個雙向鏈表原探，因為在刪除和移動節(jié)點的過程中需要訪問節(jié)點的前置和后置。Node中key也需要顽素，因為刪除節(jié)點時咽弦，map中是根據(jù)key刪除的。為了方便操作雙向鏈表胁出，使得刪除（刪除尾節(jié)點）和插入（插入頭結(jié)點）操作時間復雜度尾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ù)器大小有兩種方式顿天，一種是在元素淘汰時，先把所有元素取出來對比一下蔑担，找到最小的淘汰牌废，這種時間復雜度要O(N)，通常不采用啤握。另外一種是在元素插入時鸟缕，就按照其大小排列好，可以采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)排抬，時間復雜度可以達到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對應元素的value值么翰，并且元素訪問計數(shù)器+1牺汤，treeSet中刪除此key對應的元素辽旋，并將更新后的元素添加到treeSet浩嫌。
2、 如果不存在則map和set中直接新增元素补胚。在map中新增元素時码耐，需要判斷容量是否已滿，如果容量已滿溶其，我們需要先淘汰treeSet中的第一個元素（默認訪問計數(shù)器升序排列）骚腥，然后再在map和TreeSet中新增一個元素；如果容量未滿瓶逃，則直接在map和TreeSet中新增一個元素束铭。
get操作：
如果元素不存在廓块，直接返回null，如果元素存在契沫，從map中取出key對應元素带猴，元素訪問計數(shù)器+1，treeSet中刪除此key對應的元素懈万，并將更新后的元素添加到treeSet拴清，最后返回元素的valuie值

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

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

比如我們可以建一個freqMap牙甫，key用來存訪問次數(shù)，value則使用LinkedHashSet來存儲Node節(jié)點调违，之所以使用LinkedHashSet窟哺，而不用List，是因為首先刪除元素操作是常數(shù)階的時間復雜度技肩，另外且轨， 同一個訪問次數(shù)可能對應多個元素，需要保證這些元素是有序的虚婿，這樣我們就可以在同一個訪問次數(shù)的情況下旋奢，先刪除set中的第一個元素（也就是最久未使用的元素）。另外然痊，我們還需要維護一個min至朗，用來表示當前最小訪問次數(shù)。這樣在容量超過閾值時剧浸，我們就可以直接刪除這個訪問次數(shù)的節(jié)點元素锹引。

min的維護

具體min 怎么維護呢，我們新增元素時唆香，min = 1嫌变。另外刪除元素時，有兩個場景躬它，一個是cache中已經(jīng)存在此元素腾啥，這個時候，freqMap中需要刪除這個元素訪問次數(shù)中set對應的元素節(jié)點，刪除完了之后倘待，需要判斷一下當前set中是否還有元素疮跑，如果沒有元素，說明當前訪問次數(shù)中的元素訪問次數(shù)全部升級了凸舵。那么如果當前訪問次數(shù) = min祸挪，那么min就需要+1； 還有一個場景是cache中元素已經(jīng)滿了的情況下贞间，需要刪除min對應set中的第一個元素贿条，刪除之后，如果set中沒有數(shù)據(jù)增热，同樣需要對 min進行+1整以；
具體的put操作和get操作的實現(xià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; // 存儲當前最小頻次

    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ù)/稀疏流量無法被淘汰朝蜘，就會導致算法中緩存的命中率急劇下降，這個是它最大弊端涩金。

TinyLFU

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

Count–Min Sketch

W-TinyLFU

W-TinyLFU 又是 TinyLFU 的改進版本蔚约。TinyLFU 在實現(xiàn)減少計數(shù)器維護頻率的同時，也帶來了無法很好地應對稀疏突發(fā)訪問的問題涂籽，所謂稀疏突發(fā)訪問是指有一些絕對頻率較小苹祟，但突發(fā)訪問頻率很高的數(shù)據(jù)，譬如某些運維性質(zhì)的任務评雌，也許一天树枫、一周只會在特定時間運行一次，其余時間都不會用到景东，此時 TinyLFU 就很難讓這類元素通過 Sketch 的過濾砂轻，因為它們無法在運行期間積累到足夠高的頻率。應對短時間的突發(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）故响。每當前一段緩存滿了之后，會將低價值數(shù)據(jù)淘汰到后一段中去存儲颁独，直至最后一段也滿了之后彩届，該數(shù)據(jù)就徹底清理出緩存。
僅靠以上簡單的、有限的介紹睁蕾，你不一定能完全理解 TinyLFU 和 W-TinyLFU 的工作原理，但肯定能看出這些改進算法比起原來基礎版本的 LFU 要復雜了許多认臊。有時候為了取得理想的效果寨辩，采用較為復雜的淘汰策略是不得已的選擇吓懈。如果對具體的實現(xiàn)原理感興趣，可以看一下這篇 caffeine的緩存設計靡狞，里面有詳細的原理解析耻警。