In a peer-to-peer network, data is stored in different computers. A user needs to find out which computer the data is stored at before accessing it. Each piece of data is associated with a key, such as filename. Chord is a protocol for efficiently determining where a key is stored in such a p2p network. I will give an intuitive explanation for the lookup algorithm using concrete examples.
Each computer (“node”) in the network is assigned a number (called “identifier” or ID) on a ring using a hash function. Each ID has m bits; there are 2^m IDs available and the IDs range from 0 to (2^m) -1. If m = 8, there are 256 available IDs and the largest possible ID is 255. If the number n produced by the hash function is larger than 255, apply an modulo operation and use n % 256 as ID instead.
Suppose there are computers with the following IDs in the network: [32, 40, 45, 99, 132, 198, 234]. Their distribution on the ring looks like this:
For the data stored in the nodes, each key is assigned a number through the same hash function. A key is stored on the node with the same number as ID; if there is no node with that ID, the key is stored in the nearest node clockwise on the ring. For example, key 245 is stored on node 32 and key 33 is stored on node 40.
Now node 45 wants to find out where key 33 is located. Node 45 uses its finger table to find out which node it knows in the network is nearest to ring position 33. In general, there are m entries in a finger table. Node n calculates n + 2^i for each entry, where i ranges from 0 to m-1. The results are used to determine which node IDs should be recorded in n’s finger table. For each entry, the chosen node has an ID that is equal to or immediately larger than the calculated position number. For node 45, the result of the first entry calculation is 46; among all the nodes [32, 40, 45, 99, 132, 198, 234], node 99 is nearest to position 46 clockwise.
Remember all lookup procedures go clockwise; so among 99, 132, and 198, node 198 is nearest to position 33. Node 45 sends the query to node 198, which in turn checks its own finger table. In the seventh entry with i = 6, the initial calculation result is 262, which is larger than 256. We need a modulo operation to bring it within the range of 0 to 255. Node 32 is immediately larger than position 6. So 32 is recorded in that entry.
Node 198 discovers that node 32 is nearest to position 33 and sends the query to node 32. Node 32 checks its finger table and finds that position 33 is between itself and its successor, node 40. So key 33 should be stored on node 40. Node 33 sends the query to 40, which checks its data, finds the key, and sends back a query hit response.
The key to understanding the lookup process is to remember that all positions form a ring; queries go clockwise and wrap up back to position 0. When calculating distance between two positions, you have to go clockwise and not counter-clockwise, even if the counter-clockwise distance is shorter. If the key ID is between the current node ID and its successor, the key is stored on the successor node and the query ends.
To sum up, Chord provides an efficient way to determine which computer stores a given key in a peer-to-peer network. I have made substantial simplification to the key lookup algorithm in an effort to make it more understandable. Interested readers can refer to the original paper by Stoica et al.
