An Update-Risk Based Approach to TTL Estimation in Web Caching

Abstract

Web caching is an important technique for accelerating Web applications and reducing the load on the Web server and the network through local cache accesses. As in traditional data caching, Web caching poses the well-recognized problem of maintaining cache consistency. Web caching, however, has the advantage of delaying the refreshment of caches when the Web server updates the original data, i.e., Web caching tries to get better performance allowing tolerable inconsistency. This weak consistency requirement introduced the concept of time-to-live (TTL: the time during which the cached data item is expected to be valid) in the face of future updates. Subsequently, a number of methods have been invented to have the cache server estimate the TTL. However, the two well-known TTL estimation methods - the fixed TTL method and the heuristic method - do not allow intuitive understanding of the estimation processes and lack theoretical reasoning behind them, disallowing administrators from configuring the cache server by their intention. To mend these deficiencies, we propose the update-risk based TTL estimation method. This method uses a formal, yet intuitive, approach based on probabilistic analysis. In the proposed method, users provide the update risk as the probability that the original data will be updated within the estimated TTL. Then, based on our model, the cache server calculates the value of TTL using the update risk. The results of our experiments, performed using logs of a real cache server, show experimentally that the measured update risk closely matches that used to estimate TTL. Moreover, the notion of update risk is clear in its intention and semantics. These confirm the superiority of our method to conventional ones. We also show the impact of update risk on performance and consistency in order to help administrators select an appropriate value for update risk to obtain performance and consistency desired. In addition, we reassess the two aforementioned conventional methods in light of our method.