Skip to Content

Chord: Scable P2P Lookup Service Paper Review

Posted on 4 mins read

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Buzzwords

  • P2P, DHT
  • Consistent Hashing
  • Finger Table
  • Automatically Load Balance
  • Stabilization

Summary

The paper introduces the lookup service in the P2P applications named Chord. The Chord introduces the consistent hashing algorithm for each node only needs to remember O(log N) other nodes and resolves all lookup via O(log N) messages. What\’s more, it can also maintain the information as nodes join and leave the system in no more than n O(log^2^ N) messages even concurrently.

The Chord assigns each node and key with an m-bit identifier using SHA-1 and each key are assigned to nodes when successor(key) = node in clockwise. In order to lookup the key, we should forward and find the key to known information. The paper uses the finger table which keeps successor of nodes exponentially further away. The pseudocode is shown below. In the above algorithm, every forward take almost half way of the target, just like binary search in terms of consistency hashing.

// The pseudocode to find the successor node of an identifier . Remote procedure calls and variable lookups are precede-d by the remote node.
// ask node n to find id's successor
n.find_predecessor(id):
  n' = find_predecessor(id)
  return n'.successor

// ask node n to find id's predecessor
n.find_predecessor(id):
  n' = n
  while (id ∉ (n', n'.successor):
    n' = n'.closest_preceding_finger(id)
  return n'

// return closest_preceding_finger(id)
n.closest_preceding_finer(id):
  for i = m downto 1
    if (finger[i].node ∈ (n, id)):
      return finger[i].node
    return n

When a new node joins the system. Instead of finding all fingers\’ successor using the find_successor shown above, we can do a little optimization just like pseudocode shown below, which is O(log^2^ N) according to the paper. (If two fingers\’ interval contains no nodes, the two fingers\’ node is the same.)

// node n joins the network
// n' is an arbitrary node already in the network
n.join(n'):
  if (n'):
    init_finger_table(n')
    update_others()
    // move keys in (predecessor, n] from successor
  else: // n is only node in the network
    for i = 1 to m:
      finger[i].node = n
    predecessor = n

// initialize finger table of local node
// n' is an arbitrary node already in the network
n.init_finger_table(n'):
  finger[1].node = n'.find_successor(finger[1].start)
  predecessor = successor.predecessor
  successor.predecessor = n
  for i = 1 to m - 1:
    if (finger[i+1].start ∈ [n, finger[i].node)):
      finger[i+1].node = finger[i].node
    else:
      finger[i+1].node n'.find_sucessor(finger[i+1].start)

// update all nodes whose finger
// tables should refer to n
n.update_others():
  for i = 1 to m:
    // find last node p whse i^th finger might be n
    p = find_predecessor(n - 2^(i-1))
    p.update finger_table(n, i)

// if s is i^th finger of n, update n's finger table with s
n.update_finger_table(s, i):
  if (s ∈ [n, finger[i].node)):
    finger[i].node = s
    p = predecessor
    p.update_finger_table(s, i);

In terms of concurrent joins, the paper introduces a new algorithm to replace the above one, which is called Stabilization. The algorithm is just periodically asking its successor who its predecessor is, and If that node is closer to you, switch to that one. And after some time, all nodes will be correct according to the paper. Moreover, the nodes should periodically refresh its finger tables for correctness. The pseudocode is shown below.

n.join(n'):
  predecessor = nil
  successor = n'.find_successor(n)

// periodically verify n's immediate successor,
// and tell the successor about n
n.stabilize():
  x = successor.predecessor
  if (x ∈ (n, successor)):
    successor = x
  successor.notify(n)

// n' thinks it might be our predecessor
n.notify(n'):
  if (predecessor is nil or n' ∈ (predecessor, n)):
    predecessor = n'

// periodically refresh finger table entries
n.fix_fingers():
  i = random index > 1 into finger[]
finger[i].node = find_successor(finger[i].start)

Finally, nodes failure needs to be solved. As we all know, dealing with unreachable nodes during routing is important in reality. The paper uses successor-list, so lookup first finds live successor >= key, or forward to successor < key if possible. The paper says it can be routed successfully with high probability.

Above all, although the Chord guarantees weak consistency and alive data, it keeps less information needed to be kept, fewer messages needed to be sent and eventually consistency guarantees. The distributed hash table exposes a powerful design in P2P systems.

Strength of the paper

  • The paper introduces the P2P system with distributed hashing table. It is nice for load balance problem with less information stored.

  • The paper uses finger table to store the minimal necessary information to lookup instead of storing all information to perform a binary search style lookup.

Weakness of the paper

  • No introduction to security problem such as malicious nodes which may be common in the P2P system.

Suggestion to the paper

  • We can make use of geographic information to decided the closest available nodes.
comments powered by Disqus