現代負載平衡演算法精析：一致性雜湊、平滑加權輪詢與 P2C 最小連線數

在分散式高併發架構中，負載平衡器（Load Balancer，如 Nginx、Envoy、HAProxy、AWS ALB）是流量分發的中樞神經。無論是 L4 傳輸層代理還是 L7 應用層路由，其核心使命都是將海量請求以高效、均勻且可預測的方式分配至後端伺服器叢集。

然而，不同場景對負載平衡演算法的需求大相徑庭：

• 無狀態 API 要求請求絕對均勻分發；
• 節點硬體規格異構時需要依權重進行平滑排程；
• 分散式快取（如 Redis / Memcached）或有狀態連線（如 WebSocket）則要求會話黏滯（Session Stickiness） 與節點增減時最小化擾動；
• 超大規模微服務網格（Service Mesh）中，為避免「羊群效應」與過度探測，需要採用 P2C（Power of Two Choices）。

本文將完整拆解五大主流負載平衡演算法的數學原理、底層實作與工程邊界。

---

1. 輪詢族系：從簡單輪詢到平滑加權輪詢 (Smooth WRR)#

1.1 簡單輪詢（Round Robin, RR）#

最基礎的排程演算法，將請求依序循環分發給後端節點。

• 假設前提：所有後端節點硬體算力完全一致，且所有請求的處理耗時大致均等。
• 侷限：若請求處理時間差異巨大（例如長查詢混合輕量 ping），或伺服器效能不同，會造成部分節點過載排隊。

若有伺服器權重 A: 5, B: 1, C: 1。普通演算法會直接連續分發 5 個請求給 A，序列為 [A, A, A, A, A, B, C]。這會導致伺服器 A 瞬間承受突發壓力。

1.3 Nginx 平滑加權輪詢演算法（Smooth Weighted Round Robin）#

為了解決突發聚集問題，Nginx 開發了平滑加權輪詢演算法。每個節點維護兩個變數：weight（固定權重）與 current_weight（動態權重，初始為 0）。

演算法步驟：

1. 每次選擇時，所有節點的 current_weight += weight。
2. 挑選 current_weight 最大者處理請求。
3. 被選中的節點將其 current_weight -= sum(weights)（減去所有節點固定權重之和）。

CONFIGURATION

節點權重初始配置

• Node A: 權重 5 ｜ Node B: 權重 1 ｜ Node C: 權重 1

• 總權重和 S = 7，初始各節點動態權重 current_weight 皆為 0

↓ 第 1 輪計算

ROUND 1

第 1 輪：命中 Node A

1. 累加權重：A: 5, B: 1, C: 1

2. A(5) 最大被選中，扣除總和 S(7) 得 -2

輪次結算：命中 A，剩餘 [-2, 1, 1]

↓ 第 2 輪計算

ROUND 2

第 2 輪：命中 Node A

1. 累加權重：A: 3, B: 2, C: 2

2. A(3) 最大被選中，扣除總和 S(7) 得 -4

輪次結算：命中 A，剩餘 [-4, 2, 2]

↓ 第 3 輪計算

ROUND 3

第 3 輪：平滑命中 Node B

1. 累加權重：A: 1, B: 3, C: 3

2. B 與 C 平手取前者 B(3)，扣除 S(7) 得 -4

輪次結算：命中 B，剩餘 [1, -4, 3]

FINAL SEQUENCE

平滑分發序列結果

A ➔ A ➔ B ➔ A ➔ C ➔ A ➔ A

七次分發中 A 均勻交錯出現，完美打散高權重節點的突發聚集流量。

---

2. 最小連線數族系與 P2C (Power of Two Choices)#

2.1 最少連線數（Least Connections）與加權最少連線（WLC）#

• Least Connections：動態追蹤每台伺服器當前開啟的活動連線數（Active Connections），優先將新請求轉發給連線數最少的節點。適合長連線（如 WebSocket）或耗時差異極大的 API。
• Weighted Least Connections (WLC)：計算公式為 Active Connections / Weight，選擇該比值最小的節點。

2.2 微服務網格的救星：P2C + EWMA 演算法#

在 Envoy 或大規模分散式微服務網格中，若每個負載平衡節點都去全局查詢「哪台伺服器連線最少」，會引發兩大問題：

1. 全局狀態同步成本極高。
2. 群羊效應（Herding Effect）：所有客戶端在同一微秒內發現某個節點最閒，同時將請求打向該節點，導致其瞬間被打垮。

P2C（Power of Two Random Choices） 的解法：

1. 從節點池中隨機挑選 2 個候選節點。
2. 計算這兩個節點的負載指標（結合活動請求數與 EWMA 指數加權移動平均延遲）。
3. 將請求分發給兩者中負載較低的一方。

數學證明：僅僅透過隨機挑選 2 個節點進行比較，就能以接近 O(1) 的極低複雜度，大幅壓平叢集峰值負載，徹底消除群羊效應！

---

3. 一致性雜湊（Consistent Hashing）與虛擬節點#

在快取系統（Memcached / Redis）或分庫分表路由中，傳統的模數雜湊 hash(key) % N 存在致命缺陷：當節點數量 N 發生增減時，幾乎 100% 的快取鍵都需要重新映射，引發毀滅性的快取雪崩。

3.1 一致性雜湊環原理#

1. 將整個雜湊值空間映射到一個首尾相連的環形空間（例如 0 ~ 2^32 - 1）。
2. 將實體伺服器節點的 IP 或名稱進行雜湊，落在環上的特定點。
3. 資料鍵（Data Key）計算雜湊後，沿順時針方向尋找第一個大於或等於該雜湊值的伺服器節點。

CLOCKWISE ROUTING

一致性雜湊環順時針路由

• 將雜湊空間映射在 0 ~ 2^32-1 環狀空間。

• 實體伺服器 Node A、B、C 雜湊至環上特定位置。

• 資料鍵（Key）計算雜湊後，順時針尋找第一個碰到的節點：Key 1 ➔ Node B、Key 2 ➔ Node C、Key 3 ➔ Node A。

LOCAL IMPACT ONLY

節點下線最小化擾動

• 若 Node B 突發下線，僅有原本命中 B 的 Key 1 順延至 Node C。

• 其餘絕大多數節點與 Key 完全不受影響，彻底杜絕模數雜湊 `hash(key) % N` 導致的 100% 快取全滅雪崩！

VIRTUAL NODES

虛擬節點防資料傾斜

• 實體節點較少時，節點分佈易不均勻造成某節點被塞爆。

• 解決方案：為每個實體節點配置 160 ~ 256 個虛擬節點（如 `Node_A#1` ~ `Node_A#160`）均勻散落在環上，大幅壓平分佈標準差。

O(log M) SEARCH

高效二分查找路由

所有節點 Hash 形成有序陣列，客戶端利用二分搜尋（Binary Search）在微秒級別鎖定目標伺服器，完全無網路額外往返！

• 節點下線：若 Node B 下線，受影響的僅有原先映射到 Node B 的 Key 1（順延至 Node C），其餘 Key 2、Key 3 完全不受影響。
• 節點新增：新增節點僅需分擔其逆時針方向相鄰節點的部分資料。

3.2 虛擬節點（Virtual Nodes）防資料傾斜#

若實體節點較少（例如只有 3 台），實體節點在環上的分佈可能極不均勻，導致大量請求集中在某一節點。

• 解決方案：為每個實體節點建立複數個「虛擬節點」（如 Node_A#1, Node_A#2, …, Node_A#160），將 160 個虛擬節點散列在環上。
• 效果：資料被均勻切分成數百個微小區間，標準差大幅縮小，負載分佈極度平坦。

---

4. 主動與被動健康檢查機制#

任何負載平衡演算法都必須建立在健康的節點池之上：

---

5. 現代系統架構選型總結#

• 無狀態 HTTP API / Web 服務：優先選用 平滑加權輪詢（Smooth WRR） 或 最小連線數（Least Connections）。
• 超大規模微服務 Service Mesh：優先選用 P2C + EWMA，兼顧低延遲與極致併發擴展。
• 分散式快取 / WebSocket 連線閘道：必須採用 帶虛擬節點的一致性雜湊（Consistent Hashing），保證節點異動時的會話穩定性與快取命中率。