In geographically dispersed CRISP caches, the network latency to query any shared mapping server will be unacceptable to some proxies, regardless of where that mapping server resides in the global cache. We have implemented CRISP variants that asynchronously replicate the global directory. Replicas can be placed closer to a group of caching servers, or even colocated with each caching server. In the latter case queries are satisfied by a simple local table lookup, removing a network exchange from the critical path of cache misses. In a sense, the replicated directory structure is the opposite of the hierarchical ICP caches: rather than multicasting queries and generating no updates to the map, this structure multicasts the updates and generates local queries.
The key advantage of multicasting updates over multicasting queries is that the updates to the map can be propagated asynchronously, whereas queries are by their nature synchronous. Updates to CRISP directory replicas are propagated through the mapping service using an asynchronous protocol. Note that the replicas may be weakly coherent, since inconsistencies do not compromise correctness of the cache, only its performance. In particular, false hits in the directory are detected on access to the caching server, while false misses simply cause an extra Web server access for an object that could have been fetched from the cache.
Asynchronous propagation of directory updates enables the collective CRISP cache to cover larger network distances without affecting miss latency. For example, proxies may batch updates to the map and propagate them with periodic anti-entropy exchanges using an efficient stream protocol [15]. Our current prototype batches updates into TCP streams sent to a central distribution node at (configurable) periodic intervals, in order to amortize network connection costs over a group of updates. On typical traces, propagation intervals of up to an hour cause hit ratios to drop by at most 5%.
One problem with this structure is that map replicas increase the storage requirements for the cache. If the size of the map becomes cumbersome, a map compression scheme such as Summary Cache [6] may be used, although our prototype does not support this.