負(fù)載均衡算法 — 平滑加權(quán)輪詢

首發(fā)于樊浩柏科學(xué)院

在負(fù)載均衡算法 — 輪詢一文中磨确，我們就指出了加權(quán)輪詢算法一個明顯的缺陷。即在某些特殊的權(quán)重下罪佳，加權(quán)輪詢調(diào)度會生成不均勻的實(shí)例序列敛熬，這種不平滑的負(fù)載可能會使某些實(shí)例出現(xiàn)瞬時(shí)高負(fù)載的現(xiàn)象，導(dǎo)致系統(tǒng)存在宕機(jī)的風(fēng)險(xiǎn)鳍侣。為了解決這個調(diào)度缺陷丁稀，就提出了平滑加權(quán)輪詢調(diào)度算法。

預(yù)覽圖

待解決的問題

為了說明平滑加權(quán)輪詢調(diào)度的平滑性倚聚，使用以下 3 個特殊的權(quán)重實(shí)例來演示調(diào)度過程线衫。

服務(wù)實(shí)例	權(quán)重值
192.168.10.1:2202	5
192.168.10.2:2202	1
192.168.10.3:2202	1

我們已經(jīng)知道通過加權(quán)輪詢算法調(diào)度后，會生成如下不均勻的調(diào)度序列惑折。

請求	選中的實(shí)例
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

接下來授账，我們就使用平滑加權(quán)輪詢算法調(diào)度上述實(shí)例，看看生成的實(shí)例序列如何惨驶？

算法描述

假設(shè)有 N 臺實(shí)例 S = {S1, S2, …, Sn}白热，配置權(quán)重 W = {W1, W2, …, Wn}，有效權(quán)重 CW = {CW1, CW2, …, CWn}敞咧。每個實(shí)例 i 除了存在一個配置權(quán)重 Wi 外棘捣，還存在一個當(dāng)前有效權(quán)重 CWi辜腺，且 CWi 初始化為 Wi休建；指示變量 currentPos 表示當(dāng)前選擇的實(shí)例 ID，初始化為 -1评疗；所有實(shí)例的配置權(quán)重和為 weightSum测砂；

那么，調(diào)度算法可以描述為：
1百匆、初始每個實(shí)例 i 的 當(dāng)前有效權(quán)重 CWi 為 配置權(quán)重 Wi砌些，并求得配置權(quán)重和 weightSum；
2加匈、選出 當(dāng)前有效權(quán)重 最大的實(shí)例存璃，將 當(dāng)前有效權(quán)重 CWi 減去所有實(shí)例的 權(quán)重和 weightSum，且變量 currentPos 指向此位置雕拼；
3纵东、將每個實(shí)例 i 的 當(dāng)前有效權(quán)重 CWi 都加上 配置權(quán)重 Wi；
4啥寇、取到變量 currentPos 指向的實(shí)例偎球；
5洒扎、每次調(diào)度重復(fù)上述步驟 2、3衰絮、4袍冷；

上述 3 個服務(wù)，配置權(quán)重和 weightSum 為 7猫牡，其調(diào)度過程如下：

請求	選中前的當(dāng)前權(quán)重	currentPos	選中的實(shí)例	選中后的當(dāng)前權(quán)重
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}

可以看出上述調(diào)度序列分散是非常均勻的胡诗，且第 8 次調(diào)度時(shí)當(dāng)前有效權(quán)重值又回到 {0, 0, 0}，實(shí)例的狀態(tài)同初始狀態(tài)一致淌友，所以后續(xù)可以一直重復(fù)調(diào)度操作乃戈。

此輪詢調(diào)度算法思路首先被 Nginx 開發(fā)者提出，見 phusion/nginx 部分亩进。

代碼實(shí)現(xiàn)

這里使用 PHP 來實(shí)現(xiàn)症虑，源碼見 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()
    {
        // 獲取最大當(dāng)前有效權(quán)重實(shí)例的位置
        $this->currentPos = $this->getMaxCurrentWeightPos();

        // 當(dāng)前權(quán)重減去權(quán)重和
        $currentWeight = $this->getCurrentWeight($this->currentPos) - $this->getSumWeight();
        $this->setCurrentWeight($this->currentPos, $currentWeight);

        // 每個實(shí)例的當(dāng)前有效權(quán)重加上配置權(quán)重
        $this->recoverCurrentWeight();

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

其中归薛，getSumWeight()為所有實(shí)例的配置權(quán)重和谍憔；getCurrentWeight()和 setCurrentWeight()分別用于獲取和設(shè)置指定實(shí)例的當(dāng)前有效權(quán)重；getMaxCurrentWeightPos()求得最大當(dāng)前有效權(quán)重的實(shí)例位置主籍，實(shí)現(xiàn)如下：

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()用于調(diào)整每個實(shí)例的當(dāng)前有效權(quán)重习贫，即加上配置權(quán)重，實(shí)現(xiàn)如下：

public function recoverCurrentWeight()
{
    foreach ($this->services as $index => &$service) {
        $service['current_weight'] += $service['weight'];
    }
}

需要注意的是千元，在配置services服務(wù)列表時(shí)苫昌，同樣需要指定其權(quán)重：

$services = [
    '192.168.10.1:2202' => 5,
    '192.168.10.2:2202' => 1,
    '192.168.10.3:2202' => 1,
];

數(shù)學(xué)證明

可惜的是，關(guān)于此調(diào)度算法嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明少之又少幸海，不過網(wǎng)友 tenfy 給出的安大神證明過程祟身，非常值得參考和學(xué)習(xí)。

證明權(quán)重合理性

假如有 n 個結(jié)點(diǎn)物独，記第 i 個結(jié)點(diǎn)的權(quán)重是 $x_i$ 袜硫，設(shè)總權(quán)重為 $S = x_1 + x_2 + … + x_n$ 。選擇分兩步：
1挡篓、為每個節(jié)點(diǎn)加上它的權(quán)重值婉陷；
2、選擇最大的節(jié)點(diǎn)減去總的權(quán)重值官研；

n 個節(jié)點(diǎn)的初始化值為 [0, 0, …, 0]秽澳，數(shù)組長度為 n，值都為 0戏羽。第一輪選擇的第 1 步執(zhí)行后担神，數(shù)組的值為 $[x_1, x_2, …, x_n]$ 。

假設(shè)第 1 步后蛛壳，最大的節(jié)點(diǎn)為 j杏瞻，則第 j 個節(jié)點(diǎn)減去 S所刀。
所以第 2 步的數(shù)組為 $[x_1, x_2, …, x_j-S, …, x_n]$ 。執(zhí)行完第 2 步后捞挥，數(shù)組的和為：
$x_1 + x_2 + … + x_j-S + … + x_n => x_1 + x_2 + … + x_n - S = S - S = 0$

由此可見浮创，每輪選擇第 1 步操作都是數(shù)組的總和加上 S，第 2 步總和再減去 S砌函，所以每輪選擇完后的數(shù)組總和都為 0斩披。

假設(shè)總共執(zhí)行 S 輪選擇，記第 i 個結(jié)點(diǎn)選擇 $m_i$ 次讹俊。第 i 個結(jié)點(diǎn)的當(dāng)前權(quán)重為 $w_i$ 垦沉。假設(shè)節(jié)點(diǎn) j 在第 t 輪（t < S）之前，已經(jīng)被選擇了 $x_j$ 次仍劈，記此時(shí)第 j 個結(jié)點(diǎn)的當(dāng)前權(quán)重為 $w_j = t \* x_j - x_j \* S = (t - S) \* x_j < 0$ 厕倍，因?yàn)?t 恒小于 S，所以 $w_j < 0$ 贩疙。

前面假設(shè)總共執(zhí)行 S 輪選擇讹弯，則剩下 S-t 輪 j 都不會被選中，上面的公式 $w_j = (t - S) \* x_j + (S - t) \* x_j = 0$ 这溅。所以在剩下的選擇中组民， $w_j$ 永遠(yuǎn)小于等于 0，由于上面已經(jīng)證明任何一輪選擇后悲靴，數(shù)組總和都為 0臭胜，則必定存在一個節(jié)點(diǎn) k 使得 $w_k > 0$ ，永遠(yuǎn)不會再選中節(jié)點(diǎn) j癞尚。

由此可以得出耸三，第 i 個結(jié)點(diǎn)最多被選中 $x_i$ 次，即 $m_i <= x_i$ 否纬。
因?yàn)? $S = m_1 + m_2 + … + m_n$ 且 $S = x_1 + x_2 + … + x_n$ 吕晌。所以蛋褥，可以得出 $m_i == x_i$ 临燃。

證明平滑性

證明平滑性，只要證明不要一直都是連續(xù)選擇那一個節(jié)點(diǎn)即可烙心。

跟上面一樣膜廊，假設(shè)總權(quán)重為 S，假如某個節(jié)點(diǎn) i 連續(xù)選擇了 t（ $t < x_i$ ）次淫茵，只要存在下一次選擇的不是節(jié)點(diǎn) i爪瓜，即可證明是平滑的。

假設(shè) $t = x_i - 1$ 匙瘪，此時(shí)第 i 個結(jié)點(diǎn)的當(dāng)前權(quán)重為 $w_i = t \* x_i - t \* S = (x_i - 1) \* x_i - (x_i - 1) \* S$ 铆铆。證明下一輪的第 1 步執(zhí)行完的值 $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$

因?yàn)? $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 輪后翁都，再執(zhí)行完第 1 步的值 $w_i + x_i <= 1$ 。
如果這 t 輪剛好是最開始的 t 輪谅猾，則必定存在另一個結(jié)點(diǎn) j 的值為 $x_j \* t$ 柄慰，所以有 $w_i + x_i <= 1 < 1 \* t < x_j \* t$ 。所以下一輪肯定不會選中 i税娜。

總結(jié)

盡管坐搔，平滑加權(quán)輪詢算法改善了加權(quán)輪詢算法調(diào)度的缺陷，即調(diào)度序列分散的不均勻敬矩，避免了實(shí)例負(fù)載突然加重的可能概行，但是仍然不能動態(tài)感知每個實(shí)例的負(fù)載。

若由于實(shí)例權(quán)重配置不合理弧岳，或者一些其他原因加重系統(tǒng)負(fù)載的情況占锯，平滑加權(quán)輪詢都無法實(shí)現(xiàn)每個實(shí)例的負(fù)載均衡，這時(shí)就需要有狀態(tài) 的調(diào)度算法來完成缩筛。

相關(guān)文章 ?

負(fù)載均衡算法 — 輪詢（2018-11-29）