一般情況下，我們對負載均衡的要求就是均勻，確保調用方的請求流量能夠均勻的發(fā)送到我們冗余部署的N個服務節(jié)點上，所以負載均衡的算法一般使用隨機或輪詢都可以保證被調用結點流量的均勻。

真實情況下，往往由于部署服務的服務器性能或資源分配等原因需要我們?yōu)榉战Y點設置不同的權重，權重高的結點可以分配多一些的流量，同時降低權重低的結點的流量比例。

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

-     使用隨機數(shù)     -

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

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

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

-     隨機數(shù)組     -

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

我們?yōu)槊總€被調用的結點都生成一個隨機數(shù)組，數(shù)組長度為10?？臻g分配好后用0和1填充數(shù)組，0的個數(shù)與結點的權重值一樣，同時要保證0在數(shù)組中出現(xiàn)的位置是隨機的。

我們生成一個代表權重為“4”的隨機數(shù)組（4個0）。

和隨機數(shù)方案類似，我們在完成負載均衡計算后，進行權重攔截。這個時候我們可以通過訪問隨機數(shù)組代替生成隨機數(shù)的計算，方案描述如下：記錄上一次訪問隨機數(shù)組的位置，取數(shù)組下一位置元素值，取到0則放行，1則拒絕，重新進行負載均衡計算。方案的思路是，輪詢訪問隨機數(shù)組，到達隨機效果。因為數(shù)組的內容是隨機的。

這兩種方案思路是一致的，都是在負載均衡計算后再加一道權重攔截。但這樣的問題是流量控制不精確，無法實現(xiàn)精確個節(jié)點按權重比例分配流量。我們可以換個思路，實現(xiàn)精確的流量控制。

-     輪詢加權重負載策略     -

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

上述偽代碼中幾個變量意義如下：

• i：當前輪詢的結點；

• n：可選擇結點數(shù)量；

• cw：權重因子；

• gcd(s)：權重因子每次降低的步長；

• max(s)：所有結點中最大的權重值；

• W(si)：結點Si的權重值；

• Si：服務結點（S0~Sn-1，共n個）

權重因子的降低步長為所有結點權重值的最大公約數(shù)。

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

初始條件：

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

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

  
  

第一次調用：i=0，A權重大于等于權重因子（8），可以調用A；

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

......

第二次調用會選擇哪個結點呢，以及后面的調用如何選擇的，歡迎大家在評留言給出自己的推演結果。

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

特別推薦一個分享架構+算法的優(yōu)質內容，還沒關注的小伙伴，可以長按關注一下：
		

			

長按訂閱更多精彩▼
		

			
如有收獲，點個在看，誠摯感謝