| |
position paper |
Oh, I believe in yesterday... The Beatles |
| Alex Rousskov rousskov@plains.NoDak.edu |
Valery Soloviev soloviev@plains.NoDak.edu |
Igor Tatarinov tatarino@prairie.NoDak.edu |
|---|
| Abstract |
|---|
|
This paper presents a novel approach to Web caching called Static Caching. The Static algorithm predicts today's traffic using yesterday's server logs. The set of cached documents is recalculated only once per day. The algorithm is simple, outperforms other caching policies, and has no CPU or memory overhead. Static Caching also enables a class of new optimization techniques that may further improve cache performance. We discuss one such technique called in-cache compression. |
Many Web caching techniques have been proposed to cope with the exponential growth of the Web traffic. Most proposed algorithms rely on traditional database and file systems approaches to caching. Only a few recent studies take the specifics of the Web traffic into account. Trace driven simulations show that simple caching algorithms, such as LRU or FIFO, that are successfully used in non-Web environments perform poorly for Web traffic. On the other hand, complex algorithms, such as LRU-k or LRU-MIN, may require a lot of CPU cycles and memory for searching and maintaining additional data structures.
There are two major performance metrics for a cache server: the Hit Ratio and Byte Hit Ratio. Our discussion assumes the Hit Ratio as a primary metric, though most results are applicable to the Byte Hit Ratio as well.
The other day, our research team was discussing a buffer management policy for a Multimedia Server that supports two classes of workload: continuous media (e.g., movies, video clips) and discrete documents (e.g., Web pages). It was clear to us that the buffer pool should be somehow divided between these two classes to provide enough memory for smooth delivery of videos and still have something left to cache Web pages. During the discussion, somebody noted that preserving cache consistency on the Web server is tricky because the users may frequently modify their pages. The latter assumption was immediately attacked by other participants; we soon agreed that, in most cases, Web pages remain unchanged for quite a long period of time. Then, one of us suggested that if page modifications are rare, why wouldn't we compress pages to reduce their size to fit more of them into a cache...
As it usually happens, the discussion led nowhere. However, in the background, we kept the idea that if the Web traffic were "stable", then one could apply various interesting algorithms like in-cache compression to improve cache performance. Later, we did some estimations using a few server logs. These estimations resulted in the algorithm presented in this paper.
Any caching algorithm has two major components:
Consider the Least Recently Used algorithm with a threshold (LRU-TH):The Least Frequently Used algorithm (LFU) works as follows:
- Prediction of the future traffic. All currently cached or requested documents are considered. The documents of the size greater than the threshold are then removed from the predicted set.
- Document value estimation. The value of a document is the time of the last access to this document. That is, the document accessed least recently is assumed to be least likely to be requested again.
- Prediction of the future traffic. The algorithm must maintain a history of accesses for requested documents (both cached and not cached). All documents recorded in the history log are considered.
- Document value estimation. The value of a document is the number of accesses to this document. That is, the document accessed least frequently is assumed to be least likely to be requested again.
More complex algorithms, such as the one used in the Squid software, can be described using the same approach. We note that the two components discussed here can be selected and optimized independently. We will use this fact in the derivation of our algorithm below.
We are looking for a simple algorithm that yields a high Hit Ratio and has low overhead. One way to achieve a high Hit Ratio is to optimize both components (prediction, and value estimation). How can we reliably predict the future Web traffic without waisting too much resources? By stating that the future will be pretty much like the past! This technique is highly effective in weather or stock market forecasts. Clearly, you may miss a blizzard or market crash, but these do not happen very often, do they? Besides, an error in predicting the Web traffic is, probably, not as bad as an unexpected weather or market storm. Thus, we propose to use the following technique for prediction of the future traffic:
The traffic today is expected to be the same as it was yesterday. That is, today's requests are expected to be exactly the same as the ones we observed yesterday.Of course, the prediction period can be extended or shortened to values other than 24 hours. For simplicity, unless stated otherwise, we assume 24 hour periods. Note that the optimal algorithm for traffic prediction is not known and can hardly be developed due to the random nature of the traffic. We will show, however, that our simple prediction works as good or even better than other, more complex ones.
What is left is the estimation of a document value. Again, we propose to use conventional wisdom in calculating the value of a document. Conventionally, a value of a product can be defined as a ratio between a gain or benefit from obtaining a product and product's price. Since our goal is a high Hit Ratio, we measure a gain from caching a document by the number of references to that document. The price is, of course, the cache memory consumed by the document (i.e., the document's size). Thus, we estimate the value of a document as:
#references
value = -----------
size
Putting all things together, we get the following definition of the Static algorithm:
At the beginning of the period (e.g., at 4:00 a.m.) the access log for the previous period is analyzed: For each unique URL in the log, we calculate the total number of accesses to get the value of the corresponding document. The URLs are then sorted in the descending order of document values. Finally, by scanning the sorted array, we select a set of top URLs that have accumulated size of their documents equal to the cache size. This final set of URLs is called a working set.The idea behind the Static algorithm is simple, so is the implementation. Note that access log files are maintained on practically all cache servers. Thus, we get historical information for free. We have to build a hash table of all URLs in a log file and then sort URLs by their values. This may be an expensive operation. However, since reorganization is performed once per day, it can be scheduled to the time when the server load is light or zero. Between reorganizations, we just need to keep a static URL lookup table as our working set. Other caching algorithms have to maintain a dynamic version of this lookup table and additional data structures (e.g., a priority queue in the case of LRU-k).The working set determines the names of documents we would like to have cached. Many of them are already cached (those that were "valuable" during the previous period). The rest may be either prefetched immediately or cached when the first corresponding request comes.
During the period, the working set of the Static algorithm always remains constant. If a user requests a document with a URL in the working set, then the document is served from the cache (or cached if it is not in the cache yet). Otherwise, the document is requested from the original server (or from a cooperating cache) and not cached.
If a document gets modified, its old content is deleted from the cache. The updated document is cached if the new content fits into the cache space available. Otherwise, the document is not cached.
Using trace driven simulations, we have compared the performance of the Static algorithm with the LRU-TH, LRU-k-TH, LRU-Size, LRU-Min, LFU, and other (more exotic) algorithms. The purpose of this paper is to present the idea of our approach and not to show a detailed analysis of the algorithms. All technical details are given in [TRS97].
We used traces from the primary (not proxy) Web servers of the following organizations:
Our experiments show that Static Caching outperforms other caching policies for reasonable cache sizes. Performance of all algorithms is practically the same for unreasonably large caches.
Among all algorithms studied, only complex policies demonstrated decent performance. Note that such algorithms as LRU-k-TH or LRU-Min may perform well, but they require significant CPU and memory resources to search and maintain their complex data structures. On the other hand, Static Caching outperforms the best algorithms and introduces practically no overhead.
The Static algorithm rarely rebuilds its working set. Thus, we can afford better (thus, more expensive) heuristics to predict the future traffic. We may have enough time even to consult with other caches if such cooperation is desirable. Cooperative static caches may negotiate their working sets. The negotiations may be useful to disseminate documents within a cache hierarchy (to fill holes and avoid duplication).
The working set of URLs is constant during a long period of time. Thus, we may afford expensive operations when inserting a document into the set. For example, we can compress some documents before they are inserted. A compressed document consumes less cache space effectively allow for more documents to be cached (thus, increasing the Hit Ratio). Decompression is a fast algorithm and, if pipelined, will not increase response time of a hit request.
Moreover, cooperative caches may reduce total response time and save network bandwidth if compressed files are transferred through the network. Ideally, we could send compressed files to a client as well, but this would require a compression-aware client. The latter can be easily implemented by using standard MIME types, but it will require all browsers to have decompression plugins.
Clearly, it does not make sense to compress documents with small compression ratio (e.g., jpeg pictures or MPEG movies). However, about 25% of the Web traffic consists of HTML and other "ASCII" documents. These documents have an average compression ratio of 60% (i.e., a compressed document consumes by the factor of three less space). An algorithm may consult a pre-computed table of average compression ratios to decide if the compression of a particular document type is beneficial.
In the future, if the portion of compressible documents remains high, then all text documents could be stored on the primary server in the compressed form. Then network bandwidth could be saved and response time decreased even without Static Caching. Our rough estimations show that this could save about 20% of the Internet bandwidth. Today, however, this would require all users to manually compress their documents which is unrealistic.
Static Caching may not be applicable to all situations. The effectiveness of the Static and other known algorithms on servers with large portion of dynamic content is questionable and requires a further analysis. Caching of dynamic content may not be feasible at all.
A possible way to deal with a frequently changing content and bursts of site popularity is to combine Static Caching with a dynamic algorithm like LRU-TH or LFU. In this symbiosis, the Static algorithm handles the "constant" portion of the traffic, while the other algorithm keeps track on the dynamic changes in access patterns. The cache buffer is divided between the two algorithms. A choice of the second algorithm, an optimal buffer division, and the soundness of the symbiosis idea itself have yet to be studied.
An application of Static Caching to caching proxies is also a promising direction. We plan to test our algorithm and, possibly, the symbiosis approach against proxy caches participating in the NLANR cache hierarchy.
We have presented Static Caching, a novel approach to caching on the Web. We showed that simple and natural heuristics may be very effective in predicting the future traffic and estimating the value of Web documents. We suggested that a significant portion of cacheable Web traffic is static, i.e. it can be predicted for a long period of time based on the past observations. Our trace-driven simulations support this fact. We demonstrated that Static Caching enables a class of new optimization techniques. We presented in-cache compression, a potent optimization that can further reduce request response time and save network bandwidth. Finally, we discussed directions for future enhancements of Static Caching.
See the paper above for a comprehensive list of references.
This work was supported, in part, by NSF grants OSR-95-53368 and RIA IRI-94-09845.
| http://www.cs.ndsu.nodak.edu/~rousskov/research/papers/wcw97/index.html |
|
$Id: index.html,v 1.9 1997/04/26 05:36:07 rousskov Exp rousskov $