The consistent hash algorithm was developed in 1997 by Karger et al., MIT, in solving distributed Cache problems. It was designed to solve Hot spot problems in the Internet and has a very similar intent to CARP. Consistent hashing fixes a problem with simple hashing algorithms used by CARP, allowing DHT to be truly applied in P2P environments.
If you have studied the memcached database, you will know that the memcached server itself does not provide the consistency of the distributed cache. Instead, the client provides the consistency. To compute the consistency hash, follow the following steps:
- The first step is to compute the memcached server (node) hash and configure it on a continuum from 0 to 232.
- The hash value of the key that stores the data is then calculated in the same way and mapped to the same circle.
- The search then starts clockwise from the location to which the data is mapped, saving the data to the first server found. If no server is found beyond 232, it is saved to the first Memcached server.
Add a Memcached server from the status shown in the figure above. Remainder distribution affects cache hit ratio because the server where the key is saved changes dramatically, but Consistent Hashing affects only the first server key anticlockwise in continuum, as shown in the figure below:
Consistent Hash property
Considering that every node in a distributed system may fail, and new nodes are likely to be added dynamically, it is worth considering how to ensure that the number of nodes in the system can still provide good external services when the number of nodes changes. Especially when designing a distributed cache system, if a server fails, If you don’t use appropriate algorithm for the whole system to guarantee the consistency, the all data in the cache on the system may fail (namely due to system node number is less, the client requests when certain objects need to recalculate the hash value (usually related to the system of node number), because the hash value has changed, A consistent hash algorithm in a distributed CAhCE system should meet the following requirements:
- Balance (Balance)
Equilibrium means that the hash result can be distributed across all buffers as much as possible, so that all buffer space is used. Many hashing algorithms can satisfy this condition.
- Monotonicity (Monotonicity)
Monotonicity means that if something has been hashed to the corresponding buffer, and new buffers have been added to the system, the result of the hash should be such that the allocated content can be mapped to the new buffer, and not mapped to other buffers in the set of old buffers. Simple hashing algorithms often fail to meet the requirement of monotonicity, such as the simplest linear hash: x = (ax + b) mod (P), where P represents the size of the total buffer. It is not difficult to see that when the buffer size changes (from P1 to P2), all of the original hash results change, which does not satisfy the monotonicity requirement. Changes in the hash result mean that all mappings need to be updated across the system when the buffer space changes. However, in P2P system, the change of buffer is equivalent to the Peer joining or exiting the system. This situation occurs frequently in P2P system, so it will bring great computing and transmission load. Monotonicity requires that the hash algorithm be able to handle this situation.
- Dispersion (Spread)
In a distributed environment, it is possible for an endpoint to not see all of the buffering, but only some of it. When an endpoint wants to map content to a buffer through the hashing process, different terminals may see different buffer ranges, resulting in inconsistent hashing results. The final result is that the same content is mapped to different buffers by different terminals. This situation should obviously be avoided because it causes the same content to be stored in different buffers, reducing the efficiency of system storage. Dispersion is defined as the degree to which this happens. A good hash algorithm should be able to avoid inconsistencies as much as possible, that is, to minimize dispersion.
- Load (Load)
The load problem is really another way of looking at the dispersion problem. Since different terminals may map the same content to different buffers, it is also possible for a particular buffer to be mapped to different content by different users. Like dispersion, this situation should be avoided, so good hashing algorithms should minimize the buffering load.
- Smooth (Smoothness)
Smoothness means that the number of cache servers is smoothed in the same way that the cache objects are smoothed.
The principle of
The basic concept
Consistent Hashing algorithm (Consistent Hashing) first in the paper “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web In simple terms, consistent hashing organizes the entire hash space into a virtual ring. For example, if the value space of a hash function H is 0-2^32-1 (that is, the hash value is a 32-bit unsigned integer), the entire hash space ring is as follows:
The whole space is organized in a clockwise direction. Zero and 232-1 coincide in the direction of zero.
The next step is to Hash each server using the Hash. Specifically, the IP or host name of the server can be selected as the key word for the Hash, so that each machine can determine its position on the Hash ring. Here, it is assumed that the four servers in the above table will Hash with the IP address in the ring space as follows:
Next, use the following algorithm to locate the data access to the corresponding server: Hash the data key using the same function Hash, and determine the location of the data on the ring, “walk” clockwise along the ring from this location, the first server encountered is the server it should be located to.
For example, we have four data objects: Object A, Object B, Object C, Object D. After hash calculation, the position in the ring space is as follows:
According to the consistent hash algorithm, data A is assigned to Node A, B to Node B, C to Node C, and D to Node D.
The fault tolerance and scalability of the consistent hash algorithm are analyzed below. Now suppose Node C goes down. You can see that objects A, B, and D are not affected, and only object C is relocated to Node D. In general, in a consistent hash algorithm, if a server is unavailable, the data affected is only the data between that server and the previous server in its ring space (that is, the first server encountered along the counterclockwise path), and nothing else.
Let’s consider another case, if we add a server Node X to the system, as shown in the figure below:
In this case, objects A, B, and D are not affected, and only Object C needs to be relocated to the new Node X. In general, in a consistent hash algorithm, if you add a server, the data that is affected is only the data between the new server and the previous server in its ring space (that is, the first server encountered in the counterclockwise direction), and the rest of the data is not affected.
In conclusion, the consistent hash algorithm only needs to relocate a small part of the data in the ring space when the nodes are increased or decreased, which has good fault tolerance and scalability.
In addition, when the consistent hash algorithm has too few service nodes, it is easy to cause the data skew problem because of the uneven node segment. For example, there are only two servers in the system, and the ring distribution is as follows:
In this case, A large amount of data will inevitably be concentrated on Node A, while only A small amount will be located on Node B. In order to solve this data skewness problem, consistent hashing algorithm introduces virtual node mechanism, that is, compute multiple hashes for each service node, and place one of the service nodes in each calculated result position, which is called virtual node. You can do this by adding a number to the server IP address or host name. For example, three virtual nodes can be calculated for each server, so the hash values of “Node A#1”, “Node A#2”, “Node A#3”, “Node B#1”, “Node B#2”, and “Node B#3” can be calculated separately, resulting in six virtual nodes:
At the same time, the data location algorithm remains the same, but there is an additional step to map virtual nodes to actual nodes. For example, the data located to “Node A#1”, “Node A#2”, and “Node A#3” are all located to Node A. This solves the problem of data skew when the number of service nodes is small. In practical applications, the number of virtual nodes is usually set to 32 or more, so that even a few service nodes can achieve relatively uniform data distribution.
JAVA code implementation
package org.java.base.hash; import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import java.util.Set; import java.util.SortedMap; import java.util.SortedSet; import java.util.TreeMap; import java.util.TreeSet; public class ConsistentHash<T> { private final int numberOfReplicas; NumberOfReplicas = number of virtual nodes private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>(); Public ConsistentHash(int numberOfReplicas, int numberOfReplicas) Collection<T> nodes) { this.numberOfReplicas = numberOfReplicas; for (T node : nodes){ add(node); } } public void add(T node) { for (int i = 0; i < numberOfReplicas; I++){// for an actual machine node node, NumberOfReplicas virtual nodes /* * Different virtual nodes (I is different) have different hash values, but they all correspond to the same actual machine node * Virtual nodes are distributed evenly across the ring, and data is stored on clockwise virtual nodes */ String nodestr =node.toString() + i; int hashcode =nodestr.hashCode(); System.out.println("hashcode:"+hashcode); circle.put(hashcode, node); } } public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) circle.remove((node.toString() + i).hashCode()); } public T get(Object key) {if;} public T get(Object key) {if; (circle.isEmpty()) return null; int hash = key.hashCode(); Println (" hashCode ----->:"+hash); if (! SortedMap<Integer, T> tailMap = circle.tailMap(hash); SortedMap<Integer, T> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); } public long getSize() { return circle.size(); } public void testBalance(){Set<Integer> sets = circle.keyset (); SortedSets = new TreeSet<Integer>(sets); sortedSets= new TreeSet<Integer>(sets); For (Integer hashCode: sortedSets){system.out.println (hashCode); } System.out.println("----each location 's distance are follows: ----"); Iterator<Integer> it = sortedSets.iterator(); Iterator<Integer> it2 = sortedSets.iterator(); if(it2.hasNext()) it2.next(); long keyPre, keyAfter; while(it.hasNext() && it2.hasNext()){ keyPre = it.next(); keyAfter = it2.next(); System.out.println(keyAfter - keyPre); } } public static void main(String[] args) { Set<String> nodes = new HashSet<String>(); nodes.add("A"); nodes.add("B"); nodes.add("C"); ConsistentHash<String> consistentHash = new ConsistentHash<String>(2, nodes); consistentHash.add("D"); System.out.println("hash circle size: " + consistentHash.getSize()); System.out.println("location of each node are follows: "); consistentHash.testBalance(); String node =consistentHash.get("apple"); System.out.println("node----------->:"+node); }}Copy the code