1. LRU
1.1.?原理
LRU（Least?recently?used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪(fǎng)問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)灌曙，其核心思想是“如果數(shù)據(jù)最近被訪(fǎng)問(wèn)過(guò)菊碟，那么將來(lái)被訪(fǎng)問(wèn)的幾率也更高”。
最常見(jiàn)的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)在刺，詳細(xì)算法實(shí)現(xiàn)如下：
1.?新數(shù)據(jù)插入到鏈表頭部逆害；
2.?每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪(fǎng)問(wèn)）头镊，則將數(shù)據(jù)移到鏈表頭部；
3.?當(dāng)鏈表滿(mǎn)的時(shí)候魄幕，將鏈表尾部的數(shù)據(jù)丟棄相艇。
【命中率】
當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU的效率很好纯陨，但偶發(fā)性的坛芽、周期性的批量操作會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重翼抠。
【復(fù)雜度】
實(shí)現(xiàn)簡(jiǎn)單靡馁。
【代價(jià)】
命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引机久，然后需要將數(shù)據(jù)移到頭部。
LRU-K中的K代表最近使用的次數(shù)赔嚎，因此LRU可以認(rèn)為是LRU-1膘盖。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問(wèn)題，其核心思想是將“最近使用過(guò)1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過(guò)K次”尤误。
相比LRU侠畔，LRU-K需要多維護(hù)一個(gè)隊(duì)列，用于記錄所有緩存數(shù)據(jù)被訪(fǎng)問(wèn)的歷史损晤。只有當(dāng)數(shù)據(jù)的訪(fǎng)問(wèn)次數(shù)達(dá)到K次的時(shí)候软棺，才將數(shù)據(jù)放入緩存。當(dāng)需要淘汰數(shù)據(jù)時(shí)尤勋，LRU-K會(huì)淘汰第K次訪(fǎng)問(wèn)時(shí)間距當(dāng)前時(shí)間最大的數(shù)據(jù)喘落。詳細(xì)實(shí)現(xiàn)如下：
1.?數(shù)據(jù)第一次被訪(fǎng)問(wèn)，加入到訪(fǎng)問(wèn)歷史列表最冰；
2.?如果數(shù)據(jù)在訪(fǎng)問(wèn)歷史列表里后沒(méi)有達(dá)到K次訪(fǎng)問(wèn)瘦棋，則按照一定規(guī)則（FIFO，LRU）淘汰暖哨；
3.?當(dāng)訪(fǎng)問(wèn)歷史隊(duì)列中的數(shù)據(jù)訪(fǎng)問(wèn)次數(shù)達(dá)到K次后赌朋，將數(shù)據(jù)索引從歷史隊(duì)列刪除，將數(shù)據(jù)移到緩存隊(duì)列中篇裁，并緩存此數(shù)據(jù)沛慢，緩存隊(duì)列重新按照時(shí)間排序；
4.?緩存數(shù)據(jù)隊(duì)列中被再次訪(fǎng)問(wèn)后达布，重新排序团甲；
5.?需要淘汰數(shù)據(jù)時(shí)，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)往枣，即：淘汰“倒數(shù)第K次訪(fǎng)問(wèn)離現(xiàn)在最久”的數(shù)據(jù)伐庭。
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ù)訪(fǎng)問(wèn)才能將歷史訪(fǎng)問(wèn)記錄清除掉集乔。
【命中率】
LRU-K降低了“緩存污染”帶來(lái)的問(wèn)題去件，命中率比LRU要高。
【復(fù)雜度】
LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列扰路，算法復(fù)雜度和代價(jià)比較高尤溜。
【代價(jià)】
由于LRU-K還需要記錄那些被訪(fǎng)問(wèn)過(guò)、但還沒(méi)有放入緩存的對(duì)象汗唱，因此內(nèi)存消耗會(huì)比LRU要多宫莱；當(dāng)數(shù)據(jù)量很大的時(shí)候，內(nèi)存消耗會(huì)比較可觀(guān)哩罪。
LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序授霸，也可以即時(shí)排序），CPU消耗比LRU要高际插。
Two?queues（以下使用2Q代替）算法類(lèi)似于LRU-2碘耳，不同點(diǎn)在于2Q將LRU-2算法中的訪(fǎng)問(wèn)歷史隊(duì)列（注意這不是緩存數(shù)據(jù)的）改為一個(gè)FIFO緩存隊(duì)列，即：2Q算法有兩個(gè)緩存隊(duì)列框弛，一個(gè)是FIFO隊(duì)列辛辨，一個(gè)是LRU隊(duì)列。
當(dāng)數(shù)據(jù)第一次訪(fǎng)問(wèn)時(shí)瑟枫，2Q算法將數(shù)據(jù)緩存在FIFO隊(duì)列里面斗搞，當(dāng)數(shù)據(jù)第二次被訪(fǎng)問(wèn)時(shí)，則將數(shù)據(jù)從FIFO隊(duì)列移到LRU隊(duì)列里面力奋，兩個(gè)隊(duì)列各自按照自己的方法淘汰數(shù)據(jù)榜旦。詳細(xì)實(shí)現(xiàn)如下：
1.?新訪(fǎng)問(wèn)的數(shù)據(jù)插入到FIFO隊(duì)列；
2.?如果數(shù)據(jù)在FIFO隊(duì)列中一直沒(méi)有被再次訪(fǎng)問(wèn)景殷，則最終按照FIFO規(guī)則淘汰溅呢；
3.?如果數(shù)據(jù)在FIFO隊(duì)列中被再次訪(fǎng)問(wèn)，則將數(shù)據(jù)移到LRU隊(duì)列頭部猿挚；
4.?如果數(shù)據(jù)在LRU隊(duì)列再次被訪(fǎng)問(wèn)咐旧，則將數(shù)據(jù)移到LRU隊(duì)列頭部；
5.?LRU隊(duì)列淘汰末尾的數(shù)據(jù)绩蜻。
注：上圖中FIFO隊(duì)列比LRU隊(duì)列短铣墨，但并不代表這是算法要求，實(shí)際應(yīng)用中兩者比例沒(méi)有硬性規(guī)定办绝。
【命中率】
2Q算法的命中率要高于LRU伊约。
【復(fù)雜度】
需要兩個(gè)隊(duì)列姚淆，但兩個(gè)隊(duì)列本身都比較簡(jiǎn)單。
【代價(jià)】
FIFO和LRU的代價(jià)之和屡律。
2Q算法和LRU-2算法命中率類(lèi)似腌逢，內(nèi)存消耗也比較接近，但對(duì)于最后緩存的數(shù)據(jù)來(lái)說(shuō)超埋，2Q會(huì)減少一次從原始存儲(chǔ)讀取數(shù)據(jù)或者計(jì)算數(shù)據(jù)的操作搏讶。
MQ算法根據(jù)訪(fǎng)問(wèn)頻率將數(shù)據(jù)劃分為多個(gè)隊(duì)列，不同的隊(duì)列具有不同的訪(fǎng)問(wèn)優(yōu)先級(jí)霍殴，其核心思想是：優(yōu)先緩存訪(fǎng)問(wèn)次數(shù)多的數(shù)據(jù)媒惕。
MQ算法將緩存劃分為多個(gè)LRU隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)不同的訪(fǎng)問(wèn)優(yōu)先級(jí)来庭。訪(fǎng)問(wèn)優(yōu)先級(jí)是根據(jù)訪(fǎng)問(wèn)次數(shù)計(jì)算出來(lái)的妒蔚，例如
詳細(xì)的算法結(jié)構(gòu)圖如下，Q0月弛，Q1....Qk代表不同的優(yōu)先級(jí)隊(duì)列面睛，Q-history代表從緩存中淘汰數(shù)據(jù)，但記錄了數(shù)據(jù)的索引和引用次數(shù)的隊(duì)列：
如上圖尊搬，算法詳細(xì)描述如下：
1.?新插入的數(shù)據(jù)放入Q0；
2.?每個(gè)隊(duì)列按照LRU管理數(shù)據(jù)土涝；
3.?當(dāng)數(shù)據(jù)的訪(fǎng)問(wèn)次數(shù)達(dá)到一定次數(shù)佛寿，需要提升優(yōu)先級(jí)時(shí)，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除但壮，加入到高一級(jí)隊(duì)列的頭部冀泻；
4.?為了防止高優(yōu)先級(jí)數(shù)據(jù)永遠(yuǎn)不被淘汰，當(dāng)數(shù)據(jù)在指定的時(shí)間里訪(fǎng)問(wèn)沒(méi)有被訪(fǎng)問(wèn)時(shí)蜡饵，需要降低優(yōu)先級(jí)弹渔，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除，加入到低一級(jí)的隊(duì)列頭部溯祸；
5.?需要淘汰數(shù)據(jù)時(shí)肢专，從最低一級(jí)隊(duì)列開(kāi)始按照LRU淘汰；每個(gè)隊(duì)列淘汰數(shù)據(jù)時(shí)焦辅，將數(shù)據(jù)從緩存中刪除博杖，將數(shù)據(jù)索引加入Q-history頭部；
6.?如果數(shù)據(jù)在Q-history中被重新訪(fǎng)問(wèn)筷登，則重新計(jì)算其優(yōu)先級(jí)剃根，移到目標(biāo)隊(duì)列的頭部；
7.?Q-history按照LRU淘汰數(shù)據(jù)的索引前方。
【命中率】
MQ降低了“緩存污染”帶來(lái)的問(wèn)題狈醉，命中率比LRU要高廉油。
【復(fù)雜度】
MQ需要維護(hù)多個(gè)隊(duì)列，且需要維護(hù)每個(gè)數(shù)據(jù)的訪(fǎng)問(wèn)時(shí)間苗傅，復(fù)雜度比LRU高抒线。
【代價(jià)】
MQ需要記錄每個(gè)數(shù)據(jù)的訪(fǎng)問(wèn)時(shí)間，需要定時(shí)掃描所有隊(duì)列金吗，代價(jià)比LRU要高十兢。
注：雖然MQ的隊(duì)列看起來(lái)數(shù)量比較多，但由于所有隊(duì)列之和受限于緩存容量的大小摇庙，因此這里多個(gè)隊(duì)列長(zhǎng)度之和和一個(gè)LRU隊(duì)列是一樣的旱物，因此隊(duì)列掃描性能也相近。
由于不同的訪(fǎng)問(wèn)模型導(dǎo)致命中率變化較大卫袒，此處對(duì)比僅基于理論定性分析宵呛，不做定量分析。
對(duì)比點(diǎn)
對(duì)比
命中率
LRU-2?>?MQ(2)?>?2Q?>?LRU
復(fù)雜度
LRU-2?>?MQ(2)?>?2Q?>?LRU
代價(jià)
LRU-2??>?MQ(2)?>?2Q?>?LRU
實(shí)際應(yīng)用中需要根據(jù)業(yè)務(wù)的需求和對(duì)數(shù)據(jù)的訪(fǎng)問(wèn)情況進(jìn)行選擇夕凝，并不是命中率越高越好蟆炊。例如：雖然LRU看起來(lái)命中率會(huì)低一些，且存在”緩存污染“的問(wèn)題睬关，但由于其簡(jiǎn)單和代價(jià)小矮燎，實(shí)際應(yīng)用中反而應(yīng)用更多。
java中最簡(jiǎn)單的LRU算法實(shí)現(xiàn)转砖，就是利用jdk的LinkedHashMap须鼎，覆寫(xiě)其中的removeEldestEntry(Map.Entry)方法即可
如果你去看LinkedHashMap的源碼可知，LRU算法是通過(guò)雙向鏈表來(lái)實(shí)現(xiàn)府蔗，當(dāng)某個(gè)位置被命中晋控，通過(guò)調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到頭位置，新加入的內(nèi)容直接放在鏈表頭姓赤，如此一來(lái)赡译，最近被命中的內(nèi)容就向鏈表頭移動(dòng)，需要替換時(shí)不铆，鏈表最后的位置就是最近最少使用的位置蝌焚。
import java.util.ArrayList;?
?import java.util.Collection;?
?import java.util.LinkedHashMap;?
?import java.util.concurrent.locks.Lock;?
?import java.util.concurrent.locks.ReentrantLock;?
?import java.util.Map;? ? ??
? /**? * 類(lèi)說(shuō)明：利用LinkedHashMap實(shí)現(xiàn)簡(jiǎn)單的緩存， 必須實(shí)現(xiàn)removeEldestEntry方法誓斥，具體參見(jiàn)JDK文檔? *??
?*?@author dennis? *??
?* @param*?
@param*/?
public class LRULinkedHashMapextends LinkedHashMap{? ? ??
private final int maxCapacity;? ? ? ?
?private static final float DEFAULT_LOAD_FACTOR = 0.75f;? ? ? ?
?private final Lock lock = new ReentrantLock();? ? ? ??
?public LRULinkedHashMap(int maxCapacity) {? ? ? ? ?
?super(maxCapacity, DEFAULT_LOAD_FACTOR, true);? ? ? ? ??
this.maxCapacity = maxCapacity;? ? ? }? ? ? ??
?@Override? ??
?protected boolean removeEldestEntry(java.util.Map.Entryeldest) {? ? ? ? ?
?return size() > maxCapacity;? ??
? }? ? ??
@Override? ??
?public boolean containsKey(Object key) {? ? ? ? ??
try {? ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ??
return super.containsKey(key);? ? ? ? ?
?} finally {? ? ? ? ? ? ??
lock.unlock();? ? ? ? ?
?}? ? ??
}? ? ? ? ? ? ? ??
@Override? ??
?public V get(Object key) {? ? ? ? ?
?try {? ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ??
return super.get(key);? ? ? ? ?
?} finally {? ? ? ? ? ? ?
?lock.unlock();? ? ? ? ??
}? ? ?
?}? ? ? ??
?@Override? ?
?public V put(K key, V value) {? ? ? ? ?
?try {? ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ??
return super.put(key, value);? ? ? ? ?
?} finally {? ? ? ? ? ? ??
lock.unlock();? ? ? ??
? }? ? ?
?}? ? ??
? public int size() {? ? ? ? ?
?try { ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ?
?return super.size();? ? ? ? ?
?} finally {? ? ? ? ? ? ?
?lock.unlock();? ? ? ? ??
}? ? ??
}? ? ? ??
?public void clear() {? ? ? ? ??
try {? ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ?
?super.clear();? ? ? ? ?
?} finally {? ? ? ? ? ? ??
lock.unlock();? ? ? ? ?
?}? ? ?
?}? ? ? ?
?public Collection> getAll() {? ? ? ? ??
try {? ? ? ? ? ? ??
lock.lock();? ? ? ? ? ? ??
return new ArrayList>(super.entrySet());
} finally {
lock.unlock();
}
}
}
基于雙鏈表 的LRU實(shí)現(xiàn):
傳統(tǒng)意義的LRU算法是為每一個(gè)Cache對(duì)象設(shè)置一個(gè)計(jì)數(shù)器综看，每次Cache命中則給計(jì)數(shù)器+1，而Cache用完岖食，需要淘汰舊內(nèi)容红碑，放置新內(nèi)容時(shí)，就查看所有的計(jì)數(shù)器，并將最少使用的內(nèi)容替換掉析珊。
它的弊端很明顯羡鸥，如果Cache的數(shù)量少，問(wèn)題不會(huì)很大忠寻， 但是如果Cache的空間過(guò)大惧浴，達(dá)到10W或者100W以上，一旦需要淘汰奕剃，則需要遍歷所有計(jì)算器衷旅，其性能與資源消耗是巨大的。效率也就非常的慢了纵朋。
它的原理： 將Cache的所有位置都用雙連表連接起來(lái)柿顶，當(dāng)一個(gè)位置被命中之后，就將通過(guò)調(diào)整鏈表的指向操软，將該位置調(diào)整到鏈表頭的位置嘁锯，新加入的Cache直接加到鏈表頭中。
這樣聂薪，在多次進(jìn)行Cache操作后家乘，最近被命中的，就會(huì)被向鏈表頭方向移動(dòng)藏澳，而沒(méi)有命中的仁锯，而想鏈表后面移動(dòng)，鏈表尾則表示最近最少使用的Cache翔悠。
當(dāng)需要替換內(nèi)容時(shí)候扑馁，鏈表的最后位置就是最少被命中的位置，我們只需要淘汰鏈表最后的部分即可凉驻。
上面說(shuō)了這么多的理論， 下面用代碼來(lái)實(shí)現(xiàn)一個(gè)LRU策略的緩存复罐。
我們用一個(gè)對(duì)象來(lái)表示Cache涝登，并實(shí)現(xiàn)雙鏈表，
