内容简介:在负载均衡算法 — 轮询 一文中,我们就指出了加权轮询算法一个明显的缺陷。即在某些特殊的权重下,加权轮询调度会生成不均匀的实例序列,这种不平滑的负载可能会使某些实例出现瞬时高负载的现象,导致系统存在宕机的风险。为了解决这个调度缺陷,就提出了调度算法。为了说明平滑加权轮询调度的平滑性,使用以下 3 个特殊的权重实例来演示调度过程。
在负载均衡算法 — 轮询 一文中,我们就指出了加权轮询算法一个明显的缺陷。即在某些特殊的权重下,加权轮询调度会生成不均匀的实例序列,这种不平滑的负载可能会使某些实例出现瞬时高负载的现象,导致系统存在宕机的风险。为了解决这个调度缺陷,就提出了调度算法。
待解决的问题
为了说明平滑加权轮询调度的平滑性,使用以下 3 个特殊的权重实例来演示调度过程。
服务实例 | 权重值 |
---|---|
192.168.10.1:2202 | 5 |
192.168.10.2:2202 | 1 |
192.168.10.3:2202 | 1 |
我们已经知道通过加权轮询 算法调度后,会生成如下不均匀的调度序列。
请求 | 选中的实例 |
---|---|
1 | 192.168.10.1:2202 |
2 | 192.168.10.1:2202 |
3 | 192.168.10.1:2202 |
4 | 192.168.10.1:2202 |
5 | 192.168.10.1:2202 |
6 | 192.168.10.2:2202 |
7 | 192.168.10.3:2202 |
接下来,我们就使用平滑加权轮询算法调度上述实例,看看生成的实例序列如何?
算法描述
假设有 N 台实例 S = {S1, S2, …, Sn},配置权重 W = {W1, W2, …, Wn},有效权重 CW = {CW1, CW2, …, CWn}。每个实例 i 除了存在一个配置权重 Wi 外,还存在一个当前有效权重 CWi,且 CWi 初始化为 Wi;指示变量 currentPos 表示当前选择的实例 ID,初始化为 -1;所有实例的配置权重和为 weightSum;
那么,调度算法可以描述为:
1、初始每个实例 i 的 当前有效权重 CWi 为 配置权重 Wi,并求得配置权重和 weightSum;
2、选出 当前有效权重 的实例,将 当前有效权重 CWi 减去所有实例的 权重和 weightSum,且变量 currentPos 指向此位置;
3、将每个实例 i 的 当前有效权重 CWi 都加上 配置权重 Wi;
4、取到变量 currentPos 指向的实例;
5、每次调度重复上述步骤 2、3、4;
上述 3 个服务,配置权重和 weightSum 为 7,其调度过程如下:
请求 | 选中前的当前权重 | currentPos | 选中的实例 | 选中后的当前权重 |
---|---|---|---|---|
1 | {5, 1, 1} | 0 | 192.168.10.1:2202 | {-2, 1, 1} |
2 | {3, 2, 2} | 0 | 192.168.10.1:2202 | {-4, 2, 2} |
3 | {1, 3, 3} | 1 | 192.168.10.2:2202 | {1, -4, 3} |
4 | {6, -3, 4} | 0 | 192.168.10.1:2202 | {-1, -3, 4} |
5 | {4, -2, 5} | 2 | 192.168.10.3:2202 | {4, -2, -2} |
6 | {9, -1, -1} | 0 | 192.168.10.1:2202 | {2, -1, -1} |
7 | {7, 0, 0} | 0 | 192.168.10.1:2202 | {0, 0, 0} |
8 | {5, 1, 1} | 0 | 192.168.10.1:2202 | {-2, 1, 1} |
可以看出上述调度序列分散是非常均匀的,且第 8 次调度时当前有效权重值又回到 {0, 0, 0},实例的状态同初始状态一致,所以后续可以一直重复调度操作。
此轮询调度算法思路首先被 Nginx 开发者提出,见 phusion/nginx 部分。
代码实现
这里使用 PHP 来实现,源码见 fan-haobai/load-balance 部分。
class SmoothWeightedRobin implements RobinInterface { private $services = array(); private $total; private $currentPos = -1; public function init(array $services) { foreach ($services as $ip => $weight) { $this->services[] = [ 'ip' => $ip, 'weight' => $weight, 'current_weight' => $weight, ]; } $this->total = count($this->services); } public function next() { // 获取最大当前有效权重实例的位置 $this->currentPos = $this->getMaxCurrentWeightPos(); // 当前权重减去权重和 $currentWeight = $this->getCurrentWeight($this->currentPos) - $this->getSumWeight(); $this->setCurrentWeight($this->currentPos, $currentWeight); // 每个实例的当前有效权重加上配置权重 $this->recoverCurrentWeight(); return $this->services[$this->currentPos]['ip']; } }
其中, getSumWeight()
为每个实例个配置权重和; getCurrentWeight()
和 setCurrentWeight()
分别用于获取和设置指定实例的当前有效权重; getMaxCurrentWeightPos()
求得最大当前有效权重的实例位置,实现如下:
public function getMaxCurrentWeightPos() { $currentWeight = $pos = 0; foreach ($this->services as $index => $service) { if ($service['current_weight'] > $currentWeight) { $currentWeight = $service['current_weight']; $pos = $index; } } return $pos; }
recoverCurrentWeight()
用于调整每个实例的当前有效权重,即加上配置权重,实现如下:
public function recoverCurrentWeight() { foreach ($this->services as $index => &$service) { $service['current_weight'] += $service['weight']; } }
需要注意的是,在配置 services
服务列表时,同样需要指定其权重:
$services = [ '192.168.10.1:2202' => 5, '192.168.10.2:2202' => 1, '192.168.10.3:2202' => 1, ];
数学证明
可惜的是,关于此调度算法严谨的数学证明少之又少,不过网友 tenfy 给出的 安大神 证明过程,非常值得参考和学习。
证明权重合理性
假如有 n 个结点,记第 i 个结点的权重是 $x_i$,设总权重为 $S = x_1 + x_2 + … + x_n$。选择分两步:
1、为每个节点加上它的权重值;
2、选择最大的节点减去总的权重值;
n 个节点的初始化值为 [0, 0, …, 0],数组长度为 n,值都为 0。第一轮选择的第 1 步执行后,数组的值为 $[x_1, x_2, …, x_n]$。
假设第 1 步后,最大的节点为 j,则第 j 个节点减去 S。
所以第 2 步的数组为 $[x_1, x_2, …, x_j-S, …, x_n]$。 执行完第 2 步后,数组的和为:
$x_1 + x_2 + … + x_j-S + … + x_n => x_1 + x_2 + … + x_n - S = S - S = 0$
由此可见,每轮选择第 1 步操作都是数组的总和加上 S,第 2 步总和再减去 S,所以每轮选择完后的数组总和都为 0。
假设总共执行 S 轮选择,记第 i 个结点选择 $m_i$ 次。第 i 个结点的当前权重为 $w_i$。 假设节点 j 在第 t 轮(t < S)之前,已经被选择了 $x_j$ 次,记此时第 j 个结点的当前权重为 $w_j = t * x_j - x_j * S = (t - S) * x_j < 0$, 因为 t 恒小于 S,所以 $w_j < 0$。
前面假设总共执行 S 轮选择,则剩下 S-t 轮,上面的公式 $w_j = (t - S) * x_j + (S - t) * x_j = 0$。 所以在剩下的选择中,$w_j$ 永远小于等于 0,由于上面已经证明任何一轮选择后,数组总和都为 0,则必定存在一个节点 k 使得 $w_k > 0$,永远不会再选中 $x_j$。
由此可以得出,第 i 个结点最多被选中 $x_i$ 次,即 $m_i <= x_i$。
因为 $S = m_1 + m_2 + … + m_n$ 且 $S = x_1 + x_2 + … + x_n$。 所以,可以得出 $m_i == x_i$。
证明平滑性
证明平滑性,只要证明不要一直都是连续选择那一个节点即可。
跟上面一样,假设总权重为 S,假如某个节点 $x_i$ 连续选择了 t($t < x_i$) 次,只要存在下一次选择的不是 $x_i$,即可证明是平滑的。
假设 $t = x_i - 1$,此是第 i 个结点的当前权重为 $w_i = t * x_i - t * S = (x_i - 1) * x_i - (x_i - 1) * S$。证明下一轮的第 1 步执行完的值 $w_i + x_i$ 不是最大的即可。
$w_i + x_i => (x_i - 1) * x_i - (x_i - 1) * S + x_i =>$
$x_i^2 - x_i * S + S => (x_i - 1) * (x_i - S) + x_i$
因为 $x_i$ 恒小于 S,所以 $x_i - S <= -1$。 所以上面:
$(x_i - 1) * (x_i - S) + x_i <= (x_i - 1) * -1 + x_i = -x_i + 1 + x_i = 1$
所以第 t 轮后,再执行完第 1 步的值 $w_i + x_i <= 1$。
如果这 t 轮刚好是最开始的 t 轮,则必定存在另一个结点 j 的值为 $x_j * t$,所以有 $w_i + x_i <= 1 < 1 * t < x_j * t$。所以下一轮肯定不会选中 x。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 使用加权轮询算法和 Go 实现 HTTP 负载分发代理
- matlab练习程序(加权最小二乘)
- matlab练习程序(局部加权线性回归)
- 加权随机采样 (Weighted Random Sampling)
- 从具有加权行概率的PostgreSQL表中选择随机行
- CVPR2019 | ASRCF:基于自适应空间加权相关滤波的视觉跟踪研究(即将开源)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
游戏化革命:未来商业模式的驱动力
[美]盖布·兹彻曼、[美]乔斯琳·林德 / 应皓 / 中国人民大学出版社有限公司 / 2014-8-1 / CNY 59.00
第一本植入游戏化理念、实现APP互动的游戏化商业图书 游戏化与商业的大融合、游戏化驱动未来商业革命的权威之作 作者被公认为“游戏界的天才”,具有很高的知名度 亚马逊五星级图书 本书观点新颖,游戏化正成为最热门的商业新策略 游戏化是当今最热门的商业新策略,它能帮助龙头企业创造出前所未有的客户和员工的参与度。商业游戏化策略通过利用从游戏设计、忠诚度计划和行为经济学中所汲取......一起来看看 《游戏化革命:未来商业模式的驱动力》 这本书的介绍吧!