LoadBalance 中文意思為負載均衡，它的職責是将網絡請求，或者其他形式的負載“均攤”到不同的機器上。避免叢集中部分伺服器壓力過大，而另一些伺服器比較空閑的情況。通過負載均衡，可以讓每台伺服器擷取到适合自己處理能力的負載。在為高負載的伺服器分流的同時，還可以避免資源浪費，一舉兩得。負載均衡可分為軟體負載均衡和硬體負載均衡。在我們日常開發中，一般很難接觸到硬體負載均衡。但軟體負載均衡還是能夠接觸到一些的，比如 Nginx。在 Dubbo 中，也有負載均衡的概念和相應的實作。Dubbo 需要對服務消費者的調用請求進行配置設定，避免少數服務提供者負載過大。服務提供者負載過大，會導緻部分服務調用逾時。是以将負載均衡到每個服務提供者上，是非常必要的。Dubbo 提供了4種負載均衡實作，分别是基于權重随機算法的 RandomLoadBalance、基于最少活躍調用數算法的 LeastActiveLoadBalance、基于 hash 一緻性的 ConsistentHashLoadBalance，以及基于權重輪詢算法的 RoundRobinLoadBalance。這幾個負載均衡算法代碼不是很長，但是想看懂也不是很容易，需要大家對這幾個算法的原理有一定了解才行。如果不是很了解，也沒不用太擔心。我會在分析每個算法的源碼之前，對算法原理進行簡單的講解，幫助大家建立初步的印象。
我在寫 Dubbo 源碼分析系列文章之初，當時 Dubbo 最新的版本為 2.6.4。近期，Dubbo 2.6.5 釋出了，其中就有對負載均衡部分代碼修改。是以我在分析完 2.6.4 版本後的源碼後，會另外分析 2.6.5 更新的部分。本篇文章内容非常之豐富，需要大家耐心閱讀。好了，其他的就不多說了，進入正題吧。
在 Dubbo 中，所有負載均衡實作類均繼承自 AbstractLoadBalance，該類實作了 LoadBalance 接口方法，并封裝了一些公共的邏輯。是以在分析負載均衡實作之前，先來看一下 AbstractLoadBalance 的邏輯。首先來看一下負載均衡的入口方法 select，如下：
select 方法的邏輯比較簡單，首先會檢測 invokers 集合的合法性，然後再檢測 invokers 集合元素數量。如果隻包含一個 Invoker，直接傳回該 Inovker 即可。如果包含多個 Invoker，此時需要通過負載均衡算法選擇一個 Invoker。具體的負載均衡算法由子類實作，接下來章節會對這些子類進行詳細分析。
AbstractLoadBalance 除了實作了 LoadBalance 接口方法，還封裝了一些公共邏輯 —— 服務提供者權重計算邏輯。具體實作如下：
上面是權重的計算過程，該過程主要用于保證當服務運作時長小于服務預熱時間時，對服務進行降級，避免讓服務在啟動之初就處于高負載狀态。服務預熱是一個優化手段，與此類似的還有 JVM 預熱。主要目的是讓服務啟動後“低功率”運作一段時間，使其效率慢慢提升至最佳狀态。關于預熱方面的更多知識，大家感興趣可以自己搜尋一下。
關于 AbstractLoadBalance 就先分析到這，接下來分析各個實作類的代碼。首先，我們從 Dubbo 預設的實作類 RandomLoadBalance 看起。
RandomLoadBalance 是權重随機算法的具體實作，它的算法思想很簡單。假設我們有一組伺服器 servers = [A, B, C]，他們對應的權重為 weights = [5, 3, 2]，權重總和為10。現在把這些權重值平鋪在一維坐标值上，[0, 5) 區間屬于伺服器 A，[5, 8) 區間屬于伺服器 B，[8, 10) 區間屬于伺服器 C。接下來通過随機數生成器生成一個範圍在 [0, 10) 之間的随機數，然後計算這個随機數會落到哪個區間上。比如數字3會落到伺服器 A 對應的區間上，此時傳回伺服器 A 即可。權重越大的機器，在坐标軸上對應的區間範圍就越大，是以随機數生成器生成的數字就會有更大的機率落到此區間内。隻要随機數生成器産生的随機數分布性很好，在經過多次選擇後，每個伺服器被選中的次數比例接近其權重比例。比如，經過一萬次選擇後，伺服器 A 被選中的次數大約為5000次，伺服器 B 被選中的次數約為3000次，伺服器 C 被選中的次數約為2000次。
以上就是 RandomLoadBalance 背後的算法思想，比較簡單，不多說了，下面開始分析源碼。
RandomLoadBalance 的算法思想比較簡單，在經過多次請求後，能夠将調用請求按照權重值進行“均勻”配置設定。當然 RandomLoadBalance 也存在一定的缺點，當調用次數比較少時，Random 産生的随機數可能會比較集中，此時多數請求會落到同一台伺服器上。這個缺點并不是很嚴重，多數情況下可以忽略。RandomLoadBalance 是一個簡單，高效的負載均衡實作，是以 Dubbo 選擇它作為預設實作。
關于 RandomLoadBalance 就先到這了，接下來分析 LeastActiveLoadBalance。
LeastActiveLoadBalance 翻譯過來是最小活躍數負載均衡，所謂的最小活躍數可了解為最少連接配接數。即服務提供者目前正在處理的請求數（一個請求對應一條連接配接）最少，表明該服務提供者效率高，機關時間内可處理更多的請求。此時應優先将請求配置設定給該服務提供者。在具體實作中，每個服務提供者對應一個活躍數 active。初始情況下，所有服務提供者活躍數均為0。每收到一個請求，活躍數加1，完成請求後則将活躍數減1。在服務運作一段時間後，性能好的服務提供者處理請求的速度更快，是以活躍數下降的也越快。此時這樣的服務提供者能夠優先擷取到新的服務請求，這就是最小活躍數負載均衡算法的基本思想。除了最小活躍數，LeastActiveLoadBalance 在實作上還引入了權重值。是以準确的來說，LeastActiveLoadBalance 是基于權重最小活躍數算法實作的。舉個例子說明一下，在一個服務提供者叢集中，有兩個性能優異的服務提供者。某一時刻它們的活躍數相同，此時 Dubbo 會根據它們的權重去配置設定請求，權重越大，擷取到新請求的可能性就越大。如果兩個服務提供者權重相同，此時随機選擇一個即可。關于 LeastActiveLoadBalance 的背景知識就先介紹到這裡，下面開始分析源碼。
如上，為了幫助大家了解代碼，我在上面的代碼中寫了大量的注釋。下面簡單總結一下以上代碼所做的事情，如下：
周遊 invokers 清單，尋找活躍數最小的 Invoker
如果有多個 Invoker 具有相同的最小活躍數，此時記錄下這些 Invoker 在 invokers 集合中的下标，以及累加它們的權重，比較它們之間的權重值是否相等
如果隻有一個 Invoker 具有最小的活躍數，此時直接傳回該 Invoker 即可
如果有多個 Invoker 具有最小活躍數，且它們的權重不相等，此時處理方式和 RandomLoadBalance 一緻
如果有多個 Invoker 具有最小活躍數，但它們的權重相等，此時随機傳回一個即可
以上就是 LeastActiveLoadBalance 大緻的實作邏輯，大家在閱讀的源碼的過程中要注意區分活躍數與權重這兩個概念，不要混為一談。
以上分析是基于 Dubbo 2.6.4 版本進行了，由于近期 Dubbo 2.6.5 釋出了，對負載均衡部分的代碼進行了一些更新。這其中就包含了本節分析的 LeastActiveLoadBalance，是以下面簡單說明一下 Dubbo 2.6.5 對 LeastActiveLoadBalance 進行了怎樣的修改。回到上面的源碼中，我在上面的代碼中标注了兩個黃色的五角星⭐️。兩處标記對應的代碼分别如下：
問題出在服務預熱階段，第一行代碼直接從 url 中去權重值，未被降級過。第二行代碼擷取到的是經過降級後的權重。第一行代碼擷取到的權重值最終會被累加到權重總和 totalWeight 中，這個時候會導緻一個問題。offsetWeight 是一個在 [0, totalWeight) 範圍内的随機數，而它所減去的是經過降級的權重。很有可能在經過 leastCount 次運算後，offsetWeight 仍然是大于0的，導緻無法選中 Invoker。這個問題對應的 issue 為 #904，在 pull request #2172 中被修複。具體的修複邏輯是将标注一處的代碼修改為：
另外，2.6.4 版本中的 LeastActiveLoadBalance 還要一個缺陷，即當一組 Invoker 具有相同的最小活躍數，且其中一個 Invoker 的權重值為1，此時這個 Invoker 無法被選中。缺陷代碼如下：
問題就出在了<code>offsetWeight <= 0</code>上，舉例說明，假設有一組 Invoker 的權重為 5、2、1，offsetWeight 最大值為 7。假設 offsetWeight = 7，你會發現，當 for 循環進行第二次周遊後 offsetWeight = 7 - 5 - 2 = 0，提前傳回了。此時，權重為1的 Invoker 就沒有機會被選中。這個修改起來也不難，可以将 <code>offsetWeight < 0</code>，不過 Dubbo 的是将<code>offsetWeight + 1</code>，也就是：
兩種改動都行，不過我認為覺得第一種方式更好一點，可與 RandomLoadBalance 邏輯保持一緻。這裡+1有點突兀，大家讀到這裡要特地思考一下為什麼要+1。
以上就是 Dubob 2.6.5 對 LeastActiveLoadBalance 的更新，不是很難了解，就不多說了。接下來分析基于一緻性 hash 思想的 ConsistentHashLoadBalance。
一緻性 hash 算法由麻省理工學院的 Karger 及其合作者于1997年提供出的，算法提出之初是用于大規模緩存系統的負載均衡。它的工作過程是這樣的，首先根據 ip 或者其他資訊為緩存節點生成一個 hash，并将這個 hash 投射到 [0, 232 - 1] 的圓環上。當有查詢或寫入請求時，則為緩存項的 key 生成一個 hash 值。然後查找第一個大于或等于該 hash 值的緩存節點，并到這個節點中查詢或寫入緩存項。如果目前節點挂了，則在下一次查詢或寫入緩存時，為緩存項查找另一個大于其 hash 值的緩存節點即可。大緻效果如下，每個緩存節點在圓環上占據一個位置。如果緩存項的 key 的 hash 值小于緩存節點 hash 值，則到該緩存節點中存儲或讀取緩存項。比如下面綠色點對應的緩存項存儲到 cache-2 節點中。由于 cache-3 挂了，原本應該存到該節點中的緩存想最終會存儲到 cache-4 節點中。
關于一緻性 hash 算法，我這裡隻做掃盲。具體的細節不讨論，大家請自行補充相關的背景知識。下面來看看一緻性 hash 在 Dubbo 中的應用。我們把上圖的緩存節點替換成 Dubbo 的服務提供者，于是得到了下圖：
這裡相同顔色的節點均屬于同一個服務提供者，比如 Invoker1-1，Invoker1-2，……, Invoker1-160。這樣做的目的是通過引入虛拟節點，讓 Invoker 在圓環上分散開來，避免資料傾斜問題。所謂資料傾斜是指，由于節點不夠分散，導緻大量請求落到了同一個節點上，而其他節點隻會接收到了少量的請求。比如：
如上，由于 Invoker-1 和 Invoker-2 在圓環上分布不均，導緻系統中75%的請求都會落到 Invoker-1 上，隻有 25% 的請求會落到 Invoker-2 上。解決這個問題辦法是引入虛拟節點，通過虛拟節點均衡各個節點的請求量。
到這裡背景知識就普及完了，接下來開始分析源碼。我們先從 ConsistentHashLoadBalance 的 doSelect 方法開始看起，如下：
如上，doSelect 方法主要做了一些前置工作，比如檢測 invokers 清單是不是變動過，以及建立 ConsistentHashSelector。這些工作做完後，接下來開始調用 select 方法執行負載均衡邏輯。在分析 select 方法之前，我們先來看一下一緻性 hash 選擇器 ConsistentHashSelector 的初始化過程，如下：
ConsistentHashSelector 進行了一些列的初始化方法，比如從配置中擷取虛拟節點數以及參與 hash 計算的參數下标，預設情況下隻使用第一個參數進行 hash。需要特别說明的是，ConsistentHashLoadBalance 的負載均衡邏輯隻受參數值影響，具有相同參數值的請求将會被配置設定給同一個服務提供者。ConsistentHashLoadBalance 不 care 權重，是以使用時需要注意一下。
在擷取虛拟節點數和參數下标配置後，接下來要做到事情是計算虛拟節點 hash 值，并将虛拟節點存儲到 TreeMap 中。到此，ConsistentHashSelector 初始化工作就完成了。接下來，我們再來看看 select 方法的邏輯。
如上，選擇的過程比較簡單了。首先是對參數進行 md5 以及 hash 運算，得到一個 hash 值。然後再拿這個值到 TreeMap 中查找目标 Invoker 即可。
到此關于 ConsistentHashLoadBalance 就分析完了。在閱讀 ConsistentHashLoadBalance 之前，大家一定要先補充背景知識。否者即使這裡隻有一百多行代碼，也很難看懂。好了，本節先分析到這。
本節，我們來看一下 Dubbo 中的權重輪詢負載均衡的實作 RoundRobinLoadBalance。在詳細分析源碼前，我們還是先來了解一下什麼是權重輪詢。這裡從最簡單的輪詢開始講起，所謂輪詢就是将請求輪流配置設定給一組伺服器。舉個例子，我們有三台伺服器 A、B、C。我們将第一個請求配置設定給伺服器 A，第二個請求配置設定給伺服器 B，第三個請求配置設定給伺服器 C，第四個請求再次配置設定給伺服器 A。這個過程就叫做輪詢。輪詢是一種無狀态負載均衡算法，實作簡單，适用于每台伺服器性能相近的場景下。顯然，現實情況下，我們并不能保證每台伺服器性能均相近。如果我們将等量的請求配置設定給性能較差的伺服器，這顯然是不合理的。是以，這個時候我們需要權重輪詢算法，對輪詢過程進行幹預，使得性能好的伺服器可以得到更多的請求，性能差的得到的少一些。每台伺服器能夠得到的請求數比例，接近或等于他們的權重比。比如伺服器 A、B、C 權重比為 5:2:1。那麼在8次請求中，伺服器 A 将擷取到其中的5次請求，伺服器 B 擷取到其中的2次請求，伺服器 C 則擷取到其中的1次請求。
以上就是權重輪詢的算法思想，搞懂了這個思想，接下來我們就可以分析源碼了。我們先來看一下 2.6.4 版本的 RoundRobinLoadBalance。
如上，RoundRobinLoadBalance 的每行代碼都不是很難了解，但是将它們組合到一起之後，好像就看不懂了。這裡對上面代碼的主要邏輯進行總結，如下：
找到最大權重值，并計算出權重和
使用調用編号對權重總和進行取餘操作，得到 mod
檢測 mod 的值是否等于0，且 Invoker 權重是否大于0，如果兩個條件均滿足，則傳回該 Invoker
如果上面條件不滿足，且 Invoker 權重大于0，此時對 mod 和權重進行遞減
再次循環，重複步驟3、4
以上過程對應的原理不太好解釋，是以下面直接舉例說明把。假設我們有三台伺服器 servers = [A, B, C]，對應的權重為 weights = [2, 5, 1]。接下來對上面的邏輯進行簡單的模拟。
mod = 0：滿足條件，此時直接傳回伺服器 A
mod = 1：需要進行一次遞減操作才能滿足條件，此時傳回伺服器 B
mod = 2：需要進行兩次遞減操作才能滿足條件，此時傳回伺服器 C
mod = 3：需要進行三次遞減操作才能滿足條件，經過遞減後，伺服器權重為 [1, 4, 0]，此時傳回伺服器 A
mod = 4：需要進行四次遞減操作才能滿足條件，經過遞減後，伺服器權重為 [0, 4, 0]，此時傳回伺服器 B
mod = 5：需要進行五次遞減操作才能滿足條件，經過遞減後，伺服器權重為 [0, 3, 0]，此時傳回伺服器 B
mod = 6：需要進行六次遞減操作才能滿足條件，經過遞減後，伺服器權重為 [0, 2, 0]，此時傳回伺服器 B
mod = 7：需要進行七次遞減操作才能滿足條件，經過遞減後，伺服器權重為 [0, 1, 0]，此時傳回伺服器 B
經過8次調用後，我們得到的負載均衡結果為 [A, B, C, A, B, B, B, B]，次數比 A:B:C = 2:5:1，等于權重比。當 sequence = 8 時，mod = 0，此時重頭再來。從上面的模拟過程可以看出，當 mod >= 3 後，伺服器 C 就不會被選中了，因為它的權重被減為0了。當 mod >= 4 後，伺服器 A 的權重被減為0，此後 A 就不會再被選中。
以上是 2.6.4 版本的 RoundRobinLoadBalance 分析過程，大家如果看不懂，自己可以定義一些權重組合進行模拟。也可以寫點測試用例，進行調試分析，總之不要死看。
2.6.4 版本的 RoundRobinLoadBalance 存在着比較嚴重的性能問題，該問題最初是在 issue #2578 中被回報出來。問題出在了 Invoker 的傳回時機上，RoundRobinLoadBalance 需要在<code>mod == 0 && v.getValue() > 0</code> 條件成立的情況下才會被傳回相應的 Invoker。假如 mod 很大，比如 10000，50000，甚至更大時，doSelect 方法需要進行很多次計算才能将 mod 減為0。由此可知，doSelect 的效率與 mod 有關，時間複雜度為 O(mod)。mod 又受最大權重 maxWeight 的影響，是以當某個服務提供者配置了非常大的權重，此時 RoundRobinLoadBalance 會産生比較嚴重的性能問題。這個問題被回報後，社群很快做了回應。并對 RoundRobinLoadBalance 的代碼進行了重構，将時間複雜度優化至了常量級别。這個優化可以說很好了，下面我們來學習一下優化後的代碼。
上面代碼的邏輯是這樣的，每進行一輪循環，重新計算 currentWeight。如果目前 Invoker 權重大于 currentWeight，則傳回該 Invoker。還是舉例說明吧，假設伺服器 [A, B, C] 對應權重 [5, 2, 1]。
第一輪循環，currentWeight = 1，可傳回 A 和 B
第二輪循環，currentWeight = 2，傳回 A
第三輪循環，currentWeight = 3，傳回 A
第四輪循環，currentWeight = 4，傳回 A
第五輪循環，currentWeight = 0，傳回 A, B, C
如上，這裡的一輪循環是指 index 再次變為0所經曆過的循環，這裡可以把 index = 0 看做是一輪循環的開始。每一輪循環的次數與 Invoker 的數量有關，Invoker 數量通常不會太多，是以我們可以認為上面代碼的時間複雜度為常數級。
重構後的 RoundRobinLoadBalance 看起來已經很不錯了，但是在代碼更新不久後，很有又被重構了。這次重構原因是新的 RoundRobinLoadBalance 在某些情況下選出的伺服器序列不夠均勻。比如，伺服器 [A, B, C] 對應權重 [5, 1, 1]。現在進行7次負載均衡，選擇出來的序列為 [A, A, A, A, A, B, C]。前5個請求全部都落在了伺服器 A上，分布不夠均勻。這将會使伺服器 A 短時間内接收大量的請求，壓力陡增。而 B 和 C 無請求，處于空閑狀态。我們期望的結果是這樣的 [A, A, B, A, C, A, A]，不同伺服器可以穿插擷取請求。為了增加負載均衡結果的平滑性，社群再次對 RoundRobinLoadBalance 的實作進行了重構。這次重構參考自 Nginx 的平滑權重輪詢負載均衡，實作原理是這樣的。每個伺服器對應兩個權重，分别為 weight 和 currentWeight。其中 weight 是固定的，currentWeight 是會動态調整，初始值為0。當有新的請求進來時，周遊伺服器清單，讓它的 currentWeight 加上自身權重。周遊完成後，找到最大的 currentWeight，并将其減去權重總和，然後傳回相應的伺服器即可。
上面描述不是很好了解，下面還是舉例說明吧。仍然使用伺服器 [A, B, C] 對應權重 [5, 1, 1] 的例子進行說明，現在有7個請求依次進入負載均衡邏輯，選擇過程如下：
請求編号
currentWeight 數組
選擇結果
減去權重總和後的 currentWeight 數組
1
[5, 1, 1]
A
[-2, 1, 1]
2
[3, 2, 2]
[-4, 2, 2]
3
[1, 3, 3]
B
[1, -4, 3]
4
[6, -3, 4]
[-1, -3, 4]
5
[4, -2, 5]
C
[4, -2, -2]
6
[9, -1, -1]
[2, -1, -1]
7
[7, 0, 0]
[0, 0, 0]
如上，經過平滑性處理後，得到的伺服器序列為 [A, A, B, A, C, A, A]，相比之前的序列 [A, A, A, A, A, B, C]，分布性要好一些。初始情況下 currentWeight = [0, 0, 0]，第7個請求處理完後，currentWeight 再次變為 [0, 0, 0]，是不是很神奇。這個結果也不難了解，在7次計算過程中，每個伺服器的 currentWeight 都增加了自身權重 weight * 7，得到 currentWeight = [35, 7, 7]，A 被選中5次，要被減去 5 * 7。B 和 C 被選中1次，要被減去 1 * 7。于是 currentWeight = [35, 7, 7] - [35, 7, 7] = [0, 0, 0]。
以上就是平滑權重輪詢的計算過程，現在大家應該對平滑權重輪詢算法了有了一些了解。接下來，我們來看看 Dubbo-2.6.5 是如何實作上面的計算過程的。
以上就是 Dubbo-2.6.5 版本的 RoundRobinLoadBalance，大家如果能夠了解平滑權重輪詢算法的計算過程，再配合我寫的注釋，了解上面的代碼應該不難。
以上就是關于 RoundRobinLoadBalance 全部的分析，内容有點多，大家慢慢消化吧。好了，本節先到這。
本篇文章對 Dubbo 中的幾種負載均衡實作進行了詳細的分析，總的來說，這篇文章寫的還是有點累的。主要是每介紹一種負載均衡實作，就要介紹一下相關背景。另一方面，這裡很多東西對于我來說，也完全是新的。在此之前，我對負載均衡算法并沒太多了解。這篇文章基本上是邊學邊寫的，總共耗時5天。本來想簡單寫寫算了，但最後還是決定寫詳細點。好在，現在寫完了，我也可以放松一下了。
本篇文章是我的 Dubbo 源碼分析系列文章關于叢集容錯部分的最後一篇文章，寫完感覺學到了很多東西。通過堅持不懈的閱讀代碼，寫技術文章，使得我對 Dubbo 有了更深入的了解。當然，這還遠遠不夠。後續還有很多東西要了解，比如 Nacos、Sentinel 等。長路漫漫，步履不停。
好了，本篇文章到這裡就結束了。感謝大家的閱讀。
負載均衡之權重輪詢算法 - CSDN
dubbo源碼-預熱warmup過程 - 簡書
一緻性雜湊演算法原理 - 部落格園
時間
文章
2018-10-01
Dubbo 源碼分析 - SPI 機制
2018-10-13
Dubbo 源碼分析 - 自适應拓展原理
2018-10-31
Dubbo 源碼分析 - 服務導出
2018-11-12
Dubbo 源碼分析 - 服務引用
2018-11-17
Dubbo 源碼分析 - 叢集容錯之 Directory
2018-11-20
Dubbo 源碼分析 - 叢集容錯之 Router
2018-11-24
Dubbo 源碼分析 - 叢集容錯之 Cluster
2018-11-29
Dubbo 源碼分析 - 叢集容錯之 LoadBalance
本文在知識共享許可協定 4.0 下釋出，轉載需在明顯位置處注明出處 作者：田小波 本文同步釋出在我的個人部落格：http://www.tianxiaobo.com
本作品采用知識共享署名-非商業性使用-禁止演繹 4.0 國際許可協定進行許可。