Benefits of Cache Sharing

  Recent studies [8,23,14] have shown that under infinite cache capacity, Web cache hit ratio appears to grow logarithmically with the size of the user population served by the cache. Clearly, the overlap of requests from different users reduces the number of cold misses, often a significant portion of cache misses, since both first-time reference to documents and document modifications contribute to them.

  

Figure 1: Cache hit ratios under different cooperative caching schemes. Results on byte hit ratios are similar. Note that the x-axis is in log scale.

To examine the benefits of cache sharing under finite cache sizes, we simulate the following schemes using the traces listed in the previous section:

• No Cache Sharing: proxies do not collaborate to serve each other's cache misses;
• Simple Cache Sharing: proxies serve each other's cache misses. Once a proxy fetches a document from another proxy, it caches the document locally. Proxies do not coordinate cache replacements. This is the sharing implemented by the ICP protocol.
• Single-Copy Cache Sharing: proxies serve each other's cache misses, but a proxy does not cache documents fetched from another proxy. Rather, the other proxy marks the document as most-recently-accessed, and increases its caching priority. Compared with simple cache sharing, this scheme eliminates the storage of duplicate copies and increases the utilization of available cache space.
• Global Cache: proxies share cache contents and coordinate replacement so that they appear as one unified cache with global LRU replacement to the users. This is the fully coordinated form of cooperative caching. We simulate the scheme by assuming that all requests go to one cache whose size is the sum of all proxy cache sizes.

We examine these schemes in order to answer two questions: whether simple cache sharing significantly reduces traffic to Web servers, and whether the more tightly coordinating schemes lead to a significantly higher hit ratio.

Figure 1 shows the hit ratios under the different schemes considered when the cache size is set to 0.5%, 5%, 10%, and 20% of the size of the ``infinite cache size'' (the minimum cache size needed to completely avoid replacements) for each trace. The results on byte hit ratios are very similar, and we omit them due to space constraints.

Looking at Figure 1, we see that, first, all cache sharing schemes significantly improve the hit ratio over no cache sharing. The results amply confirm the benefit of cache sharing even with fairly small caches.

Second, the hit ratio under single-copy cache sharing and simple cache sharing are generally the same or even higher than the hit ratio under global cache. We believe the reason is that global LRU sometimes performs less well than group-wise LRU. In particular, in the global cache setting a burst of rapid successive requests from one user might disturb the working set of many users. In single-copy or simple cache sharing, each cache is dedicated to a particular user group, and traffic from each group competes for a separate cache space. Hence, the disruption is contained within a particular group.

Third, when comparing single-copy cache sharing with simple cache sharing, we see that the waste of space has only a minor effect. The reason is that a somewhat smaller effective cache does not make a significant difference in the hit ratio. To demonstrate this, we also run the simulation with a global cache 10% smaller than the original. As can be seen from Figure 1, the difference is very small.

Thus, despite its simplicity, the ICP-style simple cache sharing reaps most of the benefits of more elaborate cooperative caching. Simple cache-sharing does not perform any load balancing by moving content from busy caches to less busy ones, and does not conserve space by keeping only one copy of each document. However, if the resource planning for each proxy is done properly, there is no need to perform load-balancing and to incur the overhead of more tightly coordinating schemes.

Finally, note that the results are obtained under the LRU replacement algorithm as explained in Section 2. Different replacement algorithms [8] may give different results. Also, separate simulations have confirmed that in case of severe load imbalance, the global cache will have a better cache hit ratio, and therefore it is important to allocate cache size of each proxy to be proportional to its user population size and anticipated use.