Cooperative leases: scalable consistency maintenance in content distribution networks

ABSTRACT

In this paper, we argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object needs. To meet the twin challenges of scalability and flexibility, we introduce the notion of cooperative consistency along with a mechanism, called cooperative leases, to achieve it. By supporting &Dgr;-consistency semantics and by using a single lease for multiple proxies, cooperative leases allows the notion of leases to be applied in a flexible, scalable manner to CDNs. Further, the approach employs application-level multicast to propagate server notifications to proxies in a scalable manner. We implement our approach in the Apache web server and the Squid proxy cache and demonstrate its efficacy using a detailed experimental evaluation. Our results show a factor of 2.5 reduction in server message overhead and a 20% reduction in server state space overhead when compared to original leases albeit at an increased inter-proxy communication overhead.

REFERENCES

• 1: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In Proceedings of Infocom'99, New York, NY, March 1999.
• 2: M. Busari and C. Williamson. On the Sensitivity of Web Proxy Cache Performance to Workload Characteristics. In Proceedings of IEEE Infocom'01, Anchorage, Alaska, April 2001.
• 3: C. Liu , P. Cao, Maintaining Strong Cache Consistency in the World-Wide Web, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.12, May 27-30, 1997
• 4: V. Cate. Alex: A Global File System. In Proceedings of the 1992 USENIX File System Workshop, pages 1--12, May 1992.
• 5: John Dilley, Martin Arlitt, Stephane Perret, and Tai Jin. The Distributed Object Consistency Protocol. Technical report, Hewlett-Packard Labs Technical Reports, 1999.
• 6: V. Duvvuri, P. Shenoy, and R. Tewari. Adaptive Leases: A Strong Consistency Mechanism for the World Wide Web. In Proceedings of the IEEE Infocom'00, Tel Aviv, Israel, March 2000.
• 7: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 8: Z. Fei. A Novel Approach to Managing Consistency in Content Distribution Networks. In Proceedings of the 6th Workshop on Web Caching and Content Distribution, Boston, MA, June 2001.
• 9: P. Francis. Yoid: Extending the Internet Multicast Architecture. Technical report, AT&T Center for Internet Research at ICSI (ACIRI), April 2000.
• 10: S. Gadde, J. Chase, and M. Rabinovich. Web Caching and Content Distribution: A View From the Interior. In Proceedings of the 5th International Web Caching and Content Delivery Workshop, 2000.
• 11: C. Gray , D. Cheriton, Leases: an efficient fault-tolerant mechanism for distributed file cache consistency, Proceedings of the twelfth ACM symposium on Operating systems principles, p.202-210, November 1989
• 12: M. Gritter and D. R. Cheriton. An Architecture for Content Routing Support in the Internet. In Proceedings of the USENIX Symposium on Internet Technologies, San Francisco, CA, March 2001.
• 13: J. Gwertzman and M. Seltzer. World-Wide Web Cache Consistency. In Proceedings of the 1996 USENIX Technical Conference, January 1996.
• 14: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 15: B. Krishnamurthy and C. Wills. Study of Piggyback Cache Validation for Proxy Caches in the WWW. In Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, Monterey, CA, pages 1--12, December 1997.
• 16: D. Li, P. Cao, and M. Dahlin. WCIP: Web Cache Invalidation Protocol. IETF Internet Draft, November 2000.
• 17: Jeffrey C. Mogul , Fred Douglis , Anja Feldmann , Balachander Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.181-194, September 14-18, 1997, Cannes, France
• 18: A. Ninan. Maintaining Cache Consistency in Content Distribution Networks. Master's thesis, Department of Computer Science, Univ. of Massachusetts, June 2001.
• 19: R. Srinivasan , C. Liang , K. Ramamritham, Maintaining Temporal Coherency of Virtual Data Warehouses, Proceedings of the IEEE Real-Time Systems Symposium, p.60, December 02-04, 1998
• 20: Design Considerations for Distributed Caching on the Internet, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.273, May 31-June 04, 1999
• 21: Maintaining Mutual Consistency for Cached Web Objects, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.371, April 16-19, 2001
• 22: A. Venkataramani, P. Yalagandula, R. Kokku, S. Sharif, and M. Dahlin. Potential Costs and Benefits of Long-term Prefetching for Content Distribution. In Proceedings of the Web Caching Workshop, Boston, MA, June 2001.
• 23: Jian Yin , Lorenzo Alvisi , Mike Dahlin , Arun Iyengar, Engineering server-driven consistency for large scale dynamic Web services, Proceedings of the 10th international conference on World Wide Web, p.45-57, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371935]
• 24: Jian Yin , Lorenzo Alvisi , Michael Dahlin , Calvin Lin, Volume Leases for Consistency in Large-Scale Systems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.563-576, July 1999 [doi>10.1109/69.790806]
• 25: Jian Yin, Lorenzo Alvisi, Mike Dahlin, and Calvin Lin. Hierarchical Cache Consistency in a WAN. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, Boulder, Colorado, October 1999.
• 26: Haobo Yu , Lee Breslau , Scott Shenker, A scalable Web cache consistency architecture, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.163-174, August 30-September 03, 1999, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Web-based interaction

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
content distribution networks, data consistency, data dissemination, dynamic data, leases, pullC, push, scalability, world wide web