简要介绍Cache替换算法,及几种不同替换算法.

Question

简要介绍Cache替换算法,及几种不同替换算法.

Answer 1

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算法一致,只是大小超过一定阈值的文档不能被缓存 ...