前言

在反向代理、路由、分布式應用調度等場景中通常都需要用到負載均衡算法，負載均衡的關鍵要點是“均衡”，即確保調用請求能均衡地落到多個處理節點上，負載均衡算法一般使用隨機或輪詢都可以保證均衡性。

現實中由于服務器性能或資源分配的差異，導致我們需要為服務節點設置不同的權重，權重高的節點得到更多流量，同時降低低權重節點的流量比例。也即帶權重的均衡算法。

下面我們討論幾種常見的負載均衡算法，并針對其中一種給出完整的算法講解及實現。

一、隨機

這是最簡單的負載均衡算法，每次生成一個隨機數，然后對服務節點數進行取模，模值即為服務節點序號，很明顯這只能做到“均勻”，無法根據各服務節點的權重進行加權分配。不過略加調整即可實現加權分配：

構造一個范圍為總權重值的序列，然后用隨機數對總權重取模，模值所在區間即為對應的服務節點。譬如：有三個服務節點，其權重分別為：50、30、20，則節點集圖像大致如下：

|<-----------A----------->|<-----B----->|<---C--->|

|<0--------------------50>|<51-------80>|<81--100>|

代碼簡示：

struct Node<TKey> where TKey : IEquatable<TKey>
{public Node(TKey key, int boundary) {this.Key = key;this.Boundary = boundary;}public TKey Key;public int Boundary;
}class NodeSelector
{int _total;Node<string> _nodes;void Initialize() {_total = 50 + 30 + 20;_nodes = new[] {new Node<string>("Node-A", 50),new Node<string>("Node-B", 50 + 30),new Node<string>("Node-C", 50 + 30 + 20),};}string Select() {var value = Randomizer.GenerateInt32() % _total;for(int i = 0; i < _nodes.Length; i++) {if(value <= _nodes[i].Boundary)return _nodes[i].Key;}return null;}
}

隨機算法的表現恰如其名，在一個甚至多個調度周期內也無法確保各節點的權重匹配度，只能在大樣本條件下滿足權重的概率分布，總之就兩字：隨緣。

二、一致哈希

關于一致性哈希算法的文章已經汗牛充棟，亦不是本文的重點，所以就不再贅述。在構建哈希環的時候需要依據服務節點的權重比來設置相應數量的虛擬節點，之后確定服務節點的算法與上述隨機算法基本差不多。

三、平滑加權輪詢

終于來到本文的重點部分，我們假設有三個服務節點，其權重分別為：4、2、1，那么在一個調度周期內，最簡單調度序列如：{A,A,A,A,B,B,C}、{C,B,B,A,A,A,A} 或 {B,B,C,A,A,A,A}，但直覺這樣的調度順序不友好，因為它會在某一陣把壓力都落到同一個節點上，導致某個節點突然很忙的情況，類似汽車換擋的那種頓挫感。

如果調度序列變成：{A,B,A,C,A,B,A} 或 {A,A,B,A,C,A,B} 這樣就顯得“平滑”和“均衡”多了，我們主要參考 Nginx 和 LVS 采用的兩種算法。

Nginx 算法

• Nginx 的實現源碼：https://github.com/nginx/nginx/blob/52327e0627/src/http/ngx_http_upstream_round_robin.c

• Nginx 的算法摘要：https://github.com/nginx/nginx/commit/52327e0627f49dbda1e8db695e63a4b0af4448b1

on?each?peer?selection?we?increase?current_weight?of?each?eligible?peer?by?its?weight,?select?peer?with?greatest?current_weight?and?reduce?its?urrent_weight?by?total?number?of?weight?points?distributed?among?peers.

算法詳解

• 當前節點集初始值均為零：{0,0,0}

• 所有節點的當前權重值加上設定的權重值

• 在當前節點集中選取最大權重值的節點作為命中節點

• 命中節點的當前權重值減去總權重值作為其新權重值，其他節點保持不變

設 A、B、C 三個節點的權重分別為：4、2、1，演算步驟如下：

步驟	選擇前當前值	選擇節點(命中)	選擇后當前值
1	{ 4, 2, 1}	A	{-3, 2, 1}
2	{ 1, 4, 2}	B	{ 1,-3, 2}
3	{ 5,-1, 3}	A	{-2,-1, 3}
4	{ 2, 1, 4}	C	{ 2, 1,-3}
5	{ 6, 3,-2}	A	{-1, 3,-2}
6	{ 3, 5,-1}	B	{ 3,-2,-1}
7	{ 7, 0, 0}	A	{ 0, 0, 0}

由上發現三個節點的命中次數符合 4:2:1，而且權重大的節點不會霸占選擇權。經過一個周期(7輪選擇)后，當前權重值又回到了{0, 0, 0}，以上過程將按照周期進行循環，完全符合我們先前期望的平滑性。

數學證明

該算法的合理性和平滑性的數學證明：https://tenfy.cn/2018/11/12/smooth-weighted-round-robin

LVS 算法

Linux Virtual Server 采用的是另外一種，算法wiki文檔：http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling

從算法步驟和計算量上看，相對 Nginx 而言 LVS 算法略微簡單一些，性能可能會略好一點點（但都是同一個量級）；通過模擬數據發現當節點權重差異較大時，其平滑性沒有 Nginx 算法好。

總結

在 Zongsoft.Data 數據訪問框架的讀寫分離中需要將讀寫操作路由到不同權重的數據庫，于是采用 Nginx 的平滑權重輪詢均衡算法實現了數據源路由選擇器，下面分別是平滑權重輪詢器和數據路由的代碼：

• 平滑權重輪詢源碼：https://github.com/Zongsoft/Framework/blob/master/Zongsoft.Core/src/Components/Weighter.cs

• 數據源權重選擇器：https://github.com/Zongsoft/Framework/blob/master/Zongsoft.Data/src/Common/DataSourceSelector.cs

---

參考資料

• Nginx 平滑的基于權重輪詢算法分析

• Nginx 負載均衡及算法分析

• Nginx SWRR 算法解讀

---

提示：點擊“閱讀原文”以更舒適的姿勢閱覽本文。