負載均衡策略與算法詳解

負載均衡策略

在分佈式架構中，負載均衡策略是非常重要的內容。它不僅能在一定程度上保證整個集羣的高可用，而且能夠提高系統的吞吐量，降低服務響應時間。每臺計算機的系統資源都是有限的，能夠承載的任務及處理的請求也是有限的。在分佈式系統中一般通過擴容來增加系統整體的承載能力，但是當大量併發的請求發生時，如果請求分配不均勻，就會導致部分機器收到了大量請求，而部分機器非常空閒，這種現象輕則導致吞吐率偏低、響應時間過大，不能讓資源的使用達到最優，重則導致接收過載的機器宕機、請求失敗，出現服務不可用的現象。所以如何讓這些請求較爲均勻地分攤到集羣內各個服務節點上，就是負載均衡策略所需要做的事情。

負載均衡的本質就是通過合理的算法將請求均勻地分攤到各個服務節點上，它需要根據一定的算法從一大批服務節點中選擇一個節點來接收和處理請求。而根據這個服務節點的集合信息是否存放在客戶端，可以將負載均衡分爲服務端負載均衡和客戶端負載均衡。

服務端負載均衡

服務端負載均衡是在服務端維護了服務節點集合信息，此處的服務端並不指服務提供者所在的節點，而是一個統一維護服務節點信息的負載均衡器 (Loadbalancer)，如下所示：

在服務消費端與服務提供端的中間有一個負載均衡器，當請求到達負載均衡器時，負載均衡器會通過一定的負載均衡算法從服務節點集合中選擇一個合適的節點，通過請求轉發器將該客戶端的請求轉發到對應的服務節點上。從上圖可以看出，服務端負載均衡可以讓客戶端和服務端解耦，保證對業務應用沒有侵入性，無論負載均衡器如何變化，都不會影響業務代碼。服務端負載均衡方案中除了負載均衡算法，最關鍵的就是網絡請求的轉發，根據網絡請求轉發發生的 層級 不同，可以分爲二層負載均衡、三層負載均衡、四層負載均衡和七層負載均衡。

這四種負載均衡方案中最常見的就是四層負載均衡和七層負載均衡。四層負載均衡與七層負載均衡最大的不同就是四層負載均衡的本質是轉發請求，而七層負載均衡是內容的交換和代理，因爲七層負載均衡中需要根據特殊字段來選擇最終的服務節點，負載均衡器就必須先反向代理最終的服務器來和客戶端建立連接，接收客戶端發送的真正的應用層內容的報文後才能選擇最終的服務節點。

除了依據請求轉發的層級進行分類，還可以根據負載均衡器的實現形態進行分類，即分爲硬件負載均衡和軟件負載均衡。常見的硬件負載均衡方案有 F5、NetScaler、Radware 等設備。常見的軟件負載均衡方案有 Nginx、LVS、HAProxy 等。

雖然服務端負載均衡方案能夠起到解耦的作用，但這種方案有兩個非常嚴重的缺點：

在微服務架構中，服務之間的依賴關係較爲複雜，在一個系統中存在許多服務和服務實例，如果通過服務端負載均衡方案實現負載均衡，則會導致負載均衡器變得尤爲重要，系統也增加了不少複雜度，如下圖所示：

隨着整個調用鏈路的增加，負載均衡器的影響越來越大，整個請求鏈路的傳輸效率由於負載均衡器不斷增加而不斷降低，所以服務端負載均衡並不適用於微服務架構的系統。

客戶端負載均衡

客戶端負載均衡的方案就是把服務列表維護在客戶端一側，由客戶端選擇某一個服務節點，並且與之通信。

客戶端負載均衡無須額外部署負載均衡器，並且也不需要進行請求轉發或者代理，客戶端可以直接和服務端連接並通信，傳輸損耗相對較少。沒有負載均衡器也就不存在負載均衡器的單點問題。但是客戶端負載均衡方案並不能像服務端負載均衡方案樣做到對業務應用的無侵入性，並且每一個客戶端都與服務節點連接並通信，所以連接數也會相應地增加。

負載均衡算法

無論是服務端負載均衡方案還是客戶端負載均衡方案，都離不開負載均衡算法。因爲無論如何都需要從服務節點的集合中挑選一個合理的節點來處理請求，而算法也直接決定了是否能將流量均勻地分攤到各個服務節點上，以實現資源的最大化利用，以及保障服務節點可用性的目的。下面我們介紹幾種常見的負載均衡算法。

隨機算法（加權隨機算法）

隨機算法最簡單的一種算法，服務消費者每次請求選擇的服務節點都是隨機的。這種算法在使用過程中的隨機性太強，非常容易出現集羣中某臺機器負載過高或者負載過低的情況，導致整個集羣的負載不夠均衡。而且每臺機器的配置和性能很可能不同，所能夠承載和處理的請求數量也不一樣，所以現實中往往會給每臺機器加上權重，將隨機算法優化爲加權隨機算法。

加權隨機算法是提供權重能力的隨機算法，舉個例子：一個服務集羣中存在服務節點 A、B、C，它們對應的權重爲 7、2、1，權重總和爲 10，現在把這些權重值平鋪在一維座標系上，分別出現三個區域，A 區域爲 [0,7)，B 區域爲 [7,9)，C 區域爲 [9,10)，然後產生一個 [10，10) 的隨機數，查找該數字落在哪個區間內，該區間所代表的機器就是此次請求選擇的服務節點：

^
|-------+
|       |--+
|       |  |-+
|   A   | B|C|
+-------|--|-|---->
0       7  9 10

這樣做可以保證權重越大的機器被擊中的概率就越大，它所承受的請求數量也會越多。加權隨機算法相對於普通的隨機算法而言，利用權重來減小隨機性，讓規模和配置不同的機器可以適當調整其權重，使整個集羣的負載更加平衡。

輪詢算法

輪詢算法可以分爲三種，分別是完全輪詢算法、加權輪詢算法和平滑加權輪詢算法。

完全輪詢算法

完全輪詢算法要求消費者每次請求所選擇的服務節點都是以輪詢的方式決定的。比如服務提供者有三個服務節點，分別是 A、B、C，服務消費者的第一個請求分配給 A 節點，第二個請求分配給 B 節點，第三個請求分配給 C 節點，第四個請求又分配給 A 服務器。這種完全輪詢的算法只適合每臺機器性能相近的情況，但是所有機器性能相近是一種非常理想的情況，更多的情況是每臺機器的性能都有所差異，這個時候性能差的機器被分到等額的請求，就會出現承受不了並且宕機的情況。

加權輪詢算法

加權輪詢算法會增加高權重節點的輪詢次數。舉個例子，服務節點 A、B、C 的權重比爲 7:2:1，那麼在 10 次請求中，服務節點 A 會收到其中的 7 次請求，服務節點 B 會收到其中的 2 次請求，服務節點 C 則收到其中的 1 次請求。也就是說，每臺機器能夠收到的請求歸結於它的權重。加權輪詢的順序則是 {A A A A A A A B B C}。

平滑加權輪詢算法

加權輪詢算法會導致流量先傾倒式地導向 A 服務節點，而其他服務節點卻短暫處於空閒狀態，降低了資源的利用率。當流量高峯到達時，也容易直接把高權重的服務節點 A 擊垮。所以平滑加權輪詢算法在加權輪詢算法的基礎上新增了平滑處理。

平滑加權輪詢算法來源於 Nginx，它通過加權和降權來保證每次請求都被均勻分發。在平滑加權輪詢算法中，每個服務節點都有兩個權重值，分別是 originalWeight 和 currentWeight。originalWeight 爲該節點的原始權重，currentWeight 的初始值爲 originalWeight 的大小。下面是平滑加權輪詢算法的推演過程：

  1. 請求到來，每個節點都計算一遍 currentWeight += originalWeight。

  2. 比較每個節點計算過的 currentWeight 值，並從中選擇最大值的節點作爲最終節點。

  3. 步驟 2 中選出的最終節點的 currentWeight -= 所有節點的 originalWeight 和。

依照上面的邏輯，舉例推演執行過程: 假設 A、B、C 三個節點的權重爲 7、2、1，下表爲計算過程：

RjBhiC

由上表可知，最後計算完成後 currentweight 又回到了原來的 7、2、1。這樣做得到的 10 次請求的輪詢順序爲 {A A A B A A C A A B}，不再是 {A A A A A A A B B C} 的順序。在保證按權重分配的基礎上，提高了輪詢的平滑性。

最少活躍數算法

最少活躍數算法是基於最小連接數算法衍生而來的，某個服務節點中活躍的調用數越小，表明該服務提節點處理請求的效率越高，也就表明單位時間內能夠處理的請求越多。此時服務消費端的請求應該選擇該服務節點作爲目標節點。

該算法實現的思路是每個服務節點都有一個活躍數 active 來記錄該服務的活躍值，每收到個請求，該 active 就會加 1，每完成一個請求，該 active 就會減 1。在服務運行一段時間後，性能相對較高的服務節點處理請求的速度更快，因此活躍數下降得也越快，此時服務消費者只需要選擇 active 最小的那個服務節點作爲目標節點，而這個 active 最小的服務節點就能夠優先獲取新的服務請求。

最少活躍數算法也可以像隨機算法和輪詢算法一樣引入權重，演變成最少活躍數加權算法，在比較活躍數時，如果最小活躍數的服務節點存在多個，則可以利用權重法來進行選擇，如果服務節點的權重也一樣，則從中隨機選擇一個服務節點。

一致性 Hash 負載均衡算法

一致性 Hash 負載均衡算法是一致性 Hash 算法在負載均上的應用。它可以保證相同的請求儘可能落到同一個服務器上，下面我們分析該算法的原理。

  1. 首先利用服務節點的 IP 地址或者其他信息生成該服務節點的唯一 Hash 值，並將這個 Hash 值投射到 [0,2^32] 的圓環上，如圖：

  1. 當請求到達時，會指定某個值來計算該請求的 Hash 值，這個值可能是請求方 IP 地址、用戶 ID 或者其他信息。當請求方的 Hash 值計算完成後，就會順時針尋找最接近該請求方 Hash 值的服務節點。例如，請求 a 計算後的 Hash 值落在服務節點 A 和服務節點 B 的 Hash 值之間，請求 b 計算後的 Hash 值落在服務節點 B 和服務節點 C 的 Hash 值之間，請求 c 計算後的 Hash 值落在服務節點 C 和服務節點 A 的 Hash 值之間，此時請求 a 將選擇 B 節點，請求 b 將選擇 C 節點，請求 c 將選擇 A 節點，如圖：

  1. 當有服務下線時，請求歸屬的節點也會按照順時針方向往後移動，比如 B 節點 “掛了” 之後請求 a 會選擇節點 C，如圖：

從上圖可以看到，Hash 一致性算法並不能夠保證 Hash 算法的平衡性，因爲如果一直往順時針的方向移動，就會導致後續的服務節點接收的請求越來越多，出現數據傾斜現象，最終導致整個集羣都被擊垮。要解決這個問題就需要引入虛擬節點。虛擬節點是實際節點在 Hash 空間的複製品，即對每一個服務節點計算多個 Hash 值，每個計算結果的位置都會放置一個此服務節點，如下圖所示：

利用虛擬節點，能夠在服務節點下線時，保持集羣內剩餘節點的負載相對均衡。舉個例子，原先 [0,2^32] 的圓環被分成了三段，分別是 A~B、B~C 和 C~A，當服務節點 B 下線後，服務節點 C 將接收單位時間內 2/3 的請求，而 A 還是繼續接收 C~A 範圍內的請求，這部分請求僅僅佔用了所有請求的 1/3。引入虛擬節點後，[0,2^32] 的圓環被分成了 3 * n 份，當服務節點 B 下線後，原先服務節點 B 所承受的壓力會被服務節點 A 和服務節點 C 分擔，避免了完全向服務節點 C 傾斜的現象。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OxJVu4giiIvw-yHPTWbVoQ

猜你喜歡