Cache 替换算法【转】

Cache替换算法是影响代理缓存系统性能的一个重要因素，一个好的Cache替换算法可以产生较高的命中率。目前已经提出的算法可以划分为以下三类：

（1）传统替换算法及其直接演化，其代表算法有：①LRU（Least Recently Used）算法：将最近最少使用的内容替换出Cache；②LFU（Lease Frequently Used）算法：将访问次数最少的内容替换出Cache；③Pitkow/Recker[10]提出了一种替换算法：如果Cache中所有内容都是同一天被缓存的，则将最大的文档替换出Cache，否则按LRU算法进行替换。

（2）基于缓存内容关键特征的替换算法，其代表算法有：①Size[10]替换算法：将最大的内容替换出Cache；②LRU—MIN[11]替换算法：该算法力图使被替换的文档个数最少。设待缓存文档的大小为S，对Cache中缓存的大小至少是S的文档，根据LRU算法进行替换；如果没有大小至少为S的对象，则从大小至少为S/2的文档中按照LRU算法进行替换；③LRU—Threshold[11] 替换算法：和LRU算法一致，只是大小超过一定阈值的文档不能被缓存；④Lowest Lacency First[12]替换算法：将访问延迟最小的文档替换出Cache。

（3）基于代价的替换算法，该类算法使用一个代价函数对Cache中的对象进行评估，最后根据代价值的大小决定替换对象。其代表算法有：①Hybrid[12] 算法：算法对Cache中的每一个对象赋予一个效用函数，将效用最小的对象替换出Cache；②Lowest Relative Value[13] 算法：将效用值最低的对象替换出Cache；③Least Normalized Cost Replacement（LCNR）[14]算法：该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档；④Bolot等人 [15]提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换；⑤Size—Adjust LRU（SLRU）[16] 算法：对缓存的对象按代价与大小的比率进行排序，并选取比率最小的对象进行替换。

总之，为了使Cache命中率最大化，围绕Cache替换算法已经开展了大量的工作，但是替换算法的性能很大程度上取决于WWW访问的特性，还没有哪一种替换算法能够对所有Web访问模式都优于其它算法。