4005-730 Distributed Systems
Lecture Notes -- Module 5. Distributed Hash Tables

Distributed Hash Tables

• Normal (non-distributed) hash table
  • Data item = (key, value)
  • All data items stored in a table
  • Data item's location in table computed from hash of key
  • Operations: Add data item, remove data item, query key

• Distributed hash table (DHT)
  • Data item = (key, value)
  • Table of data items spread out across multiple nodes
  • Data item's location (node) computed from hash of key
  • Operations: Add data item, remove data item, query key -- requires routing from originating node to destination node
  • Additional operations: Add node, remove node

CAN (Content Addressable Network)

• S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 2001), August 2001, pages 161-172.

• The coordinate space
  • A d-dimensional space (e.g., d = 2)

  

  Figure 1: Example 2-d space with 5 nodes
  Ratnasamy et al., op. cit.

• Node coordinates
  • Each node is located at a certain point in the space
  • The space is partitioned among the nodes
  • Each node owns a rectangular region of the space

• Data item key coordinates
  • Each data item (key) in the DHT is located at a certain point in the space
  • The data item is stored in the node that owns the region containing the data item's key's coordinates

• Operation: Query key (also add data item, remove data item)
  • Draw a straight line from originating node coordinates to key coordinates in the space
  • Route query to nodes that own the regions traversed by the line
  • Average number of query hops = (d/4)(n^1/d), n = number of nodes, d = number of dimensions
  • Each node has 2d neighbors

• Operation: Add node
  • Pick new node's coordinates at random
  • Route add node request to node whose region includes new node's coordinates
  • Split that region in half
  • Existing node takes half the old region
  • New node takes other half of old region; data items in that half are transferred to new node

  Figure 2: Example 2-d space before node 7 joins		Figure 3: Example 2-d space after node 7 joins
  Ratnasamy et al., op. cit.		Ratnasamy et al., op. cit.

• Operation: Remove node
  • Merge departed node's region with adjacent existing node
  • Departed node's data items in that region are transferred to that adjacent node

Chord

• I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11(1):17-32, February 2003.
  • First published in 2001 as a conference paper

• Keys and hashing
  • Each node has a key which is the hash of the node's identifier (e.g. IP address)
  • Each data item (file) has a key which is the hash of the file's identifier
  • Any hash function can be used
  • The Chord paper uses SHA-1 (for hashing, not for security)

• The Chord ring
  • The N different hash values are conceptually arranged in a circle, representing modulo N
  • For SHA-1, which yields a 160-bit hash value, N = 2¹⁶⁰

• Key storage
  • Each node "lives" at the location on the ring equal to the node's key (hash)
  • Each data item is stored in the node whose key is the smallest value greater than or equal to the data item key, modulo N
    
    Stoica et al., op. cit.

• Key lookup
  • Each node has a finger table giving the nodes that store keys K+1, K+2, K+4, K+8, . . ., where K is the node's own key
  • To find a key, find the node in the finger table that is closest to the desired key without being greater than the desired key, and forward the query to that node
  • With O(log N) messages, the query will reach the node with the desired key
    
    Stoica et al., op. cit.

• Joining a chord
  • When a new node joins the system, it must set up its own finger table
  • When a new node joins the system, the existing nodes' finger tables must be adjusted to reflect the new node's presence
  • The Chord paper describes the detailed protocol for joining a chord, beginning with these words:
  • "When node n first starts, it calls n.join(n'), where n' is any known Chord node"
  • The paper does not describe how to find a known Chord node
  • A bootstrapping server of some kind is needed

• Chord still needs a central server (for bootstrapping)

Kademlia

• P. Maymounkov and D. Mazières. Kademlia: A peer-to-peer information system based on the XOR metric. In First International Workshop on Peer-to-Peer Systems (IPTPS 2002), LNCS 2429/2002, March 2002, pages 53-65.

• Keys and hashing
  • Each node has a unique 160-bit key
  • Each data item (file) has a unique 160-bit key

• Key distance
  • The distance between two keys A and B is Dist(A,B) = A xor B (Hamming distance)

• The key space
  • In the paper they describe the key space as a tree
  • But I think it's clearer as a hypercube
  • Consider a key A
  • The other keys fall on the corners of a 160-dimensional hypercube (only 4 dimensions shown)
  • The circle labeled 0000 contains all keys B such that Dist(A,B) begins with 0000
  • The circle labeled 0001 contains all keys B such that Dist(A,B) begins with 0001, and so on
    

• Each node knows the network addresses of certain other nodes
  • Node A knows up to k other nodes in this part of the key space:
    

  • Node A knows up to k other nodes in this part of the key space:
    

  • Node A knows up to k other nodes in this part of the key space:
    

  • Node A knows up to k other nodes in this part of the key space:
    

  • And so on
  • k is a system parameter, chosen so it is unlikely that the k nodes will all be down at the same time

• Lookup -- simplified explanation
  • Node A wants to find a key B where Dist(A,B) = 1111...
  • Node A asks some node in this part of the key space, e.g. node C where Dist(A,C) = 1000...
    

  • Node C tells node A to ask some node in this part of the key space, e.g. node D where Dist(A,D) = 1100...

    

  • Node D tells node A to ask some node in this part of the key space, e.g. node E where Dist(A,E) = 1110...

    

  • Node E tells node A to ask some node in this part of the key space, e.g. node F where Dist(A,F) = 1111...

    

  • And so on
  • Eventually, node A finds a node containing key B
  • The number of queries is proportional to the logarithm of Dist(A,B)

• Actual operation -- complications
  • When doing a lookup, the querying node sends lookup requests to multiple nodes at a time, e.g. three, not just one
    • Can speed up finding the key
  • When responding to a lookup, a node sends back k other nodes to try, not just one
    • Increases flexibility
    • E.g., prefer to send requests to low-latency nodes
  • After a lookup, the querying node replicates the key and associated data on the k nodes closest to the key encountered during the lookup
    • For fault tolerance
    • To reduce the number of queries needed to look up keys
  • Each node fills in its tables of other known nodes during the lookup process

• Joining a Kademlia system
  • The paper says: "To join the network, a node u must have a contact to an already participating node w."
  • The paper does not describe how to find an already participating node
  • A bootstrapping server of some kind is needed

• Kademlia still needs a central server (for bootstrapping)

Distributed Systems 4005-730-01 Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2011 Alan Kaminsky. All rights reserved. Last updated 30-Sep-2011. Please send comments to ark­@­cs.rit.edu.