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

#Peer-to-Peer

November 23, 2023

Chord is a distributed lookup protocol that supports just one operation: mapping a given key onto a node in a Chord cluster. If an \(N\)-node system is in the steady state, each node resolves all the queries via \(O(\log N)\) messages to other nodes. Chord uses consistent hashing to assign keys to Chord nodes.

The consistent hash assigns an \(m\)-bit identifier with each node and key. Key \(k\) is assigned to the first node whose identifier is equal to or follows \(k\) in an identifier circle modulo \(2^m\). An advantage of consistent hashing is that the nodes have the same number of keys with high probability. When a node joins (or departs from) the network, only an \(O(1/N)\) fraction of the keys is moved to different locations.

Chord scales consistent hashing by making each node maintain finger table, a routing table, with up to \(m\) entries. An entry includes both the Chord identifier and the IP address of a node. An identifier is generated by hashing the IP address of a node or a key using a base hash function, such as SHA-1. The \(k\)th entry at node \(n\) contains the identifier of the first node, \(s\), that succeeds \(\n) by at least 2^{i-1} on the identifier circle. The node that succeeds a node \(n\) by \(1\) is the successor of \(n\). predecessor is the previous node on the identifier circle.

Chord assumes a new node learns the identifier and the IP address of an existing Chord node \(n’\) by some external mechanism. The following pesudecode is cited from the paper, and shows the process of joining a new node \(n\) by invoking n.join(n')

// ask node n to find id's successor.
n.find_successor(id)
  n' = find_predecessor(id);
  return n'.successor;

// ask node n to find id's predecessor
n.find_predecessor(id)
  n' = n;
  while (id not in (n', n'.successor])
    n' = n'.closest_preceding_finger(id);
  return n';
  
// return closest finger preceding id
n.closest_preceding_finger(id)
  for i = m downto 1
    if (finger[i].node in (n,id))
	  return finger[i].node;
  return n;
  
// node n joins the network;
// n' is an arbitrary node in the network
n.join(n')
  predecessor = nil
  successor = n'.find_successor(n);
  
n.stabilize()
  x = successor.predecessor;
  if (x in (n, successor))
    successor = n;
	successor.notify(n);

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

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

Every node runs stabilize, and fix_fingers periodically to know the nodes that have newly joined and departed from the cluster. The stabilization won’t correct a Chord system that has split into disjoint cycles.