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

This article is about how to implement the Consistent Hashing algorithm. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

There are many load balancing algorithms to choose from when doing server load balancing, including: round robin algorithm (Round Robin), hash algorithm (HASH), least connection algorithm (Least Connection), response speed algorithm (Response Time), weighting method (Weighted) and so on. Among them, hash algorithm is the most commonly used algorithm.

A typical application scenario is that there are N servers that provide caching services, and the servers need to be load balanced, and requests are distributed evenly to each server, and each machine is responsible for the service of 1max N.

The commonly used algorithm is to take the remainder (hash () mod N) of the hash result: for the machine number from 0 to Nmuri 1, according to the custom hash () algorithm, the hash () value of each request is modularized by N to get the remainder I, and then the request is distributed to the machine numbered I. However, this algorithm has a fatal problem. If a machine is down, the requests that should fall on the machine cannot be processed correctly, and the pawned server needs to be removed from the algorithm. At this time, the cached data of the (Nmur1) / N server will need to be recalculated; if a new machine is added, the cached data of the N / (Numb1) server will need to be recalculated. This is usually an unacceptable jolt for the system (because it means that a large number of caches are invalidated or data needs to be transferred). So, how do you design a load balancing strategy to minimize the number of requests affected?

Consistent Hashing algorithm is used in Memcached, Key-Value Store, Bittorrent DHT and LVS. It can be said that Consistent Hashing is a load balancing algorithm for distributed systems.

1. Description of Consistent Hashing algorithm

Let's take the Consisten Hashing algorithm in Memcached as an example (see memcached's distributed algorithm).

Because the result of hash algorithm is generally unsigned int, the result of hash function should be evenly distributed between [0232-1]. If we cut a circle uniformly with 232points, we first calculate the hash value of the server (node) according to the hash (key) function, and distribute it to the circle of 0,232.

Use the same hash (key) function to find the hash of the key that needs to store the data, and map it to the circle. Then start looking clockwise from the location to which the data is mapped, and save the data to the * * servers (nodes) found.

Schematic diagram of Consistent Hashing principle

1. Add a new node: only the data between the new nodes on the ring and the counterclockwise nodes will be affected (the information of increasing the nodes clockwise will need to be migrated to the added nodes).

two。 Delete a node: only the data between the original deleted node on the ring and the counterclockwise * * node will be affected (the information of the deleted node needs to be migrated to the clockwise * node). Therefore, the problem of hash value turbulence caused by new and deleted nodes in load balancing is well solved through Consistent Hashing.

Consistent Hashing add server schematic diagram

Virtual nodes (virtual nodes): virtual nodes are introduced because when the number of servers (nodes) is small (for example, there are only 3 servers), the hash values of nodes calculated by hash (key) are not evenly distributed (sparse) on the ring, and the load imbalance of each node still occurs. The virtual node can be thought of as a replicas of the actual node, which is essentially the same as the real node (the key is not the same). After the introduction of virtual nodes, the number of each actual server (node) is expanded by a certain proportion (for example, 200x) and its hash (key) value is calculated to distribute evenly to the ring. In load balancing, the hash value that falls on the virtual node actually falls on the actual node. Because all the actual nodes are copied into virtual nodes according to the same proportion, the problem of uniform distribution of hash values on the ring with a small number of nodes is solved.

The influence of Virtual Node on Consistent Hashing result

As can be seen from the above figure, when the number of virtual nodes of each actual node is 100-200 times that of the actual node when the number of nodes is 10, the result is still very balanced.

2. Implementation of Consistent Hashing algorithm:

The Java implementation of Consistent Hashing is described in the article Consistent Hashing, which is very concise.

Import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHash {private final HashFunction hashFunction; private final int numberOfReplicas; private final SortedMap circle = new TreeMap (); public ConsistentHash (HashFunction hashFunction, int numberOfReplicas, Collection nodes) {this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; for (T node: nodes) {add (node) } public void add (T node) {for (int I = 0; I < numberOfReplicas; iTunes +) {circle.put (hashFunction.hash (node.toString () + I), node);}} public void remove (T node) {for (int I = 0; I < numberOfReplicas; iTunes +) {circle.remove (hashFunction.hash (node.toString () + I)) }} public T get (Object key) {if (circle.isEmpty ()) {return null;} int hash = hashFunction.hash (key); if (! circle.containsKey (hash)) {SortedMap tailMap = circle.tailMap (hash); hash = tailMap.isEmpty ()? Circle.firstKey (): tailMap.firstKey ();} return circle.get (hash);}} Thank you for reading! This is the end of the article on "how to implement the Consistent Hashing algorithm". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it out for more people to see!

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.