LRU原理

LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高”。

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

1. 新數(shù)據(jù)插入到鏈表頭部；
2. 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問(wèn)），則將數(shù)據(jù)移到鏈表頭部；
3. 當(dāng)鏈表滿的時(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原理

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ù)被訪問(wèn)的歷史。只有當(dāng)數(shù)據(jù)的訪問(wèn)次數(shù)達(dá)到K次的時(shí)候，才將數(shù)據(jù)放入緩存。當(dāng)需要淘汰數(shù)據(jù)時(shí)，LRU-K會(huì)淘汰第K次訪問(wèn)時(shí)間距當(dāng)前時(shí)間最大的數(shù)據(jù)。詳細(xì)實(shí)現(xiàn)如下：

1. 數(shù)據(jù)第一次被訪問(wèn)，加入到訪問(wèn)歷史列表；
2. 如果數(shù)據(jù)在訪問(wèn)歷史列表里后沒(méi)有達(dá)到K次訪問(wèn)，則按照一定規(guī)則（FIFO，LRU）淘汰；
3. 當(dāng)訪問(wèn)歷史隊(duì)列中的數(shù)據(jù)訪問(wèn)次數(shù)達(dá)到K次后，將數(shù)據(jù)索引從歷史隊(duì)列刪除，將數(shù)據(jù)移到緩存隊(duì)列中，并緩存此數(shù)據(jù)，緩存隊(duì)列重新按照時(shí)間排序；
4. 緩存數(shù)據(jù)隊(duì)列中被再次訪問(wèn)后，重新排序；
5. 需要淘汰數(shù)據(jù)時(shí)，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問(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ù)訪問(wèn)才能將歷史訪問(wèn)記錄清除掉。
   【命中率】
   LRU-K降低了“緩存污染”帶來(lái)的問(wèn)題，命中率比LRU要高。
   【復(fù)雜度】
   LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列，算法復(fù)雜度和代價(jià)比較高。
   【代價(jià)】
   由于LRU-K還需要記錄那些被訪問(wèn)過(guò)、但還沒(méi)有放入緩存的對(duì)象，因此內(nèi)存消耗會(huì)比LRU要多；當(dāng)數(shù)據(jù)量很大的時(shí)候，內(nèi)存消耗會(huì)比較可觀。
   LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序，也可以即時(shí)排序），CPU消耗比LRU要高。

URL-Two queues原理

Two queues（以下使用2Q代替）算法類似于LRU-2，不同點(diǎn)在于2Q將LRU-2算法中的訪問(wèn)歷史隊(duì)列（注意這不是緩存數(shù)據(jù)的）改為一個(gè)FIFO緩存隊(duì)列，即：2Q算法有兩個(gè)緩存隊(duì)列，一個(gè)是FIFO隊(duì)列，一個(gè)是LRU隊(duì)列。
當(dāng)數(shù)據(jù)第一次訪問(wèn)時(shí)，2Q算法將數(shù)據(jù)緩存在FIFO隊(duì)列里面，當(dāng)數(shù)據(jù)第二次被訪問(wèn)時(shí)，則將數(shù)據(jù)從FIFO隊(duì)列移到LRU隊(duì)列里面，兩個(gè)隊(duì)列各自按照自己的方法淘汰數(shù)據(jù)。詳細(xì)實(shí)現(xiàn)如下：

1. 新訪問(wèn)的數(shù)據(jù)插入到FIFO隊(duì)列；
2. 如果數(shù)據(jù)在FIFO隊(duì)列中一直沒(méi)有被再次訪問(wèn)，則最終按照FIFO規(guī)則淘汰；
3. 如果數(shù)據(jù)在FIFO隊(duì)列中被再次訪問(wèn)，則將數(shù)據(jù)移到LRU隊(duì)列頭部；
4. 如果數(shù)據(jù)在LRU隊(duì)列再次被訪問(wèn)，則將數(shù)據(jù)移到LRU隊(duì)列頭部；
5. LRU隊(duì)列淘汰末尾的數(shù)據(jù)。

【命中率】
2Q算法的命中率要高于LRU。
【復(fù)雜度】
需要兩個(gè)隊(duì)列，但兩個(gè)隊(duì)列本身都比較簡(jiǎn)單。
【代價(jià)】
FIFO和LRU的代價(jià)之和。
2Q算法和LRU-2算法命中率類似，內(nèi)存消耗也比較接近，但對(duì)于最后緩存的數(shù)據(jù)來(lái)說(shuō)，2Q會(huì)減少一次從原始存儲(chǔ)讀取數(shù)據(jù)或者計(jì)算數(shù)據(jù)的操作。

Multi Queue原理

MQ算法根據(jù)訪問(wèn)頻率將數(shù)據(jù)劃分為多個(gè)隊(duì)列，不同的隊(duì)列具有不同的訪問(wèn)優(yōu)先級(jí)，其核心思想是：優(yōu)先緩存訪問(wèn)次數(shù)多的數(shù)據(jù)。
MQ算法將緩存劃分為多個(gè)LRU隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)不同的訪問(wèn)優(yōu)先級(jí)。訪問(wèn)優(yōu)先級(jí)是根據(jù)訪問(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ù)的訪問(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í)間里訪問(wèn)沒(méi)有被訪問(wèn)時(shí)，需要降低優(yōu)先級(jí)，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除，加入到低一級(jí)的隊(duì)列頭部；
5. 需要淘汰數(shù)據(jù)時(shí)，從最低一級(jí)隊(duì)列開始按照LRU淘汰；每個(gè)隊(duì)列淘汰數(shù)據(jù)時(shí)，將數(shù)據(jù)從緩存中刪除，將數(shù)據(jù)索引加入Q-history頭部；
6. 如果數(shù)據(jù)在Q-history中被重新訪問(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ù)的訪問(wèn)時(shí)間，復(fù)雜度比LRU高。
【代價(jià)】
MQ需要記錄每個(gè)數(shù)據(jù)的訪問(wèn)時(shí)間，需要定時(shí)掃描所有隊(duì)列，代價(jià)比LRU要高。
注：雖然MQ的隊(duì)列看起來(lái)數(shù)量比較多，但由于所有隊(duì)列之和受限于緩存容量的大小，因此這里多個(gè)隊(duì)列長(zhǎng)度之和和一個(gè)LRU隊(duì)列是一樣的，因此隊(duì)列掃描性能也相近。

Ref：
http://flychao88.iteye.com/blog/1977653