The persistent‐access‐caching algorithm
The persistent‐access‐caching algorithm
复制标题
持久访问缓存算法
DOI：
10.1002/rsa.20214
复制
发表时间：
2008
影响因子：
1
通讯作者：
A. Radovanovic
中科院分区：
文献类型：
--
作者：
P. Jelenkovic;A. Radovanovic
缓存被广泛认为是提高万维网性能的有效机制。设计Web缓存系统的关键组件之一是设计用于更新缓存文档集合的文档放置/替换算法。这种策略的主要设计目标是高缓存命中率、易于实现、低复杂度和对访问模式波动的适应性。这些目标基本上是由广泛使用的启发式称为最近最少使用（LRU）缓存替换规则。然而，在独立参考模型的背景下，LRU策略的性能可能显着低于最佳最不频繁使用（LFU）算法，另一方面，该算法具有更高的实现复杂性和对访问频率变化的适应性较低。为了缓解这个问题，我们引入了一个新的基于LRU的规则，称为持久访问缓存（PAC），它基本上保留了LRU方案的所有理想属性。对于这种新的启发式，根据独立的参考模型和广义Zipf定律的请求概率，我们证明，对于大的缓存大小，其性能是任意接近最优LFU算法。此外，与普通LRU策略相比，PAC算法的这种接近最优性是以大缓存大小的可忽略不计的额外复杂性为代价实现的，因为PAC算法基于在固定长度的前一间隔期间收集的引用做出替换决策。© 2008 Wiley Periodicals，Inc.随机结构算法，2008
Caching is widely recognized as an effective mechanism for improving the performance of the World Wide Web. One of the key components in engineering the Web caching systems is designing document placement/replacement algorithms for updating the collection of cached documents. The main design objectives of such a policy are the high cache hit ratio, ease of implementation, low complexity and adaptability to the fluctuations in access patterns. These objectives are essentially satisfied by the widely used heuristic called the least‐recently‐used (LRU) cache replacement rule. However, in the context of the independent reference model, the LRU policy can significantly underperform the optimal least‐frequently‐used (LFU) algorithm that, on the other hand, has higher implementation complexity and lower adaptability to changes in access frequencies. To alleviate this problem, we introduce a new LRU‐based rule, termed the persistent‐access‐caching (PAC), which essentially preserves all of the desirable attributes of the LRU scheme. For this new heuristic, under the independent reference model and generalized Zipf's law request probabilities, we prove that, for large cache sizes, its performance is arbitrarily close to the optimal LFU algorithm. Furthermore, this near‐optimality of the PAC algorithm is achieved at the expense of a negligible additional complexity for large cache sizes when compared to the ordinary LRU policy, since the PAC algorithm makes the replacement decisions based on the references collected during the preceding interval of fixed length. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008
Zipf型请求分配中最近最少使用缓存故障概率的渐进性
DOI：
--
发表时间：
2006
期刊：
Random Structures and Algorithms (掲載決定)
影响因子：
--
作者：
Toyoaki Sugimoto;Naoto Miyoshi
通讯作者：
Naoto Miyoshi