摘要：首發(fā)于樊浩柏科學院在負載均衡算法輪詢一文中，我們就指出了加權輪詢算法一個明顯的缺陷。服務實例權重值我們已經(jīng)知道通過加權輪詢算法調度后，會生成如下不均勻的調度序列。相關文章負載均衡算法輪詢

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

在 負載均衡算法 — 輪詢 一文中，我們就指出了加權輪詢算法一個明顯的缺陷。即在某些特殊的權重下，加權輪詢調度會生成不均勻的實例序列，這種不平滑的負載可能會使某些實例出現(xiàn)瞬時高負載的現(xiàn)象，導致系統(tǒng)存在宕機的風險。為了解決這個調度缺陷，就提出了 平滑加權輪詢 調度算法。

為了說明平滑加權輪詢調度的平滑性，使用以下 3 個特殊的權重實例來演示調度過程。

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

接下來，我們就使用平滑加權輪詢算法調度上述實例，看看生成的實例序列如何？

假設有 N 臺實例 S = {S1, S2, …, Sn}，配置權重 W = {W1, W2, …, Wn}，有效權重 CW = {CW1, CW2, …, CWn}。每個實例 i 除了存在一個配置權重 Wi 外，還存在一個當前有效權重 CWi，且 CWi 初始化為 Wi；指示變量 currentPos 表示當前選擇的實例 ID，初始化為 -1；所有實例的配置權重和為 weightSum；

那么，調度算法可以描述為：
1、初始每個實例 i 的 當前有效權重 CWi 為 配置權重 Wi，并求得配置權重和 weightSum；
2、選出 當前有效權重 最大 的實例，將 當前有效權重 CWi 減去所有實例的 權重和 weightSum，且變量 currentPos 指向此位置；
3、將每個實例 i 的 當前有效權重 CWi 都加上 配置權重 Wi；
4、此時變量 currentPos 指向的實例就是需調度的實例；
5、每次調度重復上述步驟 2、3、4；

上述 3 個服務，配置權重和 weightSum 為 7，其調度過程如下：

可以看出上述調度序列分散是非常均勻的，且第 8 次調度時當前有效權重值又回到 {0, 0, 0}，實例的狀態(tài)同初始狀態(tài)一致，所以后續(xù)可以一直重復調度操作。

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

這里使用 PHP 來實現(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()
    {
        // 獲取最大當前有效權重實例的位置
        $this->currentPos = $this->getMaxCurrentWeightPos();

        // 當前權重減去權重和
        $currentWeight = $this->getCurrentWeight($this->currentPos) - $this->getSumWeight();
        $this->setCurrentWeight($this->currentPos, $currentWeight);

        // 每個實例的當前有效權重加上配置權重
        $this->recoverCurrentWeight();

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

其中，getSumWeight()為所有實例的配置權重和；getCurrentWeight()和 setCurrentWeight()分別用于獲取和設置指定實例的當前有效權重；getMaxCurrentWeightPos()求得最大當前有效權重的實例位置，實現(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()用于調整每個實例的當前有效權重，即加上配置權重，實現(xiàn)如下：

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

需要注意的是，在配置services服務列表時，同樣需要指定其權重：

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

可惜的是，關于此調度算法嚴謹?shù)臄?shù)學證明少之又少，不過網(wǎng)友 tenfy 給出的 安大神 證明過程，非常值得參考和學習。

假如有 n 個結點，記第 i 個結點的權重是 $x_i$，設總權重為 $S = x_1 + x_2 + … + x_n$。選擇分兩步：
1、為每個節(jié)點加上它的權重值；
2、選擇最大的節(jié)點減去總的權重值；

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

假設第 1 步后，最大的節(jié)點為 j，則第 j 個節(jié)點減去 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。

假設總共執(zhí)行 S 輪選擇，記第 i 個結點選擇 $m_i$ 次。第 i 個結點的當前權重為 $w_i$。 假設節(jié)點 j 在第 t 輪（t < S）之前，已經(jīng)被選擇了 $x_j$ 次，記此時第 j 個結點的當前權重為 $w_j = t * x_j - x_j * S = (t - S) * x_j < 0$， 因為 t 恒小于 S，所以 $w_j < 0$。

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

由此可以得出，第 i 個結點最多被選中 $x_i$ 次，即 $m_i <= x_i$。
因為 $S = m_1 + m_2 + … + m_n$ 且 $S = x_1 + x_2 + … + x_n$。 所以，可以得出 $m_i == x_i$。

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

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

假設 $t = x_i - 1$，此時第 i 個結點的當前權重為 $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$

因為 $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 輪，則必定存在另一個結點 j 的值為 $x_j * t$，所以有 $w_i + x_i <= 1 < 1 * t < x_j * t$。所以下一輪肯定不會選中 i。

盡管，平滑加權輪詢算法改善了加權輪詢算法調度的缺陷，即調度序列分散的不均勻，避免了實例負載突然加重的可能，但是仍然不能動態(tài)感知每個實例的負載。

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

相關文章 ?

負載均衡算法 — 輪詢（2018-11-29）