一般情況下，我們對(duì)負(fù)載均衡的要求就是均勻，確保調(diào)用方的請(qǐng)求流量能夠均勻的發(fā)送到我們?nèi)哂嗖渴鸬腘個(gè)服務(wù)節(jié)點(diǎn)上，所以負(fù)載均衡的算法一般使用隨機(jī)或輪詢都可以保證被調(diào)用結(jié)點(diǎn)流量的均勻。

真實(shí)情況下，往往由于部署服務(wù)的服務(wù)器性能或資源分配等原因需要我們?yōu)榉?wù)結(jié)點(diǎn)設(shè)置不同的權(quán)重，權(quán)重高的結(jié)點(diǎn)可以分配多一些的流量，同時(shí)降低權(quán)重低的結(jié)點(diǎn)的流量比例。

這時(shí)負(fù)載均衡就不能簡(jiǎn)單的使用隨機(jī)或者輪詢了，需要添加對(duì)權(quán)重的支持。接下來我們分析幾種帶權(quán)重的負(fù)載均衡算法，并分析一下他們的優(yōu)缺點(diǎn)：

-     使用隨機(jī)數(shù)     -

設(shè)計(jì)思路如下：首先經(jīng)過負(fù)載均衡后選擇到一個(gè)結(jié)點(diǎn)，然后我們根據(jù)權(quán)重值再做一道攔截，按權(quán)重按比例放行，實(shí)現(xiàn)按降低結(jié)點(diǎn)流量的效果。例如我們規(guī)定權(quán)重的范圍從0到10之間，0拒絕，10放行。權(quán)重值越高，分配的流量就越多。

最簡(jiǎn)單的實(shí)現(xiàn)方案，可以使用隨機(jī)值，假設(shè)設(shè)置目標(biāo)結(jié)點(diǎn)的權(quán)重值為7，當(dāng)結(jié)點(diǎn)被負(fù)載均衡選中后，我們生成一個(gè)0到10之間的隨機(jī)數(shù)，小于7放行，大于7則不向目標(biāo)結(jié)點(diǎn)發(fā)送請(qǐng)求，需要從新做負(fù)載均衡計(jì)算，由此實(shí)現(xiàn)了將目標(biāo)結(jié)點(diǎn)的流量降低到原來的70%。

方案實(shí)現(xiàn)起來很簡(jiǎn)單，但問題也很明顯，我們都知道生成隨機(jī)數(shù)的計(jì)算會(huì)造成CPU的開銷，計(jì)算權(quán)重又發(fā)生在RPC調(diào)用過程中，所以每次RPC請(qǐng)求都會(huì)額外的增加一次隨機(jī)數(shù)計(jì)算，累積起來對(duì)CPU額外的開銷就很大了。我們可以進(jìn)一步優(yōu)化一下。

-     隨機(jī)數(shù)組     -

我們可以使用一個(gè)隨機(jī)數(shù)組代替上文描述的生成隨機(jī)數(shù)的策略，實(shí)現(xiàn)同樣效果的同時(shí)能夠減少CPU的計(jì)算量。接下來描述下隨機(jī)數(shù)組算法，同樣權(quán)重設(shè)計(jì)為0~10。

我們?yōu)槊總€(gè)被調(diào)用的結(jié)點(diǎn)都生成一個(gè)隨機(jī)數(shù)組，數(shù)組長(zhǎng)度為10。空間分配好后用0和1填充數(shù)組，0的個(gè)數(shù)與結(jié)點(diǎn)的權(quán)重值一樣，同時(shí)要保證0在數(shù)組中出現(xiàn)的位置是隨機(jī)的。

我們生成一個(gè)代表權(quán)重為“4”的隨機(jī)數(shù)組（4個(gè)0）。

和隨機(jī)數(shù)方案類似，我們?cè)谕瓿韶?fù)載均衡計(jì)算后，進(jìn)行權(quán)重?cái)r截。這個(gè)時(shí)候我們可以通過訪問隨機(jī)數(shù)組代替生成隨機(jī)數(shù)的計(jì)算，方案描述如下：記錄上一次訪問隨機(jī)數(shù)組的位置，取數(shù)組下一位置元素值，取到0則放行，1則拒絕，重新進(jìn)行負(fù)載均衡計(jì)算。方案的思路是，輪詢?cè)L問隨機(jī)數(shù)組，到達(dá)隨機(jī)效果。因?yàn)閿?shù)組的內(nèi)容是隨機(jī)的。

這兩種方案思路是一致的，都是在負(fù)載均衡計(jì)算后再加一道權(quán)重?cái)r截。但這樣的問題是流量控制不精確，無法實(shí)現(xiàn)精確個(gè)節(jié)點(diǎn)按權(quán)重比例分配流量。我們可以換個(gè)思路，實(shí)現(xiàn)精確的流量控制。

-     輪詢加權(quán)重負(fù)載策略     -

設(shè)計(jì)思路如下，設(shè)計(jì)一個(gè)權(quán)重因子，初始值為所有被調(diào)用的結(jié)點(diǎn)中最大權(quán)重值。負(fù)載均衡使用輪詢算法，被選中結(jié)點(diǎn)權(quán)重值大于等于權(quán)重因子則可以調(diào)用，否則用下一結(jié)點(diǎn)的權(quán)重值與權(quán)重因子比較，一輪循環(huán)結(jié)束后如果沒有選中結(jié)點(diǎn)，則降低權(quán)重因子，繼續(xù)通過與權(quán)重因子比較進(jìn)行選擇，直到選中為止。權(quán)重因子降為0后，恢復(fù)為最大權(quán)重值。

上述偽代碼中幾個(gè)變量意義如下：

• i：當(dāng)前輪詢的結(jié)點(diǎn)；

• n：可選擇結(jié)點(diǎn)數(shù)量；

• cw：權(quán)重因子；

• gcd(s)：權(quán)重因子每次降低的步長(zhǎng)；

• max(s)：所有結(jié)點(diǎn)中最大的權(quán)重值；

• W(si)：結(jié)點(diǎn)Si的權(quán)重值；

• Si：服務(wù)結(jié)點(diǎn)（S0~Sn-1，共n個(gè)）

權(quán)重因子的降低步長(zhǎng)為所有結(jié)點(diǎn)權(quán)重值的最大公約數(shù)。

假設(shè)有4個(gè)結(jié)點(diǎn)，A，B，C，D，權(quán)重值分別為，8，6，4，2，各結(jié)點(diǎn)權(quán)重值得最大公約數(shù)為2，所以權(quán)重降低步長(zhǎng)為2，通過上面的偽代碼，我們推演下負(fù)載均衡的流量分配結(jié)果。

初始條件：

• 1、i從0開始循環(huán)；

• 2、權(quán)重因子為8（偽代碼中初始化為0，減權(quán)重因子后小于0，被恢復(fù)為最大值）

  
  

第一次調(diào)用：i=0，A權(quán)重大于等于權(quán)重因子（8），可以調(diào)用A；

第二次調(diào)用：i=1，B權(quán)重小于8，不可以調(diào)用，繼續(xù)循環(huán)；

......

第二次調(diào)用會(huì)選擇哪個(gè)結(jié)點(diǎn)呢，以及后面的調(diào)用如何選擇的，歡迎大家在評(píng)留言給出自己的推演結(jié)果。

另外權(quán)重因子的降低步長(zhǎng)為什么是最大公約數(shù)呢？歡迎大家在評(píng)論區(qū)交流。

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
		

			

長(zhǎng)按訂閱更多精彩▼
		

			
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝