背景
A项目部署在三台机器，A机器（4c2g）、B机器（2c2g）、C机器（1c2g）
如何才让请求** 聪明 **地分发在三台机器？
负载均衡分类
- 基于硬件的负载均衡：比如F5等专门的负载均衡设备，通常具有更强大的性能和功能，能够处理大规模的流量和应用需求。
- 基于软件的负载均衡：比如Nginx、HAProxy等，这些软件可以通过安装在普通服务器上来实现负载均衡，通常有一定的性能和功能限制，但是适合中小规模的应用负载均衡需求。
- DNS负载均衡：通过DNS服务器根据域名解析返回不同的IP地址，从而将请求分发到不同的服务器上，实现负载均衡。LVS（Linux Virtual Server）也可以归类为这一类，它是一种基于Linux内核的负载均衡方案，可以通过网络地址转换（NAT）、直接路由（DR）、IP隧道（TUN）等方式实现负载均衡。
加权轮询算法
原始加权轮询算法：
算法思想：
- 轮询所有节点，寻找权重最大节点
- 选中节点，然后将权重减1
- 当所有节点权重都为0时，重置权重
这样的算法存在一个问题：机器A权重为4，那么前2个请求一定会打在机器A上面，造成权重大的机器压力过大，权重小的机器C一直在空闲（我能力小，不代表我一个请求都不能处理），假如权重为 {A:10,B:1,C:1} 会放大这一现象。
优化后加权轮询算法：
算法思想：
- 计算totalWeight
- 开始时计算全部节点的 currentWeight = currentWeight + weight
- 选中 currentWeight 最大的节点，并设置 currentWeight = currentWeight - totalWeight
看到这里，你可能疑惑为什么currentWeight会有一个轮回，应该有一个数学论证，但是我不会。
/**
* @author: wangjiangtao
* @description
* @date: 2023/12/19 15:03
*/
@Setter
@Getter
@ToString
public class Node implements Comparable<Node> {
// 服务器IP
private String ip;
// 固定权重
private int weight;
// 当前权重
private int currentWeight;
public Node(String ip, int weight) {
this.ip = ip;
this.weight = weight;
this.currentWeight = 0;
}
@Override
public int compareTo(Node node) {
return this.getCurrentWeight() - node.getCurrentWeight();
}
}
/**
* @author: wangjiangtao
* @description
* @date: 2023/12/19 15:03
*/
public class WeightedRoundRobin {
private static List<Node> serverList;
WeightedRoundRobin(List<Node> serverList) {
WeightedRoundRobin.serverList = serverList;
}
private String select() {
if (CollectionUtils.isEmpty(serverList)) {
throw new RuntimeException("service node is empty");
}
int totalWeight = 0;
for (Node node : serverList) {
totalWeight = totalWeight + node.getWeight();
node.setCurrentWeight(node.getCurrentWeight() + node.getWeight());
}
System.out.println(Arrays.toString(serverList.toArray()));
Node currentWeightMaxNode = Collections.max(serverList);
currentWeightMaxNode.setCurrentWeight(currentWeightMaxNode.getCurrentWeight() - totalWeight);
return currentWeightMaxNode.getIp();
}
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
Node node1 = new Node("192.168.0.1", 4);
Node node2 = new Node("192.168.0.2", 2);
Node node3 = new Node("192.168.0.3", 1);
List<Node> serverList = Arrays.asList(node1, node2, node3);
WeightedRoundRobin weightedRoundRobin = new WeightedRoundRobin(serverList);
for (int i = 0; i < 100; i++) {
String select = weightedRoundRobin.select();
map.put(select, map.getOrDefault(select, 0) + 1);
}
System.out.println(map);
}
}
Dubbo中的算法：
Dubbo官网说自己用了Nginx平滑加权轮询算法，我没找到。
代码来自 ： 3.3.0-beta.2-release
/**
* Select one invoker between a list using a random criteria
*
* @param invokers List of possible invokers
* @param url URL
* @param invocation Invocation
* @param <T>
* @return The selected invoker
*/
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
// 节点的数量 【invokers 就是需要负载均衡的节点集合】
int length = invokers.size();
// 如果不需要加权负载均衡，直接随机找一个
if (!needWeightLoadBalance(invokers, invocation)) {
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}
// 每个节点都有相同的权重?
boolean sameWeight = true;
// the maxWeight of every invoker, the minWeight = 0 or the maxWeight of the last invoker
int[] weights = new int[length];
// 总权重
int totalWeight = 0;
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
// [0,i] 权重之和
totalWeight += weight;
weights[i] = totalWeight;
// 判断每个节点都有相同的权重
if (sameWeight && totalWeight != weight * (i + 1)) {
sameWeight = false;
}
}
if (totalWeight > 0 && !sameWeight) {
int offset = ThreadLocalRandom.current().nextInt(totalWeight);
// 基于随机值选取一个节点
if (length <= 4) {
// 如果节点个数小于4，直接遍历
for (int i = 0; i < length; i++) {
if (offset < weights[i]) {
return invokers.get(i);
}
}
} else {
// 如果节点个数大于4，二分查找
int i = Arrays.binarySearch(weights, offset);
if (i < 0) {
// i = -i - 1,查看Arrays.binarySearch() 的用法,如果二分查找找不到offset,返回第一个大于查找元素的索引的负值。
i = -i - 1;
} else {
// 直到找到第一个大于offset的节点
while (weights[++i] == offset) {}
}
return invokers.get(i);
}
}
// 如果节点权重都相同，或者总权重为0，随机选一个节点。
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}