深入淺出負載均衡
作者：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