Figure 2:
Hits due exclusively to sharing
Figure 3:
Hit ratios for per-client caches
We first present results from trace-driven simulations to show the degree of sharing and temporal locality inherent in the recorded Web access traces. Our intent is to demonstrate the benefits of building large shared caches. For these experiments the caches used LRU replacement; alternative replacement policies tuned for Web access patterns would likely yield higher hit ratios [11]. CRISP caches could support alternative global replacement policies at the level of the mapping service.
The behavior of a shared cache is affected by the degree of temporal locality in the reference streams from individual clients. Temporal locality varies in the different traces, presumably because the references were filtered through private browser caches or lower-level proxies to varying degrees in the different user communities. Figure 3 shows the hit ratios yielded for each of the traces by a cache that is statically partitioned among the clients, i.e., by a cache of aggregate size X shared by N clients, each client having a private cache of size X/N. The rightmost group of bars shows the theoretical maximum hit ratio of per-client caches for each of the four traces; these are the hit ratios that would result from a partitioned cache of infinite size. This shows the degree of temporal locality inherent in the traces.
To illustrate the benefits of a shared cache, we first normalized the traces by filtering them through infinite per-client caches, then played the filtered traces into shared caches of various sizes. Figure 2 shows the resulting hit ratios for each of the four traces. These results are optimistic in the sense that the shared cache is isolated from the effects of temporal locality, i.e., the replacement policy is not biased by objects that were kept hot because of repeated references from a single client. However, the shared cache hit ratios reported in Figure 2 are conservative in three respects. First, all hits reported are due exclusively to sharing of objects among different clients. Second, a large, unified shared cache would likely yield additional temporal hits in practice, since per-client caches are not infinite, and the most active clients can receive a larger portion of the shared cache at any given time. Third, to the extent that the traces are filtered through lower-level proxies, the hit ratios in Figure 2 do not reflect hits resulting from sharing among clients using the same lower-level proxy.
We make the following observations:
The DEC trace yielded a 37% hit ratio due exclusively to sharing, illustrating the benefit of a shared cache in this instance. In fact, hits on shared objects accounted for around 60% of all hits in this trace, giving strong support for cooperative caching of Internet objects.
The shared hit ratios reported in Figure 2 do not show the effect of duplicate objects in CRISP caches. In practice, a CRISP cache yields slightly lower hit ratios than a central shared cache of the same size. This is because objects shared among clients bound to different proxy servers are duplicated in both proxies in our current prototype, reducing the effective size of the CRISP cache. This is the cost of the CRISP architecture's ability to support larger shared caches serving larger user communities than would be possible with a single central proxy. This cost could be reduced by more aggressive replacement of duplicates, under the control of mapping server, or perhaps by careful assignment of clients to proxy servers in the distributed CRISP cache.
