LRU 是啥？

定義

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

實(shí)現(xiàn)

思路：設(shè)計(jì)一個(gè)定長隊(duì)列，如果數(shù)據(jù)被命中，則更新位置，不足時(shí)候，將最舊的數(shù)據(jù)進(jìn)行丟棄。

分析

【命中率】
當(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ù)移到頭部。

改進(jìn) LRU-k

image.png

1. 數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；
2. 如果數(shù)據(jù)在訪問歷史列表里后沒有達(dá)到K次訪問，則按照一定規(guī)則（FIFO，LRU）淘汰；
3. 當(dāng)訪問歷史隊(duì)列中的數(shù)據(jù)訪問次數(shù)達(dá)到K次后，將數(shù)據(jù)索引從歷史隊(duì)列刪除，將數(shù)據(jù)移到緩存隊(duì)列中，并緩存此數(shù)據(jù)，緩存隊(duì)列重新按照時(shí)間排序；
4. 緩存數(shù)據(jù)隊(duì)列中被再次訪問后，重新排序；
5. 需要淘汰數(shù)據(jù)時(shí)，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(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ù)訪問才能將歷史訪問記錄清除掉。
6. 分析
   【命中率】
   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要高。

改進(jìn)Multi Queue（MQ）

原理

MQ算法根據(jù)訪問頻率將數(shù)據(jù)劃分為多個(gè)隊(duì)列，不同的隊(duì)列具有不同的訪問優(yōu)先級(jí)，其核心思想是：優(yōu)先緩存訪問次數(shù)多的數(shù)據(jù)。

實(shí)現(xiàn)

MQ算法將緩存劃分為多個(gè)LRU隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)不同的訪問優(yōu)先級(jí)。訪問優(yōu)先級(jí)是根據(jù)訪問次數(shù)計(jì)算出來的
詳細(xì)的算法結(jié)構(gòu)圖如下，Q0，Q1....Qk代表不同的優(yōu)先級(jí)隊(duì)列，Q-history代表從緩存中淘汰數(shù)據(jù)，但記錄了數(shù)據(jù)的索引和引用次數(shù)的隊(duì)列：

image.png

1. 新插入的數(shù)據(jù)放入Q0；

2. 每個(gè)隊(duì)列按照LRU管理數(shù)據(jù)；

3. 當(dāng)數(shù)據(jù)的訪問次數(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í)間里訪問沒有被訪問時(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中被重新訪問，則重新計(jì)算其優(yōu)先級(jí)，移到目標(biāo)隊(duì)列的頭部；

7. Q-history按照LRU淘汰數(shù)據(jù)的索引。

8. 分析

【命中率】

MQ降低了“緩存污染”帶來的問題，命中率比LRU要高。

【復(fù)雜度】

MQ需要維護(hù)多個(gè)隊(duì)列，且需要維護(hù)每個(gè)數(shù)據(jù)的訪問時(shí)間，復(fù)雜度比LRU高。

【代價(jià)】

MQ需要記錄每個(gè)數(shù)據(jù)的訪問時(shí)間，需要定時(shí)掃描所有隊(duì)列，代價(jià)比LRU要高。

注：雖然MQ的隊(duì)列看起來數(shù)量比較多，但由于所有隊(duì)列之和受限于緩存容量的大小，因此這里多個(gè)隊(duì)列長度之和和一個(gè)LRU隊(duì)列是一樣的，因此隊(duì)列掃描性能也相近。

綜合

實(shí)際應(yīng)用中需要根據(jù)業(yè)務(wù)的需求和對(duì)數(shù)據(jù)的訪問情況進(jìn)行選擇，并不是命中率越高越好。例如：雖然LRU看起來命中率會(huì)低一些，且存在”緩存污染“的問題，但由于其簡單和代價(jià)小，實(shí)際應(yīng)用中反而應(yīng)用更多

image.png

參考： http://flychao88.iteye.com/blog/1977653