深入淺出負載均衡
作者:vivo 互聯網團隊 - Zhang Peng
一、負載均衡簡介
1.1. 大型網站面臨的挑戰
大型網站都要面對龐大的用戶量,高併發,海量數據等挑戰。爲了提升系統整體的性能,可以採用垂直擴展和水平擴展兩種方式。
垂直擴展:在網站發展早期,可以從單機的角度通過增加硬件處理能力,比如 CPU 處理能力,內存容量,磁盤等方面,實現服務器處理能力的提升。但是,單機是有性能瓶頸的,一旦觸及瓶頸,再想提升,付出的成本和代價會極高。這顯然不能滿足大型分佈式系統(網站)所有應對的大流量,高併發,海量數據等挑戰。
水平擴展:通過集羣來分擔大型網站的流量。集羣中的應用服務器(節點)通常被設計成無狀態,用戶可以請求任何一個節點,這些節點共同分擔訪問壓力。水平擴展有兩個要點:
-
應用集羣:將同一應用部署到多臺機器上,組成處理集羣,接收負載均衡設備分發的請求,進行處理,並返回相應數據。
-
負載均衡:將用戶訪問請求,通過某種算法,分發到集羣中的節點。
1.2. 什麼是負載均衡
負載均衡(Load Balance,簡稱 LB)是高併發、高可用系統必不可少的關鍵組件,目標是 盡力將網絡流量平均分發到多個服務器上,以提高系統整體的響應速度和可用性。
負載均衡的主要作用如下:
**高併發:**負載均衡通過算法調整負載,盡力均勻的分配應用集羣中各節點的工作量,以此提高應用集羣的併發處理能力(吞吐量)。
**伸縮性:**添加或減少服務器數量,然後由負載均衡進行分發控制。這使得應用集羣具備伸縮性。
**高可用:**負載均衡器可以監控候選服務器,當服務器不可用時,自動跳過,將請求分發給可用的服務器。這使得應用集羣具備高可用的特性。
**安全防護:**有些負載均衡軟件或硬件提供了安全性功能,如:黑白名單處理、防火牆,防 DDos 攻擊等。
二、負載均衡的分類
支持負載均衡的技術很多,我們可以通過不同維度去進行分類。
2.1 載體維度分類
從支持負載均衡的載體來看,可以將負載均衡分爲兩類:硬件負載均衡、軟件負載均衡
2.1.1 硬件負載均衡
硬件負載均衡,一般是在定製處理器上運行的獨立負載均衡服務器,價格昂貴,土豪專屬。硬件負載均衡的主流產品有: F5 和 A10。
硬件負載均衡的 優點:
-
功能強大:支持全局負載均衡並提供較全面的、複雜的負載均衡算法。
-
性能強悍:硬件負載均衡由於是在專用處理器上運行,因此吞吐量大,可支持單機百萬以上的併發。
-
安全性高:往往具備防火牆,防 DDos 攻擊等安全功能。
硬件負載均衡的 缺點:
-
成本昂貴:購買和維護硬件負載均衡的成本都很高。
-
擴展性差:當訪問量突增時,超過限度不能動態擴容。
2.1.2 軟件負載均衡
軟件負載均衡,應用最廣泛,無論大公司還是小公司都會使用。
軟件負載均衡從軟件層面實現負載均衡,一般可以在任何標準物理設備上運行。
軟件負載均衡的 主流產品 有:Nginx、HAProxy、LVS。
-
LVS 可以作爲四層負載均衡器。其負載均衡的性能要優於 Nginx。
-
HAProxy 可以作爲 HTTP 和 TCP 負載均衡器。
-
Nginx、HAProxy 可以作爲四層或七層負載均衡器。
軟件負載均衡的 優點:
-
擴展性好:適應動態變化,可以通過添加軟件負載均衡實例,動態擴展到超出初始容量的能力。
-
成本低廉:軟件負載均衡可以在任何標準物理設備上運行,降低了購買和運維的成本。
軟件負載均衡的 缺點:
- 性能略差:相比於硬件負載均衡,軟件負載均衡的性能要略低一些。
2.2 網絡通信分類
軟件負載均衡從通信層面來看,又可以分爲四層和七層負載均衡。
- 七層負載均衡:就是可以根據訪問用戶的 HTTP 請求頭、URL 信息將請求轉發到特定的主機。
-
DNS 重定向
-
HTTP 重定向
-
反向代理
- 四層負載均衡:基於 IP 地址和端口進行請求的轉發。
-
修改 IP 地址
-
修改 MAC 地址
2.2.1 DNS 負載均衡
DNS 負載均衡一般用於互聯網公司,複雜的業務系統不適合使用。大型網站一般使用 DNS 負載均衡作爲 第一級負載均衡手段,然後在內部使用其它方式做第二級負載均衡。DNS 負載均衡屬於七層負載均衡。
DNS 即 域名解析服務,是 OSI 第七層網絡協議。DNS 被設計爲一個樹形結構的分佈式應用,自上而下依次爲:根域名服務器,一級域名服務器,二級域名服務器,... ,本地域名服務器。顯然,如果所有數據都存儲在根域名服務器,那麼 DNS 查詢的負載和開銷會非常龐大。
因此,DNS 查詢相對於 DNS 層級結構,是一個逆向的遞歸流程,DNS 客戶端依次請求本地 DNS 服務器,上一級 DNS 服務器,上上一級 DNS 服務器,... ,根 DNS 服務器(又叫權威 DNS 服務器),一旦命中,立即返回。爲了減少查詢次數,每一級 DNS 服務器都會設置 DNS 查詢緩存。
DNS 負載均衡的工作原理就是:基於 DNS 查詢緩存,按照負載情況返回不同服務器的 IP 地址。
DNS 重定向的 優點:
使用簡單:負載均衡工作,交給 DNS 服務器處理,省掉了負載均衡服務器維護的麻煩
提高性能:可以支持基於地址的域名解析,解析成距離用戶最近的服務器地址(類似 CDN 的原理),可以加快訪問速度,改善性能;
DNS 重定向的 缺點:
可用性差:DNS 解析是多級解析,新增 / 修改 DNS 後,解析時間較長;解析過程中,用戶訪問網站將失敗;
擴展性低:DNS 負載均衡的控制權在域名商那裏,無法對其做更多的改善和擴展;
維護性差:也不能反映服務器的當前運行狀態;支持的算法少;不能區分服務器的差異(不能根據系統與服務的狀態來判斷負載)。
2.2.2 HTTP 負載均衡
HTTP 負載均衡是基於 HTTP 重定向實現的。HTTP 負載均衡屬於七層負載均衡。
HTTP 重定向原理是:根據用戶的 HTTP 請求計算出一個真實的服務器地址,將該服務器地址寫入 HTTP 重定向響應中,返回給瀏覽器,由瀏覽器重新進行訪問。
HTTP 重定向的優點:方案簡單。
HTTP 重定向的 缺點:
性能較差:每次訪問需要兩次請求服務器,增加了訪問的延遲。
降低搜索排名:使用重定向後,搜索引擎會視爲 SEO 作弊。
如果負載均衡器宕機,就無法訪問該站點。
由於其缺點比較明顯,所以這種負載均衡策略實際應用較少。
2.2.3 反向代理負載均衡
反向代理(Reverse Proxy)方式是指以 代理服務器 來接受網絡請求,然後 將請求轉發給內網中的服務器,並將從內網中的服務器上得到的結果返回給網絡請求的客戶端。反向代理負載均衡屬於七層負載均衡。
反向代理服務的主流產品:Nginx、Apache。
正向代理與反向代理有什麼區別?
正向代理:發生在 客戶端,是由用戶主動發起的。翻牆軟件就是典型的正向代理,客戶端通過主動訪問代理服務器,讓代理服務器獲得需要的外網數據,然後轉發回客戶端。
反向代理:發生在 服務端,用戶不知道代理的存在。
反向代理是如何實現負載均衡的呢?以 Nginx 爲例,如下所示:
首先,在代理服務器上設定好負載均衡規則。然後,當收到客戶端請求,反向代理服務器攔截指定的域名或 IP 請求,根據負載均衡算法,將請求分發到候選服務器上。其次,如果某臺候選服務器宕機,反向代理服務器會有容錯處理,比如分發請求失敗 3 次以上,將請求分發到其他候選服務器上。
反向代理的 優點:
多種負載均衡算法:支持多種負載均衡算法,以應對不同的場景需求。
可以監控服務器:基於 HTTP 協議,可以監控轉發服務器的狀態,如:系統負載、響應時間、是否可用、連接數、流量等,從而根據這些數據調整負載均衡的策略。
反向代理的 缺點:
- 額外的轉發開銷:反向代理的轉發操作本身是有性能開銷的,可能會包括創建連接,等待連接響應,分析響應結果等操作。
- 增加系統複雜度:反向代理常用於做分佈式應用的水平擴展,但反向代理服務存在以下問題,爲了解決以下問題會給系統整體增加額外的複雜度和運維成本:
-
反向代理服務如果自身宕機,就無法訪問站點,所以需要有 高可用 方案,常見的方案有:主備模式(一主一備)、雙主模式(互爲主備)。
-
反向代理服務自身也存在性能瓶頸,隨着需要轉發的請求量不斷攀升,需要有 可擴展 方案。
2.2.4 IP 負載均衡
IP 負載均衡是在網絡層通過修改請求目的地址進行負載均衡。
如上圖所示,IP 均衡處理流程大致爲:
客戶端請求 192.168.137.10,由負載均衡服務器接收到報文。
負載均衡服務器根據算法選出一個服務節點 192.168.0.1,然後將報文請求地址改爲該節點的 IP。
真實服務節點收到請求報文,處理後,返回響應數據到負載均衡服務器。
負載均衡服務器將響應數據的源地址改負載均衡服務器地址,返回給客戶端。
IP 負載均衡在內核進程完成數據分發,較反向代理負載均衡有更好的從處理性能。但是,由於所有請求響應都要經過負載均衡服務器,集羣的吞吐量受制於負載均衡服務器的帶寬。
2.2.5 數據鏈路層負載均衡
數據鏈路層負載均衡是指在通信協議的數據鏈路層修改 mac 地址進行負載均衡。
在 Linux 平臺上最好的鏈路層負載均衡開源產品是 LVS (Linux Virtual Server)。LVS 是基於 Linux 內核中 netfilter 框架實現的負載均衡系統。netfilter 是內核態的 Linux 防火牆機制,可以在數據包流經過程中,根據規則設置若干個關卡(hook 函數)來執行相關的操作。
LVS 的工作流程大致如下:
當用戶訪問 www.sina.com.cn 時,用戶數據通過層層網絡,最後通過交換機進入 LVS 服務器網卡,並進入內核網絡層。
進入 PREROUTING 後經過路由查找,確定訪問的目的 VIP 是本機 IP 地址,所以數據包進入到 INPUT 鏈上
IPVS 是工作在 INPUT 鏈上,會根據訪問的 vip+port 判斷請求是否 IPVS 服務,如果是則調用註冊的 IPVS HOOK 函數,進行 IPVS 相關主流程,強行修改數據包的相關數據,並將數據包發往 POSTROUTING 鏈上。
POSTROUTING 上收到數據包後,根據目標 IP 地址(後端服務器),通過路由選路,將數據包最終發往後端的服務器上。
開源 LVS 版本有 3 種工作模式,每種模式工作原理截然不同,說各種模式都有自己的優缺點,分別適合不同的應用場景,不過最終本質的功能都是能實現均衡的流量調度和良好的擴展性。主要包括三種模式:DR 模式、NAT 模式、Tunnel 模式。
三、負載均衡算法
負載均衡器的實現可以分爲兩個部分:
根據負載均衡算法在候選服務器列表選出一個服務器;
將請求數據發送到該服務器上。
負載均衡算法是負載均衡服務核心中的核心。負載均衡產品多種多樣,但是各種負載均衡算法原理是共性的。負載均衡算法有很多種,分別適用於不同的應用場景,本文僅介紹最爲常見的負載均衡算法的特性及原理:輪詢、隨機、最小活躍數、源地址哈希、一致性哈希。
**注:**負載均衡算法的實現,推薦閱讀 Dubbo 官方負載均衡算法說明 ,源碼講解非常詳細,非常值得借鑑。
3.1 隨機
3.1.1 隨機算法
隨機(Random) 算法將請求隨機分發到候選服務器。
隨機算法 適合服務器硬件相同的場景。學習過概率論的都知道,調用量較小的時候,可能負載並不均勻,調用量越大,負載越均衡。
【示例】隨機算法實現示例
負載均衡接口
public interface LoadBalance<N extends Node> {
N select(List<N> nodes, String ip);
}
負載均衡抽象類
public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
@Override
public N select(List<N> nodes, String ip) {
if (CollectionUtil.isEmpty(nodes)) {
return null;
}
// 如果 nodes 列表中僅有一個 node,直接返回即可,無需進行負載均衡
if (nodes.size() == 1) {
return nodes.get(0);
}
return doSelect(nodes, ip);
}
protected abstract N doSelect(List<N> nodes, String ip);
}
服務器節點類
public class Node implements Comparable<Node> {
protected String url;
protected Integer weight;
protected Integer active;
// ...
}
隨機算法實現
public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {
// 在列表中隨機選取一個節點
int index = random.nextInt(nodes.size());
return nodes.get(index);
}
}
3.1.2 加權隨機算法
加權隨機(Weighted Rando****m) 算法在隨機算法的基礎上,按照概率調整權重,進行負載分配。
【示例】加權隨機算法實現示例
public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = ThreadLocalRandom.current();
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
AtomicInteger totalWeight = new AtomicInteger(0);
for (N node : nodes) {
Integer weight = node.getWeight();
totalWeight.getAndAdd(weight);
}
if (totalWeight.get() > 0) {
int offset = random.nextInt(totalWeight.get());
for (N node : nodes) {
// 讓隨機值 offset 減去權重值
offset -= node.getWeight();
if (offset < 0) {
// 返回相應的 Node
return node;
}
}
}
// 直接隨機返回一個
return nodes.get(random.nextInt(length));
}
}
3.2 輪詢
3.2.1 輪詢算法
**輪詢(Round Robin)**算法的策略是:將請求依次分發到候選服務器。
如下圖所示,負載均衡器收到來自客戶端的 6 個請求,(1, 3, 5) 的請求會被髮送到服務器 1,(2, 4, 6) 的請求會被髮送到服務器 2。
該算法適合場景:各服務器處理能力相近,且每個事務工作量差異不大。如果存在較大差異,那麼處理較慢的服務器就可能會積壓請求,最終無法承擔過大的負載。
【示例】輪詢算法示例
輪詢負載均衡算法實現
public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final AtomicInteger position = new AtomicInteger(0);
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
// 如果位置值已經等於節點數,重置爲 0
position.compareAndSet(length, 0);
N node = nodes.get(position.get());
position.getAndIncrement();
return node;
}
}
3.2.2 加權輪詢算法
**加權輪詢(Weighted Round Robbin)**算法在輪詢算法的基礎上,增加了權重屬性來調節轉發服務器的請求數目。性能高、處理速度快的節點應該設置更高的權重,使得分發時優先將請求分發到權重較高的節點上。
如下圖所示,服務器 A 設置權重爲 5,服務器 B 設置權重爲 1,負載均衡器收到來自客戶端的 6 個請求,那麼 (1, 2, 3, 4, 5) 請求會被髮送到服務器 A,(6) 請求會被髮送到服務器 B。
【示例】加權輪詢算法實現示例
以下實現基於 Dubbo 加權輪詢算法做了一些簡化。
public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
/**
* 60秒
*/
private static final int RECYCLE_PERIOD = 60000;
/**
* Node hashcode 到 WeightedRoundRobin 的映射關係
*/
private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
/**
* 原子更新鎖
*/
private AtomicBoolean updateLock = new AtomicBoolean();
@Override
protected N doSelect(List<N> nodes, String ip) {
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;
// 獲取當前時間
long now = System.currentTimeMillis();
N selectedNode = null;
WeightedRoundRobin selectedWRR = null;
// 下面這個循環主要做了這樣幾件事情:
// 1. 遍歷 Node 列表,檢測當前 Node 是否有相應的 WeightedRoundRobin,沒有則創建
// 2. 檢測 Node 權重是否發生了變化,若變化了,則更新 WeightedRoundRobin 的 weight 字段
// 3. 讓 current 字段加上自身權重,等價於 current += weight
// 4. 設置 lastUpdate 字段,即 lastUpdate = now
// 5. 尋找具有最大 current 的 Node,以及 Node 對應的 WeightedRoundRobin,
// 暫存起來,留作後用
// 6. 計算權重總和
for (N node : nodes) {
int hashCode = node.hashCode();
WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode);
int weight = node.getWeight();
if (weight < 0) {
weight = 0;
}
// 檢測當前 Node 是否有對應的 WeightedRoundRobin,沒有則創建
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
// 設置 Node 權重
weightedRoundRobin.setWeight(weight);
// 存儲 url 唯一標識 identifyString 到 weightedRoundRobin 的映射關係
weightMap.putIfAbsent(hashCode, weightedRoundRobin);
weightedRoundRobin = weightMap.get(hashCode);
}
// Node 權重不等於 WeightedRoundRobin 中保存的權重,說明權重變化了,此時進行更新
if (weight != weightedRoundRobin.getWeight()) {
weightedRoundRobin.setWeight(weight);
}
// 讓 current 加上自身權重,等價於 current += weight
long current = weightedRoundRobin.increaseCurrent();
// 設置 lastUpdate,表示近期更新過
weightedRoundRobin.setLastUpdate(now);
// 找出最大的 current
if (current > maxCurrent) {
maxCurrent = current;
// 將具有最大 current 權重的 Node 賦值給 selectedNode
selectedNode = node;
// 將 Node 對應的 weightedRoundRobin 賦值給 selectedWRR,留作後用
selectedWRR = weightedRoundRobin;
}
// 計算權重總和
totalWeight += weight;
}
// 對 weightMap 進行檢查,過濾掉長時間未被更新的節點。
// 該節點可能掛了,nodes 中不包含該節點,所以該節點的 lastUpdate 長時間無法被更新。
// 若未更新時長超過閾值後,就會被移除掉,默認閾值爲60秒。
if (!updateLock.get() && nodes.size() != weightMap.size()) {
if (updateLock.compareAndSet(false, true)) {
try {
// 遍歷修改,即移除過期記錄
weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
} finally {
updateLock.set(false);
}
}
}
if (selectedNode != null) {
// 讓 current 減去權重總和,等價於 current -= totalWeight
selectedWRR.decreaseCurrent(totalWeight);
// 返回具有最大 current 的 Node
return selectedNode;
}
// should not happen here
return nodes.get(0);
}
protected static class WeightedRoundRobin {
// 服務提供者權重
private int weight;
// 當前權重
private AtomicLong current = new AtomicLong(0);
// 最後一次更新時間
private long lastUpdate;
public long increaseCurrent() {
// current = current + weight;
return current.addAndGet(weight);
}
public long decreaseCurrent(int total) {
// current = current - total;
return current.addAndGet(-1 * total);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
// 初始情況下,current = 0
current.set(0);
}
public AtomicLong getCurrent() {
return current;
}
public void setCurrent(AtomicLong current) {
this.current = current;
}
public long getLastUpdate() {
return lastUpdate;
}
public void setLastUpdate(long lastUpdate) {
this.lastUpdate = lastUpdate;
}
}
}
3.3 最小活躍數
**最小活躍數(Least Active)**算法 將請求分發到連接數 / 請求數最少的候選服務器(目前處理請求最少的服務器)。
-
特點:根據候選服務器當前的請求連接數,動態分配。
-
場景:適用於對系統負載較爲敏感或請求連接時長相差較大的場景。
由於每個請求的連接時長不一樣,如果採用簡單的輪循或隨機算法,都可能出現某些服務器當前連接數過大,而另一些服務器的連接過小的情況,這就造成了負載並非真正均衡。雖然,輪詢或算法都可以通過加權重屬性的方式進行負載調整,但加權方式難以應對動態變化。
例如下圖中,(1, 3, 5) 請求會被髮送到服務器 1,但是 (1, 3) 很快就斷開連接,此時只有 (5) 請求連接服務器 1;(2, 4, 6) 請求被髮送到服務器 2,只有 (2) 的連接斷開。該系統繼續運行時,服務器 2 會承擔過大的負載。
最小活躍數算法會記錄當前時刻,每個候選節點正在處理的連接數,然後選擇連接數最小的節點。該策略能夠動態、實時地反應服務器的當前狀況,較爲合理地將負責分配均勻,適用於對當前系統負載較爲敏感的場景。
例如下圖中,服務器 1 當前連接數最小,那麼新到來的請求 6 就會被髮送到服務器 1 上。
**加權最小活躍數(Weighted Least Connection)**在最小活躍數的基礎上,根據服務器的性能爲每臺服務器分配權重,再根據權重計算出每臺服務器能處理的連接數。
最小活躍數算法實現要點:活躍調用數越小,表明該服務節點處理能力越高,單位時間內可處理更多的請求,應優先將請求分發給該服務。在具體實現中,每個服務節點對應一個活躍數 active。初始情況下,所有服務提供者活躍數均爲 0。每收到一個請求,活躍數加 1,完成請求後則將活躍數減 1。在服務運行一段時間後,性能好的服務提供者處理請求的速度更快,因此活躍數下降的也越快,此時這樣的服務提供者能夠優先獲取到新的服務請求、這就是最小活躍數負載均衡算法的基本思想。
【示例】最小活躍數算法實現
以下實現基於 Dubbo 最小活躍數負載均衡算法做了些許改動。
public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
// 最小的活躍數
int leastActive = -1;
// 具有相同“最小活躍數”的服務者提供者(以下用 Node 代稱)數量
int leastCount = 0;
// leastIndexs 用於記錄具有相同“最小活躍數”的 Node 在 nodes 列表中的下標信息
int[] leastIndexs = new int[length];
int totalWeight = 0;
// 第一個最小活躍數的 Node 權重值,用於與其他具有相同最小活躍數的 Node 的權重進行對比,
// 以檢測是否“所有具有相同最小活躍數的 Node 的權重”均相等
int firstWeight = 0;
boolean sameWeight = true;
// 遍歷 nodes 列表
for (int i = 0; i < length; i++) {
N node = nodes.get(i);
// 發現更小的活躍數,重新開始
if (leastActive == -1 || node.getActive() < leastActive) {
// 使用當前活躍數更新最小活躍數 leastActive
leastActive = node.getActive();
// 更新 leastCount 爲 1
leastCount = 1;
// 記錄當前下標值到 leastIndexs 中
leastIndexs[0] = i;
totalWeight = node.getWeight();
firstWeight = node.getWeight();
sameWeight = true;
// 當前 Node 的活躍數 node.getActive() 與最小活躍數 leastActive 相同
} else if (node.getActive() == leastActive) {
// 在 leastIndexs 中記錄下當前 Node 在 nodes 集合中的下標
leastIndexs[leastCount++] = i;
// 累加權重
totalWeight += node.getWeight();
// 檢測當前 Node 的權重與 firstWeight 是否相等,
// 不相等則將 sameWeight 置爲 false
if (sameWeight && i > 0
&& node.getWeight() != firstWeight) {
sameWeight = false;
}
}
}
// 當只有一個 Node 具有最小活躍數,此時直接返回該 Node 即可
if (leastCount == 1) {
return nodes.get(leastIndexs[0]);
}
// 有多個 Node 具有相同的最小活躍數,但它們之間的權重不同
if (!sameWeight && totalWeight > 0) {
// 隨機生成一個 [0, totalWeight) 之間的數字
int offsetWeight = random.nextInt(totalWeight);
// 循環讓隨機數減去具有最小活躍數的 Node 的權重值,
// 當 offset 小於等於0時,返回相應的 Node
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
// 獲取權重值,並讓隨機數減去權重值
offsetWeight -= nodes.get(leastIndex).getWeight();
if (offsetWeight <= 0) {
return nodes.get(leastIndex);
}
}
}
// 如果權重相同或權重爲0時,隨機返回一個 Node
return nodes.get(leastIndexs[random.nextInt(leastCount)]);
}
}
3.4 源地址哈希
**源地址哈希(IP Hash)**算法 根據請求源 IP,通過哈希計算得到一個數值,用該數值在候選服務器列表的進行取模運算,得到的結果便是選中的服務器。
可以保證同一 IP 的客戶端的請求會轉發到同一臺服務器上,用來實現會話粘滯(Sticky Session)。
特點:保證特定用戶總是請求到相同的服務器,若服務器宕機,會話會丟失。
【示例】源地址哈希算法實現示例
public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
@Override
protected N doSelect(List<N> nodes, String ip) {
if (StrUtil.isBlank(ip)) {
ip = "127.0.0.1";
}
int length = nodes.size();
int index = hash(ip) % length;
return nodes.get(index);
}
public int hash(String text) {
return HashUtil.fnvHash(text);
}
}
3.5 一致性哈希
一致性哈希(Consistent Hash)算法的目標是:相同的請求儘可能落到同一個服務器上。
一致性哈希 可以很好的解決 穩定性問題,可以將所有的 存儲節點 排列在 首尾相接 的 Hash 環上,每個 key 在計算 Hash 後會 順時針 找到 臨接 的 存儲節點 存放。而當有節點 加入 或 退出 時,僅影響該節點在 Hash 環上順時針相鄰的後續節點。
1)相同的請求是指:一般在使用一致性哈希時,需要指定一個 key 用於 hash 計算,可能是:
用戶 ID
請求方 IP
請求服務名稱,參數列表構成的串
2)儘可能是指:服務器可能發生上下線,少數服務器的變化不應該影響大多數的請求。
當某臺候選服務器宕機時,原本發往該服務器的請求,會基於虛擬節點,平攤到其它候選服務器,不會引起劇烈變動。
**優點:**加入 和 刪除 節點隻影響 哈希環 中 順時針方向 的 相鄰的節點,對其他節點無影響。
**缺點:**加減節點 會造成 哈希環 中部分數據 無法命中。當使用 少量節點 時,節點變化 將大範圍影響 哈希環 中 數據映射,不適合 少量數據節點 的分佈式方案。普通 的 一致性哈希分區 在增減節點時需要 增加一倍 或 減去一半 節點才能保證 數據 和 負載的均衡。
**注意:**因爲 一致性哈希分區 的這些缺點,一些分佈式系統採用 虛擬槽 對 一致性哈希 進行改進,比如 Dynamo 系統。
【示例】一致性哈希算法示例
public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
@SuppressWarnings("unchecked")
@Override
protected N doSelect(List<N> nodes, String ip) {
// 分片數,這裏設爲節點數的 4 倍
Integer replicaNum = nodes.size() * 4;
// 獲取 nodes 原始的 hashcode
int identityHashCode = System.identityHashCode(nodes);
// 如果 nodes 是一個新的 List 對象,意味着節點數量發生了變化
// 此時 selector.identityHashCode != identityHashCode 條件成立
ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
if (selector == null || selector.identityHashCode != identityHashCode) {
// 創建新的 ConsistentHashSelector
selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
selector = (ConsistentHashSelector<N>) selectors.get(ip);
}
// 調用 ConsistentHashSelector 的 select 方法選擇 Node
return selector.select(ip);
}
/**
* 一致性哈希選擇器
*/
private static final class ConsistentHashSelector<N extends Node> {
/**
* 存儲虛擬節點
*/
private final TreeMap<Long, N> virtualNodes;
private final int identityHashCode;
/**
* 構造器
*
* @param nodes 節點列表
* @param identityHashCode hashcode
* @param replicaNum 分片數
*/
ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
this.virtualNodes = new TreeMap<>();
this.identityHashCode = identityHashCode;
// 獲取虛擬節點數,默認爲 100
if (replicaNum == null) {
replicaNum = 100;
}
for (N node : nodes) {
for (int i = 0; i < replicaNum / 4; i++) {
// 對 url 進行 md5 運算,得到一個長度爲16的字節數組
byte[] digest = md5(node.getUrl());
// 對 digest 部分字節進行 4 次 hash 運算,得到四個不同的 long 型正整數
for (int j = 0; j < 4; j++) {
// h = 0 時,取 digest 中下標爲 0 ~ 3 的4個字節進行位運算
// h = 1 時,取 digest 中下標爲 4 ~ 7 的4個字節進行位運算
// h = 2, h = 3 時過程同上
long m = hash(digest, j);
// 將 hash 到 node 的映射關係存儲到 virtualNodes 中,
// virtualNodes 需要提供高效的查詢操作,因此選用 TreeMap 作爲存儲結構
virtualNodes.put(m, node);
}
}
}
}
public N select(String key) {
// 對參數 key 進行 md5 運算
byte[] digest = md5(key);
// 取 digest 數組的前四個字節進行 hash 運算,再將 hash 值傳給 selectForKey 方法,
// 尋找合適的 Node
return selectForKey(hash(digest, 0));
}
private N selectForKey(long hash) {
// 查找第一個大於或等於當前 hash 的節點
Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
// 如果 hash 大於 Node 在哈希環上最大的位置,此時 entry = null,
// 需要將 TreeMap 的頭節點賦值給 entry
if (entry == null) {
entry = virtualNodes.firstEntry();
}
// 返回 Node
return entry.getValue();
}
}
/**
* 計算 hash 值
*/
public static long hash(byte[] digest, int number) {
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
/**
* 計算 MD5 值
*/
public static byte[] md5(String value) {
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
md5.update(bytes);
return md5.digest();
}
}
以上示例基於 Dubbo 的一致性哈希負載均衡算法做了一些簡化。
四、參考資料
-
《大型網站技術架構:核心原理與案例分析》
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/69AGivVfwjEzCNvwJ1_2tQ