问题描述
有三个节点{a, b, c}，它们的权重分别是{a=5, b=1, c=1}，发送7次请求，要求：
- 根据权重分配：a会被分配5次，b会被分配1次，c会被分配1次
- 分配尽可能平滑：尽可能均匀的分摊节点，节点分配不再是连续的，如{a， a， a， a， a， b， c}，即前5次可能选中的都是a，这可能造成权重大的服务器造成过大压力的同时，小权重服务器还很闲
NGINX平滑加权轮询算法
算法涉及的几个概念
- weight：约定权重，在配置文件 or 初始化时指定的每个节点的权重；
- effectiveWeight：有效权重，作用是节点异常，降低其权重，初始值为 weight
在通讯过程中发现节点异常，则-1；
之后再次选取本节点，调用成功一次则+1，直达恢复到weight； - currentWeight：节点当前权重，初始化为 0；
算法逻辑
-
计算总权重totalWeight = sum(各节点的effectiveWeight)； -
计算每个节点的currentWeight = currentWeight + effectiveWeight； 选择所有节点中currentWeight最大的作为选中节点； 选中节点的currentWeight = currentWeight - totalWeight； -
再次选择时重复第2步；
以 {a=4，b=2，c=1} 为例，这里为了方便，effectiveWeight即为weight，totalWeight=7，初始currentWeight = {0，0，0}，每次选择：
| 第i次选择 | 选择前currentWeight | 选择 | 选择后currentWeight |
|---|
| 1 | {4，2，1} | a | {-3，2，1} | | 2 | {1，4，2} | b | {1，-3，2} | | 3 | {5，-1，3} | a | {-2，-1，3} | | 4 | {2，1，4} | c | {2，1，-3} | | 5 | {6，3，-2} | a | {-1，3，-2} | | 6 | {3，5，-1} | b | {3，-2，-1} | | 7 | {7，0，0} | a | {0，0，0} | | 8 | {4，2，1} | a | {-3，2，1} |
可以看到，选择序列为{a，b，a，c，a，b，a}，满足平滑的按照权重分配，下一轮又是一次重新开始；
算法证明
权重合理性
对于n个节点的权重： x1, x2, … , xn，记权重总和S = x1 + x2 + … + xn，在S轮选择中，节点i被选中了mi次。
权重合理性即证明，对于任意的i(1<= i <= n)，mi = xi。
证明：
-
首先证明，在每轮选择后，各节点当前权重总和S = 0。 这个很好理解，也很好证明： 对于第1轮：初始是{0, 0, …, 0}，加上自己的有效权重，假设选中第j个节点，则第1轮后，权重总和为 x1+x2+…+xj-S+x(j+1)+…+xn=0 假设第k轮后权限总和为0，那么在k+1轮时，先加上自己的有效权重，再在选中节点上减去权重总和，S(k)+x1+…+xn-S = 0+S-S=0 -
其次证明S轮选择中， mi = xi (1<=i<=n)
-
证明 mi <= xi 一共执行S轮，设节点i一共被选中了mi次，S轮后节点i的权重为wi 假设mi > xi，在t(t < S)轮后，已经被选中了xi次，则此时节点i的权重为 wit = xi * t - S * xi = (t - S) * xi < 0 (t < S) 在剩下的S-t轮中，节点i 没有再被选中，则S-t轮后节点i的当前权重wiS = (t - S) * xi + (S - t) * xi = 0，说明，在S-t轮中节点i的权重<0，倘若又再被选中，则在S-t轮中节点i的权重更加小 < 0 根据每轮选择后当前权重总和为0的结论，S-t轮的每轮中，必然存在一个节点k的当前权重>0，因此节点i在剩下S-t轮中根本不会被选中，因此 mi <= xi -
由于S = m1 + m2 + … +mn = x1 + x2 + … + xn，而mi <= xi，因此 mi = xi
平滑性
平滑性即证明不会一直连续选择同一个节点(连续几轮还是有可能的)
如{10，1，1}
| 第i次选择 | 选择前currentWeight | 选择 | 选择后currentWeight |
|---|
| 1 | {10，1，1} | a | {-2，1，1} | | 2 | {8，2，2} | a | {-4，-2，2} | | 3 | {6，3，3} | a | {-6，3，3} | | 4 | {4，4，4} | a | {-8，4，4} | | 5 | {2，5，5} | b | {2，-7，5} |
证明：
在权重合理性证明中，可以知道，S轮选择中，节点i会被选择xi次，假设在这S轮选择中，连续选择了t次节点i
令t = xi - 1，则 wi = t * xi - t * S = (xi - 1) * xi - (xi - 1) * S
下一轮时，wi + xi = (xi - 1) * xi - (xi - 1) * S + xi = xi ^ 2 - xi * S + S = (xi - S) * xi + S - xi + xi = (xi - S) * (xi - 1) + xi
由于 xi < S，即 xi - S <= -1，wi + xi = (xi - S) * (xi - 1) + xi <= 1 - xi + xi = 1
如果这t轮刚好是最开始的t轮，则必定存在另一个结点j的值为xj，所以有wi + xi <=1< xj * t，所以下一轮肯定不会选中xi。
参考：
负载均衡算法WeightedRoundRobin(加权轮询)简介及算法实现
Nginx中的平滑加权轮询算法蕴含的数学原理是什么呢？
nginx平滑的基于权重轮询算法分析
|