-1-
中国科技论文在线
基于 IRR 信息的改进 ARC 算法
汤茂杰，赵鹏，王瑀屏
(清华大学计算机科学与技术系 北京 100084)
摘要：缓存是增强计算机整体性能的一项重要技术，缓存替换算法作为核心技术更加重要。
通过深入研究多种数据访问模式下 ARC（adaptive replacement cache）算法的性能，总结出
ARC 算法性能较差的数据访问模式及其原因。针对发现的不足提出了一种改进的缓存替换
算法，该算法通过引入 IRR（inter reference recency）信息，提高了弱局部性访问模式下的缓
存命中率，改善了 ARC算法对不同数据访问模式的适应性。仿真实验结果表明，改进后的
算法提升了应对弱局部性访问模式的能力，增强了算法的灵活性。
关键词：缓存；缓存替换算法；ARC；IRR
中图分类号：; TP333 文献标识码：A
An IRR-based improved ARC algorithm
Tang Maojie, Zhao Peng, Wang Yuping
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
Abstract: Cache is an important technology to improve the overall performance of computers. As its
core technology, more importance is attached to cache replacement algorithm. Various data access
patterns have been thoroughly studied, and the patterns that ARC (adaptive replacement cache)
algorithm handles poorly and its cause are summed up. According to the weakness, an improved cache
replacement algorithm is proposed. By introducing IRR (inter reference recency) information, the new
algorithm improves cache hit rate of weak locality access pattern and makes ARC algorithm more
adaptive. The simulation result shows that this algorithm can improve the ability to handle weak
locality access pattern and enhance the flexibility of ARC algorithm.
Key words: cache; cache replacement algorithm; adaptive replacement cache；inter reference recency
缓存技术是计算机领域十分经典且基础的研究领域[1]，缓存替换算法作为缓存技术的核
心技术不断有新的研究成果出现。对目前已经提出的缓存替换算法可以进行如下划分。(1)
传统的缓存替换算法及其改进，典型的有 LRU、LFU、2Q、MQ[2]、Clock-Pro[3]等，这些算
法具有易于实现和被广泛应用等特点，但是也存在不可以随着应用程序数据访问模式的不同
而自适应调节的缺陷。(2) 充分挖掘数据访问模式的规律及缓存替换的历史信息以提高算法
性能的算法，具有代表性的有 LIRS[4]、ARC[5]、CAR[6]等。当前的应用更加复杂，多级存储
系统广为使用，传统单级的固定算法的不足愈加明显。所以研究热点已转向能够自适应的单
级缓存替换算法和提升多级缓存的整体性能[1]。
ARC 算法作为一种性能优异的缓存替换算法已经在工业界广泛使用。但通过对多种数
据访问模式的测试，可以发现，ARC 算法对于弱局部性访问模式表现出的性能相对较差。
如图 1所示是一种典型的弱局部性访问模式及其性能展示。其访问模式是循环读取比物理缓
存大的文件，如图 1(a)所示；LRU、OPT和 ARC三种算法对图 1(a)中测试集的性能表现如
图 1(b)所示。可以发现，ARC 算法对该数据访问模式基本不起作用。通过分析可以发现，
其原因在于，对于弱局部性访问模式，物理缓存经常存满最近读取一次的数据。而在 ARC
算法中，新读取的数据可能会轻易地将最近读取一次的数据不经过保护就直接移出物理缓
存。
基金项目：国家自然科学基金资助项目(61103020)
作者简介：汤茂杰(1990—)，男，硕士研究生，主要研究方向为操作系统
通信联系人：王瑀屏，助理研究员，主要研究方向为操作系统，
-2-
中国科技论文在线
(a) 弱局部性访问模式测试集 (b) 多种算法对测试集的性能
图 1 数据访问模式样例
本文在分析了 ARC在各种数据访问模式下的性能后，总结出表现较差的访问模式及其
原因，提出了在 ARC算法中引入 IRR信息来解决弱局部性访问模式下性能较差问题的方法，
从而实现一个更加高效的自适应算法。该方法有效地提升了 ARC算法应对弱局部性访问模
式的能力，增强了算法的灵活性。
1 相关工作
传统缓存替换算法
最优替换算法(optimal replacement algorithm)是一种理想的算法，其命中率是可能达到的
最高的命中率，常用于评价其他缓存替换算法。该算法工作于一个预先知道所有数据读取顺
序的工作集，但由于绝大部分情况下，数据读取顺序事先是不知道的，故实际应用中不使用
该算法。
传统的缓存替换算法主要包括分别以 Recency和 Frequency为关键替换因素以及在两者
之间权衡的算法。其中，Recency 指缓存队列中缓存数据到队列尾部的距离，而 Frequency
则指缓存数据读取的频率。Recency类算法假设，最近最少使用的数据在接下来读取的概率
在统计上比其它数据低。Frequency 类算法假设，最近读取频率较高的数据在接下来读取的
概率比最近读取频率较低的数据高。两类算法都使用了数据访问的局部性原理。
现在已经提出的很多缓存替换算法都是在 Recency 和 Frequency 之间进行权衡，如
LRFU、2Q、MQ和 Clock-Pro等。
ARC算法
ARC(adaptive replacement cache)算法是一种可以自适应调整的缓存替换算法。该算法权
衡于 Recency和 Frequency之间，并保存了最近从缓存中替换出去的数据的历史信息。其成
功的原因主要有两点：(1) 引入了最近被替换出的数据的历史信息，借助该信息来预测未来
并保护缓存中经常读取的数据不被轻易污染；(2) 设计了一个可以自适应调整的参数，使得
该参数对于多种访问模式和不同缓存大小，无需预先了解和调整参数，就可以拥有良好的性
能。
ARC算法目前已经应用于 ZFS文件系统中。该算法是 scan-resistant的，也就是说，其
允许只有一次的顺序读取经过缓存，却不会影响到已经保存在缓存中具有临时局部性的数
据。但对于更可能读取旧数据或者短时间内读取两次干扰数据的弱局部性模式就表现得较
差。鉴于 ARC算法性能优异，IBM已将其作为大型服务器和蓝云系统的主要缓存管理算法
[8]。
-3-
中国科技论文在线
IRR信息
IRR(inter reference recency，也称为 Reuse)指的是同一个缓存数据在新近两次读取之间
读取其他数据的次数[9]，易于统计、实现简单[10]。当需要替换时，替换 IRR较大的数据。IRR
信息的提出源于如下假设：如果一个数据的读取间隔周期比较短，那么接下来读取该数据的
概率会相对较高。其基本思想是对数据进行分类，即一部分是热数据(经常读取的数据)；一
部分是冷数据(偶尔读取的数据)。对热数据分配绝大部分的缓存资源，对冷数据分配较少的
剩下的缓存资源，然后借助冷数据提高数据进入热数据的门槛，并保证热数据不会被轻易地
替换出来，从而使得经常读取的数据一直存于缓存中，以有效避免缓存中的数据被只出现一
次的数据污染。
2 设计方案
设计思想
ARC 算法的缓存布局如图 2 所示。物理缓存由两部分组成，T1队列保存最近读取一次
的数据，T2队列保存最近至少读取两次的数据，且 T1和 T2都是 LRU 队列。为充分使用最
近从缓存中替换出来的数据这一历史信息，在内存中维护两个 LRU队列，分别记录最近从
T1队列中替换出的数据和最近从 T2队列中替换出的数据，分别记为 B1和 B2。4个队列中保
存的数据个数不应该超过物理缓存所能容纳的数据个数的两倍。
B1 T1 T2 B2
L1 L2LRU MRUMRU LRU
Buffer Cache
(size=c)
T1's target size: p c-p
图 2 ARC算法的缓存布局
通过分析 ARC算法，可以发现，其缓存布局中，T1队列在仅有 B1队列保护的前提下依
旧容易被新读取的数据污染。这是由于在 ARC算法中，当新读取的数据不属于上述 4个队
列且 T1队列和 B1队列的大小之和恰为缓存大小时，T1队列的 LRU可能会不经过 B1队列而
直接被移出缓存，从而出现一些垃圾数据冲洗掉 T1队列中将会经常读取数据的可能。
为保护 T1队列中将会经常读取的数据，在 ARC算法中引入 IRR信息。当新读取的数据
不属于 ARC算法中的 4个队列时，通过维护热数据和冷数据队列，对物理缓存中需要替换
出的数据依据其冷热属性进行保护。再次读取将会经常读取的数据时，可以及时确定其为热
数据，并加入缓存和提高其被替换出缓存的门槛。而 ARC算法对 T1队列中将会经常读取的
数据保护力度不够，使热数据会轻易地被不加保护地替换出缓存。因此，引入 IRR 信息可
以避免 T1队列中将会经常读取的数据被垃圾数据污染，且不经过 B1队列就直接被移出缓存。
通过在ARC算法中引入 IRR信息，本文设计的缓存布局如图 3所示。物理缓存由HIR_Q
队列保存的最近热数据、T1队列保存的最近读取次数较少的数据和 T2队列保存的最近读取
次数较多的数据 3部分组成，且 3个队列都是 LRU队列。HIR_Q队列的大小为缓存大小的
1%，其他的 99%在 T1队列和 T2队列之间分配。B1队列和 B2队列的含义以及所有队列的大
小总和限制同原 ARC算法。
-4-
中国科技论文在线
B1 T1 T2 B2
L1 L2LRU MRUMRU LRU
Buffer Cache
(size=c)
T1's target size: p
LRU MRU
HIR_Q
图 3 改进 ARC算法的缓存布局
算法描述
除上述 5个 LRU队列外，改进算法还需引入一个 LIR_Q队列保存最近冷数据，以完成
算法的设计。LIR_Q、HIR_Q、T1、 B1、 T2和 B2均初始化为空，调整参数 p，初始化为 0，
令 x为要读取的数据，c为缓存的大小。
首先重新定义 ARC 算法中调整参数 p 的子程序 Replace(p)。如果|T1|=p 且 xB2或者
|T1|>p，移动 T1的 LRU位置到 HIR_Q的MRU位置，并删除 LIR_Q的 LRU，直到该数据属
于 T1，移动 HIR_Q的 LRU到 B1的MRU，并从缓存中将其删除。否则，将 T2的 LRU移动
到 B2的MRU并从缓存中删除它。
因为改进算法中 T1、B1、T2、B2的含义不变，所以如果新读取的数据属于这四个队列，
除属于 T1时需额外维护 LIR_Q队列，其他情形和原算法操作一样。如果新读取的数据属于
HIR_Q，则维护 LIR_Q、HIR_Q 和 T1队列以将相应冷热属性的数据放入对应队列。如果新
读取的数据不属于上述情形，则根据各个队列是否已满以及原冷热属性来分类处理。
下面是完整的算法描述：
1) xT1，缓存命中。将 x从 T1移至 T2的MRU位置，从 LIR_Q中删除 x，删除 LIR_Q
的 LRU，直到该数据属于 T1。
2) xT2，缓存命中。将 x从 T2移至 T2的MRU位置。
3) xHIR_Q，缓存命中。
(1) 若 x∉ LIR_Q，将 x加至 LIR_Q的MRU位置，并将 x移至 HIR_Q的MRU位置；
(2) 否则，将 x移至 LIR_Q的MRU位置，从 HIR_Q中删除 x，将 x加至 T1的MRU位
置，将 T1的 LRU移至 HIR_Q的MRU，删除 LIR_Q的 LRU，直到该数据属于 T1。
4) xB1，缓存缺失。调整 p为 min{,p+max{| B2|/| B1|,1}}，Replace(p)，将 x移至 T2
的 LRU位置，并将 x放入缓存中。
5) x B2，缓存缺失。调整 p为 max{0,p－max{| B1|/| B2|,1}}，Replace(p)，将 x移至 T2
的 LRU位置，并将 x放入缓存中。
6) x不属于以上情形，缓存缺失。
(1) |L1|+| L2|<，将 x加至 T1和 LIR_Q的MRU位置，并加入缓存中。
(2) | T1|+|T2|=。
① x∉ LIR_Q且 HIR_Q未满。将 x加至 LIR_Q和 HIR_Q的MRU位置，并加入缓存中。
② x�LIR_Q且 HIR_Q已满。若 B1为空，则删除 HIR_Q的 LRU元素，并从缓存移除，
将 x加至 LIR_Q和 HIR_Q的MRU位置，并加入缓存中。否则，删除 B1的 LRU，Replace(p)，
将 x加至 T1和 LIR_Q的MRU，并加入缓存中。
③ xLIR_Q且 HIR_Q未满。将 x移至 LIR_Q的MRU，加至 T1的MRU，并加入缓存
中。将 T1的 LRU移至 HIR_Q的MRU，删除 LIR_Q的 LRU，直到该数据属于 T1。
-5-
中国科技论文在线
④ xLIR_Q且 HIR_Q已满。若 B1为空，则删除 HIR_Q的 LRU元素，并从缓存移除。
将 x 移至 LIR_Q 的 MRU，加至 T1的 MRU，并加入缓存中。将 T1的 LRU 移至 HIR_Q 的
MRU，删除 LIR_Q的 LRU，直到该数据属于 T1。否则，删除 B1的 LRU元素，Replace(p)，
将 x移至 LIR_Q的MRU，加至 T1的MRU，并加入缓存中。
(3) |L1|<，|L1|+|L2|>=,若|L1|+|L2|=，删除 B2的 LRU。接着 Replace(p)，将 x
加至或移至 LIR_Q和 T1的MRU，并加入缓存中。
3 实验评测
测试集简介
为评测改进后的 ARC算法(简称为MyARC算法)，本文采用如表 1所示的测试集[4]。
表 1 实验采用的测试集
测试集 说明
2_pools 人工合成的 trace，模拟 100000次对一个多用户数据库的随机访问
Cpp GNU C编译器预处理的 trace，作为输入的 C源文件的大小为 11MB左右
Cs 交互的 C源程序测试工具的 trace，作为输入的 C源文件的大小为 9 MB左右
Glimpse 文本信息检索的 trace，作为输入的文本文件总大小为 50 MB左右
Postgres 关系数据库中 4个关系的连接查询的 trace
Multi1 同时执行 cs和 cpp时得到的
Multi2 同时执行 cs、cpp和 postgres时得到的
Multi3 同时执行 cpp，gnuplot、glimpse和 postgres时得到的
从表中可以看出，2_pools是随机访问模式，Cpp是顺序读取访问模式，Cs是大文件的
循环访问模式，其他的也是一些典型的访问模式。
仿真实验结果
为了充分评测MyARC算法的性能，将MyARC算法对各个测试集在不同缓存大小下的命
中率和 OPT、LRU、ARC 算法的仿真实验结果进行比较。对于随机访问模式和顺序读取访
问模式，ARC算法的性能已经足够好，MyARC算法没有带来太多的提升。其它各种测试集
在不同缓存大小下的算法性能如图 4所示。
(a) 各种算法对 Cs测试集的性能 (b) 各种算法对 Glimpse测试集的性能
-6-
中国科技论文在线
(c) 各种算法对 Postgres测试集的性能 (d) 各种算法对Multi1测试集的性能
(e) 各种算法对Multi2测试集的性能 (f) 各种算法对Multi3测试集的性能
图 3 各种测试集和缓存大小下的算法性能
4种算法对测试集 Cs在不同物理缓存大小下的命中率如图 4(a)所示。Cs测试集是对大
文件的循环读取，对文件的一次循环需要读取约 1400个不同的地址。从图中可以看出，当
物理缓存小于循环大小时，ARC算法和 LRU算法的性能都十分低，而MyARC算法的性能
十分优秀，几乎接近 OPT算法的性能。这是因为 ARC循环读取大文件时，大文件数据顺序
流经缓存。而引入 IRR信息后，T1队列中的数据不会不经 B1就直接从物理缓存中删除。因
此，冷数据无法将物理缓存中的热数据挤出。图 4(b)中的 Glimpse和图 4(c)中的 Postgres测
试集也因为包含类似的弱局部性读取序列，所以MyARC算法的性能显著地高于 ARC算法。
图 4(d)、图 4(e)和图 4(f)分别是多个不同程序同时执行时采集的测试集的仿真实验结果。
对比图中的数据表明，MyARC算法对于多计算任务具有较高的命中率。
4 结 论
本文提出了一种基于 IRR信息的改进的 ARC缓存替换算法。通过引入 IRR信息，有效
地保护了物理缓存中可能会经常读取的热数据，避免这部分数据被较少读取的数据污染，并
提高了污染数据进入物理缓存常驻热数据的门槛。仿真实验结果表明，改进的 ARC算法提
高了弱局部性访问模式下的算法性能，增强了 ARC算法的适应性，具备更加广泛的应用前
景。
[参考文献] ( References)
[1] 黄敏, 蔡志刚. 缓存替换算法研究综述[J]. 计算机科学, 2006, 33(B12): 191-193.
Huang Min, Cai Zhigang. Summary of cache replacement algorithm [J]. Comput Sci, 2006, 33(B12):
191-193. (in Chinese)
[2] Zhou Yuanyuan, James Philbin, Li Kai. The multi-queue replacement algorithm for second level buffer
caches [C]//2001 USENIX Annual Technical Conference. Berkeley, USA: ACM, 2001: 91-104.
[3] Jiang Song, Chen Feng, Zhang Xiaodong. CLOCK-Pro: an effective improvement of the clock replacement
[C]//2005 USENIX Annual Technical Conference. Berkeley, USA: ACM, 2005: 323-336.
-7-
中国科技论文在线
[4] Jiang Song, Zhang Xiaodong. LIRS: an efficient low inter-reference recency set replacement policy to
improve buffer cache performance [C]//2002 ACM SIGMETRICS International Conference on
Measurement and Modeling of Computer Systems. California, USA: ACM, 2002: 31-42.
[5] Megiddo N, Modha D S. ARC: A self-tuning, low overhead replacement cache [C]// USENIX Conference on
File and Storage Technologies. Berkerley, USA: ACM, 2003: 115-130.
[6] Bansal S, Modha D S. CAR: Clock with adaptive replacement [C]//USENIX Conference on File and Storage
Technologies. Berkerley, USA: ACM, 2004: 187-200.
[7] 李志. 面向闪存的缓冲区管理算法研究[D]. 合肥: 中国科学技术大学, 2010.
Li Zhi. Research on buffer management algorithms for flash memory [D]. Hefei: University of Science and
Technology of China, 2010. (in Chinese)
[8] 王超宇. 缓存替换策略研究[D]. 哈尔滨: 哈尔滨工程大学, 2012.
Wang Chaoyu. Research on cache replacement strategies [D]. Harbin: Harbin Engineering University, 2012.
(in Chinese)
[9] 刘何秀. 神经网络集成算法的研究[D]. 青岛: 中国海洋大学, 2009.
Liu Hexiu. Research on neural network ensemble algorithm [D]. Qingdao: Ocean University of China, 2009.
(in Chinese)
[10] 徐鹏. 老化算法的改进及其在 LBCIS中的应用研究[D]. 长春: 吉林大学,2010.
Xu Peng. Improvement on aging algorithm and research on its application in LBCIS [D]. Changchun: Jilin
University, 2010. (in Chinese)
