If the distributed storage of data is needed in large and highly concurrent systems and the data is expected to be evenly distributed and scalable, the consistent hash algorithm can perfectly solve this problem. The application of the consistent hash algorithm can cache Hadoop ES distributed database in many fields
Principle of consistent Hash algorithm
The consistent Hash algorithm is modulo, and the consistent Hash algorithm is modulo 32 squared of 2. That is, the consistent Hash algorithm organizes the entire Hash space into a virtual circle. The value space of the Hash function is 0 ~ 2^ 32-1 (a 32-bit unsigned integer). The entire Hash ring is as follows: Hash value is a nonnegative integer, some properties of clusters such as node name hash value on the ring, the data key hash values are also on the ring, in accordance with the clockwise direction is to find the nearest node in it, the whole circle group in a clockwise direction, ring 0 points on the right side of the first dot represents the n1 server, and so on. We Hash each server using Hash. Specifically, we can choose the IP or host name of the server as the keyword to Hash, so that each server is determined to a position in the Hash ring. For example, we have three machines, and the position in the ring space after using IP address Hash is shown in the figure:
Calculate the Hash value of the data Key using the same function Hash, and determine the position of the data on the ring. From this position, search clockwise along the ring, and the server encountered is the server to which it should be located.
The positions of O1,O2 and O3 in ring space after hashing are as follows: O1–> N1 O2–>n2 O3–> N3
Fault tolerance and extensibility of consistent Hash algorithms
Now, suppose our N3 goes down. As we can see from the diagram, N1 and N2 will not be affected, and only THE O3 object will be relocated to N1. So we found that in the consistent Hash algorithm, if a server is unavailable, the only data affected is the data between that server and the previous server in its ring space. As shown in the figure:
Now we have added a server N4 to the system, as shown in the figure
The consistent Hash algorithm only needs to relocate a small part of the data in the ring space for the increase or decrease of nodes, which has good fault tolerance and scalability. When there are too few service nodes in the consistent Hash algorithm, it is easy to cause data skew (most cached objects are cached on a certain server) due to uneven node distribution, as shown in the following figure:
At this time, we find that A large amount of data is concentrated on node A, while node B has only A small amount of data. 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 server node and places a service node, called a virtual node, in each computed result position. The specific operation can be realized by adding the number after the server IP or host name, as shown in the figure: for example, for an N1 node, we have 100 virtual nodes, and the virtual node on the ring is the virtual node. Similarly, N2 and N3 also have 100 virtual nodes.
How do you decide which server to put the data on when it comes in
In this way, data can be evenly distributed by adding virtual nodes. The more virtual nodes there are, the more data there are. Generally, 200 virtual nodes can be placed on a server
The data location algorithm remains the same. Only one step needs to be added: the mapping between virtual nodes and real points. Therefore, after virtual nodes are added, data can be evenly distributed even when there are few service nodes. The above cases are uniformly distributed when the data is ideal. In fact, the consistent Hash algorithm has a data skew problem
Algorithmic interface class
public interface IHashService {
Long hash(String key);
}
Copy the codeAlgorithm interface implementation class
Public class HashService implements IHashService {/** * MurMurHash algorithm, high performance, low collision rate ** @param key String * @return Long
*/
public Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
returnh; }}Copy the codeAnalog machine node
public class Node<T> {
private String ip;
private String name;
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) { this.name = name; } /** * use the IP addresshashKey * * @return String
*/
@Override
public String toString() {
returnip; }}Copy the codeConsistent Hash operation
Public class ConsistentHash<T> {// Hash function interface Private Final IHashService IHashService; // Number of virtual nodes associated with each machine node private final int numberOfReplicas; Private final SortedMap<Long, T> circle = new TreeMap<Long, T>(); public ConsistentHash(IHashService iHashService, int numberOfReplicas, Collection<T> nodes) { this.iHashService = iHashService; this.numberOfReplicas = numberOfReplicas;for(T node : nodes) { add(node); }} @param node T */ public void add(T node) {for(int i = 0; i < this.numberOfReplicas; i++) { circle.put(this.iHashService.hash(node.toString() + i), node); }} @param node T */ public void remove(T node) {for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.iHashService.hash(node.toString() + i));
}
}
public T get(String key) {
if (circle.isEmpty()) return null;
long hash= iHashService.hash(key); // Find a virtual node clockwise around the ringif(! circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash); }}Copy the codeThe test class
Public class TestHashCircle {// Machine node IP prefix private static final String IP_PREFIX ="192.168.0."; Public static void main(String[] args) {// The number of records stored on each real machine node Map<String, Integer> Map = new HashMap<String, Integer>(); List<Node<String>> Nodes = new ArrayList<Node<String>>();for(int i = 1; i <= 10; i++) { map.put(IP_PREFIX + i, 0); Node<String> Node = new Node<String>(IP_PREFIX + I,"node"+ i); nodes.add(node); } IHashService iHashService = new HashService(); ConsistentHash<Node<String>> ConsistentHash = new ConsistentHash<Node<String>>(iHashService, 500, nodes); // Store 5000 records on 10 machine nodes as evenly as possiblefor(int i = 0; i < 5000; I ++) {// Generate a random String as a record, which can be other more complex business objects, such as a random String equivalent to the object's business unique identifier String data = uuid.randomuuid ().toString() + I; Node<String> Node = consistenthash.get (data); // Other tools can be used to store records on real machine nodes, such as MemoryCache, etc. Map.put (node.getip (), map.get(node.getip ()) + 1); } // Prints the number of records kept by each real machine nodefor (int i = 1; i <= 10; i++) {
System.out.println(IP_PREFIX + i + "Node record number:"+ map.get(IP_PREFIX + i)); }}}Copy the codeThe running results are as follows:
