BuddyCache: high-performance object storage for collaborative strong-consistency applications in a WAN

ABSTRACT

Collaborative applications provide a shared work environment for groups of networked clients collaborating on a common task. They require strong consistency for shared persistent data and efficient access to fine-grained objects. These properties are difficult to provide in wide area networks because of high network latency.BuddyCache is a new transactional caching approach that improves the latency of access to shared persistent objects for collaborative strong-consistency applications in high-latency network environments. The challenge is to improve performance while providing the correctness and availability properties of a transactional caching protocol in the presence of node failures and slow peers.We have implemented a BuddyCache prototype and evaluated its performance. Analytical results, confirmed by measurements of the BuddyCache prototype using the multi-user 007 benchmark indicate that for typical Internet latencies, e.g. ranging from 40 to 80 milliseconds round trip time to the storage server, peers using BuddyCache can reduce by up to 50% the latency of access to shared objects compared to accessing the remote servers directly.

REFERENCES

• 1: 'emulab.net',the Utah Network Emulation Facility. http://www.emulab.net.
• 2: Atul Adya , Miguel Castro , Barbara Liskov , Umesh Maheshwari , Liuba Shrira, Fragment Reconstruction: Providing Global Cache Coherence in a Transactional Storage System, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.2, May 27-30, 1997
• 3: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.23-34, May 22-25, 1995, San Jose, California, United States
• 4: Cristiana Amza , Alan L. Cox , Sandhya Dwarkadas , Pete Keleher , Honghui Lu , Ramakrishnan Rajamony , Weimin Yu , Willy Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations, Computer, v.29 n.2, p.18-28, February 1996 [doi>10.1109/2.485843]
• 5: C. Anderson and A. Karlin. Two Adaptive Hybrid Cache Coherency Protocols. In Proceedings of
• 6: Mary Louise Gray Baker, Fast crash recovery in distributed file systems, University of California at Berkeley, Berkeley, CA, 1995
• 7: 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
• 8: Michael J. Carey , David J. DeWitt , Chander Kant , Jeffrey F. Naughton, A status report on the OO7 OODBMS benchmarking effort, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.414-426, October 23-28, 1994, Portland, Oregon, United States
• 9: A. Chankhunthod, M. Schwartz, P. Danzig, K. Worrell, and C. Neerdaels. A Hierarchical Internet Object Cache. In USENIX Annual Technical Conference, January 1995.
• 10: J. Chase, S. Gadde, and M. Rabinovich. Directory Structures for Scalable Internet Caches. Technical Report CS-1997-18, Dept. of Computer Science, Duke University, November 1997.
• 11: J. Chase, S. Gadde, and M. Rabinovich. Not All Hits Are Created Equal: Cooperative Proxy Caching Over a Wide-Area Network. In Third International WWW Caching Workshop, June 1998.
• 12: D. R. Cheriton and D. Li. Scalable Web Caching of Frequently Updated Objects using Reliable Multicast. 2nd USENIX Symposium on Internet Technologies and Systems, October 1999.
• 13: M. D. Dahlin, R. Y. Wang, T. E. Anderson, and D. A. Patterson.Cooperative caching: Using remote client memory to improve file system performance. Proceedings of the USENIX Conference on Operating Systems Design and Implementation, November 1994.
• 14: S. Dwarkadas, H. Lu, A. L. Cox, R. Rajamony, and W. Zwaenepoel. Combining Compile-Time and Run-Time Support for Efficient Software Distributed Shared Memory.In Proceedings of IEEE, Special Issue on Distributed Shared Memory, March 1999.
• 15: 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
• 16: M. J. Feeley , W. E. Morgan , E. P. Pighin , A. R. Karlin , H. M. Levy , C. A. Thekkath, Implementing global memory management in a workstation cluster, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.201-212, December 03-06, 1995, Copper Mountain, Colorado, United States
• 17: M. J. Feeley, J. S. Chase, V. R. Narasayya, and H. M. Levy. Integrating Coherency and Recoverablity in Distributed Systems. In Proceedings of the First Usenix Symposium on Operating sustems Design and Implementation, May 1994.
• 18: Paulo Ferreira , Marc Shapiro , Xavier Blondel , Olivier Fambon , João Garcia , Sytse Kloosterman , Nicolas Richer , Marcus Roberts , Fadi Sandakly , George Coulouris , Jean Dollimore , Paulo Guedes , Daniel Hagimont , Sacha Krakowiak, PerDiS: Design, Implementation, and Use of a PERsistent DIstributed Store, Advances in Distributed Systems, Advanced Distributed Computing: From Algorithms to Systems, p.427-452, January 1999
• 19: Michael J. Franklin , Michael J. Carey , Miron Livny, Transactional client-server cache consistency: alternatives and performance, ACM Transactions on Database Systems (TODS), v.22 n.3, p.315-363, Sept. 1997 [doi>10.1145/261124.261125]
• 20: Michael J. Franklin , Michael J. Carey , Miron Livny, Global Memory Management in Client-Server Database Architectures, Proceedings of the 18th International Conference on Very Large Data Bases, p.596-609, August 23-27, 1992
• 21: Sanjay Ghemawat , Barbara H. Liskov , M. Frans Kaashoek, The modified object buffer: a storage management technique for object-oriented databases, 1995
• 22: Leonard Kawell, Jr. , Steven Beckhardt , Timothy Halvorsen , Raymond Ozzie , Irene Greif, Replicated document management in a group communication system, Proceedings of the 1988 ACM conference on Computer-supported cooperative work, September 26-28, 1988, Portland, Oregon, United States [doi>10.1145/62266.1024798]
• 23: Barbara Liskov , Miguel Castro , Liuba Shrira , Atul Adya, Providing Persistent Objects in Distributed Systems, Proceedings of the 13th European Conference on Object-Oriented Programming, p.230-257, June 14-18, 1999
• 24: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 25: Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62549]
• 26: J. O 'Toole and L. Shrira. Opportunistic Log: Efficient Installation Reads in a Reliable Object Server. In Usenix Symposium on Operation Systems Design and Implementation, November 1994.
• 27: D. Pendarakis, S. Shi, and D. Verma. ALMI: An Application Level Multicast Infrastructure. In 3rd USENIX Symposium on Internet Technologies and Systems, March 2001.
• 28: Prasenjit Sarkar , John Hartman, Efficient cooperative caching using hints, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.35-46, October 29-November 01, 1996, Seattle, Washington, United States
• 29: A. M. Vahdat, P. C. Eastham, and T. E Anderson. WebFS: A Global Cache Coherent File System. Technical report, University of California, Berkeley, 1996.
• 30: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.16-31, December 12-15, 1999, Charleston, South Carolina, United States
• 31: J. Yin, L. Alvisi, M. Dahlin, and C. Lin. Hierarchical Cache Consistency in a WAN. In USENIX Symposium on Internet Technologies and Systems, October 1999.
• 32: 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]
• 33: Markos Zaharioudakis , Michael J. Carey , Michael J. Franklin, Adaptive, fine-grained sharing in a client-server OODBMS: a callback-based approach, ACM Transactions on Database Systems (TODS), v.22 n.4, p.570-627, Dec. 1997 [doi>10.1145/278245.278249]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Design, Performance

Keywords:
cooperative caching, fault-tolerance, fine-grain sharing, object storage systems, transactions, wide-area network