Assumptions have relative knowledge of consistent Hash, if you don’t understand can look at www.zsythink.net/archives/11… Code address: github.com/zexho994/Co…
We know that the core idea of consistent hash is to modulo 2^32 and store it on a hash ring:
To implement a consistent Hash, resolve several issues:
- How do I represent this ring?
- How do I insert, delete, and find the nearest node on a ring?
- How are virtual nodes represented and inserted into rings?
Hash ring
Considering the characteristics of this hash ring, the position to which our node will be inserted is determined by the hash value of the node. Now there are two nodes A and B added, a.hash code = 50, b.hash code = 100. Since the ring is searched clockwise, the search logic is as follows:
- [0,50], (50,2^32) will find A
- The data of (50,100) will find B
You can find a feature that is ordered, and can support quickly find the next node,TreeMap
The right subtree of each node is the smallest and nearest node larger than a hashcode.The whole core of the algorithm is also based onTreeMap
Implementation, first declaredring
, all subsequent node data will be stored on the ring.
public class ConsistentHashManager {
private final SortedMap<Integer/* Index size */, Node/ * * / node> ring = new TreeMap();
}
Copy the code
Ring = key; val = Node; val = Node; ring = key; val = Node;
public class Node {
// Server name
private String name;
// Server domain name
private String host;
// Server port
private Integer port;
public Node(String name, String host, int port) {
this.name = name;
this.host = host;
this.port = port;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if(! (oinstanceof Node)) return false;
Node node = (Node) o;
return getPort() == node.getPort() && getName().equals(node.getName()) && getHost().equals(node.getHost());
}
@Override
public int hashCode(a) {
returnObjects.hash(getName(), getHost(), getPort()); }}Copy the code
Adding a New Node
To store a node on the ring, the first step is to know where to store it, which is determined by the size of the index, which requires calculationThe Node object
The index of the valueDeclare an interface object first. Since there may be various methods of computation in the future, there will be various concrete implementation classes, so the interface-based approach is used instead of an instance:
public interface HashUtil {
int hash(String key);
}
Copy the code
Here’s how to use MD5, which is definitely not the best way to do it, but to express what hash() does
public class Md5HashUtil implements HashUtil {
private MessageDigest messageDigest;
public Md5HashUtil(a) {
try {
this.messageDigest = MessageDigest.getInstance("MD5");
} catch(NoSuchAlgorithmException e) { e.printStackTrace(); }}@Override
public int hash(String key) {
this.messageDigest.update(String.valueOf(key).getBytes();
byte[] digest = this.messageDigest.digest();
int h = 0;
for (int i = 0; i < 4; i++) {
h |= ((int) digest[i]) & 0xFF;
// Loop 4 times, 8 bits each time, exactly 32 times
h <<= 8;
}
returnh; }}Copy the code
With the hash() method, we know the index value of the Node, and we can store the Node in the ring
public void addNode(Node node) {
ring.put(hashUtil.hash(node.getKey()), node);
}
Copy the code
So there’s one more thing to do, how do you add virtual nodes? At the beginning, I thought that to ensure even distribution, the distribution characteristics of virtual nodes should be as follows:
But the problem is, how do you keep the distribution even as you continue to add more physical nodes? That’s hard to do, but think about it another way: what are virtual nodes for? The idea is to make the distribution more even, to prevent the probability of a blood collapse, but even if these virtual nodes are randomly located, if there are enough of them, that’s what’s going to happen.
Perfect the addNode() method
public void addNode(Node node) {
ring.put(hashUtil.hash(node.getKey()), node);
for (int i = 0; i < this.virNodeCount; i++) {
this.ring.put(hashUtil.hash(node.getKey() + i), node); }}Copy the code
Remove nodes
The val stored in the ring is Node, which can be deleted by traversing the matching Node of the ring
public void removeNote(Node node) {
ring.entrySet().removeIf(next -> next.getValue().equals(node));
}
Copy the code
Gets the next node
This part of the code to understand the TreeMap API can be understood, is not difficult
public Node getNextNode(String key) {
SortedMap<Integer, Node> longNodeSortedMap = ring.tailMap(hashUtil.hash(key));
if (longNodeSortedMap.isEmpty()) {
return ring.get(ring.firstKey());
}
return longNodeSortedMap.get(longNodeSortedMap.firstKey());
}
Copy the code
test
Load balancing
@Test
void loadBalancingTest(a) {
ConsistentHashManager consistentHashManager = new ConsistentHashManager();
// Add four nodes
consistentHashManager.addNode(new Node("node1"."192.0.0.1".8080));
consistentHashManager.addNode(new Node("node2"."192.0.0.2".8080));
consistentHashManager.addNode(new Node("node3"."192.0.0.3".8080));
consistentHashManager.addNode(new Node("node4"."192.0.0.4".8080));
String preKey = "Data_";
// Map records the number of hits on each node
Map<String, Integer> map = new HashMap<>(200000);
map.put("node1".0);
map.put("node2".0);
map.put("node3".0);
map.put("node4".0);
// Suppose there is 20W data
for (int i = 0; i < 200000; i++) {
Node nextNote = consistentHashManager.getNextNote(preKey + i);
// Add the number of hits
map.computeIfPresent(nextNote.getName(), (k, v) -> v + 1);
}
/ / print
map.entrySet().forEach(System.out::println);
}
Copy the code
The overall ratio is 5:6:4.5:4.5
Hit ratio after nodes are deleted
@Test
void removeNodeTest(a) {
// omit the code to add nodes...
// Remove a node
consistentHashManager.removeNote(node4);
// Test the hit ratio after removing the node
AtomicInteger n1 = new AtomicInteger(0);
AtomicInteger n2 = new AtomicInteger(0);
AtomicInteger n3 = new AtomicInteger(0);
for (int i = 0; i < 200000; i++) {
Node nextNode = consistentHashManager.getNextNode(preKey + i);
if (nextNode.getName().equals("node1")) {
n1.incrementAndGet();
} else if (nextNode.getName().equals("node2")) {
n2.incrementAndGet();
} else if (nextNode.getName().equals("node3")) {
n3.incrementAndGet();
} else {
throw new RuntimeException("Node4 not cleaned up"); }}// Print hit ratio, original times/deleted times
statistic.forEach((key, value) -> {
if (key.equals("node1")) {
System.out.println("Node1, total access =" + n1 + ", valid access" + value + "Hit ratio =" + (double) (value) / n1.get());
} else if (key.equals("node2")) {
System.out.println("Node2, total accesses =" + n2 + ", valid access" + value + "Hit ratio =" + (double) (value) / n2.get());
} else if (key.equals("node3")) {
System.out.println("Node3, total visits =" + n3 + ", valid access" + value + "Hit ratio =" + (double) (value) / n3.get()); }}); }Copy the code