负载均衡算法 — 轮询

福建健康网 2019-10-14

在分布式系统中,为了实现负载均衡,必然会涉及到负载调度算法,如 Nginx 和 RPC 服务发现等场景。常见的负载均衡算法有 轮询、源地址 Hash、最少连接数,而 轮询 是最简单且应用最广的算法。


负载均衡算法 — 轮询

3 种常见的轮询调度算法,分别为 简单轮询、加权轮询、平滑加权轮询。本文将用如下 4 个服务,来详细说明轮询调度过程。

服务实例权重值192.168.10.1:22021192.168.10.2:22022192.168.10.3:22023192.168.10.4:22024

简单轮询

简单轮询是轮询算法中最简单的一种,但由于它不支持配置负载,所以应用较少。

算法描述

假设有 N 台实例 S = {S1, S2, …, Sn},指示变量 currentPos 表示当前选择的实例 ID,初始化为 -1。算法可以描述为:

1、调度到下一个实例;

2、若所有实例已被 调度 过一次,则从头开始调度;

3、每次调度重复步骤 1、2;

调度过程,如下:

请求currentPos选中的实例10192.168.10.1:220221192.168.10.2:220232192.168.10.3:220243192.168.10.4:220250192.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、从上一次调度实例起,遍历后面的每个实例;

2、若所有实例已被遍历过一次,则减小 currentWeight 为 currentWeight - gcd(S),并从头开始遍历;若 currentWeight 小于等于 0,则重置为 max(S);

3、直到 遍历的实例的权重大于等于 currentWeight 时结束,此时实例为需调度的实例;

4、每次调度重复步骤 1、2、3;

例如,上述 4 个服务,最大权重 max(S) 为 4,最大公约数 gcd(S) 为 1。其调度过程如下:

请求currentPoscurrentWeight选中的实例134192.168.10.4:2202223192.168.10.3:2202333192.168.10.4:2202412192.168.10.2:2202………….921192.168.10.3:22021034192.168.10.4:2202

代码实现

这里使用 PHP 来实现,源码见 fan-haobai/load-balance 部分。

class WeightedRobin 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}。对于神秘的平滑加权轮询算法,我将在后续文章中详细介绍它的原理和实现。

总结

轮询算法是最简单的调度算法,因为它无需记录当前所有连接的状态,所以它是一种 无状态 的调度算法,这些特性使得它应用较广。

轮询调度算法并不能动态感知每个实例的负载,它完全依赖于我们的工程经验,人为配置权重来实现基本的负载均衡,并不能保证服务的高可用性。若服务的某些实例因其他原因负载突然加重,轮询调度还是会一如既往地分配请求给这个实例,因此可能会形成小面积的宕机,导致服务的局部不可用。

本文作者: 樊浩柏科学院

本文链接: https://www.fanhaobai.com/2018/11/load-balance-round-robin.html