负载均衡算法

负载均衡算法

随机

image.png

调用关系如上图（简化了公网->防火墙处理），适合场景：所有服务器性能基本一致，且无超阈值流量。

1
2
3
4
5
private K doSelect(List<K> nodes, String ip) {
    // 在列表中随机选取一个节点
    int index = random.nextInt(nodes.size());
    return nodes.get(index);
}

如果存在部分机器性能更优，此时可以在随机基础上增加权重，升级为：随机权重算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private K doSelect(List<K> nodes, String ip) {
    int length = nodes.size();
    AtomicInteger totalWeight = new AtomicInteger(0);
    for (K node : nodes) {
        Integer weight = node.getWeight();
        totalWeight.getAndAdd(weight);
    }

    if (totalWeight.get() > 0) {
        int offset = random.nextInt(totalWeight.get());
        for (N node : nodes) {
            // 让随机值 offset 减去当前node权重值
            offset -= node.getWeight();
            if (offset < 0) {
                // 当前node大于随机值offset，返回此Node
                return node;
            }
        }
    }
    // 随机返回
    return nodes.get(random.nextInt(length));
}

轮询

img

轮询不再是在多台服务器随机挑选，而是按照顺序一个个排队调用，调用完再插入队尾等待下一次调用

1
2
3
4
5
6
7
8
9
protected K doSelect(List<K> nodes, String ip) {
    int length = nodes.size();
    // 如果位置值已经等于长度重置为0(走一轮了)
    position.compareAndSet(length, 0);
    N node = nodes.get(position.get());
    // 数据原子增加，对应调用从1->2->3->4
    position.getAndIncrement();
    return node;
}

同加权随机，轮询也同样存在加权轮询的场景，此时流量调度将发生如下变化：

img

此处逻辑相对复杂，笔者在此说出主要思路，后续有时间补充伪代码，感兴趣的可以参照Dubbo的实现

如上有服务器servers=[A,B]，对应权重weights=[3,1]，总权重为4。我们可以理解为有4台服务器，3台A，1台B，一次调用过来的时候，需要按顺序访问。如有5次调用，调用顺序为AAABA。

选举思路如下：

次数 WeightedRoundRobin 选择结果 选择后的WeightedRoundRobin
1 3、1 A 2、1
2 2、1 A 1、1
3 1、1 A 0、1
4 0、1 B 0、0(等于0-0时复原成：3、1)
5 3、1 A 2、1

最小活跃数

指：将当前请求转发到连接数/请求数最少的机器上，其特点是根据服务器实时运行状态动态分配，保障服务负载不会过饱和。如下图当请求4过来时，Nginx判断目前服务器1连接数>服务器2，故4会请求到服务器2上：

image.png

源地址哈希

根据请求源IP哈希计算得到一个数值，用该数值在候选服务器列表的进行取模运算，得到的结果便是选中的服务器，此操作可以保证固定IP的请求总是到某一台服务器上，伪代码如下：

1
2
3
4
5
private K doSelect(List<K> nodes, String ip) {
    int length = nodes.size();
    int index = hash(ip) % length;
    return nodes.get(index);
}

一致性哈希

相同的请求尽可能落到同一个服务器上。一致性哈希解决稳定性问题，可以将所有的存储节点排列在首尾相接的 Hash 环上，每个 key 在计算 Hash 后会 顺时针找到临接的存储节点存放。而当有节点加入或退出时，仅影响该节点在 Hash环上顺时针相邻的后续节点。