Consistency analysis and evaluation of TTL-based Internet caches

Abstract

Consistency algorithms have been proposed for a wide range of applications that include distributed shared memories (DSM), distributed file systems, and databases. Fundamental definitions and operational constraints that are specific for each system do not necessarily translate well to Internet caches. A Web object is consistent if it is identical to the master document at the origin server, at the time it is served to users, therefore cached objects become stale immediately after the master is modified. Stale cache copies remain served to users until the cache is refreshed, subject to the network transmit delays. However, the performance of Internet consistency algorithms is evaluated through the corresponding cache hit rate and network traffic load that do not inform on the service of stale data, and are therefore inadequate, as outlined in numerous studies. To date, neither an analytical framework nor a suitable measure are available to model the service of stale data to users. In this paper we seek to remedy this state of affairs by formalizing both a framework and the novel hit* rate consistency measure, which captures non-stale downloads from the cache. To demonstrate this new methodology, we analyze and evaluate the consistency performance of a well studied TTL algorithm, under both zero and non-zero download latency. We conclude that data consistency can be significantly degraded even when a high hit rate is achieved, by calculating the incurred hit and hit* rates. The proposed procedure can be used to evaluate additional TTL and other (e.g., polling and invalidation) Web consistency protocols, as well as those retained by other applications (e.g., virtual shared memories).