A scheme for load balancing in heterogenous distributed hash tables

ABSTRACT

We present a scheme for evenly partitioning the key space in distributed hash tables among the participating nodes. The scheme is based on the multiple random choices paradigm [3, 19], and handles both node joins and leaves. It achieves, with high probability, a ratio of at most 4 between the loads of the most and least burdened nodes, in the face or arbitrary node arrivals and departures. Each join or leave operation incurs message cost that is, with high probability, Oh(log²ⁿ), where n is the number of nodes, and causes the relocation of keys from at most one node (for joins) or three nodes (for leaves). A version of our scheme is suitable for heterogeneous systems, where the capacities of nodes to serve keys can vary widely.

REFERENCES

• 1: Ittai Abraham , Baruch Awerbuch , Yossi Azar , Yair Bartal , Dahlia Malkhi , Elan Pavlov, A Generic Scheme for Building Overlay Networks in Adversarial Scenarios, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.40.2, April 22-26, 2003
• 2: Micah Adler , Eran Halperin , Richard M. Karp , Vijay V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780626]
• 3: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
• 4: P. Fraigniaud and P. Gauron. The content-addressable network D2B. Technical Report 1349, RI, University of Paris-Sud, France, Jan. 2003.
• 5: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 6: F. Kaashoek and D. Karger. Koorde: A simple degree-optimal hash table. In Proc. 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), pages 98--107, Feb. 2003.
• 7: 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]
• 8: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 9: Krishnaram Kenthapadi , Gurmeet Singh Manku, Decentralized algorithms using both local and random probes for P2P load balancing, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073990]
• 10: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 11: Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872054]
• 12: Gurmeet Singh Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011797]
• 13: G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS '03), pages 127--140, Mar. 2003.
• 14: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 17: 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
• 18: Sylvia Ratnasamy , Ion Stoica , Scott Shenker, Routing Algorithms for DHTs: Some Open Questions, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.45-52, March 07-08, 2002
• 19: A. Richa, M. Mitzenmacher, and S. Sitaraman. The power of two random choices: A survey of techniques and results, Sept. 2000.
• 20: 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
• 21: 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

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Performance, Theory

Keywords:
distributed hash tables, load balancing, peer-to-peer