一种基于时钟自适应的改进缓存替换算法*

魏文国，赵慧民，庄林凯，许鸿俊

(广东技术师范学院电子与信息学院,广东 广州 510665)

1 研究背景分析

缓存算法是存储系统、数据库、Web服务器等计算机领域的核心技术之一[1-5]，几种经典的缓存页面替代算法LRU、CLOCK、ARC和CAR各有优缺点[6]，其中LRU是代替最近最少使用的页面的算法[7-8]，Oracle数据库使用该算法管理缓存。LRU 实现极其简单，具有常数的时间和空间复杂度，能捕捉很多工作负载的“最近期”特性。但是LRU 有4个很明显的缺点：

1)用进程锁去保证数据正确和统一，这是在高性能、高吞吐量环境下所不能接受的，如虚拟缓存管理、数据库和文件系统。

2)在每次命中缓存时，它必须移动到最多最近使用(MRU)的位置。在异步计算环境下，多个线程都试图将页面移动到 MRU位置是不可接受的。

3)LRU 捕捉工作负载的“最近期”特性，但是没有捕捉“频率”特性。

4)LRU 容易被内存扫描影响，即一系列一次使用的页面导致系统的低性能。

CLOCK缓存算法是LRU的一种单位元量近似实现[9-10]，它在每个页面包含“单位引用次数”，当页面第一次被插入缓存时，引用次数将设为0。页面在缓存里以一个钟的形式循环存放，当缓存命中时，页面的引用次数设为1。钟的指针用来替代缓存，当缓存容量满了的时候，指针会从起始位置开始扫描整个缓存，当指针指向引用次数为1的页面时，会将引用次数设为0，如果指向引用次数为0的页面，则将此页面替换出缓存。CLOCK解决了LRU的缺点1和缺点2，它完全去除了进程锁，这样使得缓存算法能更快地进行缓存的插入和清理，大大提高了缓存工作的效率。 CLOCK算法第一次提出page reference bit，每次缓存命中后只需将页面引用次数设为1，不用像LRU一样每次缓存命中都将页面转移到MRU位置。但是缺点3和4导致CLOCK算法的实际命中率比LRU并没有明显的提高。这是因为两种算法都只捕捉“近期使用”的特性，而不能捕捉“频率”特性，导致了此类算法及其变体的命中率并没有实质性的提高。

2003年，IBM研究中心的Nimrod Megiddo等人[11]提出了ARC算法如图1所示，该算法创造性地运用四条LRU链：T1，T2，B1和B2分别捕捉近期和频率特性。T1、T2存放缓存中的数据，B1、B2的数据并不放在缓存中。T1管理近期使用页面，T2管理多次使用的页面，B1、B2则分别接收从T1、T2淘汰的页面并进行后续管理。ARC算法将多次命中的页面从T1转移到有关频率的T2中，使得缓存能同时管理“近期”和“频率”两个重要的特性。ARC解决了缺点3和缺点4，将高频使用的页面与最近使用页面分开管理，从而捕捉到高频使用的页面并进行区分管理。同时也避免了在一次一系列浏览后，缓存页面被全部破坏的问题。这两点使得ARC缓存算法相对于LRU，CLOCK等类似的缓存算法在命中率方面有很明显的提高，ARC思想的提出对当代缓存算法有十分重要的意义，后面涌现出众多类似的改良算法都基于此算法。ARC算法虽然解决了缺点3和缺点4，但是该算法的实现完全基于LRU算法，从而暴露出LRU几个严重的缺陷，其中上面所阐述的缺点1和2就是很关键的两点，LRU自身的缺点导致了ARC在缓存替代效率上还有提高的空间。

图1 ARC缓存管理算法数据结构示意图

IBM研究中心的Dharmendra Modha[12-13]不久又提出了一种改良ARC的缓存算法CAR：Clock with Adaptive Replacement。CAR缓存算法是当前较经典的几个缓存算法之一，运用广泛。CAR将ARC与CLOCK结合，同时解决了LRU的4个缺点，T1，T2用CLOCK算法实现，B1，B2用LRU实现。能同时捕捉“近期”和“频率”两个特性，并完全解决了LRU算法的缺陷。

虽然CAR对缓存算法进行了较充分的改良，但是它并不能很完善地捕捉缓存使用的“频率”特性。我们在文献[14]中提出了对缓存页面的“频率”特性进行更加精细化管理的缓存管理算法GCAR，该算法在集群协作缓存环境下被验证能取得更好的缓存命中率，本文在此基础上进行改进，改变GCAR算法的部分流程，并在3种典型的概率分布(例如随机分布、泊松分布和正态分布)的读请求进入缓存的情况下进行对比测试，都能取得更好的缓存命中率，证明该ICAR缓存管理算法的适用性更好。本文还研究基于时钟自适应的改进缓存替换算法ICAR的思想与流程；在3种典型的概率分布(例如随机分布、泊松分布和正态分布)的读请求进入缓存的情况下进行对比测试LRU、CAR和ICAR的缓存命中率；最后给出结论和阐述将来的工作。

2 基于时钟自适应的改进缓存替换算法ICAR

通过对CAR算法以及经典缓存算法的研究，我们发现：CAR用于捕捉频率特性的CLOCK T2并不能很完善地捕捉“频率”特性。虽然多次使用的数据会从T1传递到T2并进行分开管理，但是CLOCK T2里的引用次数只是0或1。这样导致即使该数据块经过了多次访问，但是它的引用次数依然只是1。当缓存进行替代操作的时候，多次访问的数据块与少量访问的数据块在T2中引用次数都为1，导致两者被清理出缓存的几率相同。所以，CAR算法只能粗线条地对T2数据进行管理，并不能很精确地捕捉数据“频率”特性。

针对CAR不能精确捕捉数据块“频率”特性的缺陷，我们试图改变CLOCK的数据结构，使CLOCK的引用次数不局限于0和1，当每次缓存命中的时候我们将引用次数进行“加1”处理。这样可以使CLOCK T2能对“频率”特性进行更精确地管理。通过对CLOCK算法的改变，并对CAR算法的适应性调整，我们提出ICAR缓存算法，其流程如图2所示。与ARC和CAR算法类似，同样T1和T2采用CLOCK类型的缓存数据结构，他们包含了缓存里的所有数据。B1和B2只是简单的LRU列表的实现，包含那些近期从缓存淘汰出的数据。

CLOCK T1捕捉“近期”的页面，并且T1是按照缓存页面使用由新到旧排序头进尾出的循环链表；CLOCK T2则捕捉“长期”的页面(即被频繁访问的页面)，即T2是头进尾出的循环链表。从T1淘汰的数据进入B1，即B1是按照页面使用由新到旧排序头进尾出的循环链表。从T2淘汰的数据进入B2，即B2也是头进尾出的循环链表，B1、B2的数据不存放在缓存中。算法限制|T1|+|T2|的大小不超过缓存容量c，将B1的大小限制与T2大小一致，B2与T1大小一致。其中T1和T2的大小此消彼长，并且由自适应变量p调节：当B1内的数据命中时，T1的大小将增加1；反之，当B2内的数据命中时，T1的大小将减小1。

当缓存未命中时，新的数据将被插入至T1，同时引用次数将被设为0。当缓存命中任何在T1或T2的数据时，引用次数都将+1。

“整理缓存”子模块的流程如图3所示，缓存清理时，CLOCK T1的指针从尾部移动到头部。当CLOCK T1指针指向的页面引用次数为0时，页面将清理到B1的MRU(最近使用)位置，当引用次数为不为0时，页面将插入至CLOCK T2的头部并使指针指向下一个页面；当CLOCK T2指针指向的页面引用次数为0或1时，页面将清理到B2的MRU位置，当引用次数大于1时，将页面引用次数-1并移动至CLOCK T2的头部并使指针指向下一个页面。

图2 缓存替换算法ICAR流程图

图3 ICAR子模块“整理缓存”流程图

3 仿真实验与测试结果

实验环境与条件：不失一般性假设，缓存容量为1 024个页面；主要测试读请求到达的时间服从随机分布、泊松分布和正态分布等三种代表性的情况；若读请求太大，超过缓存容量的一定比例之后，命中缓存的几率很低，研究的意义不大，所以假设每次读请求的大小在[1,20]之间随机产生。使用Java语言开发仿真程序，模拟三种缓存管理算法：LRU、CAR和ICAR在读请求按照上述概率分布到达时的缓存命中率。

第一组实验在读请求以随机分布到达时对比测试LRU、CAR和ICAR三种缓存管理算法的缓存命中率如图4所示。请求大小在[1,20]中随机产生，即读请求的平均大小为10。缓存容量为1 024，表示缓存大约能够容纳(1 024 /100)约100个请求。当概率模型为随机分布时，读请求进入缓存的概率没有明显的高低之分，没有固定的高频页面，难以捕捉频率的特性，所以三种缓存算法的命中率都近似相同，当不同读请求的个数较少(例如图4最右边的只有128个不同读请求的测试案例)，能够在一定程度反映读请求的“频率”特性时，ICAR的缓存命中率较其他两种略高。

图4 读请求按照随机分布到达的缓存命中率对比

第二组实验在读请求以正态分布到达时对比测试LRU、CAR和ICAR三种缓存管理算法的缓存命中率如图5所示。高频率的读请求会更长时间停留在缓存中，结果表明：当命中率较低时(低于30%)，页面“频率”的特性难以捕捉，ICAR的命中率与CAR命中率近似，但比LRU命中率高；当命中率适中时(高于30%且低于80%)，页面“频率”特性体现得较为明显，ICAR较CAR命中率有比较明显的增加，平均增幅约为12.5%；当命中率较高时(高于80%)，CAR与ICAR两者缓存命中率相对于LRU都有非常明显的提高，但ICAR与CAR命中率几乎相同，因为“高频率”页面长期驻留缓存，不能体现差异。

图5 读请求按照正态分布到达的缓存命中率对比

第三组实验在读请求以泊松分布到达时对比测试LRU、CAR和ICAR三种缓存管理算法的缓存命中率。测试结果与正态分布有相似的规律。

4 总结与展望

本文比较和分析了4种经典的缓存管理算法LRU、CLOCK、ARC和CAR，提出基于时钟自适应的改进缓存替换算法ICAR，仿真实验验证该算法在大多数情况下能取得更高的缓存命中率。文献[14]中提出的GCAR缓存管理算法对集群协作缓存能取得较好的缓存命中率，本文的改进在于ICAR的适用性更好。进一步的研究可在缓存命中率相当高(高于80%)或者比较低(低于30%)的情况下改进和优化ICAR算法。

参考文献：

[1] CHRIS G,ALI R, BUTT Y, et al. Program-counter-based pattern classification in buffer caching[C]∥ 6th Symposium on Operating Systems Design and Implementation,2004:321-349.

[2] ALI R. The performance impact of kernel prefetching on buffer cache replacement algorithms[C]∥ Proceedings of the 2005 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems,2005:157-168.

[3] JEONG J.Simple penalty-sensitive cache replacement policies[J]. Journal of Instruction-Level Parallelism,2008,10:1-24.

[4] 王欣，周南，邱小彬.JCS数据缓存技术在动态Web系统中的应用[J].中山大学学报:自然科学版, 2009(S1)：356-357.

[5] 陈华竣，郑智，倪德明.一种面向分层访问的目录结构在RDBMS中的存储方法[J].中山大学学报:自然科学版， 2005(S1)：138-141.

[6] BANSAL S, MCKENNEY P E , MODHA D S. Apparatus and system for dynamically allocating main memory among a plurality of applications: US Patent,7 487 320[P].2009-02-03.

[7] LEE D, CHOI J, KIM J, et al. On the existence of a spectrum of policies that subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU)policies[C]∥Proceeding of 1999 ACM Sigmetrics Conference, 1999: 134 - 143

[8] LI Zhansheng.CRFP: A novel adaptive replacement policy combined the LRU and LFU policies[C]∥ IEEE 8th International Conference on Computer and Information Technology,2008:72-79.

[9] BANSAL S. Method and system of clock with adaptive cache replacement and temporal filtering:US Patent App,10/955 201[P]. 2006.

[10] JIANG S,CHEN F,ZHANG X. CLOCK-Pro: an effective improvement of the CLOCK replacement[C]∥ Proc of USENIX ′05,2005:121-130.

[11] MEGIDDO N,MODHA D. ARC: a self-tuning, low overhead replacement cache[C]∥ Proceedings of the 2nd USENIX Symposium on File and Storage Technologies,2003:115-130.

[12] BANSAL S,MODHA D.CAR: clock with adaptive replacement[C]∥ Proceedings of the 3nd USENIX Symposium on File and Storage Technologies, 2004:203-215

[13] SHAMSHEER S M.A throughput analysis on page replacement algorithms in cache memory management[J]. International Journal of Engineering Research and Applications,2012,2(2):126-130.

[14] 魏文国，陈潮填，闫俊虎.集群协作缓存机制研究[J].计算机科学，2008 (1)：282-284.