Shulou(Shulou.com)06/03 Report--

This article mainly explains "what is consistent hash". Friends who are interested may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "what is consistent hash"?

What is Hash?

Hash is the input of arbitrary length, through the hash algorithm, transformed into a fixed length output, the output is the hash value. For example, Integer.hashCode (), String.hashCode (), etc. Even if the input content is inconsistent, it may lead to the output hash value consistent, this case is hash collision, hash collision is inevitable, it is not easy to design an efficient hash algorithm.

Assuming that the service has four servers and multiple users to access our service, the following analysis uses this assumption

Analysis of ordinary Hash

When users come to visit my service, we simply calculate the number of requests and services until hash, and then distribute requests to different services according to the calculated hash.

Hash is calculated as hash = request% serverCount

Suppose there are four requests: request 1, request 2, request 3, and request 4. Now calculate the four requests and distribute the requests to different non-services. The result is as follows

Problems existing in ordinary Hash

From the figure above, we can see that we distribute different requests to the corresponding servers through calculation, but there will be some problems in this way, which we will analyze next.

Let's assume that server3 is down, and the distribution of requests after name recalculation is as follows

In practice, service downtime or expansion is very common. When downtime or expansion occurs, all the hash previously calculated need to be recalculated. In the production environment, we have many backend servers and clients, so the impact is very serious. Both capacity reduction and expansion will have such a problem. Requests from "quantity" customers will be routed to other servers for processing. All sessions of the subscriber in the original server will be lost.

Consistent Hashg concept

The emergence of consistent Hash solves the above problems, affecting the distribution of requests as little as possible in the event of downtime or expansion.

The idea of consistent Hash is as follows:

First of all, there is a straight line, which begins with 0 and ends with 2 to the 32 power minus 1, which is equivalent to an address, and then bends the line to form a ring to form a closed loop, which is the hash ring. We ask the server for hash and put the server in the corresponding position on the hash ring. When a request comes, we calculate the request, put the request in the corresponding position of the hash ring, and then get the nearest server node clockwise.

The schematic diagram is as follows

When a service outage or expansion occurs, request forwarding will also change. This time, I use the example of capacity expansion, which is the same as downtime.

If we add a server4 between server1 and server2, the request is forwarded as follows

From the above picture, we can draw a conclusion that when expansion or downtime occurs, it will only affect a very small number of users and maximize the improved experience.

Of course, there may be some problems with consistent hash. For example, as shown in the following figure, the distribution of servers is unreasonable, and a large number of requests fall on the same server, which puts great pressure on the service.

In view of this situation, we can add virtual nodes to distribute requests as reasonably as possible, so as to reduce the pressure on a certain service.

In the following figure, we add two virtual nodes to each node.

Implement normal Hash and consistent Hash ordinary Hash implement public static void main (String [] args) {String [] ips = new String [] {"101.1.1.1", "101.1.1.2", "101.1.1.3", "101.1.1.4"}; int serverCount = 4 for (String ip: ips) {System.out.println (ip + "requests are distributed to server" + ip.hashCode ()% serverCount) } System.out.println ("= = downtime split line = ="); / / simulate downtime a serverCount = 3 for (String ip: ips) {System.out.println (ip + "request is distributed to server" + ip.hashCode ()% serverCount);}}

Output

101.1.1.1 request distribution to server3101.1.1.2 request distribution to server0101.1.1.3 request distribution to server1101.1.1.4 request distribution to server2== downtime split line = = 101.1.1.1 request distribution to server1101.1.1.2 request distribution to server2101.1.1.3 request distribution to server0101.1.1.4 request distribution to server1 consistency Hash implementation without virtual Quasi-node implementation of public static void main (String [] args) {String [] serverIps = new String [] {"101.231.123.11" "11.1.112.234", "123.112.11.123", "232.12.11.22"} / / SortedMap hashServerMap = new TreeMap () for storing server; for (String ip: serverIps) {hashServerMap.put (Math.abs (ip.hashCode ()), ip);} / / client ipString [] clientIps = new String [] {"101.23.234.33", "11.1.112.2", "123.112.11.12", "23.121.11.22"} The for (String ip: clientIps) {/ / tailMap method returns a collection greater than the parameter SortedMap serverMap = hashServerMap.tailMap (Math.abs (ip.hashCode (); / / fetch the first server on the hash ring if (serverMap.isEmpty ()) {Integer firstKey = hashServerMap.firstKey (); the request for System.out.println (ip +) is distributed to "+ hashServerMap.get (firstKey)) } else {/ / the first server to get the result set System.out.println (the request from ip + "is distributed to" + hashServerMap.get (serverMap.firstKey ();}

Distribute the results

101.23.234.33 request distribution to 232.12.11.2211.1.112.2 request distribution to 123.112.11.123123.112.11.12 request distribution to 123.112.23423.121.11.22 request distribution to 123.112.11.123 with virtual node implementation public static void main (String [] args) {String [] serverIps = new String [] {"101.231.123.11", "11.1.112.234"} / / the number of virtual nodes per node int virtualNodeCount = 2; SortedMap hashServerMap = new TreeMap (); for (String ip: serverIps) {hashServerMap.put (Math.abs (ip.hashCode ()), ip); / / processing virtual node for (int I = 0; I < virtualNodeCount; inodes +) {hashServerMap.put (Math.abs ((ip + "#" + I). HashCode ()), ip + "#" + I) }} / / client ipString [] clientIps = new String [] {"101.23.234.33", "11.1.112.2", "123.112.11.12", "23.121.11.22"}; the for (String ip: clientIps) {/ / tailMap method returns a collection greater than the parameter SortedMap serverMap = hashServerMap.tailMap (Math.abs (ip.hashCode () / / fetch the first server if (serverMap.isEmpty ()) {Integer firstKey = hashServerMap.firstKey () on the hash ring; System.out.println (the request of ip + "is distributed to" + hashServerMap.get (firstKey));} else {/ / the first server of the result set System.out.println (the request of ip + "is distributed to" + hashServerMap.get (serverMap.firstKey ();}

Distribute the results

101.23.234.33 request to be distributed to 101.231.123.1111.112.2 request to 11.1.112.234123.112.11.12 request to 11.1.112.23423.121.11.22 request to 101.231.123.11 to this point, I believe you have a deeper understanding of "what is consistent hash", you might as well do it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.