Recently, when I was optimizing the departmental distributed scheduling task and reading xxL-job source code, I found that its load balancing logic used consistent hash algorithm. In fact, the consistent hash algorithm is also used in distributed cache clusters (such as Redis cluster) to improve the fault tolerance and scalability of the cache. As for xxL-job source code is not much to say, here only for the consistency of the hash algorithm analysis of a wave, in order to prepare for knowledge consolidation, but also to share with partners to grow together.

Hash algorithm and consistent hash algorithm

Speaking of consistent hash algorithms, I have to talk a little bit about hash algorithms, which is a term you hear a lot, how many of you actually know exactly what it is?

❝

A Hash is a Hash algorithm that transforms an input of any length (also known as a pre-mapped pre-image) into a fixed-length output, which is a Hash value. This transformation is a compression mapping, that is, the space of hash values is usually much smaller than the space of input, and different inputs may be hashed into the same output, so it is impossible to determine a unique input value from the hash value. Simply put, it is a function that compresses a message of any length into a message digest of a fixed length.

❞

To put it simply, a hash is a hash that “compresses” an input value into a smaller value, which is usually unique and extremely compact. Therefore, most business systems are microservice architectures, and the hash algorithm is not suitable for the natural distributed nature.

For example, in a distributed storage system, to store data to a specific node, if we use a common hash algorithm for routing, the data is mapped to a specific node, such as key%N, key is the key of the data, N is the number of machine nodes, a machine joins or exits the cluster, All data mappings are invalid. If persistent storage is used, data migration is performed, and distributed caches are used, and other caches are invalidated. A large amount of data is rehash, affecting the normal running of the service system.

Is there nothing we can do at this point? Of course there is: consistent hash algorithms.

Consistent hash algorithm

❝

Consistent hashing algorithm was proposed by MIT in 1997. It is a special hashing algorithm to solve the problem of distributed cache. When removing or adding a server, the mapping between existing service requests and the server that processes them can be changed as little as possible. Consistent Hash solves the dynamic scaling problems of simple Hash algorithms in Distributed Hash tables (DHT).

❞

The consistent hash algorithm has the following characteristics:

Balance (Balance)

Equilibrium means that the result of hashing can be distributed among all the buffer nodes as much as possible, so that all the buffer space can be utilized. Many hash algorithms can satisfy this condition.

Monotonicity (Monotonicity)

Monotony refers to Consistent hashing that protects allocated content from being remapped to a new cache when the buffer size changes, thereby reducing significant rehashing and improving performance.

Dispersion (Spread)

In a distributed environment, it is possible for an endpoint to not see all of the caches, but only some of them. When the terminal wants to map the content to the cache through the hash process, different terminals may see different buffer scope, resulting in the hash result is inconsistent, the final result is the same content is mapped to different buffers by different terminals. This situation should obviously be avoided because it results in the same content being stored in different caches, reducing the efficiency of system storage.

Load (Load)

The problem of load is actually another way of looking at the problem of dispersion. Since different endpoints may map the same content to different cache instances, it is also possible for a particular cache instance to be mapped to different content by different users. Like dispersity, this should be avoided, so a good hash algorithm should minimize the buffering load.

Application scenarios

Let’s look at a specific scenario: how Redis uses consistent hash algorithms to ensure cache hit ratio, fault tolerance, and scalability.

  • First, the hash value of redis server (node) is calculated and configured to a continuum of 0 ~ 2 power 32.

  • The hash value of the key storing the data is then calculated using the same method and mapped to the same circle.

  • It then searches clockwise from the location to which the data is mapped, saving the data to the first server it finds. If no server is found beyond 2 ^ 32, it is saved to the first Redis server.


(This picture is stolen from Baidu Encyclopedia.) Add a Redis server from the state shown above. The remainder distributed algorithm will affect the hit ratio of the cache due to the change of the cache instance of the key. However, in the consistent hash algorithm, only a small part of the anti-clockwise hash with the added node (node5) will be affected, as shown in the figure below:


This approach works well for cache hit ratio, fault tolerance, and scalability, but when there are few service nodes, another problem is “data skewness”, where many keys are assigned to the same service instance. Such a hidden danger is also very big, if just a lot of key nodes fail, the use of the system will also cause a great impact. How to solve it? Virtual Node

For example, we have two servers on our system with the following ring distribution:


At this point, a large amount of data is bound to be concentrated on Redis2, while very little is located on Redis1. In order to solve the problem of data skew, the consistent hash algorithm introduces the virtual node mechanism, that is, it computes multiple hashes for each service node and places one service node for each computed result, which is called the virtual node. This can be done by adding a number after the server IP address or host name. For example, we decide to compute two virtual nodes for each server, so we can compute the hashes of “Redis2 #1”, “Redis2 #2”, “Redis1 #1”, and “Redis1 #2” respectively to form four virtual nodes:


At the same time, the data location algorithm remains the same, but the mapping between virtual nodes and actual nodes is added. For example, data located to Redis2#1 and Redis2#2 virtual nodes are located to Redis2. This solves the problem of data skew when there are few service nodes. In practical applications, the number of virtual nodes is usually set to 32 or more, so even data distribution can be achieved even with a few service nodes.

In the code

Lost so much, or to practice, otherwise just on paper, practice is the real knowledge. Approach!

package com.demo.hash;

import java.util.SortedMap;
import java.util.TreeMap;

/ * ** consistencyhashAlgorithm demo *  * @author dongx on 2020/9/18 * /public class ConsistentHashDemo {  / * ** List of servers to be added to the Hash ring* / private static String[] servers = {"10.0.0.1"."10.0.0.2"."10.0.0.3"};  / * ** key indicates the serverhashValue, value indicates the server* / private static SortedMap<Integer, String> sortedMap = new TreeMap<>();   / * ** Program initialization, all the servers into the sortedMap* / static {  for (int i=0; i<servers.length; i++) {  int hash = getHash(servers[i]);  System.out.println("[" + servers[i] + "] added to map with Hash value" + hash);  sortedMap.put(hash, servers[i]);  }  }  / * ** Get the node to which the route is routed * @param key  * @return * / private static String getServer(String key) { // Get the keyhashvalue int hash = getHash(key); // Get all maps greater than the Hash value. Here we use sortedMap with sorting function. There are many apis that are convenient SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);  if(subMap.isEmpty()){ // If there is no more than this keyhashIf the value is large, start from the first node Integer i = sortedMap.firstKey(); // Returns the corresponding server return sortedMap.get(i);  }else{ // The first Key is the node closest to the node clockwise Integer i = subMap.firstKey(); // Returns the corresponding server return subMap.get(i);  }  }  / * ** Compute the Hash value using the FNV1_32_HASH algorithm (standard algorithm found online) * @param str  * @return * / private static int getHash(String str) {  final int p = 16777619;  int hash = (int) 2166136261L;  for (int i = 0; i < str.length(); i++) {  hash = (hash ^ str.charAt(i)) * p;  }  hash+ =hash< < 13; hash^ =hash> > 7; hash+ =hash< < 3; hash^ =hash> > 17; hash+ =hash< < 5; // If the value is negative, take the absolute value if (hash < 0) {  hash = Math.abs(hash);  }  return hash;  }   public static void main(String[] args) {  String[] keys = {"The doctor"."Nurse"."Patients"};  for(int i=0; i<keys.length; i++) {  System.out.println("[" + keys[i] + The hash value of "] is ". + getHash(keys[i])  + ", is routed to node [" + getServer(keys[i]) + "]");  }   } }  Copy the code

This section of code I wrote a more clear annotation, the next partner can be combined with the previous content of the digestion. FNV1_32_HASH is a standard algorithm method found on the Internet.

The running results are as follows:


The end of the

Consistent hash algorithms are widely used in distributed scenarios, such as task scheduling and caching. For the majority of programmers, understanding this algorithm is very helpful to the problem investigation and analysis. In addition, for the interviewer, hash and consistency hash are commonly asked by the interviewer. For Java development, this is also a required course on the way to advanced. I hope you know more about it and will continue to share with you in the future.