Dubbo的五種負載均衡策略

2020 年 5 月 15 日，Dubbo 發布 2.7.7 release 版本。其中有這么一個 Features

 

新增一個負載均衡策略。

熟悉我的老讀者肯定是知道的，Dubbo 的負載均衡我都寫過專門的文章，對每個負載均衡算法進行了源碼的解讀，還分享了自己調試過程中的一些騷操作。

新的負載均衡出來了，那必須的得解讀一波。

先看一下提交記錄：

https://github.com/chickenlj/incubator-dubbo/commit/6d2ba7ec7b5a1cb7971143d4262d0a1bfc826d45

 

負載均衡是基于 SPI 實現的，我們看到對應的文件中多了一個名為 shortestresponse 的 key。

這個，就是新增的負載均衡策略了。看名字，你也知道了這個策略的名稱就叫：最短響應。

所以截止 2.7.7 版本，官方提供了五種負載均衡算法了，他們分別是：

1. ConsistentHashLoadBalance 一致性哈希負載均衡
2. LeastActiveLoadBalance 最小活躍數負載均衡
3. RandomLoadBalance 加權隨機負載均衡
4. RoundRobinLoadBalance 加權輪詢負載均衡
5. ShortestResponseLoadBalance 最短響應時間負載均衡

前面四種我已經在之前的文章中進行了詳細的分析。有的讀者反饋說想看合輯，所以我會在這篇文章中把之前文章也整合進來。

所以，需要特別強調一下的是，這篇文章集合了之前寫的三篇負載均衡的文章。看完最短響應時間負載均衡這一部分后，如果你看過我之前的那三篇文章，你可以溫故而知新，也可以直接拉到文末看看我推薦的一個活動，然后點個贊再走。如果你沒有看過那三篇，這篇文章如果你細看，肯定有很多收獲，以后談起負載均衡的時候若數家珍，但是肯定需要看非常非常長的時間，做好心理準備。

我已經預感到了，這篇文章妥妥的會超過 2 萬字。屬于硬核勸退文章，想想就害怕。

最短響應時間負載均衡

首先，我們看一下這個類上的注解，先有個整體的認知。

org.Apache.dubbo.rpc.cluster.loadbalance.ShortestResponseLoadBalance

 

我來翻譯一下是什么意思：

1. 從多個服務提供者中選擇出調用成功的且響應時間最短的服務提供者，由于滿足這樣條件的服務提供者有可能有多個。所以當選擇出多個服務提供者后要根據他們的權重做分析。
2. 但是如果只選擇出來了一個，直接用選出來這個。
3. 如果真的有多個，看它們的權重是否一樣，如果不一樣，則走加權隨機算法的邏輯。
4. 如果它們的權重是一樣的，則隨機調用一個。

再配個圖，就好理解了，可以先不管圖片中的標號：

 

有了上面的整體概念的鋪墊了，接下來分析源碼的時候就簡單了。

源碼一共就 66 行，我把它分為 5 個片段去一一分析。

 

這里一到五的標號，對應上面流程圖中的標號。我們一個個的說。

標號為①的部分

 

這一部分是定義并初始化一些參數，為接下來的代碼服務的，翻譯一下每個參數對應的注釋：

length 參數：服務提供者的數量。

shortestResponse 參數：所有服務提供者的估計最短響應時間。（這個地方我覺得注釋描述的不太準確，看后面的代碼可以知道這只是一個零時變量，在循環中存儲當前最短響應時間是多少。）

shortCount 參數：具有相同最短響應時間的服務提供者個數，初始化為 0。

shortestIndexes 參數：數組里面放的是具有相同最短響應時間的服務提供者的下標。

weights 參數：每一個服務提供者的權重。

totalWeight 參數：多個具有相同最短響應時間的服務提供者對應的預熱（預熱這個點還是挺重要的，在下面講最小活躍數負載均衡的時候有詳細說明）權重之和。

firstWeight 參數：第一個具有最短響應時間的服務提供者的權重。

sameWeight 參數：多個滿足條件的提供者的權重是否一致。

標號為②的部分

 

這一部分代碼的關鍵，就在上面框起來的部分。而框起來的部分，最關鍵的地方，就在于第一行。

 

獲取調用成功的平均時間。

成功調用的平均時間怎么算的？

調用成功的請求數總數對應的總耗時 / 調用成功的請求數總數 = 成功調用的平均時間。

所以，在下面這個方法中，首先獲取到了調用成功的請求數總數：

 

這個 succeeded 參數是怎么來的呢？

 

答案就是：總的請求數減去請求失敗的數量，就是請求成功的總數！

那么為什么不能直接獲取請求成功的總數呢？

別問，問就是沒有這個選項啊。你看，在 RpcStatus 里面沒有這個參數呀。

 

請求成功的總數我們有了，接下來成功總耗時怎么拿到的呢？

 

答案就是：總的請求時間減去請求失敗的總時間，就是請求成功的總耗時！

那么為什么不能直接獲取請求成功的總耗時呢？

別問，問就是......

我們看一下 RpcStatus 中的這幾個參數是在哪里維護的：

org.apache.dubbo.rpc.RpcStatus#endCount(org.apache.dubbo.rpc.RpcStatus, long, boolean)

 

其中的第二個入參是本次請求調用時長，第三個入參是本次調用是否成功。

具體的方法不必細說了吧，已經顯而易見了。

再回去看框起來的那三行代碼：

 

1. 第一行獲取到了該服務提供者成功請求的平均耗時。
2. 第二行獲取的是該服務提供者的活躍數，也就是堆積的請求數。
3. 第三行獲取的就是如果當前這個請求發給這個服務提供者預計需要等待的時間。乘以 active 的原因是因為它需要排在堆積的請求的后面嘛。

這里，我們就獲取到了如果選擇當前循環中的服務提供者的預計等待時間是多長。

后面的代碼怎么寫？

當然是出來一個更短的就把這個踢出去呀，或者出來一個一樣長時間的就記錄一下，接著去 pk 權重了。

所以，接下來 shortestIndexes 參數和 weights 參數就排上用場了：

 

另外，多說一句的，它里面有這樣的一行注釋：

 

和 LeastActiveLoadBalance 負載均衡策略一致，我給你截圖對比一下：

 

可以看到，確實是非常的相似，只是一個是判斷誰的響應時間短，一個是判斷誰的活躍數低。

標號為③的地方

標號為③的地方是這樣的：

 

里面參數的含義我們都知道了，所以，標號為③的地方的含義就很好解釋了：經過選擇后只有一個服務提供者滿足條件。所以，直接使用這個服務提供者。

標號為④的地方

 

這個地方我就不展開講了（后面的加權隨機負載均衡那一小節有詳細說明），熟悉的朋友一眼就看出來這是加權隨機負載均衡的寫法了。

不信？我給你對比一下：

 

你看，是不是一模一樣的。

標號為⑤的地方

 

一行代碼，沒啥說的。就是從多個滿足條件的且權重一樣的服務提供者中隨機選擇一個。

如果一定要多說一句的話，我截個圖吧：

 

可以看到，這行代碼在最短響應時間、加權隨機、最小活躍數負載均衡策略中都出現了，且都在最后一行。

好了，到這里最短響應時間負載均衡策略就講完了，你再回過頭去看那張流程圖，會發現其實流程非常的清晰，完全可以根據代碼結構畫出流程圖。一個是說明這個算法是真的不復雜，另一個是說明好的代碼會說話。

優雅

你知道 Dubbo 加入這個新的負載均衡算法提交了幾個文件嗎？

四個文件，其中還包含兩個測試文件：

 

這里就是策略模式和 SPI 的好處。對原有的負載均衡策略沒有任何侵略性。只需要按照規則擴展配置文件，實現對應接口即可。

這是什么？

這就是值得學習優雅！

那我們優雅的進入下一議題。

最小活躍數負載均衡

這一小節所示源碼，沒有特別標注的地方均為 2.6.0 版本。

為什么沒有用截止目前（我當時寫這段文章的時候是2019年12月01日）的最新的版本號 2.7.4.1 呢？因為 2.6.0 這個版本里面有兩個 bug 。從 bug 講起來，印象更加深刻。

最后會對 2.6.0/2.6.5/2.7.4.1 版本進行對比，通過對比學習，加深印象。

我這里補充一句啊，僅僅半年的時間，版本號就從 2.7.4.1 到了 2.7.7。其中還包含一個 2.7.5 這樣的大版本。

所以還有人說 Dubbo 不夠活躍？（幾年前的文章現在還有人在發。）

對吧，我們不吵架，我們擺事實，聊數據嘛。

Demo 準備

我看源碼的習慣是先搞個 Demo 把調試環境搭起來。然后帶著疑問去抽絲剝繭的 Debug，不放過在這個過程中在腦海里面一閃而過的任何疑問。

這一小節分享的是Dubbo負載均衡策略之一最小活躍數(LeastActiveLoadBalance)。所以我先搭建一個 Dubbo 的項目，并啟動三個 provider 供 consumer 調用。

三個 provider 的 loadbalance 均配置的是 leastactive。權重分別是默認權重、200、300。

 

**默認權重是多少？**后面看源碼的時候，源碼會告訴你。

三個不同的服務提供者會給調用方返回自己是什么權重的服務。

 

啟動三個實例。(注:上面的 provider.xml 和 DemoServiceImpl 其實只有一個，每次啟動的時候手動修改端口、權重即可。)

 

到 zookeeper 上檢查一下，服務提供者是否正常：

 

可以看到三個服務提供者分別在 20880、20881、20882 端口。（每個紅框的最后5個數字就是端口號）。

最后，我們再看服務消費者。消費者很簡單，配置consumer.xml

 

直接調用接口并打印返回值即可。

 

斷點打在哪？

相信很多朋友也很想看源碼，但是不知道從何處下手。處于一種在源碼里面"亂逛"的狀態，一圈逛下來，收獲并不大。

這一部分我想分享一下我是怎么去看源碼。首先我會帶著問題去源碼里面尋找答案，即有針對性的看源碼。

如果是這種框架類的，正如上面寫的，我會先翻一翻官網（Dubbo 的官方文檔其實寫的挺好了），然后搭建一個簡單的 Demo 項目，然后 Debug 跟進去看。Debug 的時候當然需要是設置斷點的，那么這個斷點如何設置呢？

第一個斷點，當然毋庸置疑，是打在調用方法的地方，比如本文中，第一個斷點是在這個地方：

 

接下里怎么辦？

你當然可以從第一個斷點處，一步一步的跟進去。但是在這個過程中，你發現了嗎？大多數情況你都是被源碼牽著鼻子走的。本來你就只帶著一個問題去看源碼的，有可能你Debug了十分鐘，還沒找到關鍵的代碼。也有可能你Debug了十分鐘，問題從一個變成了無數個。

所以不要慌，我們點支煙，慢慢分析。

首先怎么避免被源碼牽著四處亂逛呢？

我們得找到一個突破口，還記得我在《很開心，在使用mybatis的過程中我踩到一個坑》這篇文章中提到的逆向排查的方法嗎？這次的文章,我再次展示一下該方法。

看源碼之前，我們的目標要十分明確，就是想要找到 Dubbo 最小活躍數算法的具體實現類以及實現類的具體邏輯是什么。

根據我們的 provider.xml 里面的：

 

很明顯，我們知道 loadbalance 是關鍵字。所以我們拿著 loadbalance 全局搜索，可以看到 Dubbo 包下面的 LoadBalance。

 

這是一個 SPI 接口 
com.alibaba.dubbo.rpc.cluster.LoadBalance：

 

其實現類為:

com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance

AbstractLoadBalance 是一個抽象類，該類里面有一個抽象方法doSelect。這個抽象方法其中的一個實現類就是我們要分析的最少活躍次數負載均衡的源碼。

 

同時，到這里我們知道了 LoadBalance 是一個 SPI 接口，說明我們可以擴展自己的負載均衡策略。抽象方法 doSelect 有四個實現類。這個四個實現類，就是 Dubbo 官方提供的負載均衡策略（截止 2.7.7 版本之前），他們分別是:

1. ConsistentHashLoadBalance 一致性哈希算法
2. LeastActiveLoadBalance 最小活躍數算法
3. RandomLoadBalance 加權隨機算法
4. RoundRobinLoadBalance 加權輪詢算法

我們已經找到了 LeastActiveLoadBalance 這個類了，那么我們的第二個斷點打在哪里已經很明確了。

 

目前看來，兩個斷點就可以支撐我們的分析了。

有的朋友可能想問，那我想知道 Dubbo 是怎么識別出我們想要的是最少活躍次數算法，而不是其他的算法呢？其他的算法是怎么實現的呢？從第一個斷點到第二個斷點直接有著怎樣的調用鏈呢？

在沒有徹底搞清楚最少活躍數算法之前，這些統統先記錄在案但不予理睬。一定要明確目標，帶著一個問題進來，就先把帶來的問題解決了。之后再去解決在這個過程中碰到的其他問題。在這樣環環相扣解決問題的過程中，你就慢慢的把握了源碼的精髓。這是我個人的一點看源碼的心得。供諸君參考。

模擬環境

既然叫做最小活躍數策略。那我們得讓現有的三個消費者都有一些調用次數。所以我們得改造一下服務提供者和消費者。

服務提供者端的改造如下:

 

 

PS：這里以權重為 300 的服務端為例。另外的兩個服務端改造點相同。

客戶端的改造點如下：

 

一共發送 21 個請求：其中前 20 個先發到服務端讓其 hold 住(因為服務端有 sleep)，最后一個請求就是我們需要 Debug 跟蹤的請求。

運行一下，讓程序停在斷點的地方,然后看看控制臺的輸出:

 

 

 

權重為300的服務端共計收到9個請求

權重為200的服務端共計收到6個請求

默認權重的服務端共計收到5個請求

我們還有一個請求在 Debug。直接進入到我們的第二個斷點的位置，并 Debug 到下圖所示的一行代碼(可以點看查看大圖):

 

正如上面這圖所說的：weight=100 回答了一個問題，active=0 提出的一個問題。

weight=100 回答了什么問題呢？

默認權重是多少？是 100。

我們服務端的活躍數分別應該是下面這樣的

• 權重為300的服務端，active=9
• 權重為200的服務端，active=6
• 默認權重(100)的服務端，active=5

但是這里為什么截圖中的active會等于 0 呢？這是一個問題。

繼續往下 Debug 你會發現，每一個服務端的 active 都是 0。所以相比之下沒有一個 invoker 有最小 active 。于是程序走到了根據權重選擇 invoker 的邏輯中。

 

active為什么是0？

active 為 0 說明在 Dubbo 調用的過程中 active 并沒有發生變化。那 active 為什么是 0，其實就是在問 active 什么時候發生變化？

要回答這個問題我們得知道 active 是在哪里定義的，因為在其定義的地方，必有其修改的方法。

下面這圖說明了active是定義在RpcStatus類里面的一個類型為AtomicInteger 的成員變量。

 

在 RpcStatus 類中，有三處()調用 active 值的方法，一個增加、一個減少、一個獲取：

 

很明顯，我們需要看的是第一個，在哪里增加。

所以我們找到了 beginCount(URL,String) 方法，該方法只有兩個 Filter 調用。ActiveLimitFilter，見名知意，這就是我們要找的東西。

 

com.alibaba.dubbo.rpc.filter.ActiveLimitFilter具體如下：

 

看到這里，我們就知道怎么去回答這個問題了：為什么active是0呢？因為在客戶端沒有配置ActiveLimitFilter。所以，ActiveLimitFilter沒有生效，導致active沒有發生變化。

怎么讓其生效呢？已經呼之欲出了。

 

好了，再來試驗一次:

 

 

 

加上Filter之后，我們通過Debug可以看到，對應權重的活躍數就和我們預期的是一致的了。

1.權重為300的活躍數為6

2.權重為200的活躍數為11

3.默認權重(100)的活躍數為3

 

根據活躍數我們可以分析出來，最后我們Debug住的這個請求，一定會選擇默認權重的invoker去執行，因為他是當前活躍數最小的invoker。如下所示：

 

雖然到這里我們還沒開始進行源碼的分析，只是把流程梳理清楚了。但是把Demo完整的搭建了起來，而且知道了最少活躍數負載均衡算法必須配合ActiveLimitFilter使用，位于RpcStatus類的active字段才會起作用，否則，它就是一個基于權重的算法。

比起其他地方直接告訴你，要配置ActiveLimitFilter才行哦，我們自己實驗得出的結論，能讓我們的印象更加深刻。

我們再仔細看一下加上ActiveLimitFilter之后的各個服務的活躍數情況：

• 權重為300的活躍數為6
• 權重為200的活躍數為11
• 默認權重(100)的活躍數為3

你不覺得奇怪嗎，為什么權重為200的活躍數是最高的？

其在業務上的含義是：我們有三臺性能各異的服務器，A服務器性能最好，所以權重為300，B服務器性能中等，所以權重為200，C服務器性能最差，所以權重為100。

當我們選擇最小活躍次數的負載均衡算法時，我們期望的是性能最好的A服務器承擔更多的請求，而真實的情況是性能中等的B服務器承擔的請求更多。這與我們的設定相悖。

如果你說20個請求數據量太少，可能是巧合，不足以說明問題。說明你還沒被我帶偏，我們不能基于巧合編程。

所以為了驗證這個地方確實有問題，我把請求擴大到一萬個。

 

同時，記得擴大 provider 端的 Dubbo 線程池：

 

由于每個服務端運行的代碼都是一樣的，所以我們期望的結果應該是權重最高的承擔更多的請求。但是最終的結果如圖所示:

 

各個服務器均攤了請求。這就是我文章最開始的時候說的Dubbo 2.6.0 版本中最小活躍數負載均衡算法的Bug之一。

接下來，我們帶著這個問題，去分析源碼。

剖析源碼

com.alibaba.dubbo.rpc.cluster.loadbalance.LeastActiveLoadBalance的源碼如下，我逐行進行了解讀。可以點開查看大圖，細細品讀，非常爽：

 

下圖中紅框框起來的部分就是一個基于權重選擇invoker的邏輯：

 

我給大家畫圖分析一下：

 

請仔細分析圖中給出的舉例說明。同時，上面這圖也是按照比例畫的，可以直觀的看到，對于某一個請求，區間(權重)越大的服務器，就越可能會承擔這個請求。所以，當請求足夠多的時候，各個服務器承擔的請求數，應該就是區間，即權重的比值。

其中第 81 行有調用 getWeight 方法，位于抽象類 AbstractLoadBalance 中，也需要進行重點解讀的代碼。

com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance 的源碼如下，我也進行了大量的備注:

 

在 AbstractLoadBalance 類中提到了一個預熱的概念。官網中是這樣的介紹該功能的：

權重的計算過程主要用于保證當服務運行時長小于服務預熱時間時，對服務進行降權，避免讓服務在啟動之初就處于高負載狀態。服務預熱是一個優化手段，與此類似的還有 JVM 預熱。主要目的是讓服務啟動后“低功率”運行一段時間，使其效率慢慢提升至最佳狀態。

從上圖代碼里面的公式(演變后)：*計算后的權重=(uptime/warmup)weight 可以看出：隨著服務啟動時間的增加(uptime)，計算后的權重會越來越接近weight。從實際場景的角度來看，隨著服務啟動時間的增加，服務承擔的流量會慢慢上升，沒有一個陡升的過程。所以這是一個優化手段。同時 Dubbo 接口還支持延遲暴露。

在仔細的看完上面的源碼解析圖后，配合官網的總結加上我的靈魂畫作，相信你可以對最小活躍數負載均衡算法有一個比較深入的理解：

1. 遍歷 invokers 列表，尋找活躍數最小的 Invoker
2. 如果有多個 Invoker 具有相同的最小活躍數，此時記錄下這些 Invoker 在 invokers 集合中的下標，并累加它們的權重，比較它們的權重值是否相等
3. 如果只有一個 Invoker 具有最小的活躍數，此時直接返回該 Invoker 即可
4. 如果有多個 Invoker 具有最小活躍數，且它們的權重不相等，此時處理方式和 RandomLoadBalance 一致
5. 如果有多個 Invoker 具有最小活躍數，但它們的權重相等，此時隨機返回一個即可

 

所以我覺得最小活躍數負載均衡的全稱應該叫做：有最小活躍數用最小活躍數，沒有最小活躍數根據權重選擇，權重一樣則隨機返回的負載均衡算法。

Bug在哪里？

Dubbo2.6.0最小活躍數算法Bug一

 

問題出在標號為 ① 和 ② 這兩行代碼中：

標號為 ① 的代碼在url中取出的是沒有經過 getWeight 方法降權處理的權重值，這個值會被累加到權重總和(totalWeight)中。

標號為 ② 的代碼取的是經過 getWeight 方法處理后的權重值。

取值的差異會導致一個問題，標號為 ② 的代碼的左邊，offsetWeight 是一個在 [0，totalWeight) 范圍內的隨機數，右邊是經過 getWeight 方法降權后的權重。所以在經過 leastCount 次的循環減法后，offsetWeight 在服務啟動時間還沒到熱啟動設置（默認10分鐘）的這段時間內，極大可能仍然大于 0。導致不會進入到標號為 ③ 的代碼中。直接到標號為 ④ 的代碼處，變成了隨機調用策略。這與設計不符，所以是個 bug。

前面章節說的情況就是這個Bug導致的。

這個Bug對應的issues地址和pull request分為:

https://github.com/apache/dubbo/issues/904

https://github.com/apache/dubbo/pull/2172

那怎么修復的呢？我們直接對比 Dubbo 2.7.4.1 的代碼:

 

可以看到獲取weight的方法變了：從url中直接獲取變成了通過getWeight方法獲取。獲取到的變量名稱也變了：從weight變成了afterWarmup，更加的見名知意。

還有一處變化是獲取隨機值的方法的變化，從Randmo變成了ThreadLoaclRandom，性能得到了提升。這處變化就不展開講了，有興趣的朋友可以去了解一下。

 

Dubbo2.6.0最小活躍數算法Bug二

這個Bug我沒有遇到，但是我在官方文檔上看了其描述（官方文檔中的版本是2.6.4），引用如下：

 

官網上說這個問題在2.6.5版本進行修復。我對比了2.6.0/2.6.5/2.7.4.1三個版本，發現每個版本都略有不同。如下所示：

 

圖中標記為①的三處代碼：

2.6.0版本的是有Bug的代碼，原因在上面說過了。

2.6.5版本的修復方式是獲取隨機數的時候加一，所以取值范圍就從**[0,totalWeight)變成了[0,totalWeight]**，這樣就可以避免這個問題。

2.7.4.1版本的取值范圍還是[0,totalWeight)，但是它的修復方法體現在了標記為②的代碼處。2.6.0/2.6.5版本標記為②的地方都是if(offsetWeight<=0)，而2.7.4.1版本變成了if(offsetWeight<0)。

你品一品，是不是效果是一樣的，但是更加優雅了。

朋友們，魔鬼，都在細節里啊！

好了，進入下一議題。

一致性哈希負載均衡

這一部分是對于Dubbo負載均衡策略之一的一致性哈希負載均衡的詳細分析。對源碼逐行解讀、根據實際運行結果，配以豐富的圖片，可能是東半球講一致性哈希算法在Dubbo中的實現最詳細的文章了。

本小節所示源碼，沒有特別標注的地方，均為2.7.4.1版本。

在撰寫本文的過程中，發現了Dubbo2.7.0版本之后的一個bug。會導致性能問題，如果你們的負載均衡配置的是一致性哈希或者考慮使用一致性哈希的話，可以了解一下。

哈希算法

在介紹一致性哈希算法之前，我們看看哈希算法，以及它解決了什么問題，帶來了什么問題。

 

如上圖所示，假設0,1,2號服務器都存儲的有用戶信息，那么當我們需要獲取某用戶信息時，因為我們不知道該用戶信息存放在哪一臺服務器中，所以需要分別查詢0,1,2號服務器。這樣獲取數據的效率是極低的。

對于這樣的場景，我們可以引入哈希算法。

 

還是上面的場景，但前提是每一臺服務器存放用戶信息時是根據某一種哈希算法存放的。所以取用戶信息的時候，也按照同樣的哈希算法取即可。

假設我們要查詢用戶號為100的用戶信息，經過某個哈希算法，比如這里的userId mod n，即100 mod 3結果為1。所以用戶號100的這個請求最終會被1號服務器接收并處理。

這樣就解決了無效查詢的問題。

但是這樣的方案會帶來什么問題呢？

擴容或者縮容時，會導致大量的數據遷移。最少也會影響百分之50的數據。

 

為了說明問題，我們加入一臺服務器3。服務器的數量n就從3變成了4。還是查詢用戶號為100的用戶信息時，100 mod 4結果為0。這時，請求就被0號服務器接收了。

當服務器數量為3時，用戶號為100的請求會被1號服務器處理。

當服務器數量為4時，用戶號為100的請求會被0號服務器處理。

所以，當服務器數量增加或者減少時，一定會涉及到大量數據遷移的問題。可謂是牽一發而動全身。

對于上訴哈希算法其優點是簡單易用，大多數分庫分表規則就采取的這種方式。一般是提前根據數據量，預先估算好分區數。

其缺點是由于擴容或收縮節點導致節點數量變化時，節點的映射關系需要重新計算，會導致數據進行遷移。所以擴容時通常采用翻倍擴容，避免數據映射全部被打亂，導致全量遷移的情況，這樣只會發生50%的數據遷移。

假設這是一個緩存服務，數據的遷移會導致在遷移的時間段內，有緩存是失效的。

緩存失效，可怕啊。還記得我之前的文章嗎，《當周杰倫把QQ音樂干翻的時候，作為程序猿我看到了什么？》就是講緩存擊穿、緩存穿透、緩存雪崩的場景和對應的解決方案。

一致性哈希算法

為了解決哈希算法帶來的數據遷移問題，一致性哈希算法應運而生。

對于一致性哈希算法，官方說法如下：

一致性哈希算法在1997年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠盡可能小地改變已存在的服務請求與處理請求服務器之間的映射關系。一致性哈希解決了簡單哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的動態伸縮等問題。

什么意思呢？我用大白話加畫圖的方式給你簡單的介紹一下。

一致性哈希，你可以想象成一個哈希環，它由0到2^32-1個點組成。A，B，C分別是三臺服務器，每一臺的IP加端口經過哈希計算后的值，在哈希環上對應如下：

 

當請求到來時，對請求中的某些參數進行哈希計算后，也會得出一個哈希值，此值在哈希環上也會有對應的位置，這個請求會沿著順時針的方向，尋找最近的服務器來處理它，如下圖所示：

 

一致性哈希就是這么個東西。那它是怎么解決服務器的擴容或收縮導致大量的數據遷移的呢？

看一下當我們使用一致性哈希算法時，加入服務器會發什么事情。

當我們加入一個D服務器后，假設其IP加端口，經過哈希計算后落在了哈希環上圖中所示的位置。

 

這時影響的范圍只有圖中標注了五角星的區間。這個區間的請求從原來的由C服務器處理變成了由D服務器請求。而D到C，C到A，A到B這個區間的請求沒有影響，加入D節點后，A、B服務器是無感知的。

所以，在一致性哈希算法中，如果增加一臺服務器，則受影響的區間僅僅是新服務器(D)在哈希環空間中，逆時針方向遇到的第一臺服務器(B)之間的區間，其它區間(D到C，C到A，A到B)不會受到影響。

在加入了D服務器的情況下，我們再假設一段時間后，C服務器宕機了：

 

當C服務器宕機后，影響的范圍也是圖中標注了五角星的區間。C節點宕機后，B、D服務器是無感知的。

所以，在一致性哈希算法中，如果宕機一臺服務器，則受影響的區間僅僅是宕機服務器(C)在哈希環空間中，逆時針方向遇到的第一臺服務器(D)之間的區間，其它區間(C到A，A到B，B到D)不會受到影響。

綜上所述，在一致性哈希算法中，不管是增加節點，還是宕機節點，受影響的區間僅僅是增加或者宕機服務器在哈希環空間中，逆時針方向遇到的第一臺服務器之間的區間，其它區間不會受到影響。

是不是很完美？

不是的，理想和現實的差距是巨大的。

一致性哈希算法帶來了什么問題？

 

當節點很少的時候可能會出現這樣的分布情況，A服務會承擔大部分請求。這種情況就叫做數據傾斜。

怎么解決數據傾斜呢？加入虛擬節點。

怎么去理解這個虛擬節點呢？

首先一個服務器根據需要可以有多個虛擬節點。假設一臺服務器有n個虛擬節點。那么哈希計算時，可以使用IP+端口+編號的形式進行哈希值計算。其中的編號就是0到n的數字。由于IP+端口是一樣的，所以這n個節點都是指向的同一臺機器。

如下圖所示：

 

在沒有加入虛擬節點之前，A服務器承擔了絕大多數的請求。但是假設每個服務器有一個虛擬節點（A-1，B-1，C-1），經過哈希計算后落在了如上圖所示的位置。那么A服務器的承擔的請求就在一定程度上（圖中標注了五角星的部分）分攤給了B-1、C-1虛擬節點，實際上就是分攤給了B、C服務器。

一致性哈希算法中，加入虛擬節點，可以解決數據傾斜問題。

當你在面試的過程中，如果聽到了類似于數據傾斜的字眼。那大概率是在問你一致性哈希算法和虛擬節點。

在介紹了相關背景后，我們可以去看看一致性哈希算法在Dubbo中的應用了。

一致性哈希算法在Dubbo中的應用

前面我們說了Dubbo中負載均衡的實現是通過
org.apache.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance中的 doSelect 抽象方法實現的，一致性哈希負載均衡的實現類如下所示：

org.apache.dubbo.rpc.cluster.loadbalance.ConsistentHashLoadBalance

 

由于一致性哈希實現類看起來稍微有點抽象，不太好演示，所以我想到了一個"騷"操作。前面的文章說過 LoadBalance 是一個 SPI 接口：

 

既然是一個 SPI 接口，那我們可以自己擴展一個一模一樣的算法，只是在算法里面加入一點輸出語句方便我們觀察情況。怎么擴展 SPI 接口就不描述了，只要記住代碼里面的輸出語句都是額外加的，此外沒有任何改動即可，如下：

 

整個類如下圖片所示，請先看完整個類，有一個整體的概念后，我會進行方法級別的分析。

圖片很長，其中我加了很多注釋和輸出語句，可以點開大圖查看，一定會幫你更加好的理解一致性哈希在Dubbo中的應用：

改造之后，我們先把程序跑起來，有了輸出就好分析了。

 

服務端代碼如下：

 

其中的端口是需要手動修改的，我分別啟動服務在20881和20882端口。

項目中provider.xml配置如下：

 

consumer.xml配置如下:

 

然后，啟動在20881和20882端口分別啟動兩個服務端。客戶端消費如下：

 

運行結果輸出如下，可以先看個大概的輸出，下面會對每一部分輸出進行逐一的解讀。

 

好了，用例也跑起來了，日志也有了。接下來開始結合代碼和日志進行方法級別的分析。

首先是doSelect方法的入口：

 

從上圖我們知道了，第一次調用需要對selectors進行put操作，selectors的 key 是接口中定義的方法，value 是 ConsistentHashSelector 內部類。

ConsistentHashSelector通過調用其構造函數進行初始化的。invokers(服務端)作為參數傳遞到了構造函數中，構造函數里面的邏輯，就是把服務端映射到哈希環上的過程，請看下圖，結合代碼，仔細分析輸出數據：

 

從上圖可以看出，當 ConsistentHashSelector 的構造方法調用完成后，8個虛擬節點在哈希環上已經映射完成。兩臺服務器，每一臺4個虛擬節點組成了這8個虛擬節點。

doSelect方法繼續執行，并打印出每個虛擬節點的哈希值和對應的服務端，請仔細品讀下圖：

 

說明一下：上面圖中的哈希環是沒有考慮比例的，僅僅是展現了兩個服務器在哈希環上的相對位置。而且為了演示說明方便，僅僅只有8個節點。假設我們有4臺服務器，每臺服務器的虛擬節點是默認值(160)，這個情況下哈希環上一共有160*4=640個節點。

哈希環映射完成后，接下來的邏輯是把這次請求經過哈希計算后，映射到哈希環上，并順時針方向尋找遇到的第一個節點，讓該節點處理該請求：

 

還記得地址為 468e8565 的 A 服務器是什么端口嗎？前面的圖片中有哦，該服務對應的端口是 20882 。

 

最后我們看看輸出結果:

 

和我們預期的一致。整個調用就算是完成了。

再對兩個方法進行一個補充說明。

第一個方法是 selectForKey，這個方法里面邏輯如下圖所示：

 

虛擬節點都存儲在 TreeMap 中。順時針查詢的邏輯由 TreeMap 保證。看一下下面的 Demo 你就明白了。

 

第二個方法是 hash 方法，其中的 & 0xFFFFFFFFL 的目的如下:

 

&是位運算符，而 0xFFFFFFFFL 轉換為四字節表現后，其低32位全是1，所以保證了哈希環的范圍是 [0,Integer.MAX_VALUE]：

 

所以這里我們可以改造這個哈希環的范圍，假設我們改為 100000。十進制的 100000 對于的 16 進制為 186A0 。所以我們改造后的哈希算法為：

 

再次調用后可以看到，計算后的哈希值都在10萬以內。但是分布極不均勻，說明修改數據后這個哈希算法不是一個優秀的哈希算法：

 

以上，就是對一致性哈希算法在Dubbo中的實現的解讀。需要特殊說明一下的是，一致性哈希負載均衡策略和權重沒有任何關系。

我又發現了一個BUG

前面我介紹了Dubbo 2.6.5版本之前，最小活躍數算法的兩個 bug。

很不幸，這次我又發現了Dubbo 2.7.4.1版本，一致性哈希負載均衡策略的一個bug，我提交了issue 地址如下：

https://github.com/apache/dubbo/issues/5429

 

我在這里詳細說一下這個Bug現象、原因和我的解決方案。

現象如下，我們調用三次服務端：

 

輸出日志如下（有部分刪減）：

 

可以看到，在三次調用的過程中并沒有發生服務的上下線操作，但是每一次調用都重新進行了哈希環的映射。而我們預期的結果是應該只有在第一次調用的時候進行哈希環的映射，如果沒有服務上下線的操作，后續請求根據已經映射好的哈希環進行處理。

上面輸出的原因是由于每次調用的invokers的identityHashCode發生了變化：

 

我們看一下三次調用invokers的情況：

 

經過debug我們可以看出因為每次調用的invokers地址值不是同一個，所以System.identityHashCode(invokers)方法返回的值都不一樣。

接下來的問題就是為什么每次調用的invokers地址值都不一樣呢？

經過Debug之后，可以找到這個地方：

org.apache.dubbo.rpc.cluster.RouterChain#route

 

問題就出在這個TagRouter中：

org.apache.dubbo.rpc.cluster.router.tag.TagRouter#filterInvoker

 

所以，在TagRouter中的stream操作，改變了invokers，導致每次調用時其

System.identityHashCode(invokers)返回的值不一樣。所以每次調用都會進行哈希環的映射操作，在服務節點多，虛擬節點多的情況下會有一定的性能問題。

到這一步，問題又發生了變化。這個TagRouter怎么來的呢？

如果了解Dubbo 2.7.x版本新特性的朋友可能知道，標簽路由是Dubbo2.7引入的新功能。

 

通過加載下面的配置加載了RouterFactrory：

META-INFdubbointernal
org.apache.dubbo.rpc.cluster.RouterFactory（Dubbo 2.7.0版本之前）

META-INFdubbointernal
com.alibaba.dubbo.rpc.cluster.RouterFactory（Dubbo 2.7.0之前）

下面是Dubbo 2.6.7(2.6.x的最后一個版本)和Dubbo 2.7.0版本該文件的對比:

 

可以看到確實是在 Dubbo 2.7.0 之后引入了 TagRouter。

至此，Dubbo 2.7.0 版本之后，一致性哈希負載均衡算法的 Bug 的來龍去脈也介紹清楚了。

解決方案是什么呢？特別簡單，把獲取 identityHashCode 的方法從 System.identityHashCode(invokers) 修改為 invokers.hashCode() 即可。

此方案是我提的 issue 里面的評論，這里 System.identityHashCode 和 hashCode 之間的聯系和區別就不進行展開講述了，不清楚的大家可以自行了解一下。

（我的另外一篇文章：夠強！一行代碼就修復了我提的Dubbo的Bug。）

 

改完之后，我們再看看運行效果：

 

可以看到第二次調用的時候并沒有進行哈希環的映射操作，而是直接取到了值，進行調用。

加入節點，畫圖分析

最后，我再分析一種情況。在A、B、C三個服務器(20881、20882、20883端口)都在正常運行，哈希映射已經完成的情況下，我們再啟動一個D節點（20884端口），這時的日志輸出和對應的哈希環變化情況如下:

 

根據日志作圖如下：

 

根據輸出日志和上圖再加上源碼，你再細細回味一下。我個人覺得還是講的非常詳細了。

一致性哈希的應用場景

當大家談到一致性哈希算法的時候，首先的第一印象應該是在緩存場景下的使用，因為在一個優秀的哈希算法加持下，其上下線節點對整體數據的影響(遷移)都是比較友好的。

但是想一下為什么 Dubbo 在負載均衡策略里面提供了基于一致性哈希的負載均衡策略？它的實際使用場景是什么？

我最開始也想不明白。我想的是在 Dubbo 的場景下，假設需求是想要一個用戶的請求一直讓一臺服務器處理，那我們可以采用一致性哈希負載均衡策略，把用戶號進行哈希計算，可以實現這樣的需求。但是這樣的需求未免有點太牽強了，適用場景略小。

直到有天晚上，我睡覺之前，電光火石之間突然想到了一個稍微適用的場景了。

如果需求是需要保證某一類請求必須順序處理呢？

如果你用其他負載均衡策略，請求分發到了不同的機器上去，就很難保證請求的順序處理了。比如A，B請求要求順序處理，現在A請求先發送，被負載到了A服務器上，B請求后發送，被負載到了B服務器上。而B服務器由于性能好或者當前沒有其他請求或者其他原因極有可能在A服務器還在處理A請求之前就把B請求處理完成了。這樣不符合我們的要求。

這時，一致性哈希負載均衡策略就上場了，它幫我們保證了某一類請求都發送到固定的機器上去執行。比如把同一個用戶的請求發送到同一臺機器上去執行，就意味著把某一類請求發送到同一臺機器上去執行。所以我們只需要在該機器上運行的程序中保證順序執行就行了，比如你加一個隊列。

一致性哈希算法+隊列，可以實現順序處理的需求。

好了，一致性哈希負載均衡算法就寫到這里。

原文鏈接：
https://juejin.im/post/5ed39adef265da76dc1bb817