緩存淘汰算法研究

王永亮

摘要

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

【關(guān)鍵詞】數(shù)據(jù)存儲 緩存淘汰算法

1 引言

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

2 緩存淘汰算法分析

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

2.1 LRU

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

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

2.2 LFU

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

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

2.3 FIFO

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

2.4 LRU-K

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

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

（2）對象緩存隊列;

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

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

2.5 MRU

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

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

2.6 RR

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

2.7 MQ

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

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

（2）數(shù)據(jù)淘汰的優(yōu)先級由數(shù)據(jù)的訪問頻率決定;

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

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

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

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

2.8 ARC

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

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

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

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

（4）F隊列，F(xiàn)隊列的影子隊列，存儲從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算法會根據(jù)對象的訪問特性，同時跟蹤對象訪問頻率、訪問時間以及兩者的訪問歷史。如果對象訪問偏向于LRU，算法會增加R隊列的長度，如果對象訪問偏向于LFU，算法會增加F隊列的長度，從而能夠達到自動適應對象的訪問特性。ARC算法比單獨的LRU和LFU表現(xiàn)出更好的適應性，但是實現(xiàn)稍微復雜。

3 總結(jié)

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

參考文獻

[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]錢培杰，武娟，高成英.視頻點播環(huán)境下的緩存算法研究[J].計算機科學，2015，6（6A）.

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