负载均衡算法

对服务器均衡请求，达到每个服务器能够均衡处理请求。

常见算法

  • 随机访问：可能每次都在一个服务器上，并不能分布均匀到每个服务器上
  • 轮询：请求均匀分配，但是服务器性能差异无法解决
  • 权重轮询：可提前根据服务器性能来配置权重，但是配置后无法动态配置
  • Hash取模：通过对服务器个数取模来选择服务器，但是如果其中增加或者减少服务器，会导致取模结果不一致，例如 原来只有3台服务器，新增一台但是hash(key)是一致的，但是mod不一样数字，结果是不一致的。这样如果新增的服务器是有问题的，就会导致请求失败。业务不能正常执行。
  • hash一致性：增删对原hash结果影响较小，每个节点获取也相对均匀

Hash一致性

下方节点ABC放在hash环上， 但是这样会导致大部分hash后到节点A上, 造成hash倾斜。

image-20231126203418022

这种问题，可以通过虚拟节点来将原来的节点扩容翻倍，再放到hash环上。从而尽量均衡

image-20231126210207242

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class ConsistentHashing {

    private final SortedMap<Integer, String> circle = new TreeMap<>();
    private final List<String> nodes = new ArrayList<>();
    private final int numberOfReplicas;

    public ConsistentHashing(List<String> nodes, int numberOfReplicas) {
        this.numberOfReplicas = numberOfReplicas;
        this.nodes.addAll(nodes);
        for (String node : nodes) {
            addNode(node);
        }
    }

    public void addNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = getHash(node + i);
            circle.put(hash, node);
        }
    }

    public void removeNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = getHash(node + i);
            circle.remove(hash);
        }
    }

    public String getNode(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = getHash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    private int getHash(String input) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            md.update(input.getBytes());
            byte[] digest = md.digest();
            return byteArrayToInt(digest);
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("Unable to find MD5 algorithm");
        }
    }

    private int byteArrayToInt(byte[] bytes) {
        int value = 0;
        for (int i = 0; i < Math.min(bytes.length, 4); i++) {
            value |= (bytes[i] & 0xFF) << (8 * i);
        }
        return value;
    }

    public static void main(String[] args) {
        List<String> nodes = new ArrayList<>();
        nodes.add("Node1");
        nodes.add("Node2");
        nodes.add("Node3");

        ConsistentHashing consistentHashing = new ConsistentHashing(nodes, 160);

        System.out.println("Key1: " + consistentHashing.getNode("Key1"));
        System.out.println("Key2: " + consistentHashing.getNode("Key2"));
        System.out.println("Key3: " + consistentHashing.getNode("Key3"));

        consistentHashing.addNode("Node4");
        consistentHashing.addNode("Node5");

        System.out.println("Key1: " + consistentHashing.getNode("Key1"));
        System.out.println("777: " + consistentHashing.getNode("777"));
        System.out.println("Key3: " + consistentHashing.getNode("Key3"));
    }
}