Distributed Hash Table(DHT)

0. Why:
In network scenario, the data is distributedly stored among a collection of machines.
Distributed Lookup Services deal with the problem of locating data that
is distributed among a collection of machines.

There are three basic approaches we can take to locate such data:
1. centralized server
2. flooding
3. distributed hash tables

For centralized server approach, a central server holds the entire database to serve the action of lookup
which server contain the data being looked up. However, it can be a problem
if a central server is not reliable or dead.

For flooding approach,  via peer to peer forwarding the loop-up, the peer who has the data can respond whoever sent the look-up request. However, the problem is that peers were not always
reliable up or fast (especially those connected to slow modems).

1. What:
In a distributed implementation, known as a distributed hash table, or DHT,
the hash table is distributed among a set of nodes. Nodes all use the same hash function.

The entire goal of a DHT is to allow anyone to find the node that corresponds to a given key.
that node will be responsible for holding the information associated with that key. So looking up a key gives you a node ID that holds the data.

A key difference between the DHT approach and the centralized or flooding approaches is that
a specific node is responsible for holding information relating to the key (even if it just sends a link to the content). However, in DHT, any node can hold the information relating which node ID holds the data.

2. How
For the implementation of DHT, there are two approaches to do it
1. chord
2. CAN, a Content-Addressable Network

Chord
Hash Function = hash(IP)%(n) = position index = 0,1,2,...n
IP is IP address and n refers to the number of node in a ring, thinking of a sequence of numbers in a logical ring, 0,1,2,.....n, and looping back to 0. Each node occupies a position this ring.

A (key,value) would be stored at a node that matches hash(key).
If there is no node at that position, the next node ahead of that number is responsible for storing the data. This is the next node you hit if you traverse the ring clockwise starting from that hash(key) position. This node (the next node of hash(key) ) is called the successor node. => Look up

When a node "joins" a network at some position j, where j = hash(node's IP), some (key,value) data has to migrate from successor's node to this new node. => Insert

For routing queries, a node only needs to know of its successor node. Queries can be forwarded through successors until a node that holds the value is found.

However, the problem would arise if it traverse the entire circle. To avoid this worst case and increase performance, nodes may maintain a table containing additional routing information about other nearby nodes. The reason is when a node needs to locate one that is farther away, it contacts the furthest node that knows about which node is nearby node of wanted located node. It means contacting the node whose ID is less than the hash(key) and asking it to locate the node for hash(key). The process can be repeated recursively to locate the node.


CAN, Content-Addressable Network
CAN use 2D hash function to locate the node that holds the key and value pair. It means thinking of a grid and two seperate hash function hash_x(key) and hash_y(key). The key is hashed with both of them and produce x = hash_x(key) and y = hash_y(key) coordiante value. The node responsible for the location (x,y) stores (key,value).

A node only knows about its immediate nodes. For looking up and routing messages to the node that holds the data it needs, it will use neighbors that minimize the distance to the destination.

A new node is inserted is inserted by the following process:
1. pick up a random pair of values in the grid (i,j)
2. cotact some node in the grid and ask it look up the node that is responsible for location (i,j)
3. Negotiate with that node to split its zone in half. The new node will own half of this area (i,j)
=> Insert

3. Implementation
Some essential elements to do the implementation:

1. Network overlay : it is very simple to simulate overlay, you can use a simple Circular Linked List, where each node points to a successor node forming the circular list.

2. Choosing Node ID: by hashing the Nodes IP, using a consistent hash function like SHA-1, a m bit identifier is generated which is set as the Node Id. Similarly, the value is hashed to generate a m bit identifier to be used as the key. Any key has to be of the same range of the Node Id so that they can be compared.

3. Store (insert)

# This is a clockwise ring distance function.
# It depends on a globally defined k, the key size
# The largest possible node id is 2**k
# Returns the node which is closest to the key
public Node closest_node(Node node, Node successor, int key)
{
if ( node.id > successor.id ) // 2^4 - 2(successor.id) - 6 > 6 - 4(node.id)
{
if ( (pow(2,k) - successor.id - key) > (key-node.id) )
return node;
else
return successor;
} 
}
else
{ 
if ( ( key - node.id) > ( successor.id - key )  )
{
return successor;
 }
else
{
 return node;
 }

}
}

# Find the responsible node and get the value for the key
public int lookup(Node start, int key)

    Node node = find_node(start, key);
    return node.value// node.data[key];
}

5. Analysis