Optimal inter-object correlation when replicating for availability

ABSTRACT

Data replication is a key technique for ensuring data availability. Traditionally, researchers have focused on the availability of individual objects, even though user-level tasks (called operations) typically request multiple objects. Our recent experimental study has shown that the assignment of object replicas to machines results in subtle yet dramatic effects on the availability of these operations, even though the availability of individual objects remains the same.

This paper is the first to approach the assignment problem from a theoretical perspective, and obtains a series of results regarding assignments that provide the best and the worst availability for user-level operations. We use a range of techniques to obtain our results, from standard combinatorial techniques and hill climbing methods to Janson's inequality (a strong probabilistic tool). Some of the results demonstrate that even quite simple versions of the assignment problem can have surprising answers.

REFERENCES

• 1: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 2000.
• 3: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 4: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: John R. Douceur , Roger Wattenhofer, Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System, Proceedings of the 15th International Conference on Distributed Computing, p.48-62, October 03-05, 2001
• 6: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: Andreas Haeberlen , Alan Mislove , Peter Druschel, Glacier: highly durable, decentralized storage despite massive correlated failures, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.143-158, May 02-04, 2005
• 8: Larry Huston , Rahul Sukthankar , Rajiv Wickremesinghe , M. Satyanarayanan , Gregory R. Ganger , Erik Riedel , Anastassia Ailamaki, Diamond: A Storage Architecture for Early Discard in Interactive Search, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 9: S. Janson. Poisson Approximations for Large Deviations. Random Structures and Algorithms, 1:221--230, 1990.
• 10: Svante Janson, New versions of Suen's correlation inequality, Random Structures & Algorithms, v.13 n.3-4, p.467-483, Oct., 1998
• 11: S. Janson, T. Luczak, and A. Rucinski. An Exponential Bound for the Probability of Nonexistence of a Specified Subgraph in a Random Graph. In Random Graphs'87 (M. Karo'nski and J. Jaworski and A. Ruci'nski, Eds.). John Wiley & Sons, 1990.
• 12: 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]
• 13: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 14: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 15: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 16: 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
• 17: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 18: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 19: Jose Renato Santos , Richard R. Muntz , Berthier Ribeiro-Neto, Comparing random data allocation and data striping in multimedia servers, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.44-55, June 18-21, 2000, Santa Clara, California, United States
• 20: 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
• 21: S. Suen. A Correlation Inequality and a Poisson Limit Theorem for Nonoverlapping Balanced Subgraphs of a Random Graph. Random Structures and Algorithms, 1(2):231--242, 1990.
• 22: Alexander S. Szalay , Peter Z. Kunszt , Ani Thakar , Jim Gray , Don Slutz , Robert J. Brunner, Designing and mining multi-terabyte astronomy archives: the Sloan Digital Sky Survey, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.451-462, May 15-18, 2000, Dallas, Texas, United States
• 23: TPC Benchmark. http://www.tpc.org/.
• 24: L. G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. on Computing, 8(3):410--421, 1979.
• 25: Robbert van Renesse , Fred B. Schneider, Chain replication for supporting high throughput and availability, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.7-7, December 06-08, 2004, San Francisco, CA
• 26: Haifeng Yu , Phillip B. Gibbons , Suman Nath, Availability of multi-object operations, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.16-16, May 08-10, 2006, San Jose, CA
• 27: Haifeng Yu , Amin Vahdat, Minimal replication cost for availability, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571839]

INDEX TERMS

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

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
availability, data replication, inter-object correlation, multi-object operation, object assignment