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,TreeMapThe right subtree of each node is the smallest and nearest node larger than a hashcode.The whole core of the algorithm is also based onTreeMapImplementation, 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 objectThe 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