Performance, Scalability, and Reliability

Performance, scalability, and reliability are critically important for middleware systems. In many cases, the overhead for a system can be substantially reduced by caching. In order for an application to benefit from caching, it must repeatedly use data which is expensive to calculate or fetch. By caching such data, the application only needs to calculate or fetch the data once. Whenever the data is needed after it has been cached, the application can fetch the data from the cache instead of recalculating it or fetching it from a remote location. Caching can take place at several points within a system. A processor cache might have one or more caches for reducing the latency for accessing data. A database might also have a cache for storing frequently requested data. Caching within Web systems can occur at several different points such as within browsers, servers, and proxies. Browser and proxy caching reduce the latency for fetching remote documents and network utilization; server CPU cycles may also be reduced. Server caching can reduce processing cycles consumed by the server, particularly if the server generates considerable dynamic content which can be cached.

We have used caching to improve the performance of several distributed systems, most notably large-scale commercial Web systems. One of our key contributions has been to reduce the overhead for serving dynamic Web data by caching [USITS'97]. The key problem with caching dynamic data is maintaining consistent caches. One key technique for maintaining consistent caches is Data Update Propagation (DUP) [ToN'04, INFOCOM'99]. DUP maintains dependencies between underlying data such as database tables and cached objects such as Web pages in a graph. When underlying data change, graph traversal algorithms are applied to determine the cached objects affected by the change.

We have also developed other methods for maintaining Web cache consistency. Web caching is promising in reducing latency and increasing scalability of internet-wide services. The effectiveness of web caching is determined to a great extent by the performance of underlying cache consistency protocols. Designing high performance web cache consistency protocols is challenging because of the large scale of the web. A popular web server can have millions of clients. The large number of clients also implies that a significant number of clients cannot be reached by the server at any given time as the probability of partial failures is multiplied with the scale of the system. On the one hand, client polling with short cached object lifetimes is highly scalable and failure-resilient, but incurs a large number of client polls for reads and thus reduces the effectiveness of caching. On the other hand, server invalidation minimizes server accesses for cache revalidation, but can not handle failures well and is not as scalable. We have developed the Volume Lease protocol to maintain Web cache consistency [ToIT'02, WWW10]. Volume Lease amortizes cache revalidation costs over many objects in a volume. Experimental results show that Volume Lease can match the performance of server invalidation and the scalability and failure-resiliency of client polling.

Another key technique for efficiently generating dynamic Web data is to compose Web pages from fragments [ToIT'05, INFOCOM2000]. Fragments typically have different lifetimes. A key advantage to using fragments is that when a fragment changes, the entire Web page doesn't have to be updated; only the fragment needs to be updated. Fragment-based Web publication allows parts of dynamic Web pages to be cached. Caches may dynamically assemble Web pages from fragments; relatively static fragments may be cached remotely while highly dynamic and personalized fragments are fetched from the server. We have demonstrated the effectiveness of fragment-based Web publication at highly accessed Web sites and developed techniques for automatically detecting fragments in Web pages. We have also developed techniques for automatically detecting fragments in Web pages [TKDE'05, WWW2004]; automatic fragment detection makes it much easier to develop Web pages using fragments.

In some systems, it is possible to improve performance by employing caches explicitly managed by the application. We refer to this type of caching as application-level caching. Application-level caching has been critically important for improving middleware systems we have worked on such as the Accessible Business Rules (ABR) (also known as Business Rule Beans, or BRBeans) for IBM's Websphere. ABR is a middleware system which enables application writers to build applications where the time and situation-variable parts of their business logic are externally applied entities known as business rules. The techniques we have used for caching in ABR can be applied to other applications as well. The General-Purpose Software cache (GPS cache) which we used is designed to be plugged into different applications. The GPS cache has also been successfully deployed in a Web server accelerator. The GPS cache has very efficient code for storing data in memory, on disk, or both. It also has optimized support for invalidating objects based on expiration times and for logging cache transactions [IPCCC'99]. The GPS cache, as applied in ABR, stores the results of queries ultimately made to a database. A key problem with caching query results is determining which queries are affected by changes that occur to the database. In order to keep caches current after database updates, we use an enhanced version of data update propagation (DUP). A query result may depend on several attributes, and these dependency relationships are represented by an object dependence graph (ODG). DUP had been previously used to cache dynamic Web data. We made two key innovations to DUP for caching in ABR. When attributes change, we consider the old and new values of the attributes in order to determine how to update the cache. This value-aware update policy is implemented by annotating edges of ODG's with values based on queries. When DUP was used for caching dynamic Web data, an application program was responsible for generating the ODG. The second key innovation we made to DUP for ABR was to automatically generate ODG's from the queries within an ABR application [Middleware 2000].

Papers

• "Automatic Fragment Detection in Dynamic Web Pages and its Impact on Caching" Lakshmish Ramaswamy, Arun Iyengar, Ling Liu, and Fred Douglis. In IEEE Transactions on Knowledge and Data Engineering vol. 17 #6, June 2005 (TKDE'05).
  
• "A Fragment-Based Approach for Efficiently Creating Dynamic Web Content" Jim Challenger, Paul Dantzig, Arun Iyengar, and Karen Witting. In ACM Transactions on Internet Technology vol. 5 #2, May 2005 (ToIT'05).
  
• "Improving Availability and Performance with Application-Specific Data Replication", Lei Gao, Mike Dahlin, Amol Nayate, Jiandan Zheng, and Arun Iyengar. In IEEE Transactions on Knowledge and Data Engineering vol. 17 #1, January 2005.
  
• "Improving Web Site Performance" Arun Iyengar, Erich Nahum, Anees Shaikh, and Renu Tewari. In The Practical Handbook of Internet Computing, Copyright 2005, Chapman & Hall/CRC Press, Munindar P. Singh ed.
  
• "Web Caching, Consistency and Content Distribution" Arun Iyengar, Erich Nahum, Anees Shaikh, and Renu Tewari. In The Practical Handbook of Internet Computing, Copyright 2005, Chapman & Hall/CRC Press, Munindar P. Singh ed.
  
• "Automatic Detection of Fragments in Dynamically Generated Web Pages" Lakshmish Ramaswamy, Arun Iyengar, Ling Liu, and Fred Douglis. Best Paper Award. In Proceedings of the 13th International World Wide Web Conference (WWW2004), New York City, May 2004.
  
• "Efficiently Serving Dynamic Data at Highly Accessed Web Sites" Jim Challenger, Paul Dantzig, Arun Iyengar, Mark Squillante, and Li Zhang. In IEEE/ACM Transactions on Networking vol. 12 #2, April 2004 (ToN'04).
  
• "A Tiered System for Serving Differentiated Content" Huamin Chen and Arun Iyengar. In World Wide Web: Internet and Web Information Systems vol. 6 #4, December 2003.
  
• "Application-Specific Delta-Encoding via Resemblance Detection" Fred Douglis and Arun Iyengar. In Proceedings of the 2003 USENIX Annual Technical Conference (USENIX '03), San Antonio, Texas, June 2003.
  
• "Application Specific Data Replication for Edge Services" Lei Gao, Mike Dahlin, Amol Nayate, Jiandan Zheng, and Arun Iyengar. Best Student Paper Award. In Proceedings of the 12th International World Wide Web Conference (WWW2003), Budapest, Hungary, May 2003.
  
• "Engineering Web Cache Consistency", Jian Yin, Lorenzo Alvisi, Mike Dahlin, and Arun Iyengar. In ACM Transactions on Internet Technology vol. 2 # 3, August 2002 (ToIT'02).
• "Performance Considerations in Web Security" Arun Iyengar, Ronald Mraz and Mary Ellen Zurko. In Proceedings of the 2002 IFIP International Workshop on Certification and Security in E-Services (CSES 2002) (Certification and Security in E-Services: From E-Government to E-Business), World Computer Congress, Montreal, Canada, August 2002, Copyright IFIP, Published by Kluwer Academic Publishers, Boston, ISBN 1-4020-7493-X.
• "Architecting Web Sites for High Performance" Arun Iyengar and Daniela Rosu. In Scientific Programming, vol. 10 #1, June 2002.
  
• "Architecture of a Web Server Accelerator" Junehwa Song, Arun Iyengar, Eric Levy-Abegnoli, and Daniel Dias. In Computer Networks, vol. 38 #1, January 2002.
  
• "Engineering server-driven consistency for large scale dynamic web services" Jian Yin, Lorenzo Alvisi, Mike Dahlin, and Arun Iyengar. Best Paper Award. In Proceedings of the 10th International World Wide Web Conference (WWW10), Hong Kong, May 2001.
  
• "A Middleware System Which Intelligently Caches Query Results" Louis Degenaro, Arun Iyengar Ilya Lipkind, and Isabelle Rouvellou. In Proceedings of ACM/IFIP Middleware 2000, Palisades, New York, April 2000 (published by Springer-Verlag).
  
• "High-Performance Web Site Design Techniques" Arun Iyengar, Jim Challenger, Daniel Dias, and Paul Dantzig. In IEEE Internet Computing, vol. 4 #2, March/April 2000.
  
• "A Publishing System for Efficiently Creating Dynamic Web Data", Jim Challenger, Arun Iyengar, Karen Witting, Cameron Ferstat, and Paul Reed. In Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000.
  
• "Analysis and Characterization of Large-Scale Web Server Access Patterns and Performance", Arun Iyengar, Mark Squillante, and Li Zhang. In World Wide Web vol. 2 #1, 2, June 1999.
  
• "A Scalable System for Consistently Caching Dynamic Web Data" Jim Challenger, Arun Iyengar, and Paul Dantzig. In Proceedings of IEEE INFOCOM'99, New York, New York, March 1999.
  
• "Design and Performance of a General-Purpose Software Cache", Arun Iyengar. In Proceedings of the 18th IEEE International Performance, Computing, and Communications Conference (IPCCC'99), Phoenix/Scottsdale, Arizona, February 1999.
• "Improving Web Server Performance by Caching Dynamic Data", Arun Iyengar and Jim Challenger . In Proceedings of the USENIX 1997 Symposium on Internet Technologies and Systems (USITS '97), Monterey, CA, December 1997.
  

Copyright Notices

• ACM Papers - Copyright © by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post of servers, or to redistribute to lists, requires prior specific permission and/or a fee.
• IEEE Papers - Copyright © by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit. To copy otherwise, to republish, to post of servers, or to redistribute to lists, requires prior specific permission and/or a fee.

More

Questions and/or comments about this work can be directed to Arun Iyengar (email: aruni(at)us(dot)ibm(dot)com), Lou Degenaro (email: degenaro(at)us(dot)ibm(dot)com), Jian Yin (email: jianyin(at)us(dot)ibm(dot)com), or Isabelle Rouvellou (email: rouvellou(at)us(dot)ibm(dot)com).