缓存淘汰算法研究

王永亮

摘要

在海量数据系统中，海量数据受缓存大小的限制会出现缓存满的情况，淘汰数据的选择就变得非常关键，会影响缓存未命中的次数，从而影响整个系统的性能，因此需要选择合适的缓存数据淘汰算法。本文通过对常用缓存淘汰算法的原理、适用场景和优缺点进行分析对比研究，为缓存淘汰算法的选择提供帮助。

【关键词】数据存储 缓存淘汰算法

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.