Chord : A Scalable Peer To Peer lookup service for Internet Applications

In continuation with the previous post on consistent hashing, today we will look at a distributed lookup protocol by name Chord. The protocol was published as part of paper “Chord : A Scalalable Peer To Peer lookup service for Internet Applications” by MIT Laboratory of Computer Science. This is one of the game-changing papers of distributed systems.

Chord at its heart is a simple distributed lookup protocol which maps a key onto a node. Chord adapts efficiently as nodes join and leave the system and can answer queries even if the system is continually changing.

The Base Chord Protocol

The base chord protocol specifies how to find the location of keys, how new nodes join the system and how to recover from failure or departure of a node.

Internally, chord uses a consistent hash function for mapping keys to node locations. The consistent hash function of chord is based on standard hash functions like SHA1 that produces m bit output..

* Fron now on when we say hash it refers to SHA1. The output of SHA1 will be termed as an identifier.

It organizes the the output of the standard hash function like SHA1 to m bit identifier ring, i.e it orders numbers from 0 to 2^m-1 as a circle. The nodes are hashed based on their ip address, while key,value pair is hashed based on their key. Like a standard consistent hash function, the key gets assigned to the node whose hash is clockwise greater than the hash of key. This node is denoted as successor(hash(key)).

Each node is aware of it’s successor node in the identifier ring. Queries for a key gets passed around the circle of nodes via these successor pointers until it encounters the node that hosts the key. This may not be a very ideal lookup method. Hence chord maintains a finger table at each node. Let’s assume the node’s IP address hashes to the identifier value of n, the ith entry in the finger table of this node points to node hosting identifier value (n + 2 ^ i-1 mod 2 ^ m), i.e. successor(n + 2 ^ i-1 mod 2 ^ m). The finger table has at most m entries. For example, for m = 3 node at identifier 1, finger(1) points to the node hosting identifier (1 + 2⁰ = 2), finger(2) points to the node hosting identifier (1 + 2¹ = 3), finger(3) points to the node hosting identifier (3 + 2² = 7)

Node n = {

IP address : some address uniquely identifying a node.

identifier : location of node in the hash ring i.e. hash(IP address)

}

Node n # finger(i) = {

start : start of the interval pointed by the finger, (n.identifier + 2 ^ i — 1 mod 2 ^ m)

node : Address of the node whose identifier in the identifier ring which is clockwise greater than start of the interval pointed by this finger.

}

Depiction of a 3 bit chord ring with nodes being located at identifiers 0, 1, 3

Key Lookup

The pseudocode to lookup node corresponding to a key is as follows.

  • From now on when we mention identifier of a node (n.identifier) it refers to the hash of IP address of the machine in the identifier ring.

Node Join

When a new node joins the ring, we update it’s successor and finger nodes appropriately. We also move the pairs hosted in the new node’s successor back to the new node. We also update the finger table in other nodes to point appropriately to the new node that’s joining.

The new node identifies it’s position in the ring by hashing it’s ip address. For simplicity reasons let’s assume that the new node that’s joining is aware of some existing node in the ring and let’s call this existing node as n’

A simple algorithm is as follows.

The above algorithm aggressively maintains the pointers between nodes and also updates the finger tables. The chord system has been designed to perform correct lookups where there is a lot of node additions and removal are happening. However, there is a room for failed lookups. Chord system periodically runs a stabilization procedure on each node to make sure that identifier ring is intact and the new node additions are successfully integrated into the identifier ring.

A simple stabilization algorithm run by the chord at every node n verifies that node n is still the predecessor to the node n’s successor. However, if there is a new node x between n and it’s successor, update n.successor as x and set x.predecessor as n.