ERCIM News No.25 - April 1996 - FORTH

Caching, Prefetching and Coherence in the World Wide Web

by Evangelos P. Markatos and Catherine E. Chronaki

Without caching, the World Wide Web will soon become a victim of its own success. Experience suggests that Web servers become inaccessible as soon as they become popular. As a result, popular Web servers appear slow, and users become frustrated with their service. A scalable and effective way to improve Web performance is the sophisticated use of caching and prefetching.

If a document is cached the first time it is accessed by a client, it will be retrieved more efficiently on subsequent accesses by the same client or by nearby clients. The use of prefetching improves performance even further, by reducing the server's load and the client's latency even from the first time a Web document is accessed.

Although caching and prefetching are key ideas in the success of the Web, a brute force approach to them will lead to disastrous performance. Simply, a Web server can neither cache, nor prefetch the entire Web. At ICS-FORTH we are currently developing sophisticated caching and prefetching policies, which improve performance without saturating the Internet with useless traffic.

Throughout the Web, we envision a number of Web Brokers. A Web Broker is a mediator between the client and the Web content. Web Brokers provide storage, processing, and communication capacity which are used to offload the client, the server and the network from unnecessary network transfers. Instead of asking the relevant servers for the required documents, clients request documents from a Web Broker, which in turn may request the documents from other Web Brokers, or from the relevant servers.

To reduce network traffic, Web Brokers cache documents that they fetch on behalf of their clients. They also keep extensive indices of other Web Brokers that cache documents so that they know approximately which Brokers cache which varieties of documents. Cached documents are kept in a multi-level storage hierarchy that consists of main memory, magnetic disks, and even tapes. Small and popular documents should be kept at the upper levels of the hierarchy to optimize for low latency. Large and less frequently accessed documents should be kept at the lower levels of the hierarchy in such a way as to optimize for bandwidth.

To reduce network traffic even further, Web Brokers calculate document access patterns in order to define clusters of documents that are probably requested together. For example, once a client requests a page from a book, it will probably request more pages and pictures from the same book. Clustering pages into chapters, and chapters into books, will allow Web Brokers to prefetch large amounts of useful information with one request. Based on the calculated access patterns, Web Brokers prefetch popular documents. For example, Web Brokers may prefetch magazines, newspapers, etc., so that clients will find it there when they need it. Based on its clients reading habits, a Web Broker will soon 'learn' which newspapers, magazines, etc. to prefetch.

To make sure that their data are not stale, Web Brokers take care of the consistency of their cached documents. Periodically updated documents, like newspapers are regularly fetched in the cache. Other documents are kept up-to-date using a combination of update-based and invalidate-based protocols. Finally, there may even be some documents where a small out-of-date information can be tolerated in the interests of reduced network traffic.

We are currently evaluating various caching and prefetching policies to be used by Web Brokers. For our evaluations, we use trace-driven simulation based on real access traces of Web servers and Web clients. At the same time, we investigate alternative schemes of integrating our results into Web servers.

Please contact:
Evangelos P. Markatos - ICS-FORTH
Tel. +30 81 391655

return to the contents page