Proxy cache algorithms: Design, implementation, and performance

Caching at proxy servers is one of the ways to reduce the response time per ceived by World Wide Web users. Cache replacement algorithms play a central rolfe in the response time reduction by selecting a subset of documents fo r caching, so that a given performance metric is maximized. At the same tim e, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate gua rantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-W3-U, which integrates both cache replac ement and consistency algorithms. The LNC-R-W3-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. C onsequently, the documents that took a long time to fetch are preferentiall y kept in the cache. The LNC-R-W3-U algorithm also considers in the evictio n consideration the validation rate of each document, as provided by the ca che consistency component of LNC-R-W3-U. Consequently, documents that are i nfrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-d riven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance.