内容简介:在分布式系统中,为了实现负载均衡,必然会涉及到负载调度算法,如 Nginx 和 RPC 服务发现等场景。常见的负载均衡算法有3 种常见的轮询调度算法,分别为、、
在分布式系统中,为了实现负载均衡,必然会涉及到负载调度算法,如 Nginx 和 RPC 服务发现等场景。常见的负载均衡算法有 轮询 、 源地址 Hash 、 最少连接数 ,而 轮询 是最简单且应用最广的算法。
3 种常见的轮询调度算法,分别为、、 平滑加权轮询 。本文将用如下 4 个服务,来详细说明轮询调度过程。
服务实例 | 权重值 |
---|---|
192.168.10.1:2202 | 1 |
192.168.10.2:2202 | 2 |
192.168.10.3:2202 | 3 |
192.168.10.4:2202 | 4 |
简单轮询
简单轮询是轮询算法中最简单的一种,但由于它不支持配置负载,所以应用较少。
算法描述
假设有 N 台实例 S = {S1, S2, …, Sn},指示变量 currentPos 表示当前选择的实例 ID,初始化为 -1。算法可以描述为:
1、请求到来时,自加变量 currentPos,使其指向下一个实例;
2、若所有实例已被 调度 过一次(上一次调度时 currentPos 指向了最后一个实例),则重置为 0;
调度过程,如下:
请求 | currentPos | 选中的实例 |
---|---|---|
1 | 0 | 192.168.10.1:2202 |
2 | 1 | 192.168.10.2:2202 |
3 | 2 | 192.168.10.3:2202 |
4 | 3 | 192.168.10.4:2202 |
5 | 0 | 192.168.10.1:2202 |
代码实现
这里使用 PHP 来实现,源码见 fan-haobai/load-balance 部分。
首先,定义一个统一的操作接口,主要有 init()
和 next()
这 2 个方法。
interface RobinInterface { /** * 初始化服务权重 * * @param array $services * * @return mixed */ public function init(array $services); /** * 获取一个服务 * * @return mixed */ public function next(); }
然后,根据简单轮询算法思路,实现上述接口:
class Robin implements RobinInterface { private $services = array(); private $total; private $currentPos = -1; public function init(array $services) { $this->services = $services; $this->total = count($services); } public function next() { // 已调度完一圈,重置currentPos值为第一个实例位置 $this->currentPos = ($this->currentPos + 1) % $this->total; return $this->services[$this->currentPos]; } }
其中, total
为总实例数量, services
为服务实例列表。由于简单轮询不需要配置权重,因此可简单配置为:
$services = [ '192.168.10.1:2202', '192.168.10.2:2202', '192.168.10.3:2202', '192.168.10.4:2202', ];
优缺点分析
在实际应用中,同一个服务会部署到不同的硬件环境,会出现性能不同的情况。若直接使用简单轮询调度算法,给每个服务实例相同的负载,那么,必然会出现资源浪费的情况。因此为了避免这种情况,一些人就提出了下面的算法。
加权轮询
加权轮询算法引入了“权”值,改进了简单轮询算法,可以根据硬件性能配置实例负载的权重,从而达到资源的合理利用。
算法描述
假设有 N 台实例 S = {S1, S2, …, Sn},权重 W = {W1, W2, …, Wn},指示变量 currentPos 表示当前选择的实例 ID,初始化为 -1;变量 currentWeight 表示当前权重,初始值为 max(S);max(S) 表示 N 台实例的最大权重值,gcd(S) 表示 N 台实例权重的最大公约数。
算法可以描述为:
1、请求到来时,i 从 currentPos 起自加,遍历每个实例;
2、若所有实例已被遍历过一次(上一次遍历时 i 指向了最后一个实例),则重置 i 为 0;且 currentWeight 减小为 currentWeight - gcd(S),若 currentWeight 小于或等于 0,则重置为 max(S);
3、 直到 i 指向的实例的权重大于或等于 currentWeight,赋值 currentPos 为 i;
例如,上述 4 个服务,最大权重 max(S) 为 4,最大公约数 gcd(S) 为 1。其调度过程如下:
请求 | currentPos | currentWeight | 选中的实例 |
---|---|---|---|
1 | 3 | 4 | 192.168.10.4:2202 |
2 | 2 | 3 | 192.168.10.3:2202 |
3 | 3 | 3 | 192.168.10.4:2202 |
4 | 1 | 2 | 192.168.10.2:2202 |
… | … | … | …. |
9 | 2 | 1 | 192.168.10.3:2202 |
10 | 3 | 4 | 192.168.10.4:2202 |
代码实现
这里使用 PHP 来实现,源码见 fan-haobai/load-balance 部分。
class WeightRobin implements RobinInterface { private $services = array(); private $total; private $currentPos = -1; private $currentWeight; public function init(array $services) { foreach ($services as $ip => $weight) { $this->services[] = [ 'ip' => $ip, 'weight' => $weight, ]; } $this->total = count($this->services); } public function next() { $i = $this->currentPos; while (true) { $i = ($i + 1) % $this->total; // 已全部被遍历完一次 if (0 === $i) { // 减currentWeight $this->currentWeight -= $this->getGcd(); // 赋值currentWeight为0,回归到初始状态 if ($this->currentWeight <= 0) { $this->currentWeight = $this->getMaxWeight(); } } // 直到当前遍历实例的weight大于或等于currentWeight if ($this->services[$i]['weight'] >= $this->currentWeight) { $this->currentPos = $i; return $this->services[$this->currentPos]['ip']; } } }
其中, getMaxWeight()
为所有实例的最大权重值; getGcd()
为所有实例权重的最大公约数,主要是通过 gcd()
方法(可用 gmp_gcd()
函数)求得 2 个数的最大公约数,然后求每一个实例的权重与当前最大公约数的最大公约数。实现如下:
private function getGcd() { $gcd = $this->services[0]['weight']; for ($i = 0; $i < $this->total; $i++) { $gcd = $this->gcd($gcd, $this->services[$i]['weight']); } return $gcd; }
需要注意的是,在配置 services
服务列表时,需要指定其权重:
$services = [ '192.168.10.1:2202' => 1, '192.168.10.2:2202' => 2, '192.168.10.3:2202' => 3, '192.168.10.4:2202' => 4, ];
优缺点分析
算法虽然通过配置实例权重,解决了的资源利用问题,但是它还是存在一个比较明显的 缺陷 。例如:
服务实例 S = {a, b, c},权重 W = {5, 1, 1},使用加权轮询调度生成的实例序列为 {a, a, a, a, a, b, c},那么就会存在连续 5 个请求都被调度到实例 a。而实际中,这种不均匀的负载是不被允许的,因为连续请求会突然加重实例 a 的负载,可能会导致严重的事故。
为了解决加权轮询调度不均匀的缺陷,一些人提出了 平滑加权轮询 调度算法,它会生成的更均匀的调度序列 {a, a, b, a, c, a, a}。对于神秘的平滑加权轮询算法,我将在后续文章中详细介绍它的原理和实现。
总结
轮询算法是最简单的调度算法,因为它无需记录当前所有连接的状态,所以它是一种 无状态 的调度算法,这些特性使得它应用较广。
轮询调度算法并不能动态感知每个实例的负载,它完全依赖于我们的工程经验,人为配置权重来实现基本的负载均衡,并不能保证服务的高可用性。若服务的某些实例因其他原因负载突然加重,轮询调度还是会一如既往地分配请求给这个实例,因此可能会形成小面积的宕机,导致服务的局部不可用。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
轻量级Django
茱莉亚·埃尔曼 (Julia Elman)、马克·拉温 (Mark Lavin) / 侯荣涛、吴磊 / 中国电力出版社; 第1版 / 2016-11-1 / 35.6
自Django 创建以来,各种各样的开源社区已经构建了很多Web 框架,比如JavaScript 社区创建的Angular.js 、Ember.js 和Backbone.js 之类面向前端的Web 框架,它们是现代Web 开发中的先驱。Django 从哪里入手来适应这些框架呢?我们如何将客户端MVC 框架整合成为当前的Django 基础架构? 本书讲述如何利用Django 强大的“自支持”功......一起来看看 《轻量级Django》 这本书的介绍吧!