LRU算法—緩存淘汰算法原理

1、LRU

1.1 LRU核心原理
Least recently used(LRU，最近最少使用)算法根據(jù)數(shù)據(jù)的歷史訪問記錄淘汰數(shù)據(jù)。其核心思想是“如果數(shù)據(jù)最近被訪問過丈秩，那么將來被訪問的幾率也更高”；

1.2 算法實(shí)現(xiàn)
最常見的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)淳衙，詳細(xì)算法實(shí)現(xiàn)如下：

LRU簡化模型算法.png

算法流程：

新數(shù)據(jù)插入到鏈表頭部蘑秽；
每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問）饺著，則將數(shù)據(jù)移到鏈表頭部；
當(dāng)鏈表滿的時(shí)候肠牲，將鏈表尾部的數(shù)據(jù)丟棄幼衰。

幾種實(shí)現(xiàn)方案：
1.用一個(gè)數(shù)組來存儲(chǔ)數(shù)據(jù)，給每一個(gè)數(shù)據(jù)項(xiàng)標(biāo)記一個(gè)訪問時(shí)間戳缀雳，每次插入新數(shù)據(jù)項(xiàng)的時(shí)候渡嚣，先把數(shù)組中存在的數(shù)據(jù)項(xiàng)的時(shí)間戳自增，并將新數(shù)據(jù)項(xiàng)的時(shí)間戳置為0并插入到數(shù)組中肥印。每次訪問數(shù)組中的數(shù)據(jù)項(xiàng)的時(shí)候严拒，將被訪問的數(shù)據(jù)項(xiàng)的時(shí)間戳置為0。當(dāng)數(shù)組空間已滿時(shí)竖独，將時(shí)間戳最大的數(shù)據(jù)項(xiàng)淘汰。

2.利用一個(gè)鏈表來實(shí)現(xiàn)挤牛，每次新插入數(shù)據(jù)的時(shí)候?qū)⑿聰?shù)據(jù)插到鏈表的頭部；每次緩存命中（即數(shù)據(jù)被訪問）墓赴，則將數(shù)據(jù)移到鏈表頭部竞膳；那么當(dāng)鏈表滿的時(shí)候诫硕，就將鏈表尾部的數(shù)據(jù)丟棄。

3.利用LinkedHashMap章办。 LinkedHashMap是用的HashMap加雙鏈表實(shí)現(xiàn)的锉走，而且本身已經(jīng)實(shí)現(xiàn)了按照訪問順序的存儲(chǔ)藕届，這樣可以直接用這個(gè)類來保存數(shù)據(jù)，只需要在移除元素時(shí)簡單處理就行休偶。

對(duì)于第一種方法，需要不停地維護(hù)數(shù)據(jù)項(xiàng)的訪問時(shí)間戳踏兜，另外词顾，在插入數(shù)據(jù)碱妆、刪除數(shù)據(jù)以及訪問數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度都是O(n)山橄。對(duì)于第二種方法垮媒，鏈表在定位數(shù)據(jù)的時(shí)候時(shí)間復(fù)雜度為O(n)。所以在一般使用第三種方式來是實(shí)現(xiàn)LRU算法睡雇。

1.3 分析
【命中率】
當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU的效率很好它抱，但偶發(fā)性的秕豫、周期性的批量操作會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重观蓄。
【復(fù)雜度】
實(shí)現(xiàn)簡單混移。
【代價(jià)】
命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引侮穿，然后需要將數(shù)據(jù)移到頭部歌径。
1.4 代碼實(shí)現(xiàn)

/**
 * 類說明：利用LinkedHashMap實(shí)現(xiàn)LRU緩存， 必須實(shí)現(xiàn)removeEldestEntry方法
 */
public class LRU<K, V> {
    private static final float LOAD_FACTOR = 0.75f;
    private LinkedHashMap<K, V> map;
    private int capacitySize;

    public LRU(int capacitySize) {
        this.capacitySize = capacitySize;
        map = new LinkedHashMap<K, V>(capacitySize, LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Entry<K, V> eldest) {
                return size() > capacitySize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

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

    public synchronized void clear() {
        map.clear();
    }
}

2亲茅、LRU-K

2.1 LRU-K核心原理
LRU-K中的K代表最近使用的次數(shù)回铛，因此LRU可以認(rèn)為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題克锣，其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過K次”茵肃。

2.2 算法實(shí)現(xiàn)

LRU-K模型算法.png

算法流程：
1）數(shù)據(jù)第一次被訪問，加入到訪問歷史記錄表（簡稱記錄表）袭祟；在記錄表中對(duì)應(yīng)的K單元中設(shè)置最后訪問時(shí)間=new()验残，且設(shè)置訪問次數(shù)為1；
2）如果數(shù)據(jù)訪問次數(shù)沒有達(dá)到K次巾乳，則訪問次數(shù)+1您没。最后訪問時(shí)間與當(dāng)前時(shí)間間隔超過預(yù)設(shè)的值(如30秒)，訪問次數(shù)清0并加1胆绊；
3）當(dāng)數(shù)據(jù)訪問計(jì)數(shù)超過(>=)K次后紊婉，則訪問次數(shù)+1。將數(shù)據(jù)保存到LRU緩存隊(duì)列中辑舷，緩存隊(duì)列重新按照時(shí)間排序喻犁；
4）LRU緩存隊(duì)列中數(shù)據(jù)被再次訪問后，重新排序何缓；
5）LRU緩存隊(duì)列需要淘汰數(shù)據(jù)時(shí)肢础，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)碌廓。

2.3 分析
【命中率】
LRU-K降低了“緩存污染”帶來的問題传轰，命中率比LRU要高。
【復(fù)雜度】
LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列谷婆，算法復(fù)雜度和代價(jià)比較高慨蛙。
【代價(jià)】
由于LRU-K還需要記錄那些被訪問過辽聊、但還沒有放入緩存的對(duì)象，因此內(nèi)存消耗會(huì)比LRU要多期贫；當(dāng)數(shù)據(jù)量很大的時(shí)候跟匆，內(nèi)存消耗會(huì)比較可觀。
LRU-K需要基于時(shí)間進(jìn)行排序（可以在需要淘汰時(shí)再排序通砍，也可以即時(shí)排序）玛臂，CPU消耗比LRU要高。

總結(jié)：
LRU-K具有LRU的優(yōu)點(diǎn)封孙，同時(shí)能夠避免LRU的缺點(diǎn)迹冤，實(shí)際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會(huì)高虎忌，但適應(yīng)性差泡徙，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉。

參考：
1）緩存淘汰算法--LRU算法
2）基于LRU-K算法設(shè)計(jì)本地緩存實(shí)現(xiàn)流量削峰
3）LRU算法四種實(shí)現(xiàn)方式介紹