天天看點

緩存淘汰算法-LRU算法

轉載自:緩存淘汰算法-LRU算法

1. LRU

1.1. 原理

LRU(Least recently used,最近最少使用)算法根據資料的曆史通路記錄來進行淘汰資料,其核心思想是“如果資料最近被通路過,那麼将來被通路的幾率也更高”。

1.2. 實作

最常見的實作是使用一個連結清單儲存緩存資料,詳細算法實作如下:

緩存淘汰算法-LRU算法

1. 新資料插入到連結清單頭部;

2. 每當緩存命中(即緩存資料被通路),則将資料移到連結清單頭部;

3. 當連結清單滿的時候,将連結清單尾部的資料丢棄。

1.3. 分析

【命中率】

當存在熱點資料時,LRU的效率很好,但偶發性的、周期性的批量操作會導緻LRU命中率急劇下降,緩存污染情況比較嚴重。

【複雜度】

實作簡單。

【代價】

命中時需要周遊連結清單,找到命中的資料塊索引,然後需要将資料移到頭部。

2. LRU-K

2.1. 原理

LRU-K中的K代表最近使用的次數,是以LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題,其核心思想是将“最近使用過1次”的判斷标準擴充為“最近使用過K次”。

2.2. 實作

相比LRU,LRU-K需要多元護一個隊列,用于記錄所有緩存資料被通路的曆史。隻有當資料的通路次數達到K次的時候,才将資料放入緩存。當需要淘汰資料時,LRU-K會淘汰第K次通路時間距目前時間最大的資料。詳細實作如下:

緩存淘汰算法-LRU算法

1. 資料第一次被通路,加入到通路曆史清單;

2. 如果資料在通路曆史清單裡後沒有達到K次通路,則按照一定規則(FIFO,LRU)淘汰;

3. 當通路曆史隊列中的資料通路次數達到K次後,将資料索引從曆史隊列删除,将資料移到緩存隊列中,并緩存此資料,緩存隊列重新按照時間排序;

4. 緩存資料隊列中被再次通路後,重新排序;

5. 需要淘汰資料時,淘汰緩存隊列中排在末尾的資料,即:淘汰“倒數第K次通路離現在最久”的資料。

LRU-K具有LRU的優點,同時能夠避免LRU的缺點,實際應用中LRU-2是綜合各種因素後最優的選擇,LRU-3或者更大的K值命中率會高,但适應性差,需要大量的資料通路才能将曆史通路記錄清除掉。

2.3. 分析

【命中率】

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

【複雜度】

LRU-K隊列是一個優先級隊列,算法複雜度和代價比較高。

【代價】

由于LRU-K還需要記錄那些被通路過、但還沒有放入緩存的對象,是以記憶體消耗會比LRU要多;當資料量很大的時候,記憶體消耗會比較可觀。

LRU-K需要基于時間進行排序(可以需要淘汰時再排序,也可以即時排序),CPU消耗比LRU要高。

3. Two queues(2Q)

3.1. 原理

Two queues(以下使用2Q代替)算法類似于LRU-2,不同點在于2Q将LRU-2算法中的通路曆史隊列(注意這不是緩存資料的)改為一個FIFO緩存隊列,即:2Q算法有兩個緩存隊列,一個是FIFO隊列,一個是LRU隊列。

3.2. 實作

當資料第一次通路時,2Q算法将資料緩存在FIFO隊列裡面,當資料第二次被通路時,則将資料從FIFO隊列移到LRU隊列裡面,兩個隊列各自按照自己的方法淘汰資料。詳細實作如下:

緩存淘汰算法-LRU算法

1. 新通路的資料插入到FIFO隊列;

2. 如果資料在FIFO隊列中一直沒有被再次通路,則最終按照FIFO規則淘汰;

3. 如果資料在FIFO隊列中被再次通路,則将資料移到LRU隊列頭部;

4. 如果資料在LRU隊列再次被通路,則将資料移到LRU隊列頭部;

5. LRU隊列淘汰末尾的資料。

注:上圖中FIFO隊列比LRU隊列短,但并不代表這是算法要求,實際應用中兩者比例沒有硬性規定。

3.3. 分析

【命中率】

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

【複雜度】

需要兩個隊列,但兩個隊列本身都比較簡單。

【代價】

FIFO和LRU的代價之和。

2Q算法和LRU-2算法命中率類似,記憶體消耗也比較接近,但對于最後緩存的資料來說,2Q會減少一次從原始存儲讀取資料或者計算資料的操作。

4. Multi Queue(MQ)

4.1. 原理

MQ算法根據通路頻率将資料劃分為多個隊列,不同的隊列具有不同的通路優先級,其核心思想是:優先緩存通路次數多的資料。

4.2. 實作

MQ算法将緩存劃分為多個LRU隊列,每個隊列對應不同的通路優先級。通路優先級是根據通路次數計算出來的,例如

詳細的算法結構圖如下,Q0,Q1….Qk代表不同的優先級隊列,Q-history代表從緩存中淘汰資料,但記錄了資料的索引和引用次數的隊列:

緩存淘汰算法-LRU算法

如上圖,算法較長的描述如下:

1. 新插入的資料放入Q0;

2. 每個隊列按照LRU管理資料;

3. 當資料的通路次數達到一定次數,需要提升優先級時,将資料從目前隊列删除,加入到高一級隊列的頭部;

4. 為了防止高優先級資料永遠不被淘汰,當資料在指定的時間裡通路沒有被通路時,需要降低優先級,将資料從目前隊列删除,加入到低一級的隊列頭部;

5. 需要淘汰資料時,從最低一級隊列開始按照LRU淘汰;每個隊列淘汰資料時,将資料從緩存中删除,将資料索引加入Q-history頭部;

6. 如果資料在Q-history中被重新通路,則重新計算其優先級,移到目标隊列的頭部;

7. Q-history按照LRU淘汰資料的索引。

4.3. 分析

【命中率】

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

【複雜度】

MQ需要維護多個隊列,且需要維護每個資料的通路時間,複雜度比LRU高。

【代價】

MQ需要記錄每個資料的通路時間,需要定時掃描所有隊列,代價比LRU要高。

注:雖然MQ的隊列看起來數量比較多,但由于所有隊列之和受限于緩存容量的大小,是以這裡多個隊列長度之和和一個LRU隊列是一樣的,是以隊列掃描性能也相近。

5. LRU類算法對比

由于不同的通路模型導緻命中率變化較大,此處對比僅基于理論定性分析,不做定量分析。

對比點 對比
命中率 LRU-2 > MQ(2) > 2Q > LRU
複雜度 LRU-2 > MQ(2) > 2Q > LRU
代價 LRU-2  > MQ(2) > 2Q > LRU

實際應用中需要根據業務的需求和對資料的通路情況進行選擇,并不是命中率越高越好。例如:雖然LRU看起來命中率會低一些,且存在”緩存污染“的問題,但由于其簡單和代價小,實際應用中反而應用更多。

繼續閱讀