The Persistent-Access-Caching Algorithm

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 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 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. On the other hand, the benefit of the LFU rule is counterbalanced by its 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. Furthermore, for the independent reference model and generalized Zipf’s law request probabilities, we prove that, for large cache sizes, the PAC policy performs arbitrarily close to the optimal LFU algorithm. The PAC algorithm makes the replacement decisions based on the references collected during the preceding interval of fixed length that, for large caches, adds a negligible additional complexity when compared to the ordinary LRU policy