Copyright © (2004) 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 distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
This paper presents techniques for efficiently serving dynamic data at highly accessed Web sites and presents a quantitative analysis of the design motivation and performance benefits of these techniques. To reduce the overhead for generating dynamic data, we use the Data Update Propagation (DUP) algorithms for keeping cached data consistent so that dynamic pages can be cached at the Web server and dynamic content can be served at the performance level of static content. DUP maintains data dependence information between cached objects and the underlying data affecting their values in a graph. When the system becomes aware of a change to the underlying data, graph traversal algorithms are applied to determine which cached objects are affected by the change. Cached objects that are found to be highly obsolete, relative to requests for the page, are then either invalidated or updated depending upon request and update patterns for the objects. DUP is one of a few critical components of a general multitier architecture that has been deployed for high-performance serving of dynamic data to many clients at several Web sites hosted by IBM. The design of this architecture and the DUP algorithms is based on a detailed analysis of the stochastic aspects of the client request patterns and the dynamic page update patterns at a few previous highly accessed Web sites. Our considerable experience with this system design at subsequent highly accessed Web sites has proven to be consistent with the results of this motivating analysis. In particular, our system design is able to achieve cache hit ratios close to 100%, as a result of which Web sites based on our system design are able to serve data quickly even during peak request periods. Proper deployments of our system result in cached data which is almost never obsolete by more than a few seconds, if at all. Our system architecture and algorithms for efficiently serving dynamic data provide more than an order of magnitude improvement in performance using an order of magnitude fewer servers over that obtained under existing methods for serving dynamic content. High availability is achieved via redundant hardware and intelligent routing techniques.
By: James R. Challenger, Paul M. Dantzig, Arun K. Iyengar, Mark S. Squillante, Li Zhang
Published in: IEEE/ACM Transactions on Networking, volume 12, (no 2), pages 233-46 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .