一种自适应分类重用距离来捕捉热数据的缓存算法

摘要 缓存算法在构建一个大的存储系统的存储器层次结构中起着重要作用.许多的缓存算法都集中在利用块的新进度（Recency)和访问频率(Frequency)来确定该块是否为热数据块.然而这里存在两个问题，首先热数据块的热度是有时间限制的，其次算法并没有考虑数据块还具有重用距离等其它特征.因此如果仅仅考虑将相同访问频率的数据块放在一起，那么热数据块之间必然会产生缓存污染问题.因为算法无法保证短的重用距离的热数据块的缓存驻留时间小于长的重用距离的数据块.针对这一问题，本文提出一种名为自适应分类重用距离的缓存算法（ACRD）.算法利用数据的重用距离特征和缓存替换的元数据历史信息来深度挖掘数据访问模式的特征，并以一种自适应的方式实现这种热数据识别和缓存时间分配的问题.实验结果表明，算法的性能明显优于LRU算法，并且在许多场合优于目前比较优秀的LIRS和ARC算法.同时，算法在不同的缓存规模下的命中率具有稳定性