Dubbo的五種負(fù)載均衡策略
2020 年 5 月 15 日，Dubbo 發(fā)布 2.7.7 release 版本。其中有這么一個(gè) Features
新增一個(gè)負(fù)載均衡策略。
熟悉我的老讀者肯定是知道的，Dubbo 的負(fù)載均衡我都寫(xiě)過(guò)專(zhuān)門(mén)的文章，對(duì)每個(gè)負(fù)載均衡算法進(jìn)行了源碼的解讀，還分享了自己調(diào)試過(guò)程中的一些騷操作。
新的負(fù)載均衡出來(lái)了，那必須的得解讀一波。
先看一下提交記錄：
https://github.com/chickenlj/incubator-dubbo/commit/6d2ba7ec7b5a1cb7971143d4262d0a1bfc826d45
負(fù)載均衡是基于 SPI 實(shí)現(xiàn)的，我們看到對(duì)應(yīng)的文件中多了一個(gè)名為 shortestresponse 的 key。
這個(gè)，就是新增的負(fù)載均衡策略了。看名字，你也知道了這個(gè)策略的名稱(chēng)就叫：最短響應(yīng)。
所以截止 2.7.7 版本，官方提供了五種負(fù)載均衡算法了，他們分別是：
- ConsistentHashLoadBalance 一致性哈希負(fù)載均衡
- LeastActiveLoadBalance 最小活躍數(shù)負(fù)載均衡
- RandomLoadBalance 加權(quán)隨機(jī)負(fù)載均衡
- RoundRobinLoadBalance 加權(quán)輪詢(xún)負(fù)載均衡
- ShortestResponseLoadBalance 最短響應(yīng)時(shí)間負(fù)載均衡
前面四種我已經(jīng)在之前的文章中進(jìn)行了詳細(xì)的分析。有的讀者反饋說(shuō)想看合輯，所以我會(huì)在這篇文章中把之前文章也整合進(jìn)來(lái)。
所以，需要特別強(qiáng)調(diào)一下的是，這篇文章集合了之前寫(xiě)的三篇負(fù)載均衡的文章。看完最短響應(yīng)時(shí)間負(fù)載均衡這一部分后，如果你看過(guò)我之前的那三篇文章，你可以溫故而知新，也可以直接拉到文末看看我推薦的一個(gè)活動(dòng)，然后點(diǎn)個(gè)贊再走。如果你沒(méi)有看過(guò)那三篇，這篇文章如果你細(xì)看，肯定有很多收獲，以后談起負(fù)載均衡的時(shí)候若數(shù)家珍，但是肯定需要看非常非常長(zhǎng)的時(shí)間，做好心理準(zhǔn)備。
我已經(jīng)預(yù)感到了，這篇文章妥妥的會(huì)超過(guò) 2 萬(wàn)字。屬于硬核勸退文章，想想就害怕。
最短響應(yīng)時(shí)間負(fù)載均衡
首先，我們看一下這個(gè)類(lèi)上的注解，先有個(gè)整體的認(rèn)知。
org.Apache.dubbo.rpc.cluster.loadbalance.ShortestResponseLoadBalance
我來(lái)翻譯一下是什么意思：
- 從多個(gè)服務(wù)提供者中選擇出調(diào)用成功的且響應(yīng)時(shí)間最短的服務(wù)提供者，由于滿(mǎn)足這樣條件的服務(wù)提供者有可能有多個(gè)。所以當(dāng)選擇出多個(gè)服務(wù)提供者后要根據(jù)他們的權(quán)重做分析。
- 但是如果只選擇出來(lái)了一個(gè)，直接用選出來(lái)這個(gè)。
- 如果真的有多個(gè)，看它們的權(quán)重是否一樣，如果不一樣，則走加權(quán)隨機(jī)算法的邏輯。
- 如果它們的權(quán)重是一樣的，則隨機(jī)調(diào)用一個(gè)。
再配個(gè)圖，就好理解了，可以先不管圖片中的標(biāo)號(hào)：
有了上面的整體概念的鋪墊了，接下來(lái)分析源碼的時(shí)候就簡(jiǎn)單了。
源碼一共就 66 行，我把它分為 5 個(gè)片段去一一分析。
這里一到五的標(biāo)號(hào)，對(duì)應(yīng)上面流程圖中的標(biāo)號(hào)。我們一個(gè)個(gè)的說(shuō)。
標(biāo)號(hào)為①的部分
這一部分是定義并初始化一些參數(shù)，為接下來(lái)的代碼服務(wù)的，翻譯一下每個(gè)參數(shù)對(duì)應(yīng)的注釋?zhuān)?/p>
length 參數(shù)：服務(wù)提供者的數(shù)量。
shortestResponse 參數(shù)：所有服務(wù)提供者的估計(jì)最短響應(yīng)時(shí)間。（這個(gè)地方我覺(jué)得注釋描述的不太準(zhǔn)確，看后面的代碼可以知道這只是一個(gè)零時(shí)變量，在循環(huán)中存儲(chǔ)當(dāng)前最短響應(yīng)時(shí)間是多少。）
shortCount 參數(shù)：具有相同最短響應(yīng)時(shí)間的服務(wù)提供者個(gè)數(shù)，初始化為 0。
shortestIndexes 參數(shù)：數(shù)組里面放的是具有相同最短響應(yīng)時(shí)間的服務(wù)提供者的下標(biāo)。
weights 參數(shù)：每一個(gè)服務(wù)提供者的權(quán)重。
totalWeight 參數(shù)：多個(gè)具有相同最短響應(yīng)時(shí)間的服務(wù)提供者對(duì)應(yīng)的預(yù)熱（預(yù)熱這個(gè)點(diǎn)還是挺重要的，在下面講最小活躍數(shù)負(fù)載均衡的時(shí)候有詳細(xì)說(shuō)明）權(quán)重之和。
firstWeight 參數(shù)：第一個(gè)具有最短響應(yīng)時(shí)間的服務(wù)提供者的權(quán)重。
sameWeight 參數(shù)：多個(gè)滿(mǎn)足條件的提供者的權(quán)重是否一致。
標(biāo)號(hào)為②的部分
這一部分代碼的關(guān)鍵，就在上面框起來(lái)的部分。而框起來(lái)的部分，最關(guān)鍵的地方，就在于第一行。
獲取調(diào)用成功的平均時(shí)間。
成功調(diào)用的平均時(shí)間怎么算的？
調(diào)用成功的請(qǐng)求數(shù)總數(shù)對(duì)應(yīng)的總耗時(shí) / 調(diào)用成功的請(qǐng)求數(shù)總數(shù) = 成功調(diào)用的平均時(shí)間。
所以，在下面這個(gè)方法中，首先獲取到了調(diào)用成功的請(qǐng)求數(shù)總數(shù)：
這個(gè) succeeded 參數(shù)是怎么來(lái)的呢？
答案就是：總的請(qǐng)求數(shù)減去請(qǐng)求失敗的數(shù)量，就是請(qǐng)求成功的總數(shù)！
那么為什么不能直接獲取請(qǐng)求成功的總數(shù)呢？
別問(wèn)，問(wèn)就是沒(méi)有這個(gè)選項(xiàng)啊。你看，在 RpcStatus 里面沒(méi)有這個(gè)參數(shù)呀。
請(qǐng)求成功的總數(shù)我們有了，接下來(lái)成功總耗時(shí)怎么拿到的呢？
答案就是：總的請(qǐng)求時(shí)間減去請(qǐng)求失敗的總時(shí)間，就是請(qǐng)求成功的總耗時(shí)！
那么為什么不能直接獲取請(qǐng)求成功的總耗時(shí)呢？
別問(wèn)，問(wèn)就是......
我們看一下 RpcStatus 中的這幾個(gè)參數(shù)是在哪里維護(hù)的：
org.apache.dubbo.rpc.RpcStatus#endCount(org.apache.dubbo.rpc.RpcStatus, long, boolean)
其中的第二個(gè)入?yún)⑹潜敬握?qǐng)求調(diào)用時(shí)長(zhǎng)，第三個(gè)入?yún)⑹潜敬握{(diào)用是否成功。
具體的方法不必細(xì)說(shuō)了吧，已經(jīng)顯而易見(jiàn)了。
再回去看框起來(lái)的那三行代碼：
- 第一行獲取到了該服務(wù)提供者成功請(qǐng)求的平均耗時(shí)。
- 第二行獲取的是該服務(wù)提供者的活躍數(shù)，也就是堆積的請(qǐng)求數(shù)。
- 第三行獲取的就是如果當(dāng)前這個(gè)請(qǐng)求發(fā)給這個(gè)服務(wù)提供者預(yù)計(jì)需要等待的時(shí)間。乘以 active 的原因是因?yàn)樗枰旁诙逊e的請(qǐng)求的后面嘛。
這里，我們就獲取到了如果選擇當(dāng)前循環(huán)中的服務(wù)提供者的預(yù)計(jì)等待時(shí)間是多長(zhǎng)。
后面的代碼怎么寫(xiě)？
當(dāng)然是出來(lái)一個(gè)更短的就把這個(gè)踢出去呀，或者出來(lái)一個(gè)一樣長(zhǎng)時(shí)間的就記錄一下，接著去 pk 權(quán)重了。
所以，接下來(lái) shortestIndexes 參數(shù)和 weights 參數(shù)就排上用場(chǎng)了：
另外，多說(shuō)一句的，它里面有這樣的一行注釋?zhuān)?/p>
和 LeastActiveLoadBalance 負(fù)載均衡策略一致，我給你截圖對(duì)比一下：
可以看到，確實(shí)是非常的相似，只是一個(gè)是判斷誰(shuí)的響應(yīng)時(shí)間短，一個(gè)是判斷誰(shuí)的活躍數(shù)低。
標(biāo)號(hào)為③的地方
標(biāo)號(hào)為③的地方是這樣的：
里面參數(shù)的含義我們都知道了，所以，標(biāo)號(hào)為③的地方的含義就很好解釋了：經(jīng)過(guò)選擇后只有一個(gè)服務(wù)提供者滿(mǎn)足條件。所以，直接使用這個(gè)服務(wù)提供者。
標(biāo)號(hào)為④的地方
這個(gè)地方我就不展開(kāi)講了（后面的加權(quán)隨機(jī)負(fù)載均衡那一小節(jié)有詳細(xì)說(shuō)明），熟悉的朋友一眼就看出來(lái)這是加權(quán)隨機(jī)負(fù)載均衡的寫(xiě)法了。
不信？我給你對(duì)比一下：
你看，是不是一模一樣的。
標(biāo)號(hào)為⑤的地方
一行代碼，沒(méi)啥說(shuō)的。就是從多個(gè)滿(mǎn)足條件的且權(quán)重一樣的服務(wù)提供者中隨機(jī)選擇一個(gè)。
如果一定要多說(shuō)一句的話(huà)，我截個(gè)圖吧：
可以看到，這行代碼在最短響應(yīng)時(shí)間、加權(quán)隨機(jī)、最小活躍數(shù)負(fù)載均衡策略中都出現(xiàn)了，且都在最后一行。
好了，到這里最短響應(yīng)時(shí)間負(fù)載均衡策略就講完了，你再回過(guò)頭去看那張流程圖，會(huì)發(fā)現(xiàn)其實(shí)流程非常的清晰，完全可以根據(jù)代碼結(jié)構(gòu)畫(huà)出流程圖。一個(gè)是說(shuō)明這個(gè)算法是真的不復(fù)雜，另一個(gè)是說(shuō)明好的代碼會(huì)說(shuō)話(huà)。
優(yōu)雅
你知道 Dubbo 加入這個(gè)新的負(fù)載均衡算法提交了幾個(gè)文件嗎？
四個(gè)文件，其中還包含兩個(gè)測(cè)試文件：
這里就是策略模式和 SPI 的好處。對(duì)原有的負(fù)載均衡策略沒(méi)有任何侵略性。只需要按照規(guī)則擴(kuò)展配置文件，實(shí)現(xiàn)對(duì)應(yīng)接口即可。
這是什么？
這就是值得學(xué)習(xí)優(yōu)雅！
那我們優(yōu)雅的進(jìn)入下一議題。
最小活躍數(shù)負(fù)載均衡
這一小節(jié)所示源碼，沒(méi)有特別標(biāo)注的地方均為 2.6.0 版本。
為什么沒(méi)有用截止目前（我當(dāng)時(shí)寫(xiě)這段文章的時(shí)候是2019年12月01日）的最新的版本號(hào) 2.7.4.1 呢？因?yàn)?2.6.0 這個(gè)版本里面有兩個(gè) bug 。從 bug 講起來(lái)，印象更加深刻。
最后會(huì)對(duì) 2.6.0/2.6.5/2.7.4.1 版本進(jìn)行對(duì)比，通過(guò)對(duì)比學(xué)習(xí)，加深印象。
我這里補(bǔ)充一句啊，僅僅半年的時(shí)間，版本號(hào)就從 2.7.4.1 到了 2.7.7。其中還包含一個(gè) 2.7.5 這樣的大版本。
所以還有人說(shuō) Dubbo 不夠活躍？（幾年前的文章現(xiàn)在還有人在發(fā)。）
對(duì)吧，我們不吵架，我們擺事實(shí)，聊數(shù)據(jù)嘛。
Demo 準(zhǔn)備
我看源碼的習(xí)慣是先搞個(gè) Demo 把調(diào)試環(huán)境搭起來(lái)。然后帶著疑問(wèn)去抽絲剝繭的 Debug，不放過(guò)在這個(gè)過(guò)程中在腦海里面一閃而過(guò)的任何疑問(wèn)。
這一小節(jié)分享的是Dubbo負(fù)載均衡策略之一最小活躍數(shù)(LeastActiveLoadBalance)。所以我先搭建一個(gè) Dubbo 的項(xiàng)目，并啟動(dòng)三個(gè) provider 供 consumer 調(diào)用。
三個(gè) provider 的 loadbalance 均配置的是 leastactive。權(quán)重分別是默認(rèn)權(quán)重、200、300。
**默認(rèn)權(quán)重是多少？**后面看源碼的時(shí)候，源碼會(huì)告訴你。
三個(gè)不同的服務(wù)提供者會(huì)給調(diào)用方返回自己是什么權(quán)重的服務(wù)。
啟動(dòng)三個(gè)實(shí)例。(注:上面的 provider.xml 和 DemoServiceImpl 其實(shí)只有一個(gè)，每次啟動(dòng)的時(shí)候手動(dòng)修改端口、權(quán)重即可。)
到 zookeeper 上檢查一下，服務(wù)提供者是否正常：
可以看到三個(gè)服務(wù)提供者分別在 20880、20881、20882 端口。（每個(gè)紅框的最后5個(gè)數(shù)字就是端口號(hào)）。
最后，我們?cè)倏捶?wù)消費(fèi)者。消費(fèi)者很簡(jiǎn)單，配置consumer.xml
直接調(diào)用接口并打印返回值即可。
斷點(diǎn)打在哪？
相信很多朋友也很想看源碼，但是不知道從何處下手。處于一種在源碼里面"亂逛"的狀態(tài)，一圈逛下來(lái)，收獲并不大。
這一部分我想分享一下我是怎么去看源碼。首先我會(huì)帶著問(wèn)題去源碼里面尋找答案，即有針對(duì)性的看源碼。
如果是這種框架類(lèi)的，正如上面寫(xiě)的，我會(huì)先翻一翻官網(wǎng)（Dubbo 的官方文檔其實(shí)寫(xiě)的挺好了），然后搭建一個(gè)簡(jiǎn)單的 Demo 項(xiàng)目，然后 Debug 跟進(jìn)去看。Debug 的時(shí)候當(dāng)然需要是設(shè)置斷點(diǎn)的，那么這個(gè)斷點(diǎn)如何設(shè)置呢？
第一個(gè)斷點(diǎn)，當(dāng)然毋庸置疑，是打在調(diào)用方法的地方，比如本文中，第一個(gè)斷點(diǎn)是在這個(gè)地方：
接下里怎么辦？
你當(dāng)然可以從第一個(gè)斷點(diǎn)處，一步一步的跟進(jìn)去。但是在這個(gè)過(guò)程中，你發(fā)現(xiàn)了嗎？大多數(shù)情況你都是被源碼牽著鼻子走的。本來(lái)你就只帶著一個(gè)問(wèn)題去看源碼的，有可能你Debug了十分鐘，還沒(méi)找到關(guān)鍵的代碼。也有可能你Debug了十分鐘，問(wèn)題從一個(gè)變成了無(wú)數(shù)個(gè)。
所以不要慌，我們點(diǎn)支煙，慢慢分析。
首先怎么避免被源碼牽著四處亂逛呢？
我們得找到一個(gè)突破口，還記得我在《很開(kāi)心，在使用mybatis的過(guò)程中我踩到一個(gè)坑》這篇文章中提到的逆向排查的方法嗎？這次的文章,我再次展示一下該方法。
看源碼之前，我們的目標(biāo)要十分明確，就是想要找到 Dubbo 最小活躍數(shù)算法的具體實(shí)現(xiàn)類(lèi)以及實(shí)現(xiàn)類(lèi)的具體邏輯是什么。
根據(jù)我們的 provider.xml 里面的：
很明顯，我們知道 loadbalance 是關(guān)鍵字。所以我們拿著 loadbalance 全局搜索，可以看到 Dubbo 包下面的 LoadBalance。
這是一個(gè) SPI 接口
com.alibaba.dubbo.rpc.cluster.LoadBalance：
其實(shí)現(xiàn)類(lèi)為:
com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance
AbstractLoadBalance 是一個(gè)抽象類(lèi)，該類(lèi)里面有一個(gè)抽象方法doSelect。這個(gè)抽象方法其中的一個(gè)實(shí)現(xiàn)類(lèi)就是我們要分析的最少活躍次數(shù)負(fù)載均衡的源碼。
同時(shí)，到這里我們知道了 LoadBalance 是一個(gè) SPI 接口，說(shuō)明我們可以擴(kuò)展自己的負(fù)載均衡策略。抽象方法 doSelect 有四個(gè)實(shí)現(xiàn)類(lèi)。這個(gè)四個(gè)實(shí)現(xiàn)類(lèi)，就是 Dubbo 官方提供的負(fù)載均衡策略（截止 2.7.7 版本之前），他們分別是:
- ConsistentHashLoadBalance 一致性哈希算法
- LeastActiveLoadBalance 最小活躍數(shù)算法
- RandomLoadBalance 加權(quán)隨機(jī)算法
- RoundRobinLoadBalance 加權(quán)輪詢(xún)算法
我們已經(jīng)找到了 LeastActiveLoadBalance 這個(gè)類(lèi)了，那么我們的第二個(gè)斷點(diǎn)打在哪里已經(jīng)很明確了。
目前看來(lái)，兩個(gè)斷點(diǎn)就可以支撐我們的分析了。
有的朋友可能想問(wèn)，那我想知道 Dubbo 是怎么識(shí)別出我們想要的是最少活躍次數(shù)算法，而不是其他的算法呢？其他的算法是怎么實(shí)現(xiàn)的呢？從第一個(gè)斷點(diǎn)到第二個(gè)斷點(diǎn)直接有著怎樣的調(diào)用鏈呢？
在沒(méi)有徹底搞清楚最少活躍數(shù)算法之前，這些統(tǒng)統(tǒng)先記錄在案但不予理睬。一定要明確目標(biāo)，帶著一個(gè)問(wèn)題進(jìn)來(lái)，就先把帶來(lái)的問(wèn)題解決了。之后再去解決在這個(gè)過(guò)程中碰到的其他問(wèn)題。在這樣環(huán)環(huán)相扣解決問(wèn)題的過(guò)程中，你就慢慢的把握了源碼的精髓。這是我個(gè)人的一點(diǎn)看源碼的心得。供諸君參考。
模擬環(huán)境
既然叫做最小活躍數(shù)策略。那我們得讓現(xiàn)有的三個(gè)消費(fèi)者都有一些調(diào)用次數(shù)。所以我們得改造一下服務(wù)提供者和消費(fèi)者。
服務(wù)提供者端的改造如下:
PS：這里以權(quán)重為 300 的服務(wù)端為例。另外的兩個(gè)服務(wù)端改造點(diǎn)相同。
客戶(hù)端的改造點(diǎn)如下：
一共發(fā)送 21 個(gè)請(qǐng)求：其中前 20 個(gè)先發(fā)到服務(wù)端讓其 hold 住(因?yàn)榉?wù)端有 sleep)，最后一個(gè)請(qǐng)求就是我們需要 Debug 跟蹤的請(qǐng)求。
運(yùn)行一下，讓程序停在斷點(diǎn)的地方,然后看看控制臺(tái)的輸出:
權(quán)重為300的服務(wù)端共計(jì)收到9個(gè)請(qǐng)求
權(quán)重為200的服務(wù)端共計(jì)收到6個(gè)請(qǐng)求
默認(rèn)權(quán)重的服務(wù)端共計(jì)收到5個(gè)請(qǐng)求
我們還有一個(gè)請(qǐng)求在 Debug。直接進(jìn)入到我們的第二個(gè)斷點(diǎn)的位置，并 Debug 到下圖所示的一行代碼(可以點(diǎn)看查看大圖):
正如上面這圖所說(shuō)的：weight=100 回答了一個(gè)問(wèn)題，active=0 提出的一個(gè)問(wèn)題。
weight=100 回答了什么問(wèn)題呢？
默認(rèn)權(quán)重是多少？是 100。
我們服務(wù)端的活躍數(shù)分別應(yīng)該是下面這樣的
- 權(quán)重為300的服務(wù)端，active=9
- 權(quán)重為200的服務(wù)端，active=6
- 默認(rèn)權(quán)重(100)的服務(wù)端，active=5
但是這里為什么截圖中的active會(huì)等于 0 呢？這是一個(gè)問(wèn)題。
繼續(xù)往下 Debug 你會(huì)發(fā)現(xiàn)，每一個(gè)服務(wù)端的 active 都是 0。所以相比之下沒(méi)有一個(gè) invoker 有最小 active 。于是程序走到了根據(jù)權(quán)重選擇 invoker 的邏輯中。
active為什么是0？
active 為 0 說(shuō)明在 Dubbo 調(diào)用的過(guò)程中 active 并沒(méi)有發(fā)生變化。那 active 為什么是 0，其實(shí)就是在問(wèn) active 什么時(shí)候發(fā)生變化？
要回答這個(gè)問(wèn)題我們得知道 active 是在哪里定義的，因?yàn)樵谄涠x的地方，必有其修改的方法。
下面這圖說(shuō)明了active是定義在RpcStatus類(lèi)里面的一個(gè)類(lèi)型為AtomicInteger 的成員變量。
在 RpcStatus 類(lèi)中，有三處()調(diào)用 active 值的方法，一個(gè)增加、一個(gè)減少、一個(gè)獲取：
很明顯，我們需要看的是第一個(gè)，在哪里增加。
所以我們找到了 beginCount(URL,String) 方法，該方法只有兩個(gè) Filter 調(diào)用。ActiveLimitFilter，見(jiàn)名知意，這就是我們要找的東西。
com.alibaba.dubbo.rpc.filter.ActiveLimitFilter具體如下：
看到這里，我們就知道怎么去回答這個(gè)問(wèn)題了：為什么active是0呢？因?yàn)樵诳蛻?hù)端沒(méi)有配置ActiveLimitFilter。所以，ActiveLimitFilter沒(méi)有生效，導(dǎo)致active沒(méi)有發(fā)生變化。
怎么讓其生效呢？已經(jīng)呼之欲出了。
好了，再來(lái)試驗(yàn)一次:
加上Filter之后，我們通過(guò)Debug可以看到，對(duì)應(yīng)權(quán)重的活躍數(shù)就和我們預(yù)期的是一致的了。
1.權(quán)重為300的活躍數(shù)為6
2.權(quán)重為200的活躍數(shù)為11
3.默認(rèn)權(quán)重(100)的活躍數(shù)為3
根據(jù)活躍數(shù)我們可以分析出來(lái)，最后我們Debug住的這個(gè)請(qǐng)求，一定會(huì)選擇默認(rèn)權(quán)重的invoker去執(zhí)行，因?yàn)樗钱?dāng)前活躍數(shù)最小的invoker。如下所示：
雖然到這里我們還沒(méi)開(kāi)始進(jìn)行源碼的分析，只是把流程梳理清楚了。但是把Demo完整的搭建了起來(lái)，而且知道了最少活躍數(shù)負(fù)載均衡算法必須配合ActiveLimitFilter使用，位于RpcStatus類(lèi)的active字段才會(huì)起作用，否則，它就是一個(gè)基于權(quán)重的算法。
比起其他地方直接告訴你，要配置ActiveLimitFilter才行哦，我們自己實(shí)驗(yàn)得出的結(jié)論，能讓我們的印象更加深刻。
我們?cè)僮屑?xì)看一下加上ActiveLimitFilter之后的各個(gè)服務(wù)的活躍數(shù)情況：
- 權(quán)重為300的活躍數(shù)為6
- 權(quán)重為200的活躍數(shù)為11
- 默認(rèn)權(quán)重(100)的活躍數(shù)為3
你不覺(jué)得奇怪嗎，為什么權(quán)重為200的活躍數(shù)是最高的？
其在業(yè)務(wù)上的含義是：我們有三臺(tái)性能各異的服務(wù)器，A服務(wù)器性能最好，所以權(quán)重為300，B服務(wù)器性能中等，所以權(quán)重為200，C服務(wù)器性能最差，所以權(quán)重為100。
當(dāng)我們選擇最小活躍次數(shù)的負(fù)載均衡算法時(shí)，我們期望的是性能最好的A服務(wù)器承擔(dān)更多的請(qǐng)求，而真實(shí)的情況是性能中等的B服務(wù)器承擔(dān)的請(qǐng)求更多。這與我們的設(shè)定相悖。
如果你說(shuō)20個(gè)請(qǐng)求數(shù)據(jù)量太少，可能是巧合，不足以說(shuō)明問(wèn)題。說(shuō)明你還沒(méi)被我?guī)覀儾荒芑谇珊暇幊獭?/p>
所以為了驗(yàn)證這個(gè)地方確實(shí)有問(wèn)題，我把請(qǐng)求擴(kuò)大到一萬(wàn)個(gè)。
同時(shí)，記得擴(kuò)大 provider 端的 Dubbo 線(xiàn)程池：
由于每個(gè)服務(wù)端運(yùn)行的代碼都是一樣的，所以我們期望的結(jié)果應(yīng)該是權(quán)重最高的承擔(dān)更多的請(qǐng)求。但是最終的結(jié)果如圖所示:
各個(gè)服務(wù)器均攤了請(qǐng)求。這就是我文章最開(kāi)始的時(shí)候說(shuō)的Dubbo 2.6.0 版本中最小活躍數(shù)負(fù)載均衡算法的Bug之一。
接下來(lái)，我們帶著這個(gè)問(wèn)題，去分析源碼。
剖析源碼
com.alibaba.dubbo.rpc.cluster.loadbalance.LeastActiveLoadBalance的源碼如下，我逐行進(jìn)行了解讀。可以點(diǎn)開(kāi)查看大圖，細(xì)細(xì)品讀，非常爽：
下圖中紅框框起來(lái)的部分就是一個(gè)基于權(quán)重選擇invoker的邏輯：
我給大家畫(huà)圖分析一下：
請(qǐng)仔細(xì)分析圖中給出的舉例說(shuō)明。同時(shí)，上面這圖也是按照比例畫(huà)的，可以直觀的看到，對(duì)于某一個(gè)請(qǐng)求，區(qū)間(權(quán)重)越大的服務(wù)器，就越可能會(huì)承擔(dān)這個(gè)請(qǐng)求。所以，當(dāng)請(qǐng)求足夠多的時(shí)候，各個(gè)服務(wù)器承擔(dān)的請(qǐng)求數(shù)，應(yīng)該就是區(qū)間，即權(quán)重的比值。
其中第 81 行有調(diào)用 getWeight 方法，位于抽象類(lèi) AbstractLoadBalance 中，也需要進(jìn)行重點(diǎn)解讀的代碼。
com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance 的源碼如下，我也進(jìn)行了大量的備注:
在 AbstractLoadBalance 類(lèi)中提到了一個(gè)預(yù)熱的概念。官網(wǎng)中是這樣的介紹該功能的：
權(quán)重的計(jì)算過(guò)程主要用于保證當(dāng)服務(wù)運(yùn)行時(shí)長(zhǎng)小于服務(wù)預(yù)熱時(shí)間時(shí)，對(duì)服務(wù)進(jìn)行降權(quán)，避免讓服務(wù)在啟動(dòng)之初就處于高負(fù)載狀態(tài)。服務(wù)預(yù)熱是一個(gè)優(yōu)化手段，與此類(lèi)似的還有 JVM 預(yù)熱。主要目的是讓服務(wù)啟動(dòng)后“低功率”運(yùn)行一段時(shí)間，使其效率慢慢提升至最佳狀態(tài)。
從上圖代碼里面的公式(演變后)：*計(jì)算后的權(quán)重=(uptime/warmup)weight 可以看出：隨著服務(wù)啟動(dòng)時(shí)間的增加(uptime)，計(jì)算后的權(quán)重會(huì)越來(lái)越接近weight。從實(shí)際場(chǎng)景的角度來(lái)看，隨著服務(wù)啟動(dòng)時(shí)間的增加，服務(wù)承擔(dān)的流量會(huì)慢慢上升，沒(méi)有一個(gè)陡升的過(guò)程。所以這是一個(gè)優(yōu)化手段。同時(shí) Dubbo 接口還支持延遲暴露。
在仔細(xì)的看完上面的源碼解析圖后，配合官網(wǎng)的總結(jié)加上我的靈魂畫(huà)作，相信你可以對(duì)最小活躍數(shù)負(fù)載均衡算法有一個(gè)比較深入的理解：
- 遍歷 invokers 列表，尋找活躍數(shù)最小的 Invoker
- 如果有多個(gè) Invoker 具有相同的最小活躍數(shù)，此時(shí)記錄下這些 Invoker 在 invokers 集合中的下標(biāo)，并累加它們的權(quán)重，比較它們的權(quán)重值是否相等
- 如果只有一個(gè) Invoker 具有最小的活躍數(shù)，此時(shí)直接返回該 Invoker 即可
- 如果有多個(gè) Invoker 具有最小活躍數(shù)，且它們的權(quán)重不相等，此時(shí)處理方式和 RandomLoadBalance 一致
- 如果有多個(gè) Invoker 具有最小活躍數(shù)，但它們的權(quán)重相等，此時(shí)隨機(jī)返回一個(gè)即可
所以我覺(jué)得最小活躍數(shù)負(fù)載均衡的全稱(chēng)應(yīng)該叫做：有最小活躍數(shù)用最小活躍數(shù)，沒(méi)有最小活躍數(shù)根據(jù)權(quán)重選擇，權(quán)重一樣則隨機(jī)返回的負(fù)載均衡算法。
Bug在哪里？
Dubbo2.6.0最小活躍數(shù)算法Bug一
問(wèn)題出在標(biāo)號(hào)為 ① 和 ② 這兩行代碼中：
標(biāo)號(hào)為 ① 的代碼在url中取出的是沒(méi)有經(jīng)過(guò) getWeight 方法降權(quán)處理的權(quán)重值，這個(gè)值會(huì)被累加到權(quán)重總和(totalWeight)中。
標(biāo)號(hào)為 ② 的代碼取的是經(jīng)過(guò) getWeight 方法處理后的權(quán)重值。
取值的差異會(huì)導(dǎo)致一個(gè)問(wèn)題，標(biāo)號(hào)為 ② 的代碼的左邊，offsetWeight 是一個(gè)在 [0，totalWeight) 范圍內(nèi)的隨機(jī)數(shù)，右邊是經(jīng)過(guò) getWeight 方法降權(quán)后的權(quán)重。所以在經(jīng)過(guò) leastCount 次的循環(huán)減法后，offsetWeight 在服務(wù)啟動(dòng)時(shí)間還沒(méi)到熱啟動(dòng)設(shè)置（默認(rèn)10分鐘）的這段時(shí)間內(nèi)，極大可能仍然大于 0。導(dǎo)致不會(huì)進(jìn)入到標(biāo)號(hào)為 ③ 的代碼中。直接到標(biāo)號(hào)為 ④ 的代碼處，變成了隨機(jī)調(diào)用策略。這與設(shè)計(jì)不符，所以是個(gè) bug。
前面章節(jié)說(shuō)的情況就是這個(gè)Bug導(dǎo)致的。
這個(gè)Bug對(duì)應(yīng)的issues地址和pull request分為:
https://github.com/apache/dubbo/issues/904
https://github.com/apache/dubbo/pull/2172
那怎么修復(fù)的呢？我們直接對(duì)比 Dubbo 2.7.4.1 的代碼:
可以看到獲取weight的方法變了：從url中直接獲取變成了通過(guò)getWeight方法獲取。獲取到的變量名稱(chēng)也變了：從weight變成了afterWarmup，更加的見(jiàn)名知意。
還有一處變化是獲取隨機(jī)值的方法的變化，從Randmo變成了ThreadLoaclRandom，性能得到了提升。這處變化就不展開(kāi)講了，有興趣的朋友可以去了解一下。
Dubbo2.6.0最小活躍數(shù)算法Bug二
這個(gè)Bug我沒(méi)有遇到，但是我在官方文檔上看了其描述（官方文檔中的版本是2.6.4），引用如下：
官網(wǎng)上說(shuō)這個(gè)問(wèn)題在2.6.5版本進(jìn)行修復(fù)。我對(duì)比了2.6.0/2.6.5/2.7.4.1三個(gè)版本，發(fā)現(xiàn)每個(gè)版本都略有不同。如下所示：
圖中標(biāo)記為①的三處代碼：
2.6.0版本的是有Bug的代碼，原因在上面說(shuō)過(guò)了。
2.6.5版本的修復(fù)方式是獲取隨機(jī)數(shù)的時(shí)候加一，所以取值范圍就從**[0,totalWeight)變成了[0,totalWeight]**，這樣就可以避免這個(gè)問(wèn)題。
2.7.4.1版本的取值范圍還是[0,totalWeight)，但是它的修復(fù)方法體現(xiàn)在了標(biāo)記為②的代碼處。2.6.0/2.6.5版本標(biāo)記為②的地方都是if(offsetWeight<=0)，而2.7.4.1版本變成了if(offsetWeight<0)。
你品一品，是不是效果是一樣的，但是更加優(yōu)雅了。
朋友們，魔鬼，都在細(xì)節(jié)里啊！
好了，進(jìn)入下一議題。
一致性哈希負(fù)載均衡
這一部分是對(duì)于Dubbo負(fù)載均衡策略之一的一致性哈希負(fù)載均衡的詳細(xì)分析。對(duì)源碼逐行解讀、根據(jù)實(shí)際運(yùn)行結(jié)果，配以豐富的圖片，可能是東半球講一致性哈希算法在Dubbo中的實(shí)現(xiàn)最詳細(xì)的文章了。
本小節(jié)所示源碼，沒(méi)有特別標(biāo)注的地方，均為2.7.4.1版本。
在撰寫(xiě)本文的過(guò)程中，發(fā)現(xiàn)了Dubbo2.7.0版本之后的一個(gè)bug。會(huì)導(dǎo)致性能問(wèn)題，如果你們的負(fù)載均衡配置的是一致性哈希或者考慮使用一致性哈希的話(huà)，可以了解一下。
哈希算法
在介紹一致性哈希算法之前，我們看看哈希算法，以及它解決了什么問(wèn)題，帶來(lái)了什么問(wèn)題。
如上圖所示，假設(shè)0,1,2號(hào)服務(wù)器都存儲(chǔ)的有用戶(hù)信息，那么當(dāng)我們需要獲取某用戶(hù)信息時(shí)，因?yàn)槲覀儾恢涝撚脩?hù)信息存放在哪一臺(tái)服務(wù)器中，所以需要分別查詢(xún)0,1,2號(hào)服務(wù)器。這樣獲取數(shù)據(jù)的效率是極低的。
對(duì)于這樣的場(chǎng)景，我們可以引入哈希算法。
還是上面的場(chǎng)景，但前提是每一臺(tái)服務(wù)器存放用戶(hù)信息時(shí)是根據(jù)某一種哈希算法存放的。所以取用戶(hù)信息的時(shí)候，也按照同樣的哈希算法取即可。
假設(shè)我們要查詢(xún)用戶(hù)號(hào)為100的用戶(hù)信息，經(jīng)過(guò)某個(gè)哈希算法，比如這里的userId mod n，即100 mod 3結(jié)果為1。所以用戶(hù)號(hào)100的這個(gè)請(qǐng)求最終會(huì)被1號(hào)服務(wù)器接收并處理。
這樣就解決了無(wú)效查詢(xún)的問(wèn)題。
但是這樣的方案會(huì)帶來(lái)什么問(wèn)題呢？
擴(kuò)容或者縮容時(shí)，會(huì)導(dǎo)致大量的數(shù)據(jù)遷移。最少也會(huì)影響百分之50的數(shù)據(jù)。
為了說(shuō)明問(wèn)題，我們加入一臺(tái)服務(wù)器3。服務(wù)器的數(shù)量n就從3變成了4。還是查詢(xún)用戶(hù)號(hào)為100的用戶(hù)信息時(shí)，100 mod 4結(jié)果為0。這時(shí)，請(qǐng)求就被0號(hào)服務(wù)器接收了。
當(dāng)服務(wù)器數(shù)量為3時(shí)，用戶(hù)號(hào)為100的請(qǐng)求會(huì)被1號(hào)服務(wù)器處理。
當(dāng)服務(wù)器數(shù)量為4時(shí)，用戶(hù)號(hào)為100的請(qǐng)求會(huì)被0號(hào)服務(wù)器處理。
所以，當(dāng)服務(wù)器數(shù)量增加或者減少時(shí)，一定會(huì)涉及到大量數(shù)據(jù)遷移的問(wèn)題。可謂是牽一發(fā)而動(dòng)全身。
對(duì)于上訴哈希算法其優(yōu)點(diǎn)是簡(jiǎn)單易用，大多數(shù)分庫(kù)分表規(guī)則就采取的這種方式。一般是提前根據(jù)數(shù)據(jù)量，預(yù)先估算好分區(qū)數(shù)。
其缺點(diǎn)是由于擴(kuò)容或收縮節(jié)點(diǎn)導(dǎo)致節(jié)點(diǎn)數(shù)量變化時(shí)，節(jié)點(diǎn)的映射關(guān)系需要重新計(jì)算，會(huì)導(dǎo)致數(shù)據(jù)進(jìn)行遷移。所以擴(kuò)容時(shí)通常采用翻倍擴(kuò)容，避免數(shù)據(jù)映射全部被打亂，導(dǎo)致全量遷移的情況，這樣只會(huì)發(fā)生50%的數(shù)據(jù)遷移。
假設(shè)這是一個(gè)緩存服務(wù)，數(shù)據(jù)的遷移會(huì)導(dǎo)致在遷移的時(shí)間段內(nèi)，有緩存是失效的。
緩存失效，可怕啊。還記得我之前的文章嗎，《當(dāng)周杰倫把QQ音樂(lè)干翻的時(shí)候，作為程序猿我看到了什么？》就是講緩存擊穿、緩存穿透、緩存雪崩的場(chǎng)景和對(duì)應(yīng)的解決方案。
一致性哈希算法
為了解決哈希算法帶來(lái)的數(shù)據(jù)遷移問(wèn)題，一致性哈希算法應(yīng)運(yùn)而生。
對(duì)于一致性哈希算法，官方說(shuō)法如下：
一致性哈希算法在1997年由麻省理工學(xué)院提出，是一種特殊的哈希算法，在移除或者添加一個(gè)服務(wù)器時(shí)，能夠盡可能小地改變已存在的服務(wù)請(qǐng)求與處理請(qǐng)求服務(wù)器之間的映射關(guān)系。一致性哈希解決了簡(jiǎn)單哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的動(dòng)態(tài)伸縮等問(wèn)題。
什么意思呢？我用大白話(huà)加畫(huà)圖的方式給你簡(jiǎn)單的介紹一下。
一致性哈希，你可以想象成一個(gè)哈希環(huán)，它由0到2^32-1個(gè)點(diǎn)組成。A，B，C分別是三臺(tái)服務(wù)器，每一臺(tái)的IP加端口經(jīng)過(guò)哈希計(jì)算后的值，在哈希環(huán)上對(duì)應(yīng)如下：
當(dāng)請(qǐng)求到來(lái)時(shí)，對(duì)請(qǐng)求中的某些參數(shù)進(jìn)行哈希計(jì)算后，也會(huì)得出一個(gè)哈希值，此值在哈希環(huán)上也會(huì)有對(duì)應(yīng)的位置，這個(gè)請(qǐng)求會(huì)沿著順時(shí)針的方向，尋找最近的服務(wù)器來(lái)處理它，如下圖所示：
一致性哈希就是這么個(gè)東西。那它是怎么解決服務(wù)器的擴(kuò)容或收縮導(dǎo)致大量的數(shù)據(jù)遷移的呢？
看一下當(dāng)我們使用一致性哈希算法時(shí)，加入服務(wù)器會(huì)發(fā)什么事情。
當(dāng)我們加入一個(gè)D服務(wù)器后，假設(shè)其IP加端口，經(jīng)過(guò)哈希計(jì)算后落在了哈希環(huán)上圖中所示的位置。
這時(shí)影響的范圍只有圖中標(biāo)注了五角星的區(qū)間。這個(gè)區(qū)間的請(qǐng)求從原來(lái)的由C服務(wù)器處理變成了由D服務(wù)器請(qǐng)求。而D到C，C到A，A到B這個(gè)區(qū)間的請(qǐng)求沒(méi)有影響，加入D節(jié)點(diǎn)后，A、B服務(wù)器是無(wú)感知的。
所以，在一致性哈希算法中，如果增加一臺(tái)服務(wù)器，則受影響的區(qū)間僅僅是新服務(wù)器(D)在哈希環(huán)空間中，逆時(shí)針方向遇到的第一臺(tái)服務(wù)器(B)之間的區(qū)間，其它區(qū)間(D到C，C到A，A到B)不會(huì)受到影響。
在加入了D服務(wù)器的情況下，我們?cè)偌僭O(shè)一段時(shí)間后，C服務(wù)器宕機(jī)了：
當(dāng)C服務(wù)器宕機(jī)后，影響的范圍也是圖中標(biāo)注了五角星的區(qū)間。C節(jié)點(diǎn)宕機(jī)后，B、D服務(wù)器是無(wú)感知的。
所以，在一致性哈希算法中，如果宕機(jī)一臺(tái)服務(wù)器，則受影響的區(qū)間僅僅是宕機(jī)服務(wù)器(C)在哈希環(huán)空間中，逆時(shí)針方向遇到的第一臺(tái)服務(wù)器(D)之間的區(qū)間，其它區(qū)間(C到A，A到B，B到D)不會(huì)受到影響。
綜上所述，在一致性哈希算法中，不管是增加節(jié)點(diǎn)，還是宕機(jī)節(jié)點(diǎn)，受影響的區(qū)間僅僅是增加或者宕機(jī)服務(wù)器在哈希環(huán)空間中，逆時(shí)針?lè)较蛴龅降牡谝慌_(tái)服務(wù)器之間的區(qū)間，其它區(qū)間不會(huì)受到影響。
是不是很完美？
不是的，理想和現(xiàn)實(shí)的差距是巨大的。
一致性哈希算法帶來(lái)了什么問(wèn)題？
當(dāng)節(jié)點(diǎn)很少的時(shí)候可能會(huì)出現(xiàn)這樣的分布情況，A服務(wù)會(huì)承擔(dān)大部分請(qǐng)求。這種情況就叫做數(shù)據(jù)傾斜。
怎么解決數(shù)據(jù)傾斜呢？加入虛擬節(jié)點(diǎn)。
怎么去理解這個(gè)虛擬節(jié)點(diǎn)呢？
首先一個(gè)服務(wù)器根據(jù)需要可以有多個(gè)虛擬節(jié)點(diǎn)。假設(shè)一臺(tái)服務(wù)器有n個(gè)虛擬節(jié)點(diǎn)。那么哈希計(jì)算時(shí)，可以使用IP+端口+編號(hào)的形式進(jìn)行哈希值計(jì)算。其中的編號(hào)就是0到n的數(shù)字。由于IP+端口是一樣的，所以這n個(gè)節(jié)點(diǎn)都是指向的同一臺(tái)機(jī)器。
如下圖所示：
在沒(méi)有加入虛擬節(jié)點(diǎn)之前，A服務(wù)器承擔(dān)了絕大多數(shù)的請(qǐng)求。但是假設(shè)每個(gè)服務(wù)器有一個(gè)虛擬節(jié)點(diǎn)（A-1，B-1，C-1），經(jīng)過(guò)哈希計(jì)算后落在了如上圖所示的位置。那么A服務(wù)器的承擔(dān)的請(qǐng)求就在一定程度上（圖中標(biāo)注了五角星的部分）分?jǐn)偨o了B-1、C-1虛擬節(jié)點(diǎn)，實(shí)際上就是分?jǐn)偨o了B、C服務(wù)器。
一致性哈希算法中，加入虛擬節(jié)點(diǎn)，可以解決數(shù)據(jù)傾斜問(wèn)題。
當(dāng)你在面試的過(guò)程中，如果聽(tīng)到了類(lèi)似于數(shù)據(jù)傾斜的字眼。那大概率是在問(wèn)你一致性哈希算法和虛擬節(jié)點(diǎn)。
在介紹了相關(guān)背景后，我們可以去看看一致性哈希算法在Dubbo中的應(yīng)用了。
一致性哈希算法在Dubbo中的應(yīng)用
前面我們說(shuō)了Dubbo中負(fù)載均衡的實(shí)現(xiàn)是通過(guò)
org.apache.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance中的 doSelect 抽象方法實(shí)現(xiàn)的，一致性哈希負(fù)載均衡的實(shí)現(xiàn)類(lèi)如下所示：
org.apache.dubbo.rpc.cluster.loadbalance.ConsistentHashLoadBalance
由于一致性哈希實(shí)現(xiàn)類(lèi)看起來(lái)稍微有點(diǎn)抽象，不太好演示，所以我想到了一個(gè)"騷"操作。前面的文章說(shuō)過(guò) LoadBalance 是一個(gè) SPI 接口：
既然是一個(gè) SPI 接口，那我們可以自己擴(kuò)展一個(gè)一模一樣的算法，只是在算法里面加入一點(diǎn)輸出語(yǔ)句方便我們觀察情況。怎么擴(kuò)展 SPI 接口就不描述了，只要記住代碼里面的輸出語(yǔ)句都是額外加的，此外沒(méi)有任何改動(dòng)即可，如下：
整個(gè)類(lèi)如下圖片所示，請(qǐng)先看完整個(gè)類(lèi)，有一個(gè)整體的概念后，我會(huì)進(jìn)行方法級(jí)別的分析。
圖片很長(zhǎng)，其中我加了很多注釋和輸出語(yǔ)句，可以點(diǎn)開(kāi)大圖查看，一定會(huì)幫你更加好的理解一致性哈希在Dubbo中的應(yīng)用：
改造之后，我們先把程序跑起來(lái)，有了輸出就好分析了。
服務(wù)端代碼如下：
其中的端口是需要手動(dòng)修改的，我分別啟動(dòng)服務(wù)在20881和20882端口。
項(xiàng)目中provider.xml配置如下：
consumer.xml配置如下:
然后，啟動(dòng)在20881和20882端口分別啟動(dòng)兩個(gè)服務(wù)端。客戶(hù)端消費(fèi)如下：
運(yùn)行結(jié)果輸出如下，可以先看個(gè)大概的輸出，下面會(huì)對(duì)每一部分輸出進(jìn)行逐一的解讀。
好了，用例也跑起來(lái)了，日志也有了。接下來(lái)開(kāi)始結(jié)合代碼和日志進(jìn)行方法級(jí)別的分析。
首先是doSelect方法的入口：
從上圖我們知道了，第一次調(diào)用需要對(duì)selectors進(jìn)行put操作，selectors的 key 是接口中定義的方法，value 是 ConsistentHashSelector 內(nèi)部類(lèi)。
ConsistentHashSelector通過(guò)調(diào)用其構(gòu)造函數(shù)進(jìn)行初始化的。invokers(服務(wù)端)作為參數(shù)傳遞到了構(gòu)造函數(shù)中，構(gòu)造函數(shù)里面的邏輯，就是把服務(wù)端映射到哈希環(huán)上的過(guò)程，請(qǐng)看下圖，結(jié)合代碼，仔細(xì)分析輸出數(shù)據(jù)：
從上圖可以看出，當(dāng) ConsistentHashSelector 的構(gòu)造方法調(diào)用完成后，8個(gè)虛擬節(jié)點(diǎn)在哈希環(huán)上已經(jīng)映射完成。兩臺(tái)服務(wù)器，每一臺(tái)4個(gè)虛擬節(jié)點(diǎn)組成了這8個(gè)虛擬節(jié)點(diǎn)。
doSelect方法繼續(xù)執(zhí)行，并打印出每個(gè)虛擬節(jié)點(diǎn)的哈希值和對(duì)應(yīng)的服務(wù)端，請(qǐng)仔細(xì)品讀下圖：
說(shuō)明一下：上面圖中的哈希環(huán)是沒(méi)有考慮比例的，僅僅是展現(xiàn)了兩個(gè)服務(wù)器在哈希環(huán)上的相對(duì)位置。而且為了演示說(shuō)明方便，僅僅只有8個(gè)節(jié)點(diǎn)。假設(shè)我們有4臺(tái)服務(wù)器，每臺(tái)服務(wù)器的虛擬節(jié)點(diǎn)是默認(rèn)值(160)，這個(gè)情況下哈希環(huán)上一共有160*4=640個(gè)節(jié)點(diǎn)。
哈希環(huán)映射完成后，接下來(lái)的邏輯是把這次請(qǐng)求經(jīng)過(guò)哈希計(jì)算后，映射到哈希環(huán)上，并順時(shí)針?lè)较?/strong>尋找遇到的第一個(gè)節(jié)點(diǎn)，讓該節(jié)點(diǎn)處理該請(qǐng)求：
還記得地址為 468e8565 的 A 服務(wù)器是什么端口嗎？前面的圖片中有哦，該服務(wù)對(duì)應(yīng)的端口是 20882 。
最后我們看看輸出結(jié)果:
和我們預(yù)期的一致。整個(gè)調(diào)用就算是完成了。
再對(duì)兩個(gè)方法進(jìn)行一個(gè)補(bǔ)充說(shuō)明。
第一個(gè)方法是 selectForKey，這個(gè)方法里面邏輯如下圖所示：
虛擬節(jié)點(diǎn)都存儲(chǔ)在 TreeMap 中。順時(shí)針查詢(xún)的邏輯由 TreeMap 保證。看一下下面的 Demo 你就明白了。
第二個(gè)方法是 hash 方法，其中的 & 0xFFFFFFFFL 的目的如下:
&是位運(yùn)算符，而 0xFFFFFFFFL 轉(zhuǎn)換為四字節(jié)表現(xiàn)后，其低32位全是1，所以保證了哈希環(huán)的范圍是 [0,Integer.MAX_VALUE]：
所以這里我們可以改造這個(gè)哈希環(huán)的范圍，假設(shè)我們改為 100000。十進(jìn)制的 100000 對(duì)于的 16 進(jìn)制為 186A0 。所以我們改造后的哈希算法為：
再次調(diào)用后可以看到，計(jì)算后的哈希值都在10萬(wàn)以?xún)?nèi)。但是分布極不均勻，說(shuō)明修改數(shù)據(jù)后這個(gè)哈希算法不是一個(gè)優(yōu)秀的哈希算法：
以上，就是對(duì)一致性哈希算法在Dubbo中的實(shí)現(xiàn)的解讀。需要特殊說(shuō)明一下的是，一致性哈希負(fù)載均衡策略和權(quán)重沒(méi)有任何關(guān)系。
我又發(fā)現(xiàn)了一個(gè)BUG
前面我介紹了Dubbo 2.6.5版本之前，最小活躍數(shù)算法的兩個(gè) bug。
很不幸，這次我又發(fā)現(xiàn)了Dubbo 2.7.4.1版本，一致性哈希負(fù)載均衡策略的一個(gè)bug，我提交了issue 地址如下：
https://github.com/apache/dubbo/issues/5429
我在這里詳細(xì)說(shuō)一下這個(gè)Bug現(xiàn)象、原因和我的解決方案。
現(xiàn)象如下，我們調(diào)用三次服務(wù)端：
輸出日志如下（有部分刪減）：
可以看到，在三次調(diào)用的過(guò)程中并沒(méi)有發(fā)生服務(wù)的上下線(xiàn)操作，但是每一次調(diào)用都重新進(jìn)行了哈希環(huán)的映射。而我們預(yù)期的結(jié)果是應(yīng)該只有在第一次調(diào)用的時(shí)候進(jìn)行哈希環(huán)的映射，如果沒(méi)有服務(wù)上下線(xiàn)的操作，后續(xù)請(qǐng)求根據(jù)已經(jīng)映射好的哈希環(huán)進(jìn)行處理。
上面輸出的原因是由于每次調(diào)用的invokers的identityHashCode發(fā)生了變化：
我們看一下三次調(diào)用invokers的情況：
經(jīng)過(guò)debug我們可以看出因?yàn)槊看握{(diào)用的invokers地址值不是同一個(gè)，所以System.identityHashCode(invokers)方法返回的值都不一樣。
接下來(lái)的問(wèn)題就是為什么每次調(diào)用的invokers地址值都不一樣呢？
經(jīng)過(guò)Debug之后，可以找到這個(gè)地方：
org.apache.dubbo.rpc.cluster.RouterChain#route
問(wèn)題就出在這個(gè)TagRouter中：
org.apache.dubbo.rpc.cluster.router.tag.TagRouter#filterInvoker
所以，在TagRouter中的stream操作，改變了invokers，導(dǎo)致每次調(diào)用時(shí)其
System.identityHashCode(invokers)返回的值不一樣。所以每次調(diào)用都會(huì)進(jìn)行哈希環(huán)的映射操作，在服務(wù)節(jié)點(diǎn)多，虛擬節(jié)點(diǎn)多的情況下會(huì)有一定的性能問(wèn)題。
到這一步，問(wèn)題又發(fā)生了變化。這個(gè)TagRouter怎么來(lái)的呢？
如果了解Dubbo 2.7.x版本新特性的朋友可能知道，標(biāo)簽路由是Dubbo2.7引入的新功能。
通過(guò)加載下面的配置加載了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的最后一個(gè)版本)和Dubbo 2.7.0版本該文件的對(duì)比:
可以看到確實(shí)是在 Dubbo 2.7.0 之后引入了 TagRouter。
至此，Dubbo 2.7.0 版本之后，一致性哈希負(fù)載均衡算法的 Bug 的來(lái)龍去脈也介紹清楚了。
解決方案是什么呢？特別簡(jiǎn)單，把獲取 identityHashCode 的方法從 System.identityHashCode(invokers) 修改為 invokers.hashCode() 即可。
此方案是我提的 issue 里面的評(píng)論，這里 System.identityHashCode 和 hashCode 之間的聯(lián)系和區(qū)別就不進(jìn)行展開(kāi)講述了，不清楚的大家可以自行了解一下。
（我的另外一篇文章：夠強(qiáng)！一行代碼就修復(fù)了我提的Dubbo的Bug。）
改完之后，我們?cè)倏纯催\(yùn)行效果：
可以看到第二次調(diào)用的時(shí)候并沒(méi)有進(jìn)行哈希環(huán)的映射操作，而是直接取到了值，進(jìn)行調(diào)用。
加入節(jié)點(diǎn)，畫(huà)圖分析
最后，我再分析一種情況。在A、B、C三個(gè)服務(wù)器(20881、20882、20883端口)都在正常運(yùn)行，哈希映射已經(jīng)完成的情況下，我們?cè)賳?dòng)一個(gè)D節(jié)點(diǎn)（20884端口），這時(shí)的日志輸出和對(duì)應(yīng)的哈希環(huán)變化情況如下:
根據(jù)日志作圖如下：
根據(jù)輸出日志和上圖再加上源碼，你再細(xì)細(xì)回味一下。我個(gè)人覺(jué)得還是講的非常詳細(xì)了。
一致性哈希的應(yīng)用場(chǎng)景
當(dāng)大家談到一致性哈希算法的時(shí)候，首先的第一印象應(yīng)該是在緩存場(chǎng)景下的使用，因?yàn)樵谝粋€(gè)優(yōu)秀的哈希算法加持下，其上下線(xiàn)節(jié)點(diǎn)對(duì)整體數(shù)據(jù)的影響(遷移)都是比較友好的。
但是想一下為什么 Dubbo 在負(fù)載均衡策略里面提供了基于一致性哈希的負(fù)載均衡策略？它的實(shí)際使用場(chǎng)景是什么？
我最開(kāi)始也想不明白。我想的是在 Dubbo 的場(chǎng)景下，假設(shè)需求是想要一個(gè)用戶(hù)的請(qǐng)求一直讓一臺(tái)服務(wù)器處理，那我們可以采用一致性哈希負(fù)載均衡策略，把用戶(hù)號(hào)進(jìn)行哈希計(jì)算，可以實(shí)現(xiàn)這樣的需求。但是這樣的需求未免有點(diǎn)太牽強(qiáng)了，適用場(chǎng)景略小。
直到有天晚上，我睡覺(jué)之前，電光火石之間突然想到了一個(gè)稍微適用的場(chǎng)景了。
如果需求是需要保證某一類(lèi)請(qǐng)求必須順序處理呢？
如果你用其他負(fù)載均衡策略，請(qǐng)求分發(fā)到了不同的機(jī)器上去，就很難保證請(qǐng)求的順序處理了。比如A，B請(qǐng)求要求順序處理，現(xiàn)在A請(qǐng)求先發(fā)送，被負(fù)載到了A服務(wù)器上，B請(qǐng)求后發(fā)送，被負(fù)載到了B服務(wù)器上。而B(niǎo)服務(wù)器由于性能好或者當(dāng)前沒(méi)有其他請(qǐng)求或者其他原因極有可能在A服務(wù)器還在處理A請(qǐng)求之前就把B請(qǐng)求處理完成了。這樣不符合我們的要求。
這時(shí)，一致性哈希負(fù)載均衡策略就上場(chǎng)了，它幫我們保證了某一類(lèi)請(qǐng)求都發(fā)送到固定的機(jī)器上去執(zhí)行。比如把同一個(gè)用戶(hù)的請(qǐng)求發(fā)送到同一臺(tái)機(jī)器上去執(zhí)行，就意味著把某一類(lèi)請(qǐng)求發(fā)送到同一臺(tái)機(jī)器上去執(zhí)行。所以我們只需要在該機(jī)器上運(yùn)行的程序中保證順序執(zhí)行就行了，比如你加一個(gè)隊(duì)列。
一致性哈希算法+隊(duì)列，可以實(shí)現(xiàn)順序處理的需求。
好了，一致性哈希負(fù)載均衡算法就寫(xiě)到這里。
原文鏈接：
https://juejin.im/post/5ed39adef265da76dc1bb817
