一种针对邮件服务类应用改进的2Q^＊算法及其在存储缓存中的应用  

Replacement Algorithm Improved on 2Q^＊ for Mail Service Workload and its Application in Storage Cache

作　　者：孟晓烜[1,2] 司成祥[1,2] 刘振晗[1,2] 许鲁[1] 

机构地区：[1]中国科学院计算技术研究所,北京100080 [2]中国科学院研究生院北京,100039

出　　处：《计算机科学》2010年第3期36-41,共6页Computer Science

基　　金：国家重点基础研究发展计划(2004CB318205);863国家重点基金项目(2007AA01Z402,2007AA01Z184,2009AA01Z139,2009AA01A403)资助

摘　　要：针对2Q算法对于邮件服务类负载所表现出的缓存性能特点提出了一种改进算法2Q*。模拟实验数据显示,改进后的2Q*算法在各种缓存容量下都优于包括经典2Q算法在内的其他替换算法。为了验证2Q*算法在真实系统中的有效性,将该算法集成于FlexiCache系统中并与目前主流的顺序自适应预取策略有机结合。实验结果表明,2Q*算法不仅能够在实际缓存系统中有效改善邮件服务类应用的物理I/O性能,而且其实际运行开销也非常低。This paper analyzed the performance characteristics of classic 2Q algorithm when it was performed on mail-service workloads,and proposed an improved algorithm, called 2Q^＊.The simulation results show that 2Q^＊ algorithm can outperform the other replacement algorithms,including the classic 2Q algorithm,for all the cache sizes and various mail-service workloads. To verify the simulation results in real practice, we implemented the algorithm in FIexiCache, a partitioned buffer cache system, and integrated it with a popular adaptive sectuential prefect policy properly. The experiment results in real system further confirm the effectiveness of 2Q^＊ algorithm for mail service kind of applications in improving their physical I/O performance. Moreover, its runtime overhead is also fairly low.

关 键 词：缓存 邮件服务 替换算法 2Q* 

分 类 号：TP333[自动化与计算机技术—计算机系统结构]