緩存淘汰算法研究

王永亮

摘要

在海量數據系統中，海量數據受緩存大小的限制會出現緩存滿的情況，淘汰數據的選擇就變得非常關鍵，會影響緩存未命中的次數，從而影響整個系統的性能，因此需要選擇合適的緩存數據淘汰算法。本文通過對常用緩存淘汰算法的原理、適用場景和優缺點進行分析對比研究，為緩存淘汰算法的選擇提供幫助。

【關鍵詞】數據存儲 緩存淘汰算法

1 引言

在海量數據系統中，由于數據存儲成本的原因，大多數數據都是存儲在性能相對較差的介質上，經常需要訪問的數據存儲在性能較高的介質上，作為海量數據的緩存，由于緩存大小的限制不能緩存所有的數據，因此在數據訪問時會出現需要訪問的數據不在緩存中的現象即未命中，如果出現未命中此時需要去越過緩存去全量數據中去訪問，并將未命中的數據放入緩存中，由于緩存大小的限制，會出現緩存滿的情況，此時需要淘汰一些數據，為新數據預留空間，最關鍵的就是要選擇合適的緩存數據淘汰算法。

2 緩存淘汰算法分析

由于緩存大小的限制，內存緩存算法都是為了提高緩存數據的命中率，最理想的算法是每次都能精確的淘汰在近期不會訪問的數據，在現實的系統中一般無法實現;常用的緩存淘汰算法主要從對象訪問的時間和訪問頻率來進行考慮，產生了多種緩存淘汰算法，業務需要根據自己的實際情況選擇合適的緩存淘汰算法，本文對常用緩存淘汰算法的原理、適用場景和優缺點進行了分析和研究。

2.1 LRU

LRU（least recently used）為最近最少使用算法，該算法會首先淘汰最近訪問時間離現在最久的對象，例如：緩存能緩存的對象總個數為4，訪問對象的順序為：ABCDDEC，LRI淘汰算法產生的結果過程如圖1所示。

該算法適合最近訪問時間距離現在越近的對象，越容易被訪問到的場景。

2.2 LFU

LFU（Ieast frequently used）為最少頻率使用算法，該算法主要從對象的訪問頻率進行考慮，會保存對象的訪問頻率，在需要淘汰時，會首先淘汰訪問頻率最低的對象，例如：緩存能緩存的對象的總個數為4，當前在緩存中保存的對象及頻率為：A（5次）、B（3次）、C0次）、D（2次），則有新對象E需要插入，則首先淘汰訪問頻率最低的C對象。如圖2所示。

單純使用LFU算法會帶來一些問題，如果某個對象在短時間內大量訪問，會導致此對象的頻率數據非常大，即使此對象在以后很長時間都不會訪問，也不會導致此對象被淘汰;初次訪問的對象由于頻率數據比較小，從而很容易被淘汰，所以LFU算法經常需要和其他算法一起使用。

2.3 FIFO

FIFO（first in first out）為先進先出淘汰算法，該算法根據對象的緩存次序進行緩存淘汰，如果緩存大小受限，需要淘汰對象，會首先淘汰當前最早緩存的對象。例如：緩存能緩存的對象的總個數為4，訪問對象的順序為：A、B、C、D、E，整個過程如圖3所示。

2.4 LRU-K

LRU-K為LRI算法的優化，其中的K表示對象訪問了K（k>1，若K=1則可以認為是LRU）次，LRU-K算法包含兩個隊列：

（1）對象歷史訪問信息隊列（可以是FIFO或者LRU隊列）;

（2）對象緩存隊列;

當對象a初次訪問時會被放入到對象歷史訪問信息隊列中，在對象歷史訪問信息隊列中的對象會按照FIFO或者LRU算法進行淘汰;當對象a的訪問次數達到K次時，對象a會被緩存到對象緩存隊列，同時將對象a的信息從對象歷史訪問信息隊列中刪除;對象緩存隊列中的對象按照LRU算法進行淘汰。

LRU-K算法能夠避免緩存污染，如果K值選取的較大雖能能提高緩存命中率，但是要淘汰歷史數據需要大量的數據訪問，適應性差;通常選取的K值為2。

2.5 MRU

MRU（MOSt recently used）為最近最多使用算法，該算法會首先淘汰最近訪問時間距離現在最短的對象，例如：緩存能緩存的對象總個數為4，訪問對象的順序為：ABCDDEC，MRI淘汰算法產生的結果過程如圖4所示。

MRU淘汰算法適合于訪問時間距離現在越久的對象，越容易被訪問到的場景;例如：大數據量的文件或者數據的循環掃描或者隨機掃描場景。

2.6 RR

RR（random：replacement）為隨機淘汰算法，在緩存需要淘汰對象時，該算法會隨機選擇緩存的對象進行淘汰，而不考慮對象的當前和歷史信息，所以該算法實現簡單，比較適合隨機化訪問的場景。

2.7 MQ

MQ（multi queue）為多級隊列緩存淘汰算法，滿足以下特性：

（1）對于給定的負載，緩存的數據的生命周期不少于某個固定時間;

（2）數據淘汰的優先級由數據的訪問頻率決定;

（3）頻率局部性，訪問頻率高的數據隨著訪問頻率的降低會被淘汰;

MQ包含m個LRU隊列（Q⁰，Q₁…Q_m-1）和1個FIFO隊列（Q_out），在Q₁中的緩存對象比Q₂中的緩存對象具有更長的生存時間（i>j）;Q_out為歷史隊列，其中包含從LRI隊列中淘汰的緩存對象。

當緩存對象O命中時，緩存對象放入Q_k的隊列末尾（根據緩存隊列優先級計算公式k=QueueNum（f），其中f為緩存對象O的范圍頻率），并且具有對應的生存時間;如果對緩存對象。的訪問時間間隔超過了對象。的生存時間，則對象O會從Q_k隊列降級到Q_k-1的隊列末尾，直至被淘汰;對象O被淘汰后，會將對象O的標示和訪問頻率放入歷史隊列Q_out中的末尾;如果此時對象O被訪問，則重新根據對象O的訪問頻率放入對應的優先級隊列中，并從Q_out中刪除。

MQ算法主要應用于二級緩存，能夠防止緩存污染;由于需要維護多個隊列，因此比LRU算法實現要復雜。

2.8 ARC

ARC（adaptive replacement cache）為自適應緩存淘汰算法，該算法根據對象訪問特性在LRU算法和LFU算法之間找到平衡。ARC算法緩存中包含四個隊列：

（1）R隊列，基于LRU算法;

（2）F隊列，基于LFU算法;

（3）R隊列，R隊列的影子隊列，存儲從R隊列淘汰的對象的標示;

（4）F隊列，F隊列的影子隊列，存儲從F隊列淘汰的對象的標示;

如圖5所示。

R隊列和F隊列的邊界會隨著對象訪問特性的變化而變化。對象a首次訪問時會被放入R隊列頭部，隨著新對象的加入，對象a會被推到R隊列的尾部，直至被淘汰出R隊列，進入R隊列的影子隊列R，R隊列保存對象的標示，如果對象a不被訪問并且隨著新元素的加入最后也會被從R隊列中淘汰。對象a在R隊列中，如果被再次訪問，則進入F隊列，如果被F隊列淘汰，則進入F隊列的影子隊列F隊列，直至被淘汰出F隊列。

當影子隊列R中的元素被再次訪問的時候，說明R隊列長度不夠，需要增加R隊列的長度，隊列邊界B會往F隊列方向移動;當影子隊列F中的元素被再次訪問的時候，說明F隊列的長度不夠，需要增加F隊列的長度，隊列邊界B會往R隊列方向移動。

ARC算法會根據對象的訪問特性，同時跟蹤對象訪問頻率、訪問時間以及兩者的訪問歷史。如果對象訪問偏向于LRU，算法會增加R隊列的長度，如果對象訪問偏向于LFU，算法會增加F隊列的長度，從而能夠達到自動適應對象的訪問特性。ARC算法比單獨的LRU和LFU表現出更好的適應性，但是實現稍微復雜。

3 總結

緩存淘汰算法在海量系統中非常重要，本文對常用的緩存淘汰算法進行了分析研究，分析了每種緩存淘汰算法的原理、適用場景及優缺點，為緩存淘汰算法的選擇和使用具有指導和借鑒意義。

參考文獻

[1]a cache managermeng scheme forefficient content evict ion andreplication in cache networks，Thisarticle is published in IEEEAccess，Vol.5，no.1，pp.1962-1701，Dec.2017.DOI：10.1109/ACCESS.2017.2669344

[2]ARC_A SELF-TUNING，LOW OVERHEADREPLACEMENT CACHE，USENIX File&Storage; Techno10Gies Conference（FAST），March 31，2003，SanFrancisco，CA.

[3]the multi-queue replacement algorithmfor second level ubffercaches，Boston，Massachusetts，USA，June 25-30，2001.

[4]錢培杰，武娟，高成英.視頻點播環境下的緩存算法研究[J].計算機科學，2015，6（6A）.

[5]魏維，羅時愛，劉鳳玉.視頻點播中視頻服務器節目替換算法研究[J].計算機工程與應用，2008，44（02）：245-248.