最小驻留价值缓存替换算法.docx

最小驻留价值缓存替换算法0引言缓存替换算法主要研究缓存内驻留对象的管理方法与替换策略使待处理对象更多地在缓存空间命中提升缓存效果。缓存替换算法已从传统的最近最少使用（LeastRecentelyUsedLRU）、最近最不常用（LeastFrequentlyUsedLFU）等单因子算法演进到MIX、GDSize（GreedDualSize）等多因子算法。各种算法结合数据访问的时间/空间局部性在不同的访问模型下表现出各自的性能优势。然而研究表明常用替换算法在搜索应用中可能表现出较差的适应性[1]。为衡量面向搜索应用的替换算法效率业界通常采用以下指标[2-3]：1）请求命中率（RequestHitRateRHR）。在给定统计时段内所有被请求对象在缓存内命中的总次数与请求总次数的比值。2）字节命中率（ByteHitRateBHR）。在给定统计时段内所有被请求对象在缓存内命中的字节总数与请求字节总数的比值。3）平均延迟时间（AverageLatencyTimeALT）。在给定统计时间内缓存收到对象请求直至该对象加载至内存所需的平均时间。其中RHR侧重通过请求命中次数衡量缓存替换算法效率；BHR侧重通过请求命中字节数衡量算法效率。当考虑各缓存对象具有不同字节数的情况时BHR对衡量替换算法效果更具参考价值。本文以最大化BHR为目标提出面向搜索应用的最小驻留价值（LeastCacheValueLCV）替换算法。在搜索引擎领域应用的缓存替换算法可分为：1）基于访问频率的算法。其中：LRU[4]、LRUK[5]算法仅在特定的应用下表现出较好的性能。LRFU[6]算法依据权值函数评估访问模式选择使用LRU或LFU算法但算法未指出实时动态调整策略。EDRPLRU[1]算法依据重引用距离区分冷热对象块并对不同的对象块分别采取先进先出（FirstInFirstOutFIFO）和LRU替换策略算法适用于局部性较强的访问环境。2）基于对象大小的算法。其中：Size[7]算法优先替换字节数多的对象但算法有可能使小对象过久驻留缓存。GDSize[8]算法综合考虑对象大小、对象的年龄因子以及对象进入缓存的代价等因素为每一个进入缓存的对象设置权重H=cost/size每次替换具有最小H值的对象算法并未考虑对象在过去的访问次数[9]。3）访问频率和对象大小相结合的算法。其中：MIX[10]算法综合考虑对象在缓存中的访问次数、最近访问时间差、对象大小等多种属性为每个属性设置调优参数。但算法参数选取较为复杂。ACACRA[11]算法以对象大小表示背包重量、对象的平均访问时间表示对象的价值借鉴01背包问题的蚁群算法求解替换对象但算法计算量较大适用于计算机应用层。LNC[12]算法综合对象平均引用时间、最近流逝时间、对象大小、单位价值等因素提出对象引用率的概念并以此作为替换依据；但算法计算量较大需要较高的硬件配置。基于流行度预测的流媒体算法[13]通过回归分析技术预测对象的访问频率并结合对象大小替换对象但算法对影响因素的考虑过于单一。1LCV算法模型1.1LCV算法关联因子根据引言分析基于对象大小的替换策略侧重驻留字节数较少的对象以提高RHR但因未考虑对象访问频率使算法在特定应用中BHR较低；相反基于访问频率的算法侧重驻留命中次数较高的对象以提升BHR但其并未考虑大对象命中对BHR的贡献值；访问频率和对象大小相结合的替换策略能获得较高的BHR而被广泛应用。本文定义对象驻留价值（CacheValueCV）并以此作为替换依据提出LCV算法。