1.2.1　負載均衡算法

在選定轉發方式的情況下，采用哪種調度算法將決定整個負載均衡的性能表現，不同的算法適用于不同的應用場合，有時可能需要針對特殊場合，自行設計調度算法。每個負載均衡器都有自己獨有的算法，下面給大家介紹一下LVS、HAProxy、Nginx常見的算法。

1.LVS的常見算法

（1）輪叫調度（Round Robin）

負載均衡器通過“輪叫”調度算法將外部請求按順序輪流分配到集群中的真實服務器上，它均等地對待每一臺服務器，而不管服務器上實際的連接數和系統負載。任何形式的負載均衡器（包括硬件或軟件級別的）都帶有基本的輪叫（也叫輪詢功能）。

（2）加權輪叫（Weighted Round Robin）

負載均衡器通過“加權輪叫”調度算法根據真實服務器的不同處理能力來調度訪問請求，這樣可以保證處理能力強的服務器能處理更多的訪問流量。負載均衡器可以自動問詢真實服務器的負載情況，并動態地調整其權值。

（3）最少連接（Least Connections）

負載均衡器通過“最少連接”調度算法動態地將網絡請求調度到已建立的連接數最少的服務器上。如果集群系統的真實服務器具有相近的系統性能，采用“最少連接”調度算法可以較好地實現負載均衡。

（4）加權最少連接（Weighted Least Connections）

在集群系統中的服務器性能差異較大的情況下，負載均衡器采用“加權最少連接”調度算法優化負載均衡性能，具有較高權值的服務器將承受較大比例的活動連接負載。負載均衡器可以自動問詢真實服務器的負載情況，并動態地調整其權值。

（5）基于局部性的最少連接（Locality-Based Least Connections，LBLC）

“基于局部性的最少連接”調度算法是針對目標IP地址的負載均衡，目前主要用于Cache集群系統。該算法會根據請求的目標IP地址找出該目標IP地址最近使用的服務器，若該服務器是可用的且沒有超載，則將請求發送到該服務器；若服務器不存在，或者該服務器超載且有服務器處于一半的工作負載狀態，則用“最少連接”的原則選出一個可用的服務器，并將請求發送到該服務器。

（6）帶復制的基于局部性最少連接（Locality-Based Least Connections with Replication）

“帶復制的基于局部性最少連接”調度算法也是針對目標IP地址的負載均衡，目前主要用于Cache集群系統。它與LBLC算法的不同之處是它要維護從一個目標IP地址到一組服務器的映射，而LBLC算法維護的是從一個目標IP地址到一臺服務器的映射。該算法會根據請求的目標IP地址找出該目標IP地址對應的服務器組，并按“最少連接”原則從服務器組中選出一臺服務器，若服務器沒有超載，將請求發送到該服務器；若服務器超載，則按“最少連接”原則從這個集群中選出一臺服務器，將該服務器加入服務器組中，并將請求發送到該服務器。同時，如果該服務器組有一段時間沒有被修改，則會將最忙的服務器從服務器組中刪除，以降低復制的程度。

（7）目標地址散列（Destination IP Hashing）

“目標地址散列”調度算法會以請求的目標IP地址作為散列鍵（Hash Key）從靜態分配的散列表找出對應的服務器，若該服務器是可用的且未超載，那么會將請求發送到該服務器，否則返回空。

（8）源地址散列（Source IP Hashing）

“源地址散列”調度算法會以請求的源IP地址作為散列鍵從靜態分配的散列表找出對應的服務器，若該服務器是可用的且未超載，那么會將請求發送到該服務器，否則返回空。

（9）源IP和端口的Hash（Source IP and Source Port Hashing）

通過Hash函數將來自同一個源IP地址和源端口的請求映射到后端的同一臺服務器上，該算法適用于需要保證來自同一用戶同一業務的請求被分發到同一臺服務器的場景。

（10）隨機（Random）

隨機地將請求分發到不同的服務器上，從統計學角度來看，調度的結果是為各臺服務器平均分擔用戶的連接請求，該算法適用于集群中各機器性能相當，無明顯優劣差異的場景。

2.HAProxy的常見算法

HAProxy的算法現在也越來越多了，具體有如下8種：

1）roundrobin，表示簡單的輪詢，這是負載均衡基本都具備的算法。

2）static-rr，每個服務器根據權重輪流使用，類似roundrobin，但它是靜態的，意味著運行時修改權限是無效的。另外，它對服務器的數量沒有限制。

3）leastconn，連接數最少的服務器優先接收連接。leastconn建議用于長會話服務，如LDAP、SQL、TSE等，而不適合短會話協議，如HTTP。該算法是動態的，對于實例啟動慢的服務器權重會在運行中調整。

4）source，對請求源IP地址進行散列，用可用服務器的權重總數除以散列值，根據結果進行分配。只要服務器正常，同一個客戶端IP地址總是訪問同一個服務器。如果散列的結果隨可用服務器的數量變化而變化，那么客戶端會定向到不同的服務器。該算法一般用于不能插入cookie的TCP模式。它還可以在廣域網上為拒絕使用會話cookie的客戶端提供最有效的粘連。該算法默認是靜態的，所以運行時修改服務器的權重是無效的，但是算法會根據“hash-type”的變化做調整。

5）URI，表示根據請求的URI地址進行散列，用可用服務器的權重總數除以散列值，根據結果進行分配。只要服務器正常，同一個URI地址總是會訪問同一個服務器。一般用于緩存代理，以最大限度提高緩存的命中率。該算法只能用于HTTP后端，默認是靜態的，所以運行時修改服務器的權重是無效的，但是算法會根據“hash-type”的變化做調整。

6）url_param，表示請求的URL參數。在HTTP GET請求的查詢串中查找<param>中指定的URL參數，基本上可以鎖定使用特定規則的URL到特定負載均衡器節點的要求，該算法一般用于將同一個用戶的信息發送到同一個后端服務器上。該算法默認是靜態的，所以運行時修改服務器的權重是無效的，但是算法會根據“hash-type”的變化做調整。

7）hdr(<name>)，對于每個HTTP請求，此處由<name>指定的HTTP首部將會被取出做Hash計算，并由服務器總權重相除以后將HTTP請求發至某個被挑選的服務器，沒有有效值的會被輪詢調度。此算法的目的是使用同一瀏覽器，請求被發送到同一后端主機。

8）rdp-cookie(name)，根據cookie(name)來鎖定并散列每一次TCP請求，該機制用于退化的持久模式，可以使同一個用戶或者同一個會話ID總是發送給同一臺服務器。如果沒有cookie，則使用roundrobin算法代替。該算法默認是靜態的，所以運行時修改服務器的權重是無效的，但是算法會根據“hash-type”的變化做調整。

3.Nginx的常見算法

（1）roundrobin（默認）

每個請求按時間順序逐一分配到不同的后端服務器，如果后端服務器宕掉，則會跳過該服務器分配至下一個監控的服務器。并且它無須記錄當前所有連接的狀態，所以它是一種無狀態調度。

（2）weight

指定在輪詢的基礎上加上權重，權重和訪問比率成正比，即用于表明后端服務器的性能好壞，這種情況特別適合后端服務器性能不一致的工作場景。

（3）ip_hash

每個請求按訪問IP的散列結果分配，當新的請求到達時，先將其客戶端IP通過散列算法進行散列計算，得出一個值，在隨后的請求中，只要客戶端IP的散列值相同，就會被分配至同一個后端服務器，該調度算法可以解決Session的問題，但有時會導致分配不均即無法保證負載均衡。

（4）fair（第三方）

按后端服務器的響應時間來分配請求，響應時間短的優先分配。

（5）url_hash（第三方）

按訪問URL的散列結果來分配請求，使每個URL定向到同一個后端服務器，后端服務器為緩存時比較有效。

在upstream中加入Hash語句，server語句中不能寫入weight等其他的參數，hash_method使用的是Hash算法，示例如下：

---

upstream web_pool {
server squid1:3128;
server squid2:3128;
hash $request_uri;
hash_method crc32;
}

---

（6）一致性Hash算法

應該是借鑒了目前最流行的一致性Hash算法思路。它的具體做法是：將每個服務器虛擬成N個節點，均勻分布到Hash環上，每次請求根據配置的參數計算出一個Hash值，在Hash環上查找離這個Hash最近的虛擬節點，對應的服務器作為該次請求的后端機器，這樣做的好處是，如果是動態地增加了機器或者某臺Web機器宕機，對整個集群的影響最小，其工作原理如圖1-3所示。

圖1-3　一致性Hash算法工作原理圖

當后端是緩存服務器時，經常使用一致性Hash算法來進行負載均衡。

使用一致性Hash的好處在于，增減集群的緩存服務器時，只有少量的緩存會失效，回源量較小。在CDN集群架構中，Nginx或者自研的緩存軟件系統所使用的負載均衡推薦算法便是一致性Hash。

事實上，負載均衡算法也可以分成靜態算法和動態算法。那么我們如何分類上述算法呢？

靜態調度算法，即負載均衡會根據自身設定的規則進行分配，不需要考慮節點服務器的情況，如rr、wrr及ip_hash等。

動態調度算法，即負載均衡會根據后端節點的當前狀態來決定是否分發請求，如連接數少的優先獲取請求、響應時間短的優先獲取請求等。

了解了這些負載均衡算法的原理后，我們能夠在特定的應用場合選擇最合適的調度算法，從而盡可能地保持后端服務器的最佳利用性。當然也可以自行開發算法，不過這已超出本文范圍，請參考有關算法原理的資料。