Chord: A Peer-to-peer Lookup Protocol

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

System Model

Support the following features:

  • load balance: spreading keys evenly over the nodes
  • decentralization: fully distributed; no node is more important than any other
  • scalability: the cost of a Chord loopup grows as the log of the number of nodes
  • availability: automatically adjusts its internal tables to reflect newly joined nodes as well as node failures
  • flexible naming: Chord places no constraints on the structure of the keys it looks up

The Chord Protocol

The consistent hash function assigns each node and key an m-bit identifier using SHA-1 as a base hash function. A node’s identifier is chosen by hashing the node’s IP address, while a key identifier is produced by hashing the key. The identifier length m must be large enough to make the probability of two nodes or keys hashing to the same identifier negligible.

The range of the identifier circle is $2^m$. Key k is assigned to the first node whose identifier is equal to or follows k in the circle.

The lookup algorithm makes use of binary search tech. Every node will store a table with m entries. The $i^{th}$ entry in the table at node n contains the identity of the first node s that succeeds n by at least $2^{i-1}$ on the circle. We denote the $i^{th}$ entry of node n by $n.finger[i]$.


Since from any node, we can reach half of the entire Chord circle, the lookup operation would take O($\log n$) cost.

Impact of node joins on lookups: Sometimes the nodes in the affected region have incorrect successor pointers, or keys may not yet have migrated to newly joined nodes, and the lookup may fail. The higher-layer software using Chord has to notice that the desired data was not found, and has the option of retrying the lookup after a pause.