負載均衡之輪的計算方法

㈠ 計算機的負載均衡演算法

計算機的負載均衡演算法主要有以下幾種：

1、靜態負載均衡演算法包括：輪詢，比率，優先權。

2、動態負載均衡演算法包括：最少連接數，最快響應速鄭模輪度，喊信觀察方法，預測法，動態性能分配，動態伺服器補充，服務質量，服務類型，規則模式。

負載均衡演算法的種類有很多種，常見的負載均衡演算法包括輪詢法、隨機法、源地址哈希法、加權輪詢法、加權隨機法、最小連接法等，應根據具體的使用場景選取對應的演算法。

(1)負載均衡之輪的計算方法擴展閱讀：

在計算機的世界，這就是大家耳熟能詳的負載均衡（load balancing），所謂負載均衡，就是說如果一組計算機節點（或者一組進程）提供相同的（同質的）服務，那麼對服務的請求就應該均勻的分攤到這些節點上。

負載均衡的意義在於，讓所有節點以最小的代價、最好的狀態對外提供服務，這樣系統吞吐量最大，性能更高，對於用戶而言請求的時間也更小。而且，負載均衡增強了系統的可靠性，最大化降低了單個節點過載、甚至crash的概率。不難想像，如果一個系統絕大部分請求都落在同一個節點上，那麼這些請求響應時間都很慢，而且萬一節碼沒點降級或者崩潰，那麼所有請求又會轉移到下一個節點，造成雪崩。

㈡ 負載均衡演算法 — 輪詢

在分布式系統中，為了實現負載均衡，必然會涉及到負載調度演算法，如 Nginx 和 RPC 服務發現等場景。常見的負載均衡演算法有 輪詢 、 源地址 Hash 、 最少連接數 ，而 輪詢 是最簡單且應用最廣的演算法。

3 種常見的喚晌輪詢調度演算法，分別為 簡單輪詢 、 加權輪詢 、 平滑加權輪詢 。本文將用如下 4 個服務，來詳細說明輪詢調度過程。

簡單輪詢是輪詢演算法中最簡單的一種，但扒橋由於它不支持配置負載，所以應用較少。

假設有 N 台實例 S = {S1, S2, …, Sn}，指示變數 currentPos 表示當前選擇的實例 ID，初始化為 -1。演算法可以描述為：
1、調度到下一個實例；
2、若所有實例已被 調度 過一次，則從頭開始調度；
3、每次調度重復步驟 1、2；

調度過程，如下：

這里使用 PHP 來實現，源碼見 fan-hao/load-balance 部分。

首先，定義一個統一的操作介面，主要有 init() 和 next() 這 2 個方法。

然後，根據簡單輪詢演算法思路，實現上述介面：

其中， total 為總實例數量，春鏈猛 services 為服務實例列表。由於簡單輪詢不需要配置權重，因此可簡單配置為：

在實際應用中，同一個服務會部署到不同的硬體環境，會出現性能不同的情況。若直接使用簡單輪詢調度演算法，給每個服務實例相同的負載，那麼，必然會出現資源浪費的情況。因此為了避免這種情況，一些人就提出了下面的 加權輪詢 演算法。

加權輪詢演算法引入了「權」值，改進了簡單輪詢演算法，可以根據硬體性能配置實例負載的權重，從而達到資源的合理利用。

假設有 N 台實例 S = {S1, S2, …, Sn}，權重 W = {W1, W2, ..., Wn}，指示變數 currentPos 表示當前選擇的實例 ID，初始化為 -1；變數 currentWeight 表示當前權重，初始值為 max(S)；max(S) 表示 N 台實例的最大權重值，gcd(S) 表示 N 台實例權重的最大公約數。

演算法可以描述為：
1、從上一次調度實例起，遍歷後面的每個實例；
2、若所有實例已被遍歷過一次，則減小 currentWeight 為 currentWeight - gcd(S)，並從頭開始遍歷；若 currentWeight 小於等於 0，則重置為 max(S)；
3、 直到 遍歷的實例的權重大於等於 currentWeight 時結束，此時實例為需調度的實例；
4、每次調度重復步驟 1、2、3；

例如，上述 4 個服務，最大權重 max(S) 為 4，最大公約數 gcd(S) 為 1。其調度過程如下：

這里使用 PHP 來實現，源碼見 fan-hao/load-balance 部分。

其中， getMaxWeight() 為所有實例的最大權重值； getGcd() 為所有實例權重的最大公約數，主要是通過 gcd() 方法（可用 gmp_gcd() 函數）求得 2 個數的最大公約數，然後求每一個實例的權重與當前最大公約數的最大公約數。實現如下：

需要注意的是，在配置 services 服務列表時，需要指定其權重：

加權輪詢 演算法雖然通過配置實例權重，解決了 簡單輪詢 的資源利用問題，但是它還是存在一個比較明顯的 缺陷 。例如：

服務實例 S = {a, b, c}，權重 W = {5, 1, 1}，使用加權輪詢調度生成的實例序列為 {a, a, a, a, a, b, c}，那麼就會存在連續 5 個請求都被調度到實例 a。而實際中，這種不均勻的負載是不被允許的，因為連續請求會突然加重實例 a 的負載，可能會導致嚴重的事故。

為了解決加權輪詢調度不均勻的缺陷，一些人提出了 平滑加權輪詢 調度演算法，它會生成的更均勻的調度序列 {a, a, b, a, c, a, a}。對於神秘的平滑加權輪詢演算法，我將在後續文章中詳細介紹它的原理和實現。

輪詢演算法是最簡單的調度演算法，因為它無需記錄當前所有連接的狀態，所以它是一種 無狀態 的調度演算法，這些特性使得它應用較廣。

輪詢調度演算法並不能動態感知每個實例的負載，它完全依賴於我們的工程經驗，人為配置權重來實現基本的負載均衡，並不能保證服務的高可用性。若服務的某些實例因其他原因負載突然加重，輪詢調度還是會一如既往地分配請求給這個實例，因此可能會形成小面積的宕機，導致服務的局部不可用。

相關文章 »