1.?LRU
1.1.?原理

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

1.2.?實(shí)現(xiàn)

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

1.?新數(shù)據(jù)插入到鏈表頭部；

2.?每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部；

3.?當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄。

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ù)移到頭部。

?

2.?LRU-K

2.1.?原理

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

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ù)訪問才能將歷史訪問記錄清除掉。

2.3.?分析

【命中率】

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

【復(fù)雜度】

LRU-K隊(duì)列是一個(gè)優(yōu)先級隊(duì)列，算法復(fù)雜度和代價(jià)比較高。

【代價(jià)】

由于LRU-K還需要記錄那些被訪問過、但還沒有放入緩存的對象，因此內(nèi)存消耗會(huì)比LRU要多；當(dāng)數(shù)據(jù)量很大的時(shí)候，內(nèi)存消耗會(huì)比較可觀。

LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序，也可以即時(shí)排序），CPU消耗比LRU要高。

3.?Two?queues（2Q）

3.1.?原理

Two?queues（以下使用2Q代替）算法類似于LRU-2，不同點(diǎn)在于2Q將LRU-2算法中的訪問歷史隊(duì)列（注意這不是緩存數(shù)據(jù)的）改為一個(gè)FIFO緩存隊(duì)列，即：2Q算法有兩個(gè)緩存隊(duì)列，一個(gè)是FIFO隊(duì)列，一個(gè)是LRU隊(duì)列。

3.2.?實(shí)現(xiàn)

當(dāng)數(shù)據(jù)第一次訪問時(shí)，2Q算法將數(shù)據(jù)緩存在FIFO隊(duì)列里面，當(dāng)數(shù)據(jù)第二次被訪問時(shí)，則將數(shù)據(jù)從FIFO隊(duì)列移到LRU隊(duì)列里面，兩個(gè)隊(duì)列各自按照自己的方法淘汰數(shù)據(jù)。詳細(xì)實(shí)現(xiàn)如下：

1.?新訪問的數(shù)據(jù)插入到FIFO隊(duì)列；

2.?如果數(shù)據(jù)在FIFO隊(duì)列中一直沒有被再次訪問，則最終按照FIFO規(guī)則淘汰；

3.?如果數(shù)據(jù)在FIFO隊(duì)列中被再次訪問，則將數(shù)據(jù)移到LRU隊(duì)列頭部；

4.?如果數(shù)據(jù)在LRU隊(duì)列再次被訪問，則將數(shù)據(jù)移到LRU隊(duì)列頭部；

5.?LRU隊(duì)列淘汰末尾的數(shù)據(jù)。

?

注：上圖中FIFO隊(duì)列比LRU隊(duì)列短，但并不代表這是算法要求，實(shí)際應(yīng)用中兩者比例沒有硬性規(guī)定。

3.3.?分析

【命中率】

2Q算法的命中率要高于LRU。

【復(fù)雜度】

需要兩個(gè)隊(duì)列，但兩個(gè)隊(duì)列本身都比較簡單。

【代價(jià)】

FIFO和LRU的代價(jià)之和。

2Q算法和LRU-2算法命中率類似，內(nèi)存消耗也比較接近，但對于最后緩存的數(shù)據(jù)來說，2Q會(huì)減少一次從原始存儲(chǔ)讀取數(shù)據(jù)或者計(jì)算數(shù)據(jù)的操作。

4.?Multi?Queue（MQ）

4.1.?原理

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

4.2.?實(shí)現(xiàn)

MQ算法將緩存劃分為多個(gè)LRU隊(duì)列，每個(gè)隊(duì)列對應(yīng)不同的訪問優(yōu)先級。訪問優(yōu)先級是根據(jù)訪問次數(shù)計(jì)算出來的，例如

詳細(xì)的算法結(jié)構(gòu)圖如下，Q0，Q1....Qk代表不同的優(yōu)先級隊(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ù)的訪問次數(shù)達(dá)到一定次數(shù)，需要提升優(yōu)先級時(shí)，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除，加入到高一級隊(duì)列的頭部；

4.?為了防止高優(yōu)先級數(shù)據(jù)永遠(yuǎn)不被淘汰，當(dāng)數(shù)據(jù)在指定的時(shí)間里訪問沒有被訪問時(shí)，需要降低優(yōu)先級，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除，加入到低一級的隊(duì)列頭部；

5.?需要淘汰數(shù)據(jù)時(shí)，從最低一級隊(duì)列開始按照LRU淘汰；每個(gè)隊(duì)列淘汰數(shù)據(jù)時(shí)，將數(shù)據(jù)從緩存中刪除，將數(shù)據(jù)索引加入Q-history頭部；

6.?如果數(shù)據(jù)在Q-history中被重新訪問，則重新計(jì)算其優(yōu)先級，移到目標(biāo)隊(duì)列的頭部；

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

4.3.?分析

【命中率】

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ì)列掃描性能也相近。

?

5.?LRU類算法對比

由于不同的訪問模型導(dǎo)致命中率變化較大，此處對比僅基于理論定性分析，不做定量分析。

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

?

java中最簡單的LRU算法實(shí)現(xiàn)，就是利用jdk的LinkedHashMap，覆寫其中的removeEldestEntry(Map.Entry)方法即可

如果你去看LinkedHashMap的源碼可知，LRU算法是通過雙向鏈表來實(shí)現(xiàn)，當(dāng)某個(gè)位置被命中，通過調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到頭位置，新加入的內(nèi)容直接放在鏈表頭，如此一來，最近被命中的內(nèi)容就向鏈表頭移動(dòng)，需要替換時(shí)，鏈表最后的位置就是最近最少使用的位置。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

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;? ??? ??? /** ?* 類說明：利用LinkedHashMap實(shí)現(xiàn)簡單的緩存， 必須實(shí)現(xiàn)removeEldestEntry方法，具體參見JDK文檔 ?*? ?* @author dennis ?*? ?* @param <K> ?* @param <V> ?*/? public?class?LRULinkedHashMap<K, V> extends?LinkedHashMap<K, V> {? ????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.Entry<K, V> eldest) {? ????????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<Map.Entry<K, V>> getAll() {? ????????try?{? ????????????lock.lock();? ????????????return?new?ArrayList<Map.Entry<K, V>>(super.entrySet());? ????????} finally?{? ????????????lock.unlock();? ????????}? ????}? }? ????

?

基于雙鏈表 的LRU實(shí)現(xiàn):

　　傳統(tǒng)意義的LRU算法是為每一個(gè)Cache對象設(shè)置一個(gè)計(jì)數(shù)器，每次Cache命中則給計(jì)數(shù)器+1，而Cache用完，需要淘汰舊內(nèi)容，放置新內(nèi)容時(shí)，就查看所有的計(jì)數(shù)器，并將最少使用的內(nèi)容替換掉。

?? 它的弊端很明顯，如果Cache的數(shù)量少，問題不會(huì)很大， 但是如果Cache的空間過大，達(dá)到10W或者100W以上，一旦需要淘汰，則需要遍歷所有計(jì)算器，其性能與資源消耗是巨大的。效率也就非常的慢了。

??? 它的原理： 將Cache的所有位置都用雙連表連接起來，當(dāng)一個(gè)位置被命中之后，就將通過調(diào)整鏈表的指向，將該位置調(diào)整到鏈表頭的位置，新加入的Cache直接加到鏈表頭中。

???? 這樣，在多次進(jìn)行Cache操作后，最近被命中的，就會(huì)被向鏈表頭方向移動(dòng)，而沒有命中的，而想鏈表后面移動(dòng)，鏈表尾則表示最近最少使用的Cache。

???? 當(dāng)需要替換內(nèi)容時(shí)候，鏈表的最后位置就是最少被命中的位置，我們只需要淘汰鏈表最后的部分即可。

? 上面說了這么多的理論， 下面用代碼來實(shí)現(xiàn)一個(gè)LRU策略的緩存。

??? 我們用一個(gè)對象來表示Cache，并實(shí)現(xiàn)雙鏈表，

Java代碼 ?

public?class?LRUCache?{??

????/**?

?????*?鏈表節(jié)點(diǎn)?

?????*?@author?Administrator?

?????*?

?????*/??

????class?CacheNode?{??

????????……??

????}??

????private?int?cacheSize;//緩存大小??

????private?Hashtable?nodes;//緩存容器??

????private?int?currentSize;//當(dāng)前緩存對象數(shù)量??

????private?CacheNode?first;//(實(shí)現(xiàn)雙鏈表)鏈表頭??

????private?CacheNode?last;//(實(shí)現(xiàn)雙鏈表)鏈表尾??

}??

????????????????????

public class LRUCache { /*** 鏈表節(jié)點(diǎn)* @author Administrator**/ class CacheNode { …… } private int cacheSize;//緩存大小 private Hashtable nodes;//緩存容器 private int currentSize;//當(dāng)前緩存對象數(shù)量 private CacheNode first;//(實(shí)現(xiàn)雙鏈表)鏈表頭 private CacheNode last;//(實(shí)現(xiàn)雙鏈表)鏈表尾 }

?下面給出完整的實(shí)現(xiàn)，這個(gè)類也被Tomcat所使用（ org.apache.tomcat.util.collections.LRUCache），但是在tomcat6.x版本中，已經(jīng)被棄用，使用另外其他的緩存類來替代它。

Java代碼 ?

public?class?LRUCache?{??

????/**?

?????*?鏈表節(jié)點(diǎn)?

?????*?@author?Administrator?

?????*?

?????*/??

????class?CacheNode?{??

????????CacheNode?prev;//前一節(jié)點(diǎn)??

????????CacheNode?next;//后一節(jié)點(diǎn)??

????????Object?value;//值??

????????Object?key;//鍵??

????????CacheNode()?{??

????????}??

????}??

????public?LRUCache(int?i)?{??

????????currentSize?=?0;??

????????cacheSize?=?i;??

????????nodes?=?new?Hashtable(i);//緩存容器??

????}??

??????

????/**?

?????*?獲取緩存中對象?

?????*?@param?key?

?????*?@return?

?????*/??

????public?Object?get(Object?key)?{??

????????CacheNode?node?=?(CacheNode)?nodes.get(key);??

????????if?(node?!=?null)?{??

????????????moveToHead(node);??

????????????return?node.value;??

????????}?else?{??

????????????return?null;??

????????}??

????}??

??????

????/**?

?????*?添加緩存?

?????*?@param?key?

?????*?@param?value?

?????*/??

????public?void?put(Object?key,?Object?value)?{??

????????CacheNode?node?=?(CacheNode)?nodes.get(key);??

??????????

????????if?(node?==?null)?{??

????????????//緩存容器是否已經(jīng)超過大小.??

????????????if?(currentSize?>=?cacheSize)?{??

????????????????if?(last?!=?null)//將最少使用的刪除??

????????????????????nodes.remove(last.key);??

????????????????removeLast();??

????????????}?else?{??

????????????????currentSize++;??

????????????}??

??????????????

????????????node?=?new?CacheNode();??

????????}??

????????node.value?=?value;??

????????node.key?=?key;??

????????//將最新使用的節(jié)點(diǎn)放到鏈表頭，表示最新使用的.??

????????moveToHead(node);??

????????nodes.put(key,?node);??

????}??

????/**?

?????*?將緩存刪除?

?????*?@param?key?

?????*?@return?

?????*/??

????public?Object?remove(Object?key)?{??

????????CacheNode?node?=?(CacheNode)?nodes.get(key);??

????????if?(node?!=?null)?{??

????????????if?(node.prev?!=?null)?{??

????????????????node.prev.next?=?node.next;??

????????????}??

????????????if?(node.next?!=?null)?{??

????????????????node.next.prev?=?node.prev;??

????????????}??

????????????if?(last?==?node)??

????????????????last?=?node.prev;??

????????????if?(first?==?node)??

????????????????first?=?node.next;??

????????}??

????????return?node;??

????}??

????public?void?clear()?{??

????????first?=?null;??

????????last?=?null;??

????}??

????/**?

?????*?刪除鏈表尾部節(jié)點(diǎn)?

?????*??表示?刪除最少使用的緩存對象?

?????*/??

????private?void?removeLast()?{??

????????//鏈表尾不為空,則將鏈表尾指向null.?刪除連表尾（刪除最少使用的緩存對象）??

????????if?(last?!=?null)?{??

????????????if?(last.prev?!=?null)??

????????????????last.prev.next?=?null;??

????????????else??

????????????????first?=?null;??

????????????last?=?last.prev;??

????????}??

????}??

??????

????/**?

?????*?移動(dòng)到鏈表頭，表示這個(gè)節(jié)點(diǎn)是最新使用過的?

?????*?@param?node?

?????*/??

????private?void?moveToHead(CacheNode?node)?{??

????????if?(node?==?first)??

????????????return;??

????????if?(node.prev?!=?null)??

????????????node.prev.next?=?node.next;??

????????if?(node.next?!=?null)??

????????????node.next.prev?=?node.prev;??

????????if?(last?==?node)??

????????????last?=?node.prev;??

????????if?(first?!=?null)?{??

????????????node.next?=?first;??

????????????first.prev?=?node;??

????????}??

????????first?=?node;??

????????node.prev?=?null;??

????????if?(last?==?null)??

????????????last?=?first;??

????}??

????private?int?cacheSize;??

????private?Hashtable?nodes;//緩存容器??

????private?int?currentSize;??

????private?CacheNode?first;//鏈表頭??

????private?CacheNode?last;//鏈表尾??

}<br?style="margin:?0px;?padding:?0px;"><br?style="margin:?0px;?padding:?0px;">??

public class LRUCache { /*** 鏈表節(jié)點(diǎn)* @author Administrator**/ class CacheNode { CacheNode prev;//前一節(jié)點(diǎn) CacheNode next;//后一節(jié)點(diǎn) Object value;//值 Object key;//鍵 CacheNode() { } } public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable(i);//緩存容器 } /*** 獲取緩存中對象* @param key* @return*/ public Object get(Object key) { CacheNode node = (CacheNode) nodes.get(key); if (node != null) { moveToHead(node); return node.value; } else { return null; } } /*** 添加緩存* @param key* @param value*/ public void put(Object key, Object value) { CacheNode node = (CacheNode) nodes.get(key); if (node == null) { //緩存容器是否已經(jīng)超過大小. if (currentSize >= cacheSize) { if (last != null)//將最少使用的刪除 nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new CacheNode(); } node.value = value; node.key = key; //將最新使用的節(jié)點(diǎn)放到鏈表頭，表示最新使用的. moveToHead(node); nodes.put(key, node); } /*** 將緩存刪除* @param key* @return*/ public Object remove(Object key) { CacheNode node = (CacheNode) nodes.get(key); if (node != null) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (last == node) last = node.prev; if (first == node) first = node.next; } return node; } public void clear() { first = null; last = null; } /*** 刪除鏈表尾部節(jié)點(diǎn)* 表示 刪除最少使用的緩存對象*/ private void removeLast() { //鏈表尾不為空,則將鏈表尾指向null. 刪除連表尾（刪除最少使用的緩存對象） if (last != null) { if (last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } /*** 移動(dòng)到鏈表頭，表示這個(gè)節(jié)點(diǎn)是最新使用過的* @param node*/ private void moveToHead(CacheNode node) { if (node == first) return; if (node.prev != null) node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; if (last == node) last = node.prev; if (first != null) { node.next = first; first.prev = node; } first = node; node.prev = null; if (last == null) last = first; } private int cacheSize; private Hashtable nodes;//緩存容器 private int currentSize; private CacheNode first;//鏈表頭 private CacheNode last;//鏈表尾 }

轉(zhuǎn)載于:https://www.cnblogs.com/wangdaijun/p/5581336.html

總結(jié)

以上是生活随笔為你收集整理的缓存淘汰算法 (http://flychao88.iteye.com/blog/1977653)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。