next up previous
Next: 4 Alternatives for Managing Up: Directory Structures for Scalable Previous: 2 Why Collective Caches?


3 Harvest and CRISP

  In this section we compare the latency, hit ratios, and network overhead of functioning implementations of two collective Web caches in typical configurations. We also use simulation to predict the performance of larger configurations. The first system, Harvest [3], along with its successor Squid [20], is in widespread use. We proposed CRISP [10], the second system, as a simple alternative to Harvest. The CRISP prototype was implemented by modifying the last publicly available Harvest code base (version 1.4pl3).

Harvest and CRISP define two fundamental alternatives in the querying mechanism for locating objects in the collective cache. In Harvest, each server probes the cache by multicasting the requested URL to some or all of its neighbors. In contrast, CRISP maintains a global directory that is separated from the caching servers and probed with a unicast message exchange. Harvest avoids overheads to store and maintain a separate global directory while CRISP is easy to configure, generates minimal network traffic for cache probes, and can deliver as high hit ratios with smaller aggregate cache sizes. Harvest can continue to deliver some remote hits if a caching server fails, but CRISP reverts to isolated proxies if the global directory is unavailable.

This section compares three configurations of a Harvest cache using multicast-based probes with two CRISP cache configurations using directory queries. We first describe the Harvest and CRISP algorithms and prototypes in more detail, then describe our methodology and present our experimental results.

3.1 Harvest

Harvest and its successor Squid are hierarchical caches intended to be placed at network junctures along the paths from clients to Web servers. Each caching server is configured to interact with some subset of its peer servers as parents, children, or siblings. Children are typically ``lower'' (i.e., closer to the users) in the network than their parents, and siblings are usually children of a common immediate parent, but any DAG is legal. We consider only tree configurations, which are the intended Harvest topologies.

Each server satisfies misses to its local cache by multicasting a query for the requested document to all immediate parents and siblings, if any. The implementation uses a logical multicast (i.e., it repeats the unicast message to all the recipients), rather than an IP multicast (e.g., [6]). The requesting server then fetches the document from the first proxy that responds with a HIT. If there is no hit, it fetches the document through the first parent that responds with a MISS. If it has no parents, or no parents respond within a timeout interval, it fetches the object from the home Web site. Every fetched document is cached locally.

If the request is forwarded to a parent, the query process is repeated at the next level of the hierarchy. For example, in case of a miss, the parent multicasts the query to its siblings and waits for a response before forwarding the request up the hierarchy.


The key idea behind CRISP is to avoid multicast queries by maintaining a global map of the collective cache, accessible to each caching server with a single exchange. In [10] we outlined the simplest CRISP structure in which a central mapping service tracks the contents of the cooperative cache and coordinates some aspects of location, replacement, and update management. We argued that the well-known difficulties with this structure are less significant for Web caches because (1) the cost to store and query the map is small relative to the cost to store and transfer documents, (2) the query latency for a mapping server with tens of thousands of users is imperceptible to humans, and (3) failures of the map, which are unlikely, do not interrupt service but only degrade performance.

We modified the Harvest code base to implement a CRISP prototype with a single central mapping server. We refer to this prototype as CRISP/CSD (Central Synchronous Directory). A CRISP/CSD process can be configured to act as either a mapping server or as a caching server with a single parent (its mapping server). Modifications to the Harvest code included adding new mapping service message types to the Internet Cache Protocol (ICP) [19] used in Harvest, short-circuiting the query code path and object eviction code path to send messages to the mapping server, and adding a cache directory module for the mapping server. Local misses result in a query to the mapping server, which returns either a REDIRECT message with the address of a peer server that holds a copy of the object, or a MISS, which causes the requesting server to fetch the object directly from its home site on the Internet.

3.3 Methodology

We performed two sets of experiments to study several CRISP and Harvest configurations. For small configurations, containing up to five nodes, we played the first day (8/29) of the DEC traces into real caches running within a 100 Mb/s local area network (re-executing the whole trace would make these experiments prohibitively long). Trace-driven execution allowed us to compare hit ratios, generated network traffic, as well as latencies imposed by the caches. For large configurations, we performed trace-driven simulation using the full 25-day trace. In these experiments, we measured hit ratios and network traffic. All data were generated using tools from the Proxycizer [9] application suite.

For trace-driven execution, client simulators on a separate set of machines generate requests. Assignment of clients to caching servers is round-robin. 16 clients per proxy submit requests to their caching servers at the maximum rate. Misses are serviced by a HTTP 1.0 server, which responds to HTTP requests by generating a dummy document of correct size, determined from an external DB [17] file of records for the objects in the trace, hashed by URL and request type. With the hollow HTTP server, the cache configurations consume trace data at sustained rates between 60 and 140 references per second (725 max.). Clearly, fetch latencies for misses are artificially low, since they do not include realistic network delays or end-server latencies. However, because the network and end-server delays are independent of the cache architecture, the miss latencies we measure can be used for comparison between different caching platforms. We are exploring an extension to the hollow HTTP server to model observed object transfer delays (also available in the traces).

We explored five collective cache configurations:

The Shallow Harvest, Flat Harvest, and CRISP/CSD experiments accurately measure query latencies and hit latencies, although our results do not reflect network costs for geographically dispersed configurations.

3.4 Experimental Results and Analysis

Table 1: Comparison of Shallow Harvest, Flat Harvest, and CRISP/CSD performance in trace-driven execution.
  Shallow Harvest Flat Harvest CRISP/CSD
HIT 40.19% 28 msecs. 39.41% 147 msecs. 38.74% 256 msecs.
MISS 59.81% 1554 msecs. 60.59% 460 msecs. 61.26% 330 msecs.
Avg.   941 msecs.   337 msecs.   302 msecs.
    requests time (msecs.) requests time (msecs.) requests time (msecs.)
breakdown: number of total avg. of total number of total avg. of total number of total avg. of total
local HIT 185687 32.21% 17 0.57% 186174 32.29% 93 8.94% 186367 32.33% 127 13.60%
NEIGHBOR_HIT 44796 7.77% 59 0.49% 41048 7.12% 393 8.33% 36932 6.41% 908 19.30%
PARENT_HIT 1103 0.19% 634 0.13% - - - - - - - -
  w/ probe TIMEOUT 11 0.00% 2469 0.01% - - - - - - - -
MISS 310746 53.90% 1384 79.26% 321946 55.84% 277 45.95% 350006 60.71% 289 58.24%
  w/ probe TIMEOUT 34068 5.91% 3110 19.53% 27403 4.75% 2606 36.78% 3230 0.56% 4771 8.86%

Table 1 presents various data resulting from replaying the 8/29 trace through Shallow Harvest, Flat Harvest and CRISP/CSD. The results show comparable hit ratios in all three configurations. This is expected since all three configurations find objects cached on any node (both Harvest configurations probe every server while CRISP/CSD queries the global directory). Table 1 shows that both Harvest and CRISP configurations achieve a hit ratio of 38-40% (ideal for the original trace interleaving is 42% for a 400MB cache, 43% for 500MB). Shallow Harvest yields slightly higher hit ratio due to extra cache space of the parent (its aggregate cache space is 500MB vs. 400MB for Flat Harvest and CRISP).

Though they have similar hit ratios, latencies of the three configurations vary significantly. In Shallow Harvest, the parent is responsible for acting upon every request that misses in any child cache. Table 1 shows Shallow Harvest exhibiting a very high miss latency as a result of the bottleneck parent. In contrast, the parentless Flat Harvest configuration shows a marked improvement in miss latency, but it is still higher than CRISP/CSD. The reason for this worse miss latency in Harvest is due to multicast queries. When an object is not stored in the collective, the requesting cache waits for responses from all siblings and parents (bounded by a timeout) before forwarding a request to the Web server or to the next level in the hierarchy. Latencies increase to the timeout if any of these nodes fails, or if a query or response is dropped (both are UDP messages delivered on a best-effort basis). This limits the branching of the Harvest tree, as the probability of such a failure grows with the number of siblings and parents. We see evidence of this in Table 1, where 4.75-6% of all Harvest requests result in query timeouts, accounting for 20-37% of all time spent in the cache. In contrast, CRISP/CSD unicasts queries to the mapping server; dropped messages or timeouts are less likely, simply because fewer request/response exchanges are needed, and account for less than 5% of time spent.

On the other hand, Shallow Harvest yields much lower average hit latencies than Flat Harvest, which in turn has slightly lower hit latencies than CRISP/CSD. The reasons are twofold. First, the bottleneck parent in Shallow Harvest limits the overall request rate, reducing the load on child caches, which service a majority of hits. Second, if an object is stored on more than one target server, servers in both Shallow and Flat Harvest configurations will fetch the object from the target server that responds most quickly to a multicast query. CRISP/CSD does not have that flexibility. This could be addressed to a large extent by making each CRISP/CSD proxy piggyback load information on each exchange with the mapping server. Then, the mapping server may choose the best candidate from which to fetch the object.

Figure 5: Hit ratio of simulated Deep Harvest as mid-level parent size varies (trace filtered through ideal per-user caches). Aggregate child cache size is held constant at 32GB (1GB per child).

\epsfig {file=pics/deepharvestbyparentsize-filtered.eps, width=2.75in}\end{figure}

Figure 6: Hit ratio of simulated 32-way CRISP/CSD (trace filtered through ideal per-user caches).

\epsfig {file=pics/32waycrispbyparentsize-filtered.eps, width=2.75in}\end{figure}

A hierarchical cache with multicast probes such as Harvest faces basic tradeoffs between scalability and hit ratio. Shallow hierarchies (like Shallow or Flat Harvest considered above) can deliver near-ideal hit ratios because the entire cache is probed on every request. However, shallow hierarchies do not scale; the number of queries that must be carried by the network and handled by each participating cache increases linearly with the number of neighbors (siblings and parents), for a given reference trace. Another problem limiting the branching of the hierarchy is higher miss latency as discussed above.

Harvest can be made scalable by using a deeper hierarchy, but this yields lower hit ratios because ``cousins'' are not queried on a local miss. A deep hierarchy can guarantee to detect all possible hits only if there are common parents that are large enough to cache all documents held by their descendents. This increases the aggregate cache size requirements at least twofold. Moreover, deep hierarchies impose higher latency since fetches pass through multiple caches on their ways down the tree to the leaf proxies.

Figure 5 shows Deep-Harvest hit ratios for the full 25-day trace (with traces filtered through ideal per-user caches) as the cache sizes of the mid-level parents varies. The child proxies (32) each have 1GB of cache. Figure 6 shows hit ratios for the corresponding 32-way CRISP/CSD configuration with equivalent aggregate cache sizes. The figures show that a hierarchical Harvest cache can deliver excellent hit ratios if the parents have enough disk to store a copy of all documents cached by their children, but that the hit ratio drops rapidly for smaller parent servers. With very small parents, the hit ratio is comparable to an eight-way (32GB aggregate) partitioned cache (as described in Section 2.2). With all caches (both children and parents) set at 1GB, resulting in the aggregate cache size of 40 GB, the 40-node Deep Harvest delivered a 42% hit ratio out of an achievable 53%, even though the aggregate leaf-level cache size is large enough to store the entire 25-day trace. CRISP/CSD, on the other hand, gives a 49% hit ratio for only 32 caching servers with 32GB aggregate cache size and one mapping server.

Table 2: Number of messages sent (inter-cache and inter-net) by Deep Harvest and 32-way CRISP/CSD (in millions).
  Deep 32-way
  Harvest CRISP/CSD
Queries 95.50 9.81
Query responses 95.50 9.81
Object requests 18.06 9.81
Object responses 18.06 9.81

Table 3: Number of gigabytes sent (inter-cache and inter-net) by Deep Harvest and 32-way CRISP/CSD.
  Deep 32-way
  Harvest CRISP/CSD
Queries 5.34 0.55
Query responses 4.98 0.51
Object requests 0.80 0.44
Object responses 207.29 110.65

Table 2 and Table 3 detail network usage for the Deep Harvest and 32-way CRISP/CSD simulations with 96GB aggregate cache size. Client(browser)-proxy network usage is not included; both configurations perform identically in this regard. Because the DEC traces use an integer to represent a URL, we chose an arbitrary average URL size of 32 bytes to determine the sizes of queries and HTTP requests/response headers. The table shows that Deep Harvest sends nearly 10 times as many queries as 32-way CRISP/CSD (recall that all multicasts are ``logical'' multicasts; even if IP multicast were used, the responses to the multicast query would still come from separate nodes). In addition, the number of object requests (and amount of data transferred) due to object fetches increases almost twofold. The reason is that all misses (and some hits, e.g. to an ``uncle'' cache) in Deep Harvest must travel through more than one node, a parent and a child, before being returned to the requester.

3.5 Summary

A basic tradeoff between shallow Harvest configurations and CRISP is that of miss vs. hit latency. However, miss latency and generated network traffic limit the size of a shallow Harvest. For Harvest to scale, it must resort to deep configurations. Compared to deep Harvest configurations, significantly higher hit ratios are possible with lower cost, lower latency, and less network traffic using a CRISP configuration (CRISP/CSD) with a central mapping server for the same number of proxies and the same number of users. To achieve equivalent hit ratios while maintaining a scalable Harvest hierarchy would require more disk storage than the equivalent CRISP cache. Moreover, each document fetched by a leaf proxy from an external server must pass through predecessors at each level of the tree, with a synchronous multicast probe at each level. Though the use of a multicast query enables caches to detect the fastest responding server, it increases miss latency due to increased network and CPU usage. This limits the scalability and increases the cost of hierarchical caches with multicast probes.

CSD's low-cost queries and scalability to large numbers of caches come with some limitations, however. The synchronous query to a central directory requires that all caching servers have an acceptable query latency to the mapping server, ideally below the threshold of human perception. This may limit geographic scalability. Second, a failure of the mapping server can temporarily degrade performance to that of isolated proxy caches. These issues are addressed in Section 4.

next up previous
Next: 4 Alternatives for Managing Up: Directory Structures for Scalable Previous: 2 Why Collective Caches?
Syam Gadde