摘要:首發(fā)于樊浩柏科學(xué)院在負(fù)載均衡算法輪詢一文中,我們就指出了加權(quán)輪詢算法一個明顯的缺陷。服務(wù)實例權(quán)重值我們已經(jīng)知道通過加權(quán)輪詢算法調(diào)度后,會生成如下不均勻的調(diào)度序列。相關(guān)文章負(fù)載均衡算法輪詢
</>復(fù)制代碼
首發(fā)于 樊浩柏科學(xué)院
在 負(fù)載均衡算法 — 輪詢 一文中,我們就指出了加權(quán)輪詢算法一個明顯的缺陷。即在某些特殊的權(quán)重下,加權(quán)輪詢調(diào)度會生成不均勻的實例序列,這種不平滑的負(fù)載可能會使某些實例出現(xiàn)瞬時高負(fù)載的現(xiàn)象,導(dǎo)致系統(tǒng)存在宕機(jī)的風(fēng)險。為了解決這個調(diào)度缺陷,就提出了 平滑加權(quán)輪詢 調(diào)度算法。
待解決的問題為了說明平滑加權(quán)輪詢調(diào)度的平滑性,使用以下 3 個特殊的權(quán)重實例來演示調(diào)度過程。
服務(wù)實例 | 權(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)度序列。
請求 | 選中的實例 |
---|---|
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è)有 N 臺實例 S = {S1, S2, …, Sn},配置權(quán)重 W = {W1, W2, …, Wn},有效權(quán)重 CW = {CW1, CW2, …, CWn}。每個實例 i 除了存在一個配置權(quán)重 Wi 外,還存在一個當(dāng)前有效權(quán)重 CWi,且 CWi 初始化為 Wi;指示變量 currentPos 表示當(dāng)前選擇的實例 ID,初始化為 -1;所有實例的配置權(quán)重和為 weightSum;
那么,調(diào)度算法可以描述為:
1、初始每個實例 i 的 當(dāng)前有效權(quán)重 CWi 為 配置權(quán)重 Wi,并求得配置權(quán)重和 weightSum;
2、選出 當(dāng)前有效權(quán)重 最大 的實例,將 當(dāng)前有效權(quán)重 CWi 減去所有實例的 權(quán)重和 weightSum,且變量 currentPos 指向此位置;
3、將每個實例 i 的 當(dāng)前有效權(quán)重 CWi 都加上 配置權(quán)重 Wi;
4、此時變量 currentPos 指向的實例就是需調(diào)度的實例;
5、每次調(diào)度重復(fù)上述步驟 2、3、4;
上述 3 個服務(wù),配置權(quán)重和 weightSum 為 7,其調(diào)度過程如下:
請求 | 選中前的當(dāng)前權(quán)重 | currentPos | 選中的實例 | 選中后的當(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)度時當(dāng)前有效權(quán)重值又回到 {0, 0, 0},實例的狀態(tài)同初始狀態(tài)一致,所以后續(xù)可以一直重復(fù)調(diào)度操作。
代碼實現(xiàn)</>復(fù)制代碼
此輪詢調(diào)度算法思路首先被 Nginx 開發(fā)者提出,見 phusion/nginx 部分。
這里使用 PHP 來實現(xiàn),源碼見 fan-haobai/load-balance 部分。
</>復(fù)制代碼
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)重實例的位置
$this->currentPos = $this->getMaxCurrentWeightPos();
// 當(dāng)前權(quán)重減去權(quán)重和
$currentWeight = $this->getCurrentWeight($this->currentPos) - $this->getSumWeight();
$this->setCurrentWeight($this->currentPos, $currentWeight);
// 每個實例的當(dāng)前有效權(quán)重加上配置權(quán)重
$this->recoverCurrentWeight();
return $this->services[$this->currentPos]["ip"];
}
}
其中,getSumWeight()為所有實例的配置權(quán)重和;getCurrentWeight()和 setCurrentWeight()分別用于獲取和設(shè)置指定實例的當(dāng)前有效權(quán)重;getMaxCurrentWeightPos()求得最大當(dāng)前有效權(quán)重的實例位置,實現(xiàn)如下:
</>復(fù)制代碼
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)整每個實例的當(dāng)前有效權(quán)重,即加上配置權(quán)重,實現(xiàn)如下:
</>復(fù)制代碼
public function recoverCurrentWeight()
{
foreach ($this->services as $index => &$service) {
$service["current_weight"] += $service["weight"];
}
}
需要注意的是,在配置services服務(wù)列表時,同樣需要指定其權(quán)重:
</>復(fù)制代碼
$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é)點,記第 i 個結(jié)點的權(quán)重是 $x_i$,設(shè)總權(quán)重為 $S = x_1 + x_2 + … + x_n$。選擇分兩步:
1、為每個節(jié)點加上它的權(quán)重值;
2、選擇最大的節(jié)點減去總的權(quán)重值;
n 個節(jié)點的初始化值為 [0, 0, …, 0],數(shù)組長度為 n,值都為 0。第一輪選擇的第 1 步執(zhí)行后,數(shù)組的值為 $[x_1, x_2, …, x_n]$。
假設(shè)第 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。
假設(shè)總共執(zhí)行 S 輪選擇,記第 i 個結(jié)點選擇 $m_i$ 次。第 i 個結(jié)點的當(dāng)前權(quán)重為 $w_i$。 假設(shè)節(jié)點 j 在第 t 輪(t < S)之前,已經(jīng)被選擇了 $x_j$ 次,記此時第 j 個結(jié)點的當(dāng)前權(quán)重為 $w_j = t * x_j - x_j * S = (t - S) * x_j < 0$, 因為 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é)點 k 使得 $w_k > 0$,永遠(yuǎn)不會再選中節(jié)點 j。
由此可以得出,第 i 個結(jié)點最多被選中 $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é)點即可。
跟上面一樣,假設(shè)總權(quán)重為 S,假如某個節(jié)點 i 連續(xù)選擇了 t($t < x_i$) 次,只要存在下一次選擇的不是節(jié)點 i,即可證明是平滑的。
假設(shè) $t = x_i - 1$,此時第 i 個結(jié)點的當(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$
因為 $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é)點 j 的值為 $x_j * t$,所以有 $w_i + x_i <= 1 < 1 * t < x_j * t$。所以下一輪肯定不會選中 i。
盡管,平滑加權(quán)輪詢算法改善了加權(quán)輪詢算法調(diào)度的缺陷,即調(diào)度序列分散的不均勻,避免了實例負(fù)載突然加重的可能,但是仍然不能動態(tài)感知每個實例的負(fù)載。
若由于實例權(quán)重配置不合理,或者一些其他原因加重系統(tǒng)負(fù)載的情況,平滑加權(quán)輪詢都無法實現(xiàn)每個實例的負(fù)載均衡,這時就需要 有狀態(tài) 的調(diào)度算法來完成。
相關(guān)文章 ?
負(fù)載均衡算法 — 輪詢(2018-11-29)
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/31098.html
摘要:負(fù)載均衡算法的選擇常用的負(fù)載均衡算法有哪些呢隨機(jī)算法,輪詢,算法,加權(quán)隨機(jī)算法,加權(quán)輪詢算法,一致性算法。首選,我們會有集群對應(yīng)的的地址列表,然后我們通過某種算法這里指的就是負(fù)載均衡算法,獲取其中一個的地址進(jìn)行任務(wù)提交這就是任務(wù)調(diào)度。 showImg(https://segmentfault.com/img/bVbsxlb?w=1104&h=794); 0.背景 有這么一個場景,我們有...
摘要:一篇讀懂分布式架構(gòu)下的負(fù)載均衡微信公眾號一刻鐘大型現(xiàn)實非嚴(yán)肅主義現(xiàn)場一刻鐘與你分享優(yōu)質(zhì)技術(shù)架構(gòu)與見聞,做一個有劇情的程序員關(guān)注可第一時間了解更多精彩內(nèi)容,定期有福利相送喲。 一篇讀懂分布式架構(gòu)下的負(fù)載均衡 微信公眾號:IT一刻鐘大型現(xiàn)實非嚴(yán)肅主義現(xiàn)場一刻鐘與你分享優(yōu)質(zhì)技術(shù)架構(gòu)與見聞,做一個有劇情的程序員關(guān)注可第一時間了解更多精彩內(nèi)容,定期有福利相送喲。 showImg(https:/...
閱讀 2031·2021-11-08 13:14
閱讀 2939·2021-10-18 13:34
閱讀 2028·2021-09-23 11:21
閱讀 3591·2019-08-30 15:54
閱讀 1759·2019-08-30 15:54
閱讀 2930·2019-08-29 15:33
閱讀 2580·2019-08-29 14:01
閱讀 1946·2019-08-29 13:52