To test this hypothesis we added the Alex cache consistency scheme to the simulator used by Worrell. Prior to his evaluation of consistency protocols, he had gathered several months of data on the history of 4000 URL's located around the Web. This data recorded the average age of each URL as well as its variance. He used this data to change the URL's over time, and he drove the simulator through a random stream of URL references.
His simulator was also used to test the effects of a hierarchical cache on cache consistency performance; in order to isolate the effects of the cache consistency policy from the effects of stacking caches in a hierarchy, we remodeled the hierarchy of his caches in order to simulate a single cache. We therefore could not record as Worrell could; instead we simply recorded the number of bytes used by a cache in maintaining consistency, including invalidation messages, stale-data checks, and transferring files.
Worrell did not update objects the instant they became invalidated, but instead simply marked them as invalid. Only when a client actually requested an invalidated object was it transferred from the primary server. This increases latency but decreases bandwidth.
Figure: Comparison of bandwidth used by invalidation protocol, Alex cache consistency scheme, and Time-To-Live fields. The cache is pre-loaded with valid copies of all the files held in the primary server. Note the use of a log-scale to display the bandwidth with higher accuracy. Note also, however, the discontinuity on the far right of (a); this is an artifact of the y-axis log-scale, since a value of 0 on the y-axis is infinitely far away.
Figure: Comparison of the hit rates of the Alex scheme to the hit rates of the TTL scheme. Note that the stale hit rate rises as time-to-live fields become longer and as the Alex age threshold rises. The invalidation protocol always results in a 0% stale hit rate.
The results of simulating the Alex protocol against the TTL protocol are shown in Figure and Figure . These graphs clearly show the tradeoffs involved in selecting a cache consistency protocol: invalidation consumes the optimal amount of bandwidth needed to insure no stale cache hits, but if one is willing to accept a certain number of stale hits it is possible to reduce the bandwidth requirements.
By comparing the two Figures one notes that for a given stale cache hit percentage, the TTL scheme uses nearly half the bandwidth of the Alex scheme. We had expected the Alex scheme to be more efficient than the TTL scheme; we address this discrepancy later in this chapter.
These results are comparable to those produced by Worrell, but we felt it was possible to improve the performance of TTL and Alex. We explored the possibility of not automatically deleting an object from the cache when it was found to be invalid, but rather checking first to make sure it is really invalid. This improves performance because the Alex and TTL schemes frequently invalidate and replace objects that are not yet actually stale.
Figure: Comparison of bandwidth used by invalidation protocol, Alex scheme, and TTL scheme. Files are only transmitted when they are truly stale. Note that TTL and Alex now use less bandwidth than the Invalidation Protocol.
Figure: Comparison of cache hit rates for Alex and TTL. Notice the dramatic improvement on cache hits and misses, since files are not deleted from the cache unless they are truly stale. Notice also that the stale cache hit rate is unaffected by the change.
The effect of this change on network traffic is shown in Figure , and the effect of this change on cache hits and misses is shown in Figure . TTL still creates less network traffic than Alex, but the two are both more competitive relative to the invalidation protocol. Nevertheless, choosing a TTL of 5000 for example only saves 30% of the invalidation protocol's bandwidth but results in a 17% stale cache hit rate. This might not be acceptable for the moderate bandwidth savings.