How to perform lookup in Chord distributed hash tables (DHT)

There are many distributed hash table based systems; the Chord system is the one we will focus on.

Structure of a Chord DHT

Entities are key-value pairs; the key represents the name, while the value represents the address. A hash function H is used to map the entity key and the node address to the identifier space.

• H(key) = entity identifier is generated

• H(address) = node identifier is generated

Chord DHT uses an $m$ bit circular identifier space, i.e. $2^m$ identifiers. The entity with identifier $e$ is stored on the node $n$ if $n\ge e$, making $n$ the successor of $e$.

In this diagram, $m$ is 3, which generates an identifier space of 2³ values, 0 to 7 inclusive.

The nodes have identifiers 2, 5, and 7, while the rest are entities. The list below represents which nodes are responsible for which entities.

• Node 2: Entity 0, Entity 1, and Entity 2

• Node 5: Entity 3, Entity 4, and Entity 5

• Node 7: Entity 6 and Entity 7

Finger tables

It will be difficult to understand the lookup process without understanding the finger tables in a Chord DHT. However, knowledge of how to create finger tables is not necessary.

Finger tables accelerate the lookup process in a Chord DHT. This happens because finger tables contain shortcuts to existing nodes in the ring, thus decreasing the distance traveled to search for a particular node.

Every node has a finger table containing the address of $m$ successive nodes, which is used to navigate to other nodes during lookup.

Let’s review some syntactical details of these finger tables commonly used in Chord DHT algorithms:

• $FT_{n}$ represents the finger table for node $n$. For example, $FT_{1}$will be used to refer to the finger table of node 1.

• $FT_{n}[i]$ represents the i^th successor of node $n$. For example, $FT_{1}[2]$ will be used to refer to the second successor node in the finger table of node 1.

Lookup

The search for a specific entity can begin at any node. For a successful search, we need to reach the node responsible for that particular entity. There are three distinct cases in the lookup process. We will go over the basic concept in each case before we look at them in detail.

The lookup request to search for entity $e$ is forwarded to node $n$,

1. If $n = e$, return $n$.

2. If $n < e$$\&$ $e < FT_{n}[1]$, return $FT_{n}[1]$.

3. If $FT_{n}[j] < e$$\&$ $e \le FT_{n}[j+1]$, the lookup is forwarded to node $FT_{n}[j]$.

Note: The second and third rules use $\&$ condition, so it requires both conditions to be true.

In large Chord DHTs, it’s possible that we may have to apply all or more than one rule in each lookup. Whenever the lookup request is forwarded to another node, we start checking from rule 1 again until one of the rules fits the current scenario.

Let’s look at some detailed examples to understand the application of the rules mentioned above.

Case 1

This case includes the application of rule 1 by performing the lookup of entity 1 starting from node 2.

Explanation

Condition: $n=e$

The search will begin at node 2. Applying the first rule, we will check what the entities node 2 is responsible for. Since it contains the entity we are looking for, we return the node identifier as the output of the lookup.

Case 2

This case includes the application of rule 2 by performing lookup of entity 4 starting from node 2.

Explanation

Condition: $n<e$$\&$ $e<FT_{n}[1]$

The search will begin at node 2. Applying the first rule, we will check what the entities node 2 is responsible for. Since it does not contain the entity we are looking for, we move on to check if the second rule is applicable.

The node ID is less than the entity ID. Thus, it satisfies the first condition. Also, the entity ID is less than the first entry in the finger table of node 2, which makes the second condition true as well. We return the first successor node ID as the output of the lookup.

Case 3

This case includes the application of rule 3, performing lookup of entity 6 starting from node 2.

Explanation

Condition: $FT_{n}[j] < e$ $\&$$e\le FT_{n}[j+1]$

The search will begin at node 2. Applying the first rule, we will check what entities node 2 is responsible for. Since it does not contain the entity we are looking for, we move on to check if the second rule is applicable.

The node ID is greater than the entity ID, which makes the first condition false. The entity ID is greater than the first entry in the finger table of node 2, which makes the second condition false as well. Rule 2 does not apply, so we will move on to rule 3.

The second successor node ID is less than the entity ID, and the entity ID is less than the third successor node, which makes both conditions true. Hence, we return the ID of successor node 3.

Do it yourself

Use the knowledge of the 3 rules of lookup discussed above to solve this question. If you get stuck, use the solution below to help you understand the problem.

Perform lookup of entity 0 starting from node 5.

Conclusion

The Chord distributed hash table uses an $m$ bit circular identifier space, which uses a hash function to assign identifiers to nodes and entities. Each node is responsible for entities with identifiers less than/equal to its identifier value. Finger tables make the lookup in a Chord DHT more time efficient as it contains shortcuts to other nodes. Thus, for lookup, we don’t need to explore every node until we find what we are looking for.