平滑分权路由 Aug 24, 2023
轮询调度
轮询调度非常简单，就是每次选择下一个节点进行调度。比如{a, b, c}三个节点，第一次选择a， 第二次选择b，第三次选择c，接下来又从头开始。
这样的算法有一个问题，在负载均衡中，每台机器的性能是不一样的，对于16核的机器跟4核的机器， 使用一样的调度次数，这样对于16核的机器的负载就会很低。这时，就引出了基于权重的轮询算法。
基于权重的轮询调度是在基本的轮询调度上，给每个节点加上权重，这样对于权重大的节点， 其被调度的次数会更多。比如a, b, c三台机器的负载能力分别是4:2:1，则可以给它们分配的权限为4, 2, 1。 这样轮询完一次后，a被调用4次，b被调用2次，c被调用1次。
对于普通的基于权重的轮询算法，可能会产生以下的调度顺序{a, a, a, a, b, b, c}。
这样的调度顺序其实并不友好，它会一下子把大压力压到同一台机器上，这样会产生一个机器一下子很忙的情况。 于是乎，就有了平滑的基于权重的轮询算法。
所谓平滑就是调度不会集中压在同一台权重比较高的机器上。这样对所有机器都更加公平。 比如，对于{a:5, b:1, c:1}，产生{a, a, b, a, c, a, a}的调度序列就比{c, b, a, a, a, a, a} 更加平滑。
nginx平滑的基于权重轮询算法
nginx平滑的基于权重轮询算法其实很简单。算法原文 描述为：
算法执行2步，选择出1个当前节点。
- 每个节点，用它们的当前值加上它们自己的权重。
- 选择当前值最大的节点为选中节点，并把它的当前值减去所有节点的权重总和。
例如{a:5, b:1, c:1}三个节点。一开始我们初始化三个节点的当前值为{0, 0, 0}。 选择过程如下表：
| 轮数 | 选择前的当前权重 | 选择节点 | 选择后的当前权重 |
|---|---|---|---|
| 1 | {5, 1, 1} | a | {-2, 1, 1} |
| 2 | {3, 2, 2} | a | {-4, 2, 2} |
| 3 | {1, 3, 3} | b | {1, -4, 3} |
| 4 | {6, -3, 4} | a | {-1, -3, 4} |
| 5 | {4, -2, 5} | c | {4, -2, -2} |
| 6 | {9, -1, -1} | a | {2, -1, -1} |
| 7 | {7, 0, 0} | a | {0, 0, 0} |
public final class WeightsPolling<T> {
private final List<WeightsInfo<T>> weightsInfos;
private Integer totalWeights = 0;
private Integer maxWeights;
private WeightsInfo<T> maxWeightsInfo;
public WeightsPolling(List<WeightsInfo<T>> weightsInfos) {
this.weightsInfos = weightsInfos;
weightsInfos.forEach(info -> totalWeights += info.getOriginalWeights());
}
public WeightsInfo<T> polling() {
weightsInfos.forEach(info -> {
maxWeightInfo(info);
info.setCurrentWeights(info.getCurrentWeights() + info.getOriginalWeights());
});
if (maxWeightsInfo != null) {
maxWeightsInfo.setCurrentWeights(maxWeightsInfo.getCurrentWeights() - totalWeights);
}
maxWeights = null;
return maxWeightsInfo;
}
private void maxWeightInfo(WeightsInfo<T> weightsInfo) {
if (maxWeights == null || weightsInfo.getCurrentWeights() > maxWeights) {
maxWeights = weightsInfo.getCurrentWeights();
maxWeightsInfo = weightsInfo;
}
}
}
@Data
public class WeightsInfo<T> {
/**
* 原始权重
*/
private int originalWeights;
/**
* 当前权重
*/
private int currentWeights;
private T data;
public WeightsInfo(T data, int originalWeights) {
this.originalWeights = originalWeights;
this.currentWeights = originalWeights;
this.data = data;
}
}
@Test
public void polling() {
// 创建需要路由器的数据以及分配的权重
List<WeightsInfo<String>> weightsInfoList = new LinkedList<>();
weightsInfoList.add(new WeightsInfo<>("a", 10));
weightsInfoList.add(new WeightsInfo<>("b", 30));
weightsInfoList.add(new WeightsInfo<>("c", 60));
WeightsPolling<String> weightsPolling = new WeightsPolling<>(weightsInfoList);
// 用于控制数据总量，也可可直接指定
AtomicInteger totalWeights = new AtomicInteger();
weightsInfoList.forEach(info -> totalWeights.addAndGet(info.getOriginalWeights()));
// 获取并记录每次路由的数据信息
Map<String, Integer> recordMap = new HashMap<>();
for (int i = 0; i < totalWeights.get(); i++) {
WeightsInfo<String> polling = weightsPolling.polling();
recordMap.compute(polling.getData(), (k, v) -> v == null ? 1 : v + 1);
}
// 检查最后结果是否跟权重匹配
weightsInfoList.forEach(info -> {
Assertions.assertEquals(recordMap.get(info.getData()).intValue(), info.getOriginalWeights());
});
}