国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

pinecone / 1925人閱讀

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

</>復(fù)制代碼

  1. 首發(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)度操作。

</>復(fù)制代碼

  1. 此輪詢調(diào)度算法思路首先被 Nginx 開發(fā)者提出,見 phusion/nginx 部分。
代碼實現(xiàn)

這里使用 PHP 來實現(xiàn),源碼見 fan-haobai/load-balance 部分。

</>復(fù)制代碼

  1. class SmoothWeightedRobin implements RobinInterface
  2. {
  3. private $services = array();
  4. private $total;
  5. private $currentPos = -1;
  6. public function init(array $services)
  7. {
  8. foreach ($services as $ip => $weight) {
  9. $this->services[] = [
  10. "ip" => $ip,
  11. "weight" => $weight,
  12. "current_weight" => $weight,
  13. ];
  14. }
  15. $this->total = count($this->services);
  16. }
  17. public function next()
  18. {
  19. // 獲取最大當(dāng)前有效權(quán)重實例的位置
  20. $this->currentPos = $this->getMaxCurrentWeightPos();
  21. // 當(dāng)前權(quán)重減去權(quán)重和
  22. $currentWeight = $this->getCurrentWeight($this->currentPos) - $this->getSumWeight();
  23. $this->setCurrentWeight($this->currentPos, $currentWeight);
  24. // 每個實例的當(dāng)前有效權(quán)重加上配置權(quán)重
  25. $this->recoverCurrentWeight();
  26. return $this->services[$this->currentPos]["ip"];
  27. }
  28. }

其中,getSumWeight()為所有實例的配置權(quán)重和;getCurrentWeight()setCurrentWeight()分別用于獲取和設(shè)置指定實例的當(dāng)前有效權(quán)重;getMaxCurrentWeightPos()求得最大當(dāng)前有效權(quán)重的實例位置,實現(xiàn)如下:

</>復(fù)制代碼

  1. public function getMaxCurrentWeightPos()
  2. {
  3. $currentWeight = $pos = 0;
  4. foreach ($this->services as $index => $service) {
  5. if ($service["current_weight"] > $currentWeight) {
  6. $currentWeight = $service["current_weight"];
  7. $pos = $index;
  8. }
  9. }
  10. return $pos;
  11. }

recoverCurrentWeight()用于調(diào)整每個實例的當(dāng)前有效權(quán)重,即加上配置權(quán)重,實現(xiàn)如下:

</>復(fù)制代碼

  1. public function recoverCurrentWeight()
  2. {
  3. foreach ($this->services as $index => &$service) {
  4. $service["current_weight"] += $service["weight"];
  5. }
  6. }

需要注意的是,在配置services服務(wù)列表時,同樣需要指定其權(quán)重:

</>復(fù)制代碼

  1. $services = [
  2. "192.168.10.1:2202" => 5,
  3. "192.168.10.2:2202" => 1,
  4. "192.168.10.3:2202" => 1,
  5. ];
數(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。

總結(jié)

盡管,平滑加權(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

相關(guān)文章

  • Hive集群合并之應(yīng)用端的負(fù)載均衡算法

    摘要:負(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.背景 有這么一個場景,我們有...

    wangbinke 評論0 收藏0
  • 一篇讀懂分布式架構(gòu)下的負(fù)載均衡

    摘要:一篇讀懂分布式架構(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:/...

    LuDongWei 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<