一、負載均衡簡介
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 網絡通信分類
軟體負載均衡從通信層面來看，又可以分為四層和七層負載均衡。
1) 七層負載均衡：就是可以根據通路使用者的 HTTP 請求頭、URL 資訊将請求轉發到特定的主機。
- DNS 重定向
- HTTP 重定向
- 反向代理
2) 四層負載均衡：基于 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 次以上，将請求分發到其他候選伺服器上。
反向代理的 優點：
1) 多種負載均衡算法：支援多種負載均衡算法，以應對不同的場景需求。
2) 可以監控伺服器：基于 HTTP 協定，可以監控轉發伺服器的狀态，如：系統負載、響應時間、是否可用、連接配接數、流量等，進而根據這些資料調整負載均衡的政策。
反向代理的 缺點：
1) 額外的轉發開銷：反向代理的轉發操作本身是有性能開銷的，可能會包括建立連接配接，等待連接配接響應，分析響應結果等操作。
2) 增加系統複雜度：反向代理常用于做分布式應用的水準擴充，但反向代理服務存在以下問題，為了解決以下問題會給系統整體增加額外的複雜度和運維成本：
- 反向代理服務如果自身當機，就無法通路站點，是以需要有 高可用 方案，常見的方案有：主備模式（一主一備）、雙主模式（互為主備）。
- 反向代理服務自身也存在性能瓶頸，随着需要轉發的請求量不斷攀升，需要有 可擴充 方案。
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 Random） 算法在随機算法的基礎上，按照機率調整權重，進行負載配置設定。
【示例】權重随機算法實作示例
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 的一緻性簡化哈希負載均衡算法。