算法练习(20)-平滑加权轮询算法
所有负载均衡的场景几乎都会用到这个算法：假设有2个服务器A、B，其中A的分配权重为80，B的分配权重为20，当有5个请求过来时，A希望分到4次，B希望分到1次。
一个很自然的想法：A-A-A-A-B ，按权重顺序依次分配，同时计数，每分配1次，计数减1，减到0后，再分配『次权重』的服务器。
看上去好象也凑合能用，但如果A:B的权重是100:1，A-A...-A-...(100次后)，才分到B，B要坐很长时间的冷板凳，这显然不太好。
于是就有了个这个算法，它的思路如下：
初始状态时，配置的权重为：{A:80, B:20}，然后给每个服务器，加1个动态的当前权重(curWeight)，默认为0，按以下步骤：
1、curWeight += weight (注：weight为配置的权重)
2、挑选curWeight最大的，做为本次分配的结果，然后将curWeight -= sum(weight) ，即：分到的服务器，其动态权重- sum(配置权重)
3、开始下1次分配，分配前将每台服务器上的curWeight += weight(即：重复步骤1）
不断重复上述过程即可，下面分解下具体过程：
weight 初始状态：{80, 20}，curWeight初始状态：{0，0}
请求次数 | curWeight += weight | max(curWeight) | curWeight -= sum(weight) |
|---|---|---|---|
1 | {0,0}+{80,20} = {80,20} | 80，即A | {80 - 100 ,20} = {-20, 20} |
2 | {-20，20}+{80,20} ={60,40} | 60，即A | {60-100 ,40} = {-40, 40} |
3 | {-40, 40}+{80,20}={40,60} | 60，即B | {40, 60-100} = {40, -40} |
4 | {40, -40}+{80,20}={120,-20} | 120，即A | {120-100,-20} = {20, -20} |
5 | {20, -20}+{80,20}={100,0} | 100，即A | {100-100,0} = {0,0} 注：所有服务器curWeight归0时，这一轮分配就结束，下次又回到原点，开始轮回 |
所以，最终分配的顺序就是 A - A - B - A - A，比原来的A - A - A - A - B，是不是更为合理？ 这个算法巧妙的地方在于，每一轮分配完成，所有服务器的动态权重都会归0，回到初始状态！另外1个优势在于，它能让所有权重的服务器，尽早分配到，而非等到高权重的服务器分配完，才轮到自己。
想想这其中的数学原理也不复杂，每次分到的服务器，其curWeight 减掉了 配置权重的总和sum(weight)，然后下次分配前，又将配置权重加回来了，所以一减一加，正好抵消。
理解其中的原理后，用java代码来实现一把：
先定义一个服务器类：
@Data
@AllArgsConstructor
@NoArgsConstructor
public class ServerInfo {
/**
* 服务器主机名
*/
public String hostName;
/**
* (静态)权重
*/
public Integer weight;
/**
* 当前动态权重
*/
public Integer curWeight;
}然后开干：
1 /**
2 * 平滑加权轮询算法 示例
3 * by 菩提树下的杨过 yjmyzz.cnblogs.com
4 *
5 * @param args
6 */
7 public static void main(String[] args) {
8
9 List<ServerInfo> serverList = new ArrayList<>();
10 serverList.add(new ServerInfo("A", 80, 0));
11 serverList.add(new ServerInfo("B", 20, 0));
12
13 //模拟2轮请求
14 for (int i = 1; i <= 10; i++) {
15
16 int sumWeight = 0;
17 int maxWeight = 0;
18 ServerInfo currentServer = null;
19
20 //找出最大的动态权重
21 for (ServerInfo serverInfo : serverList) {
22 serverInfo.curWeight += serverInfo.weight;
23 sumWeight += serverInfo.curWeight;
24 maxWeight = Math.max(maxWeight, serverInfo.curWeight);
25 if (maxWeight == serverInfo.curWeight) {
26 currentServer = serverInfo;
27 }
28 }
29
30 //输出本次请求的选中结果，并更新选中节点的动态权重
31 currentServer.curWeight -= sumWeight;
32 //实际应用时，下面这行，应该是将请求，转发到这台服务器
33 System.out.print(currentServer.hostName + " ");
34
35 //(以下为辅助代码) 每轮结束时，辅助输出换行
36 boolean roundEnd = true;
37 for (ServerInfo serverInfo : serverList) {
38 if (serverInfo.curWeight != 0) {
39 roundEnd = false;
40 }
41 }
42 if (roundEnd) {
43 System.out.println("");
44 }
45 }
46 }输出：
A A B A A A A B A A
最后扩展一下，这个算法不仅仅可用于负载均衡，很多业务系统也能用到，比如：在线客服系统，当有客人来咨询时，系统会从空闲的客服列表里，分配一个适合的客服来为其服务。因为客服的业务能力不同，能力强的客服可以配置更高权重，多分一些进线给他，反之新人就少分配一些，只要为客服的权重标签设置不同的值即可。