next up previous
Next: 1 Introduction

Directory Structures for Scalable Internet Caches

Syam Gadde, Jeff Chase
Dept. of Computer Science
Duke University
Durham NC, 27708
- Michael Rabinovich
AT&T Labs - Research
108 Park Avenue
Florham Park, NJ 07932


Use of Internet caches is a cheap and effective way to improve performance for all Internet users. Distributed caches offer the potential to serve larger user communities and to deliver higher hit ratios on shared Web documents. The key to building effective distributed caches is a directory structure that allows individual caching servers to locate objects cached at neighboring sites, combining them into a logically unified collective cache.

This paper uses Web traces to evaluate a range of alternatives for managing directories in distributed Internet caches. We use trace-driven executions and simulations of prototype caches to compare multicast-based queries of local maps (Harvest) with unicast queries of a global map (CRISP). We then use properties of the traces to predict performance of CRISP variants in which the global map is partitioned or replicated. Finally, we propose a novel lazy CRISP structure based on weakly consistent replication of the most valuable subset of the global map. We show that this scheme combines the best aspects of several distributed cache structures, while maintaining a near-ideal hit ratio.

next up previous
Next: 1 Introduction
Syam Gadde