By

Contents
  1. 1. 1.DHT Network
  2. 2. 2.RESTful
  3. 3. 3.Final
    1. 3.0.1. Related articles across the web

1.DHT Network

DHT(Distributed Hash Tables)is a class of a decentralized distributed system that provides a lookup service similar to a hash table; (key, value) pairs are stored in a DHT, and any participating node “Node (networking)”) can efficiently retrieve the value associated with a given key. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

The key idea for the DHT network is utilize the pair(key,value) to store and retrieve the data in distributed system.

1:Every resource has a uniquepair(key,value) to distinguish.

2:System will use hash function to process every key,and use the result to determine where this resource should be stored in the DHT network.

3:When a user want to get the resource,use the same algorithm to hash the key and get the destination of the resource.

Maybe you didn’t know what I am saying now,but I will use the real model to realize this algorithm and then you will know the key idea about the DHT.After used this algorithm,the DHT network has a new key feature different from other distributed system like the GFS(The Google File System).Every node(a computer in the DHT network) is both client and server,to responsible for a small route and storage in its area.So DHT don’t need a “super computer” to know everything in the system.This is why DHT is called decentralized distributed system.

Tips:In the GFS,system need to use a master to “control” everything.It needs to know all the information in the distributed system.Obviously,The masteris the bottleneck in this system,but google has done a lot of optimize in the system,so it is very useful,more information about GFS,you can see the paper in the reference below.
 

In that case,DHT can be very scalability because it isn’t limited from the central control like the master in the GFS.So it is beneficial to store the huge amount of data in a distributed network.The famous application is the NoSQL database such as Cassandraby facebook and Dynamo) by Amazon.

There are a lot of different way to realize the DHT algorithm like Ring, Tree, Hypercube, Skip List, BuVerfly Network, …I have used the chord) to do that because it is easy to explain and use.

45b48d324a1089fc21efa&690

figure 1

Step to realize the algorithm:

1:Every computer in the DHT network is a node which means it is responsible for store the data and route.In the figure1,each computer is represented as N1,N8,N14,N21……

2:Every resource is a pair(key,value).The resource can be everything such as the movie,music or the data in the application.The resource name will be hashed into a key and stored in a node.The resource is represented as K10,K24,K30…..The number is the key number of the resource.

3:The rule to store the resource in the computer(node) is that the resource is stored in the node which node number is bigger than resource key and the closest to that resource.For instance,the K10 need to store in N14 because N14 is bigger than 10 and N14 is the closest node to the K10.So K30 and K24 is stored in N32.In that case,once a new resource want to be stored in the DHT network,the resource name will be hashed into a key value and then use this value to determine where the resource should be stored.(This point is very important to understand the DHT network,if you can’t even understand what I am saying now,back to the step1 again.)

45b48d324a1089fd1ebbd&690

 

figure 2

Now,you should know how to store a resource in a node.But how to realize it?

rule:every node has its own finger table to route.FINGERN(i) = min {IDN2 | IDn2 ≥ IDn + 2^i (mod M)}

In the figure 2:

N8+1=N9,N9 belong to N14

N8+2=N10,N10 belong to N14

N8+8=N16,N16 belong to N21

For example,if one resource enter in the system and the key value is 22,so it is called K22.Once K22 enter in the system from the N8 and then retrieve the finger table,N8+8 is 16,N8+16 is 24.The K22 is between 16 and 24.So the K22 go to the 16 which is N21.And then use the N21 finger table to retrieve.

 

45b48d324a1089fffe1be&690

 

figure 3

If the key value is bigger than any number of the finger table,use the biggest one.Figure 3 show this condition.Screen Shot 2014-11-08 at 01.52.25

figure 4

Figure 4 show the detail about the route process.

So,what is the algorithm complexity?It is same to the finger table size!With high probability, Chord contacts O(log N) nodes to find a successor in an N-node network.

2.RESTful

The RESTful(Representational state transfer) is used to connect each node.It is easy to use because it only use the HTTP command which is familiar to us.Every node has RESTful client and server,so they can send the request to another and get the response.

In the client side,the client send the http request to the server side and get a Response from the server.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private Response getRequest(URI uri) {
		try {
			Response cr = client.target(uri)
					.request(MediaType.APPLICATION_XML_TYPE)
					.header(Time.TIME_STAMP, Time.advanceTime())
					.get();
			processResponseTimestamp(cr);
			return cr;
		} catch (Exception e) {
			error("Exception during GET request: " + e);
			return null;
		}
	}
public String[] get(NodeInfo n, String k) throws Failed{
		UriBuilder ub = UriBuilder.fromUri(n.addr);
		URI getPath = ub.queryParam("key", k).build();
		info("client get("+getPath+")");
		Response response=getRequest(getPath);
		if (response == null || response.getStatus() >= 300) {
			throw new DHTBase.Failed("GET ?key="+k+"addr="+n.addr);
		} else {
			return response.readEntity(tableRowType).getValue().vals;
		}
	}

In the server side,you can use the annotation to identify the path and response the request.

1
2
3
4
5
6
@GET
@Path("info")
@Produces("application/xml")
public Response getNodeInfoXML() {
	return new NodeService(headers, uriInfo).getNodeInfo();
}

The more detail about the RESTful you can see the wiki and the paper in the UCI.

3.Final

This is my first time to write a English technology passage,so if you have found there are some errors or someplace you didn’t understand yet,please do not hesitate to contact me through the email liulin.jacob@gmail.comor leave a message below the passage.I am glad to receive your email.If you have some comment about my blog,I am appreciated to learn from you.

Thank you,have fun

lin

liulin.jacob@gmail.com

 

References:

Contents
  1. 1. 1.DHT Network
  2. 2. 2.RESTful
  3. 3. 3.Final
    1. 3.0.1. Related articles across the web