Caching and Clustering Support for Scalable Web Services

We conduct several projects on Web caching, server clustering, and distributed system support to improve scalability and reliability of Web services.

• Neptune: Scalable Replica Management and Programming Support for Cluster-based Network Services. Neptune is a software system which allows application developers to easily deploy and replicate partitionable network services on a cluster of machines. Neptune provides location-transparent services to application front-ends by dynamically selecting proper storage nodes based on their workload, availability, and consistency requirements. Neptune also provides multiple levels of replica consistency to exploit application characteristics and performance tradeoffs. Using a version control scheme, Neptune can ensure that each client updates and obtains information in an incremental order with respect to one data partition. The paper that will appear in USITS'01 describes the programming model, replica management, and availability control in Neptune and illustrates its performance using three Internet applications.

• Service Differentiation for Cluster-based Network Servers. Service differentiation that provides prioritized service qualities to multiple classes of client requests can effectively utilize available server resources. This project studies how demand-driven service differentiation with admission control can be supported in cluster-based network services. Our objective is to provide better services to high priority request classes without over-sacrificing low priority classes. To achieve this objective, we propose a dynamic scheduling scheme that adapts to varying request resource demands and periodically repartitions servers. This scheme also employs priority-based admission control to drop excessive user requests and achieve soft performance guarantees. For each scheduling period, our scheme monitors system status and uses a queuing model to approximate server behaviors and guide resource allocation. Our experiments show that the proposed techniques achieves demand-driven service differentiation while maximizing resource utilization and that it can substantially outperform static server partitioning.

• Cachuma: Cache Invalidation and Precomputing for Dynamic Web Pages. Caching dynamic pages at a server site is beneficial in reducing server resource demands and it also helps dynamic page caching at proxy sites. Previous work has used fine-grain dependence graphs among individual dynamic pages and underlying data sets to enforce result consistency. Such an approach can be cumbersome or inefficient in dealing with an arbitrarily large number of dynamic pages. We study techniques for partitioning dynamic pages into classes based on URL patterns. Our scheme allows an application to specify page identification and data dependence for a class of dynamic pages and invalidate them collectively. To make this scheme time-efficient with small space requirement, lazy invalidation is used to minimize slow disk accesses when identifications of dynamic pages are stored in memory with a digest format. Selective precomputing is further proposed to regenerate stale pages and smoothen load peaks. A data structure is developed for efficient URL class searching during lazy or eager invalidation. We also implemented caching software called Cachuma which integrates the above techniques, runs in tandem with standard Web servers, and allows Web sites to add dynamic page caching capability with minimal changes. Our experimental results show that the proposed techniques can efficiently handle class-based page invalidation and are effective in reducing server response times for tested applications.

• Dynamic Content Caching Protocol (DCCP) Our recent work addresses partial result caching for Web servers. We classify locality in dynamic web content into three kinds: identical requests, equivalent requests, and partially equivalent requests. Equivalent requests are not identical to previous requests but result in generation of identical dynamic content. The documents generated for partially equivalent requests are not identical but can be used as temporary place holders for each other while the real document is being generated. We present a new protocol, which we refer to as Dynamic Content Caching Protocol (DCCP), to allow individual content generating applications to exploit query semantics and specify how their results should be cached and/or delivered. We illustrate the usefulness of DCCP for several applications and evaluate its effectiveness using traces from the Alexandria Digital Library and NASA Kennedy Center as case studies.

• Clustering support for Intensive Dynamic Content Processing. This work studies a two-level scheduling framework with a master/slave architecture for clustering Web servers . Such an architecture has advantages in dynamic resource recruitment, fail-over management and it can also improve server performance compared to a flat architecture. The key methods we propose to make this architecture efficient are the separation of static and dynamic content processing, low overhead remote execution, and reservation-based scheduling which considers both I/O and CPU utilization. Our study provides a comparison of several scheduling approaches using experimental evaluation and analytic modeling and the results show that proper optimization in resource management can lead to over 65% performance improvement for a fixed number of nodes, and can achieve more substantial improvement when considering idle resource recruitment.

• Cooperative caching. This work studies new methods for improving the average response time of client requests by cooperatively caching the results of requests for dynamic content on a distributed Web server. The work is motivated by our recent study of access logs from the Alexandria Digital Library Web server at UCSB, which demonstrates that approximately a 30 percent decrease in average response time could be achieved by caching dynamically generated content. We have implemented a distributed Web server called Swala which supports cooperative caching of dynamic requests. We have used a replicated global cache directory and a two-level metadata consistency protocol to maximize scalability and minimize overhead.

Papers:

• Kai Shen, Tao Yang, Lingkun Chu, JoAnne L. Holliday, Doug Kuschner, Huican Zhu, Neptune: Scalable Replica Management and Programming Support for Cluster-based Network Services. To appear in the 3rd USENIX Symposium on Internet Technologies and Systems (USITS '01) March 26-28, 2001.

• Huican Zhu, Hong Tang and Tao Yang, Demand-driven Service Differentiation for Cluster-based Network Servers. Technical Report #TRCS00-19, Dept. of Computer Science, UCSB, July 2000. Postscript version. To appear in IEEE INFOCOM'2001.

• Huican Zhu and Tao Yang, Cachuma: Class-based Cache Management for Dynamic Web Content. Technical Report #TRCS00-13, Dept. of Computer Science, UCSB, June 2000. Postscript version. To appear in IEEE INFOCOM'2001.

• Ben Smith, Anurag Acharya, Tao Yang, Huican Zhu, Caching Equivalent and Partial Results for Dynamic Web Content. To appear in Proceedings of 1999 USENIX Symposium on Internet Technologies and Systems . HTML , PS file , PDF file . Compressed Slides (gzip) in the MS powerpoint format , or the 4-in-1 PS format .

• Huican Zhu and Ben Smith and Tao Yang, Scheduling Optimization for Resource-Intensive Web Requests on Server Clusters. the Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'99). Slides:Postscript version..PDF version

• Huican Zhu, Ben Smith and Tao Yang, A Scheduling Framework for Web Server Clusters with Intensive Dynamic Content Processing Technical Report, TRCS98-29, UCSB. Dec 1998. A poster version with title ``Hierarchical Resource Management for Web Server Clusters with Dynamic Content'' appeared in Proc. of ACM SIGMETRICS'99.

• V. Holmedahl, B. Smith, and T. Yang. Cooperative Caching of Dynamic Content on a Distributed Web Server in Proc. of 7th IEEE International Symposium on High Performance Distributed Computing (HPDC-7) Chicago, IL USA July 28-31, 1998. Talk slides

• Hong Tang (htang@cs.ucsb.edu)
  
• Doug Kuschner (kuschner@cs.ucsb.edu)
  
• Kai Shen (htang@cs.ucsb.edu)
  
• Huican Zhu (hczhu@cs.ucsb.edu)
  
• Tao Yang (tyang@cs.ucsb.edu)
  

• Anurag Acharya (acha@cs.ucsb.edu, currently with Google and UCSB)
  
• Vegard Holmedahl (veho@cs.ucsb.edu) (MS 1998. Currently with Mandator Inc, Norway)
  
• Ben Smith (besmith@cs.ucsb.edu, currently with Google)
  

Links to related work at UCSB:

Our previous research on multiprocessor digital library/Web servers.
The Alexandria Digital Library .