負載均衡算法及實踐
摘要:最少鏈接(Least Connection)法 — 在 Netflix Ribbon 中稱爲 BestAvailableRule ,根據 JavaDoc 解釋來看,就是“選擇最少併發請求的服務器”,也就是“最少鏈接法”。與加權輪詢法類似,加權隨機法也是根據後端服務器不同的配置和負載情況來配置不同的權重。
前幾天在看一個資料時,看到關於負載均衡算法的介紹。最近也在研究 Spring Cloud 和 Apache Dubbo 等微服務框架。正好負載均衡是微服務框架中一個很重要的知識點。就動手做個整理和總結。方便後續學習。
常見的負載均衡算法
輪詢(Round Robin)法
輪詢選擇指的是從已有的後端節點列表中按順序依次選擇一個節點出來提供服務。
優點:試圖做到請求轉移的絕對均衡。實現簡單,使用廣泛。
加權輪詢(Weighted Round Robin)法
實際使用中各個節點往往都帶有不同的權重,所以一般都需要實現帶權重的輪詢選擇。 權重高的被選中的次數多,權重低的被選中的次數少。
優點:是改良版。適用於服務器配置不一致時,可以將配置好的服務器多幹活,配置差的服務器少幹活以使機器的負載達到相同的水平。
靜態輪詢(Static Round Robin)法
HAProxy 中實現的一個負載均衡算法。
沒有後臺服務器的限制,服務器啓動時,修改權重也不會生效。增刪服務器時,服務器準備就緒後,會立即加入到服務隊列中。
隨機(Random)法
通過隨機函數,根據後端服務器列表的大小值來隨機選擇其中一臺進行訪問。由概率統計理論可以得知,隨着調用量的增大,其實際效果越來越接近於平均分配流量到每一臺後端服務器,也就是輪詢的效果。
加權隨機(Weighted Random)法
與加權輪詢法類似,加權隨機法也是根據後端服務器不同的配置和負載情況來配置不同的權重。不同的是,它是按照權重來隨機選擇服務器的,而不是順序。
原地址哈希(IP Hashing)法
源地址哈希的思想是獲取客戶端訪問的IP地址值,通過哈希函數計算得到一個數值,用該數值對服務器列表的大小進行取模運算,得到的結果便是要訪問的服務器的序號。
優點:保證了相同客戶端 IP 地址將會被哈希到同一臺後端服務器,直到後端服務器列表變更。根據此特性可以在服務消費者與服務提供者之間建立有狀態的 Session 會話。
URI 哈希(URI Hashing)法
HAProxy 中實現的一個負載均衡算法。支持部分 URI(問號之前)和完整 URI 兩種模式。
這個算法可以把同一個 URI 的訪問發送到同一臺服務器上,以最大程度提高緩存命中率。
該算法支持兩個可選參數 len
和 depth
,後跟一個正整數。僅在需要基於URI的開頭來平衡服務器時,這些選項可能會很有用。 len
參數指示算法僅應考慮URI開頭的許多字符來計算哈希。請注意,將 len
設置爲 1
幾乎沒有意義,因爲大多數URI都以前導 /
開頭。
depth
參數指示用於計算哈希的最大目錄深度。請求中的每個斜槓都計爲一個級別。如果同時指定了兩個參數,則在達到任意一個參數時都將停止評估。
URL 參數(URL Parameter)法
HAProxy 中實現的一個負載均衡算法。根據 URL 參數的哈希值來選擇服務器。
很明顯,這個負載均衡算法只能應用在七層協議上。
HTTP Header 參數(HTTP Header Parameter Name)法
HAProxy 中實現的一個負載均衡算法。根據 HTTP Header 中的指定參數名的參數值取哈希來選擇服務器。
很明顯,這個負載均衡算法只能應用在七層協議上。
一致性哈希(Consistent Hashing)法
-
首先求出每個Cache的哈希值,並將其配置到一個 0~2 32 的圓環區間上。
-
使用同樣的方法求出需要存儲對象的哈希值,也將其配置到這個圓環上。
-
從數據映射到的位置開始順時針查找,將數據保存到找到的第一個Cache節點上。如果超過 2 32 仍然找不到Cache節點,就會保存到第一個Cache節點上。
新增服務器
在這個環形哈希空間中,服務器 5 被映射在服務器 3 和服務器 4 之間,那麼受影響的將僅是沿 服務器 5 逆時針遍歷直到下一個服務器(服務器 3)之間的對象(它們本來映射到服務器 4 上)。
移除服務器
在這個環形哈希空間中,服務器 3 被移除,那麼受影響的將僅是沿服務器 3 逆時針遍歷直到下一個服務器(服務器 2)之間的對象(它們本來映射到服務器 3 上)。
虛擬服務器節點
哈希算法並不是保證絕對的平衡,尤其服務器較少的話,對象並不能被均勻的映射到服務器上。爲了解決這種情況,Consistent Hashing 引入了“虛擬節點”的概念: “虛擬節點”是實際節點在環形空間的複製品,一個實際節點對應了若干個“虛擬節點”,這個對應個數也成爲“複製個數”,“虛擬節點”在哈希空間中以哈希值排列。
仍以4臺服務器爲例,在下圖中看到,引入虛擬節點,並設置“複製個數”爲 2 後,共有 8 個“虛擬節點”分部在環形區域上,緩解了映射不均的情況。
該圖中,相同顏色和序號的節點都是由同一臺服務器虛擬化出來的節點。可以更加均勻地分配到整個環上,以實現負載的均衡性。
最少鏈接(Least Connection)法
最小連接數算法比較靈活和智能,由於後端服務器的配置不盡相同,對於請求的處理有快有慢,它正是根據後端服務器當前的連接情況,動態地選取其中當前積壓連接數最少的一臺服務器來處理當前請求,儘可能地提高後端服務器的利用效率,將負載合理地分流到每一臺機器。
最短響應時間(Shortest Response Time)法
監控服務的響應時間,並根據響應時間排序,選擇響應時間最短的服務器。
加權響應時間(Weighted Response Time)法
Netflix Ribbon 項目中實現了該算法。根據文檔,這個算法來源於 JCS,它是這樣搞的:
假設現在有四個節點,A(wt=10), B(wt=30), C(wt=40), D(wt=20)。
將服務器的所有權重加起來, 10+30+40+20=100
。則
-
10 (A’s weight)
-
40 (A’s weight + B’s weight)
-
80 (A’s weight + B’s weight + C’s weight)
-
100(A’s weight + B’s weight + C’s weight + C’s weight)
那麼,使用隨機數生成器,每次生成 1 到 100 的數字 number
,那麼:
-
1 ≤ number ≤ 10
則將請求發送給 A; -
11 ≤ number ≤ 40
則將請求發送給 B; -
41 ≤ number ≤ 80
則將請求發送給 C; -
81 ≤ number ≤ 100
則將請求發送給 D;
分區迴避法
Netflix Ribbon 項目中實現了該算法。
通過分區過濾函數,將不可用的分區中的服務器踢出可選列表,以使請求只會被轉發到可用分區上來降低請求的出錯率。
可用鏈接過濾法
Netflix Ribbon 項目中實現了該算法。
按照文檔說明,它是選出熔斷器關閉和鏈接不超過限制的服務器。
這個沒有見其他地方在用,這裏就不過多介紹了。
Spring Cloud 的實現
-
— 代碼實現在 ribbon/RoundRobinRule.java 。
-
最少鏈接(Least Connection)法 — 在 Netflix Ribbon 中稱爲
BestAvailableRule
,根據 JavaDoc 解釋來看,就是“選擇最少併發請求的服務器”,也就是“最少鏈接法”。代碼實現在 ribbon/BestAvailableRule.java 。 -
加權響應時間(Weighted Response Time)法 — 代碼實現: ribbon/WeightedResponseTimeRule.java 。
-
— 代碼實現: ribbon/ZoneAvoidanceRule.java 。
-
— 代碼實現: ribbon/AvailabilityFilteringRule.java 。
-
— 代碼實現在 ribbon/RandomRule.java 。
Spring Cloud 3.0.0-SNAPSHOT 版中不再依賴 NetFlix Ribbon 來做負載均衡了。具體支持的負載均衡算法等發佈正式版後再來研究。
Apache Dubbo 的實現
-
一致性哈希(Consistent Hashing)法 — 具體實現在 dubbo/ConsistentHashLoadBalance.java 。
-
最少鏈接(Least Connection)法 — 在 Apache Dubbo 中被稱爲
LeastActiveLoadBalance
,看文檔解釋應該就是“最少鏈接法”。具體實現在 dubbo/LeastActiveLoadBalance.java 。 -
— 具體實現在 dubbo/RandomLoadBalance.java 。
-
— 具體實現在 dubbo/RoundRobinLoadBalance.java 。
-
最短響應時間(Shortest Response Time)法 — 具體實現在 dubbo/ShortestResponseLoadBalance.java 。