Intelligent web caching using document life histories: A comparison with existing cache management techniques

Mike Reddy & Graham P. Fletcher
{mreddy|gfletche}@glam.ac.uk

J228, School of Computing,
University of Glamorgan, Pontypridd,
Mid Glamorgan. CF37 1DL

Tel: +44 (0) 1443 482240
Fax: +44 (0) 1443 482715

Keywords

Cache Server Performance/Metrics, Intelligent Web Caching, Document Life Histories

Abstract

Hierarchical storage of web pages in proxy server and client browser caches introduce coherence problems, which require cache management techniques which are both accurate and computationally efficient. We suggest that current approaches, such as the most common Least Recently Used (LRU) technique, are inadequate for future network loads as they do not incorporate the dynamics of document selection and modification. We propose the use of an intelligent, adaptive cache management technique to overcome the coherence problem by using document life histories to optimise cache performance. This work addresses the use of damped exponential smoothing to model accurately the frequency of file requests and modifications, in order to predict the future value of cached files. Finally, we make a mathematical analysis of LRU in comparison with our technique, showing how and why the use of document life histories is a more effective cache management technique without imposing major computational overheads.

1 Introduction

Validation is currently considered the most appropriate caching technique for the web; the alternatives of call-back and prefetching are not currently considered suitable [Reddy & Fletcher (1998)]. Several simple caching mechanisms have been specifically proposed for web documents [Glassman (1994); Smith (1994)]. However, latency in proxy servers and client browsers often results in stale documents being served as current [Holtman & Kaphan (1995)]. The difficulty is that of finding a method for determining the 'value' of a document, and whether it should be cached, without dramatically increasing computation and communication overheads.

Various adaptive, or 'semi-intelligent' techniques have been proposed, which attempt to optimise cache management. These fall into two categories: those that model the `interest' in a document and/or network performance, and those that model its likely lifecycle. Bowman et al (1995) suggest that better expiry times might be calculated from the last validation date. Dingle & Partl (1996) have proposed an arbitrary staleness threshold, but this is unlikely to reflect actual file modifications. Furthermore, Dingle & Partl (1996) have suggested that the number of requests could measure the real interest in a document. Pitkow and Recker (1996) have likened caching techniques to models of human memory, concluding that a recency is more useful than frequency for predicting the likelihood of future requests.

Document size and temporal locality have been identified as important considerations for dynamic caching strategies [Abrams et al (1995)]. Bolot & Hoschka (1996) have, therefore, proposed a weighting metric, where the first term is the cost of retrieval against useful lifetime and the second term is the temporal locality:

where is the time since the last reference, is the size of the document and is the retrieval time. Given that is proportional to file size, the most significant factor in the formula is . This might encourage the indiscriminate caching of large files, which is counter productive as it has been recognised that small web documents are accessed more often on the web [Cunha et al (1995)]. Neither is it likely that would be a useful metric without some consideration of actual network performance. Furthermore, this technique does not model the life expectancy or request rate of a document. This compares with the simple Least Recently Used (LRU) approach, where:

In fact, few approaches can outperform LRU, as it is both computationally inexpensive and adapts quickly to dynamic situations. However, none of these approaches has addressed all three stages of cache management: "Which files to cache?", "Which files to validate?" and "Which files to remove?" [Reddy & Fletcher (1997)].

This paper proposes a mechanism for intelligent adaptive cache management, which attempts to improve cache performance by modelling document life histories to determine their usefulness. This technique uses damped exponential smoothing to ensure an accurate, yet responsive model of document dynamics. An empirical evaluation of this approach is made, in comparison with LRU. Finally, a mathematical analysis of both techniques is made which shows their theoretical underpinning, how they work and why LRU may not be the optimal solution to web cache management.

2 Intelligent adaptive web cache management

Few of the approaches described above are able to use effectively the information available to them on document changes, or the frequency and recency of requests. Rather they make arbitrary decisions as to the interest in, or life expectancy of documents which are not based upon the actual life history of documents. We propose the monitoring of client behaviour to provide a statistically determined weighting system for cache management, based upon document life histories. Furthermore, this approach is achievable with few, if any, changes in current protocols.

Two significant factors in determining the usefulness or 'interest' in a document are the frequency and recency of requests. LRU effectively attempts to predict the likely time between document requests, but only considers the most recent transaction. The authors suggest that the most significant factor in effective cache management is the overall frequency of use, or inversely, the predicted time until the next request for a specific document. This equates to the best use of cache space by calculating the relative value of documents, irrespective of file size. The weighting metric for the respective value of a file is the likely frequency of document requests, which is inversely proportional to the mean time to the next request:

An estimate of is provided by applying exponential smoothing techniques to the previous value, (which is a measure of the frequency of previous requests), and which is the time since the last request (which is a measure of the recency):

The initial weighting for a file is equivalent to LRU, which is always a simple measure of the most recent transaction; i.e. . The value of the damping quotient, , determines the relative importance of the frequency and recency for predicting future behaviour. Therefore, the value of will have a direct effect upon performance of the dynamic caching system. Gardner (1985) suggests a typical value of .

2.1 An empirical evaluation of LRU and exponential smoothing (Exp1)

Empirical results were obtained by use of the WebAgent simulator, which provides an environment reproducing file requests (modelling trends in user interest in documents), download delays (seasonal and catastrophic changes in network performance) and document modifications [Reddy & Fletcher (1997)]. The authors believe that experimental work is necessary because theoretical models are inadequate for understanding real internet traffic. We need quantifiable, configurable experiments with large caches, showing realistic network performance and document dynamics. As access to web server log files is often a difficult issue for privacy, security, or logistical reasons, simulation is a necessary tool. This has an added benefit of repeatability, which allows different caching techniques to be measured and compared accurately.

Fig. 1 shows a comparison between LRU and the intelligent cache mechanism, Exp1, for predicting the frequency of document requests. From these results it can be seen that the use of a damped adaptive measurement of consistently outperforms the LRU algorithm. The intelligent algorithm reacted quickly to changing network performance, where LRU, in contrast, often over-reacted to sudden change, while oscillating during relatively stable periods. In simulation, this resulted in a 5-10% improvement in the perceived retrieval rate for document delivery (see Fig. 2).

Figure 1 - Comparison of LRU & Exp1 estimates against the theoretical ideal

From experience of various simulations, we suggest that optimal performance occurs with a damping quotient somewhere in the region of . Too high a value of will over-emphasise the recency of documents, which results in oscillation similar to that shown by LRU. Too low, and Exp1 would not react quickly enough to changing circumstances. Future work will investigate the identification, and possible dynamic calculation of to optimise cache performance.

Figure 2 - Comparison of the Exp1 and LRU perceived retrieval rates.

3 A mathematical analysis of LRU and Exp1

The modelling of the likely rate of requests for a document, should follow a Poisson Distribution. However, the time between requests in a Poisson series is, in fact, an Exponential Distribution where:

where is the Poisson variable, which is the mean number of requests in a given period [Kinney (1997)]. Given that requests are independent of each other, they may occur simultaneously and their probability is time independent; i.e. the probability P(X) of receiving a request in time t is not related to the time we have already waited, s:

This suggests a paradox in the approach which LRU uses, as its only method for predicting the 'interest' in a document is from the time since the previous request. However, if we consider the General Exponential Distribution we are able to estimate the likelihood of a request, based upon the time since the last request, . The general exponential probability density function is:

for which the previous distribution function is a special case, where . For this case, the mean value for the general exponential distribution is:

where the first term, , is the time since the last request and the second term is the standard deviation, , as:

Given that LRU only makes use of only one measurement, there is no value for . So, the mean value for the expected time to the next request is:

This gives us, for the first time, an understanding of why LRU makes such a good estimate of the probability of future requests for documents. However, it is also clear that it is not optimal. Consideration of only one measurement makes the implicit assumption that the actual time between requests is unvarying. This explains why, in section 2.1, the LRU estimation of the time between requests can oscillate wildly.

In fact, we must remember that our use of the general case is an approximation only. The actual distribution of requests should be `memoryless' (with the possible exception for when the requests are made by a single user where the likelihood or a repeat request may clearly be connected in some qualitative way). Whether or not the probability distribution is truly time independent, the authors suggest that exponential smoothing is a more accurate method for estimating the mean time to next request. Whereas LRU relies solely upon the most recent transaction, Exp1 makes implicit use of the previous history of document requests.

4 Conclusions and future work

In this paper, the case has been made for intelligent modelling of the usefulness of web objects by evaluation of document life histories. We propose such a system, which shows an improvement in the handling of web objects over existing techniques, such as LRU. Estimates of document request rates, can significantly improve cache performance. Furthermore, the dynamic nature of our approach, should provide ever improving performance, and a system which can adapt itself to variable network performance. Finally, we have examined the mathematical underpinnings of both LRU and Exp1, and determined that while the former is computationally inexpensive, it is not the optimal solution for intelligent, adaptive cache management.

Future work will include an investigation into the dynamic calculation of to optimise cache performance. It is also possible that exponential smoothing might be applied to predicting file modification times to estimate document 'shelf life'. Further improvements have been identified for the WebAgent simulator, which will serve to improve the accuracy of the simulation. Finally, an intelligent dynamic caching agent should be created for an existing web browser, to evaluate performance of an actual user on a real network.

5 References

Abrams M. et al (1995), "Caching proxies: limitations and potentials," Proceedings of the Fourth World Wide Web Conference, Elsevier, Amsterdam, 1995, pp 119-133.

Bolot J-C. & Hoschka P. (1996), "Performance engineering of the World Wide Web: Application to dimensioning and cache design," Computer Networks and ISDN Systems, 1996, Vol 28, No 7-11, pp 1397-1405.

Bowman C.M. et al (1995), "The HARVEST information discovery and access system," Computer Networks and ISDN Systems, 1995, Vol 28, No 1-2, pp 119-125.

Cunha C. et al (1995), "Characteristics of WWW client based traces," TR-95-010, Boston University, April 1995.

Dingle A. & Partl T. (1996), "Web cache coherence," Computer Networks and ISDN Systems, 1996, Vol 28, No 7-11, pp 907-920.

Gardner E.S. Jr (1985), "Exponential smoothing: the state of the art," Journal of Forecasting, Vol 4, No 4, 1985, pp 1-28.

Glassman S. (1994), "A caching relay for the World Wide Web," Computer Networks and ISDN Systems, 1994, Vol 27, No 2, 1994, pp 165-173.

Holtman K. & Kaphan S. (1995), "Problems with the expires header," 1995, Unpublished web page, <http://www.amazon.com/expires-report.html>.

Kinney J.J. (1997), "Probability: An introduction with statistical applications," Wiley Press, Chichester, 1997, pp 198-199.

Pitkow J.E. & Recker M.M. (1996), "A simple yet robust caching algorithm-based on dynamic access patterns", Proceedings of the Second World-Wide Web Conference, Elsevier, Amsterdam, 1994.

Reddy M. & Fletcher G.P. (1997), "Intelligent Control of Dynamic Caching Strategies for Web Servers and Clients," Proceedings of WebNet `97, AACE Press, Charlottesville, 1997, pp 440-446.

Reddy M. & Fletcher G.P. (1998), "Intelligent Control of Dynamic Caching Strategies for Web Servers and Clients," IEEE Internet Computing, IEEE Computer Society Press, January 1998, pp 78-81.

Smith N. (1994), "What can archives offer the world wide web," Proceedings of the First International World Wide Web Conference, Elsevier, Amsterdam, 1994.