在分布式系统中，为了实现负载均衡，一定会涉及到负载调度算法，如 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、调度到下一个实例；2、若所有实例已被 调度 过一次，则从头开始调度；3、每次调度重复步骤 1、2；
调度过程，如下：
要求
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、从上一次调度实例起，遍历后面的每个实例；2、若所有实例已被遍历过一次，则减小 currentWeight 为 currentWeight - gcd(S)，并从头开始遍历；若 currentWeight 小于即是 0，则重置为 max(S)；3、直到 遍历的实例的权重大于即是 currentWeight 时结束，此时实例为需调度的实例；4、每次调度重复步骤 1、2、3；
例如，上述 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 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}。对付神秘的平滑加权轮询算法，我将在后续文章中详细先容它的事理和实现。
总结轮询算法是最大略的调度算法，由于它无需记录当前所有连接的状态，以是它是一种 无状态 的调度算法，这些特性使得它运用较广。
轮询调度算法并不能动态感知每个实例的负载，它完备依赖于我们的工程履历，人为配置权重来实现基本的负载均衡，并不能担保做事的高可用性。若做事的某些实例因其他缘故原由负载溘然加重，轮询调度还是会一如既往地分配要求给这个实例，因此可能会形成小面积的宕机，导致做事的局部不可用。
