Giggle: a framework for constructing scalable replica location services

ABSTRACT

In wide area computing systems, it is often desirable to create remote read-only copies (replicas) of files. Replication can be used to reduce access latency, improve data locality, and/or increase robustness, scalability and performance for distributed applications. We define a replica location service (RLS) as a system that maintains and provides access to information about the physical locations of copies. An RLS typically functions as one component of a data grid architecture. This paper makes the following contributions. First, we characterize RLS requirements. Next, we describe a parameterized architectural framework, which we name Giggle (for GIGa-scale Global Location Engine), within which a wide range of RLSs can be defined. We define several concrete instantiations of this framework with different performance characteristics. Finally, we present initial performance results for an RLS prototype, demonstrating that RLS systems can be constructed that meet performance goals.

REFERENCES

• 1: The DataGrid Architecture. 2001, EU DataGrid Project.
• 2: Chervenak, A., et al., The Data Grid: Towards an Architecture for the Distributed Management and Analysis of Large Scientific Data Sets. J. Network and Computer Applications, 2001(23): p. 187--200.
• 3: Foster, I. and C. Kesselman, A Data Grid Reference Architecture. 2001.
• 4: Bill Allcock , Joe Bester , John Bresnahan , Ann L. Chervenak , Ian Foster , Carl Kesselman , Sam Meder , Veronika Nefedova , Darcy Quesnel , Steven Tuecke, Data management and transfer in high-performance computational grid environments, Parallel Computing, v.28 n.5, p.749-771, May 2002 [doi>10.1016/S0167-8191(02)00094-7]
• 5: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 6: Chandy, K.M., A. Rifkin, and E. Schooler, Using Announce-Listen with Global Events to Develop Distributed Control Systems. Concurrency: Practice and Experience, 1998. 10. (11--13): p. 1021--1027.
• 7: D. Clark, The design philosophy of the DARPA internet protocols, Symposium proceedings on Communications architectures and protocols, p.106-114, August 16-18, 1988, Stanford, California, United States
• 8: Suchitra Raman , Steven McCanne, A model, analysis, and protocol framework for soft state-based communication, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.15-25, Oct. 1999
• 9: Zhang, L., et al. RSVP: A new Resource ReSerVation Protocol. in IEEE Network. 1993.
• 10: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 11: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 12: Foster, I., et al., The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. 2002, Globus Project.
• 13: Hoschek, W., A Unified Peer-to-Peer Database Framework and its Application for Scalable Service Discovery, in 2002. 2002, CERN.
• 14: Adriana Iamnitchi , Ian T. Foster, On Fully Decentralized Resource Discovery in Grid Environments, Proceedings of the Second International Workshop on Grid Computing, p.51-62, November 12, 2001
• 15: 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]
• 16: David Karger , Alex Sherman , Andy Berkheimer , Bill Bogstad , Rizwan Dhanidina , Ken Iwamoto , Brian Kim , Luke Matkins , Yoav Yerushalmi, Web caching with consistent hashing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1203-1213, May 17, 1999
• 17: Ian Foster , Carl Kesselman, The Globus toolkit, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 18: Peter J. Braam, The Coda Distributed File System, Linux Journal, v.1998 n.50es, June 1998
• 19: Yuri Breitbart , Henry F. Korth, Replication and consistency: being lazy helps sometimes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.173-184, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263681]
• 20: Dirk Düllmann , Ben Segal, Models for Replica Synchronisation and Consistency in a Data Grid, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01), p.67, August 07-09, 2001
• 21: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 22: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 23: Popek, G.J., et al. Replication in Ficus distributed file systems. in Workshop on Management of Replicated Data,. 1990: IEEE.
• 24: Jeff Sidell , Paul M. Aoki , Adam Sah , Carl Staelin , Michael Stonebraker , Andrew Yu, Data Replication in Mariposa, Proceedings of the Twelfth International Conference on Data Engineering, p.485-494, February 26-March 01, 1996
• 25: Heinz Stockinger, Distributed Database Management Systems and the Data Grid, Proceedings of the Eighteenth IEEE Symposium on Mass Storage Systems and Technologies, p.1, April 17-20, 2001
• 26: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 27: Terry, D.B., et al. The Case for Non-transparent Replication: Examples from Bayou. in IEEE Data Engineering. 1998.
• 28: Thomas W. Page, J., et al. Management of replicated volume location data in the Ficus replicated file system. in USENIX Conference Proceedings. 1991.
• 29: Matthias Wiesmann , André Schiper , Fernando Pedone , Bettina Kemme , Gustavo Alonso, Database Replication Techniques: A Three Parameter Classification, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.206, October 16-18, 2000
• 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: Wang, J. A Survey of Web Caching Schemes for the Internet. in Proceedings of ACM SIGCOMM '99 Conference. 1999.
• 32: Philip S. Yu , Edward A. MacNair, Performance study of a collaborative method for hierarchical caching in proxy servers, Proceedings of the seventh international conference on World Wide Web 7, p.215-224, April 1998, Brisbane, Australia
• 33: Ross, K.W., Hash routing for collections of shared Web caches. IEEE Network, 1997: p. 37--44.
• 34: Valloppillil, V. and K.W. Ross. Cache array routing protocol v1.0. in Internet Draft. 1988.
• 35: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 36: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 37: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 38: Ripeanu, M., I. Foster, and A. Iamnitchi, Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design. 2001, University of Chicago.
• 39: Clarke, I., et al. Freenet: A Distributed Anonymous Information Storage and Retrieval System. in ICSI Workshop on Design Issues in Anonymity and Unobservability. 1999.
• 40: Steven E. Czerwinski , Ben Y. Zhao , Todd D. Hodes , Anthony D. Joseph , Randy H. Katz, An architecture for a secure service discovery service, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.24-35, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313462]
• 41: Todd D. Hodes , Steven E. Czerwinski , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz, An architecture for secure wide-area service discovery, Wireless Networks, v.8 n.2/3, p.213-230, March-May 2002 [doi>10.1023/A:1013772027164]
• 42: Steven Fitzgerald, Grid Information Services for Distributed Resource Sharing, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01), p.181, August 07-09, 2001
• 43: Hoschek, W. A Database for Dynamic Distributed Content and its Application for Service and Resource Discovery. in International IEEE Symposium on Parallel and Distributed Computing. 2002.
• 44: Heinz Stockinger , Asad Samar , Koen Holtman , Bill Allcock , Ian Foster , Brian Tierney, File and Object Replication in Data Grids, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01), p.76, August 07-09, 2001
• 45: Chaitanya Baru , Reagan Moore , Arcot Rajasekar , Michael Wan, The SDSC storage resource broker, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.5, November 30-December 03, 1998, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

General Terms:
Design, Experimentation, Measurement, Performance