常用负载均衡调度算法实现

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 7.7k | 阅读时长 ≈ 7 分钟

介绍

用 PHP 实现几种负载均衡调度算法，详细见

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

调度算法

3种常见的轮询调度算法，分别为 简单轮询、加权轮询、平滑加权轮询

普通轮询（general Round Robin)
namespace Robin;

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];
    }

}
加权轮询（Weighted Round Robin)
namespace Robin;

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'];
            }
        }
    }

    /**
     * 求两数的最大公约数(基于欧几里德算法,可使用gmp_gcd())
     *
     * @param integer $a
     * @param integer $b
     *
     * @return integer
     */
    private function gcd($a, $b)
    {
        $rem = 0;
        while ($b) {
            $rem = $a % $b;
            $a = $b;
            $b = $rem;
        }

        return $a;
    }

    /**
     * 获取最大公约数
     *
     * @return integer
     */
    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;
    }

    /**
     * 获取最大权重值
     *
     * @return integer
     */
    private function getMaxWeight()
    {
        $maxWeight = 0;
        foreach ($this->services as $node) {
            if ($node['weight'] >= $maxWeight) {
                $maxWeight = $node['weight'];
            }
        }

        return $maxWeight;
    }

}
平滑加权轮询（Smooth Weighted Round Robin)
namespace Robin;

class SmoothWeightedRobin implements RobinInterface
{
    /**
     * 服务群组
     * @var array
     */
    private $services = array();

    /**
     * 同时累加所有peer的effective_weight，保存为total
     * @var
     */
    private $total;

    /**
     * 后端目前的权重
     * @var int
     */
    private $currentPos = -1;

    /**
     * 初始化
     * @param array $services
     */
    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 = intval($this->getCurrentWeight($this->currentPos)) - intval($this->getSumWeight());
        $this->setCurrentWeight($this->currentPos, $currentWeight);

        // 每个实例的当前有效权重加上配置权重
        $this->recoverCurrentWeight();

        return $this->services[$this->currentPos]['ip'];
    }

    /**
     * 获取最大当前有效权重实例位置
     * @return int
     */
    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;
    }

    /**
     * 配置权重和，累加所有后端的effective_weight
     *
     * @return integer
     */
    public function getSumWeight()
    {
        $sum = 0;
        foreach ($this->services as $service) {
            $sum += intval($service['weight']);
        }
        return $sum;
    }

    /**
     * 设置当前有效权重
     * @param integer $pos
     * @param integer $weight
     */
    public function setCurrentWeight($pos, $weight)
    {
        $this->services[$pos]['current_weight'] = $weight;
    }

    /**
     * 获取当前有效权重
     *
     * @param integer $pos
     * @return integer
     */
    public function getCurrentWeight($pos)
    {
        return $this->services[$pos]['current_weight'];
    }

    /**
     * 用配置权重调整当前有效权重
     */
    public function recoverCurrentWeight()
    {
        foreach ($this->services as $index => &$service) {
            $service['current_weight'] += intval($service['weight']);
        }
    }
}
调度算法接口服务
namespace Robin;

interface RobinInterface
{
    /**
     * 初始化服务权重
     *
     * @param array $services
     */
    public function init(array $services);

    /**
     * 获取一个服务
     *
     * @return string
     */
    public function next();

}

加权轮询 算法虽然通过配置实例权重，解决了 简单轮询 的资源利用问题，但是它还是存在一个比较明显的 缺陷。
为了解决加权轮询调度不均匀的缺陷，一些人提出了 平滑加权轮询 调度算法，它会生成的更均匀的调度序列 {a, a, b, a, c, a, a}。对于神秘的平滑加权轮询算法，我将在后续文章中详细介绍它的原理和实现。

Installation

log
1
composer require tinywan/load-balancing

Basic Usage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 服务器数
$services = [
    '192.168.10.1' => 6,
    '192.168.10.2' => 2,
    '192.168.10.3' => 1,
    '192.168.10.4' => 1,
];

 ------------- 1.简单轮询 ------------- 

$robin = new \Robin\Robin();
$robin->init($services);
$nodes = [];
for ($i = 1; $i <= count($services); $i++) {
    $node = $robin->next();
    $nodes[$i] = $node;
}
var_export($nodes);

 ------------- 2.加权轮询 ------------- 

$robin = new \Robin\WeightedRobin();
$robin->init($services);

$nodes = [];
for ($i = 1; $i <= 10; $i++) {
    $node = $robin->next();
    $nodes[$i] = $node;
}
var_export($nodes);

 ------------- 3.平滑加权轮询 ------------- 

$robin = new \Robin\SmoothWeightedRobin();
$robin->init($services);

$nodes = [];
$sumWeight = $robin->getSumWeight();
for ($i = 1; $i <= $sumWeight; $i++) {
    $node = $robin->next();
    $nodes[$i] = $node;
}
var_export($nodes);

Composer管理

安装提示错误：

Could not find package tinywan/load-polling in a version matching 1.0

尝试改成Packagist的地址 https://packagist.org

log
1
2
3
4
5
6
"repositories": {
    "packagist": {
        "type": "composer",
        "url": "https://packagist.org"
    }
}

要使你发布的最新包可以使用，请使用以上的镜像源，为了学习

参考

坚持原创技术分享，您的支持将鼓励我继续创作！