Dubbo負(fù)載均衡算法

1、實(shí)用標(biāo)準(zhǔn)文案負(fù)載均衡算法在集群負(fù)載均衡時(shí)，Dubbo 提供了4 種均衡策略，如：Random LoadBalance( 隨機(jī)均衡算法 ) 、； RoundRobin LoadBalance( 權(quán)重輪循均衡算法) 、 LeastActionLoadBalance( 最少活躍調(diào)用數(shù)均衡算法) 、 ConsistentHash LoadBalance(一致性Hash 均衡算法 ) 。缺省時(shí)為Random隨機(jī)調(diào)用。這四種算法的原理簡(jiǎn)要介紹如下：1、 RoundRobin LoadBalanceRound-Robin既是輪詢算法，是按照公約后的權(quán)重設(shè)置輪詢比率，即權(quán)重輪詢算法(WeightedRound

2、-Robin)，它是基于輪詢算法改進(jìn)而來(lái)的。這里之所以寫RoundRobin 是為了跟 Dubbo 中的內(nèi)容保持一致。輪詢調(diào)度算法的原理是：每一次把來(lái)自用戶的請(qǐng)求輪流分配給內(nèi)部中的服務(wù)器。如：從1 開始，一直到N( 其中， N 是內(nèi)部服務(wù)器的總個(gè)數(shù)) ，然后重新開始循環(huán)。該算法的優(yōu)點(diǎn)：其簡(jiǎn)潔性，它無(wú)需記錄當(dāng)前所有連接的狀態(tài)，所以它是一種無(wú)狀態(tài)調(diào)度。該算法的缺點(diǎn)：輪詢調(diào)度算法假設(shè)所有服務(wù)器的處理性能都相同，不關(guān)心每臺(tái)服務(wù)器的當(dāng)前連接數(shù)和響應(yīng)速度。當(dāng)請(qǐng)求服務(wù)間隔時(shí)間變化比較大時(shí)，輪詢調(diào)度算法容易導(dǎo)致服務(wù)器間的負(fù)載不平衡。所以此種均衡算法適合于服務(wù)器組中的所有服務(wù)器都有相同的軟硬件配置并且平均服務(wù)請(qǐng)

3、求相對(duì)均衡的情況。 但是， 在實(shí)際情況中，可能并不是這種情況。 由于每臺(tái)服務(wù)器的配置、安裝的業(yè)務(wù)應(yīng)用等不同， 其處理能力會(huì)不一樣。 所以，我們根據(jù)服務(wù)器的不同處理能力，給每個(gè)服務(wù)器分配不同的權(quán)值，使其能夠接受相應(yīng)權(quán)值數(shù)的服務(wù)請(qǐng)求。權(quán)重輪詢調(diào)度算法流程假設(shè)有一組服務(wù)器S = S0, S1, Sn-1， W(Si) 表示服務(wù)器Si 的權(quán)值，一個(gè)指示變量 i 表示上一次選擇的服務(wù)器，指示變量cw 表示當(dāng)前調(diào)度的權(quán)值，max(S) 表示集合S中所有服務(wù)器的最大權(quán)值， gcd(S) 表示集合 S 中所有服務(wù)器權(quán)值的最大公約數(shù)。 變量 i 初始化為-1 ， cw 初始化為零。其算法如下：while (tr

4、ue) i = (i + 1) mod n;if (i = 0) cw = cw - gcd(S);if (cw <= 0) cw = max(S);if (cw = 0)return NULL;if (W(Si) >= cw)return Si;精彩文檔實(shí)用標(biāo)準(zhǔn)文案這種算法的邏輯實(shí)現(xiàn)如圖2 所示，圖中我們假定四臺(tái)服務(wù)器的處理能力為3:1:1:1。圖 1 權(quán)重輪詢調(diào)度實(shí)現(xiàn)邏輯圖示由于權(quán)重輪詢調(diào)度算法考慮到了不同服務(wù)器的處理能力， 所以這種均衡算法能確保高性能的服務(wù)器得到更多的使用率， 避免低性能的服務(wù)器負(fù)載過(guò)重。 所以，在實(shí)際應(yīng)用中比較常見。2、 ConsistentHash Lo

5、adBalance一致性 Hash，相同參數(shù)的請(qǐng)求總是發(fā)到同一個(gè)提供者。一：一致性Hash 算法可以解決服務(wù)提供者的增加、移除及掛掉時(shí)的情況，能盡可能小的改變已存在key映射關(guān)系，盡可能的滿足單調(diào)性的要求。二：一致性Hash 通過(guò)構(gòu)建虛擬節(jié)點(diǎn)，能盡可能避免分配失衡，具有很好的平衡性。一致性 Hash 下面就來(lái)按照5個(gè)步驟簡(jiǎn)單講講consistent hash算法的基本原理。因?yàn)橐韵沦Y料來(lái)自于互聯(lián)網(wǎng)， 現(xiàn)說(shuō)明幾點(diǎn)： 一、下面例子中的對(duì)象就相當(dāng)于 Client 發(fā)的請(qǐng)求， cache 相當(dāng)于服務(wù)提供者。環(huán)形 hash 空間考慮通常的hash 算法都是將value映射到一個(gè)32為的 key值，也即是

6、0232-1次方的數(shù)值空間； 我們可以將這個(gè)空間想象成一個(gè)首(0) 尾 (232-1)相接的圓環(huán)，如下面圖2所示的那樣。精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖 2環(huán)形 hash空間把對(duì)象映射到 hash 空間接下來(lái)考慮4 個(gè)對(duì)象 object1object4，通過(guò) hash函數(shù)計(jì)算出的hash值 key在環(huán)上的分布如圖3 所示。hash(object1) = key1;hash(object4) = key4;圖 3 4 個(gè)對(duì)象的 key 值分布把 cache 映射到 hash 空間Consistent hashing的基本思想就是將對(duì)象和cache都映射到同一個(gè)hash數(shù)值空間中，并且使用相同的hash 算

7、法。假設(shè)當(dāng)前有A,B 和 C 共 3 臺(tái) cache ，那么其映射結(jié)果將如圖4所示，他們?cè)趆ash空間中，以對(duì)應(yīng)的hash值排列。hash(cache A) = key A;hash(cache C) = key C;精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖 4 cache 和對(duì)象的 key 值分布說(shuō)到這里，順便提一下 cache 的 hash 計(jì)算，一般的方法可以使用 cache 機(jī)器的 IP 地址或者機(jī)器名作為 hash 輸入。把對(duì)象映射到 cache現(xiàn)在 cache和對(duì)象都已經(jīng)通過(guò)同一個(gè)hash算法映射到hash數(shù)值空間中了，接下來(lái)要考慮的就是如何將對(duì)象映射到cache 上面了。在這個(gè)環(huán)形空間中， 如果沿

8、著順時(shí)針方向從對(duì)象的 key 值出發(fā)，直到遇見一個(gè) cache ，那么就將該對(duì)象存儲(chǔ)在這個(gè) cache 上，因?yàn)閷?duì)象和 cache 的 hash 值是固定的， 因此這個(gè)cache 必然是唯一和確定的。這樣不就找到了對(duì)象和cache的映射方法了嗎！依然繼續(xù)上面的例子（參見圖 4 ），那么根據(jù)上面的方法，對(duì)象 object1 將被存儲(chǔ)到 cache A 上； object2 和 object3 對(duì)應(yīng)到 cache C ； object4 對(duì)應(yīng)到 cache B ；考察 cache 的變動(dòng)前面講過(guò)， 一致性 Hash 算法可以解決服務(wù)提供者的增加、移除及掛掉時(shí)的情況，能盡可能 小的改變已存在 key

9、 映射關(guān)系，盡可能的滿足單調(diào)性的要求。移除cache考慮假設(shè)cache B掛掉了，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅是那些沿cache B 逆時(shí)針遍歷直到下一個(gè)cache （ cache C ）之間的對(duì)象， 也即是本來(lái)映射到cacheB 上的那些對(duì)象。因此這里僅需要變動(dòng)對(duì)象object4，將其重新映射到cache C上即可；參見圖5。精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖 5 Cache B被移除后的cache映射添加cache再考慮添加一臺(tái)新的cache D 的情況，假設(shè)在這個(gè)環(huán)形hash空間中， cache D 被映射在對(duì)象object2和 object3之間。這時(shí)受影響的將僅是那些沿cache D

10、逆時(shí)針遍歷直到下一個(gè)cache（ cache B）之間的對(duì)象（它們是也本來(lái)映射到cache C上對(duì)象的一部分），將這些對(duì)象重新映射到cache D上即可。因此這里僅需要變動(dòng)對(duì)象object2，將其重新映射到cache D上；參見圖6。圖 6添加 cache D后的映射關(guān)系虛擬節(jié)點(diǎn)考慮 Hash 算法的另一個(gè)指標(biāo)是平衡性(Balance)，定義如下：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。hash 算法并不是保證絕對(duì)的平衡，如果 cache較少的話， 對(duì)象并不能被均勻的映射到cache 上，比如在上面的例子中，僅部署 cache A 和 cach

11、e C 的情況下， 在 4個(gè)對(duì)象中，cache A僅存儲(chǔ)了object1，而 cache C則存儲(chǔ)了object2、 object3和 object4；分布是很不均衡的。為了解決這種情況，consistenthashing引入了“虛擬節(jié)點(diǎn)”的概念，它可以如下定精彩文檔實(shí)用標(biāo)準(zhǔn)文案義：“虛擬節(jié)點(diǎn)” （ virtual node）是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品（ replica），一實(shí)際個(gè)節(jié)點(diǎn)對(duì)應(yīng)了若干個(gè) “虛擬節(jié)點(diǎn)” ，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為 “復(fù)制個(gè)數(shù)” ，虛擬節(jié)點(diǎn)”“在 hash空間中以 hash 值排列。仍以僅部署 cache A 和 cacheC 的情況為例，在圖 5中我們已經(jīng)看到，

12、cache分布并不均勻。 現(xiàn)在我們引入虛擬節(jié)點(diǎn)，并設(shè)置“復(fù)制個(gè)數(shù)” 為 2，這就意味著一共會(huì)存在4 個(gè)“虛擬節(jié)點(diǎn)” ， cacheA1, cache A2 代表了 cache A ； cacheC1, cache C2 代表了 cacheC ；假設(shè)一種比較理想的情況，參見圖7。圖 7引入“虛擬節(jié)點(diǎn)”后的映射關(guān)系此時(shí)，對(duì)象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為：objec1->cache A2； objec2->cache A1； objec3->cache C1； objec4->cache C2；因此對(duì)象object1和 object2都被映射到了cache A上，而 objec

13、t3和 object4映射到了cache C上；平衡性有了很大提高。引入“虛擬節(jié)點(diǎn)”后，映射關(guān)系就從對(duì)象 ->節(jié)點(diǎn) 轉(zhuǎn)換到了對(duì)象 ->虛擬節(jié)點(diǎn) 。查詢物體所在cache時(shí)的映射關(guān)系如圖8所示。圖 8 查詢對(duì)象所在 cache“虛擬節(jié)點(diǎn)” 的 hash計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的IP地址加數(shù)字后綴的方式。例如假設(shè)精彩文檔實(shí)用標(biāo)準(zhǔn)文案cache A的 IP地址為 41。引入“虛擬節(jié)點(diǎn)”前，計(jì)算cache A的 hash值：Hash( “ 41” );引入“虛擬節(jié)點(diǎn)”后，計(jì)算“虛擬節(jié)”點(diǎn)cache A1和 cache A2的 hash值：Hash

14、( “ 41#1”); / cache A1Hash( “ 41#2”); / cache A23、 Random LoadBalance 與 LeastAction LoadBalanceRandom LoadBalance 與 LeastAction LoadBalance算法比較簡(jiǎn)單，可以參照Dubbo文檔中的給的描述及后面代碼附錄。Dubbo 文檔截圖如下圖9 所示：圖 9 負(fù)載均衡算法4、附錄1、RandomLoadBalance算法publicclassRandomLoadBalanceextendsAbstractLoadBalan

15、ce publicstaticfinalStringNAME="random" ;privatefinalRandom random =new Random();精彩文檔實(shí)用標(biāo)準(zhǔn)文案protected<T>Invoker<T>doSelect(List<Invoker<T>>invokers,URL url,Invocation invocation) intlength = invokers.size();/總個(gè)數(shù)inttotalWeight = 0;/總權(quán)重boolean sameWeight =true ;/權(quán)重是否都一

16、樣for( inti = 0; i < length; i+) intweight = getWeight(invokers.get(i), invocation);totalWeight += weight;/累計(jì)總權(quán)重if(sameWeight && i > 0&& weight != getWeight(invokers.get(i - 1), invocation) sameWeight =false ;/計(jì)算所有權(quán)重是否一樣if(totalWeight > 0 && ! sameWeight) / 如果權(quán)重不相同且權(quán)重

17、大于0 則按總權(quán)重?cái)?shù)隨機(jī)intoffset =random.nextInt(totalWeight);/ 并確定隨機(jī)值落在哪個(gè)片斷上for( inti = 0; i < length; i+) offset -= getWeight(invokers.get(i), invocation);if(offset < 0) returninvokers.get(i);/如果權(quán)重相同或權(quán)重為0 則均等隨機(jī)returninvokers.get(random.nextInt(length);2、RoundRobinLoadBalance 算法publicclassRoundRobinLoad

18、BalanceextendsAbstractLoadBalance publicstaticfinalStringNAME="roundrobin"privatefinalConcurrentMap<String, AtomicPositiveInteger>sequences =newConcurrentHashMap<String, AtomicPositiveInteger>();privatefinalConcurrentMap<String, AtomicPositiveInteger>weightSequences= newC

19、oncurrentHashMap<String, AtomicPositiveInteger>();protected<T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocationinvocation) String key = invokers.get(0).getUrl().getServiceKey() +"."+invocation.getMethodName();intlength = invokers.size();/總個(gè)數(shù)i

20、ntmaxWeight = 0;/最大權(quán)重intminWeight = Integer.MAX_VALUE;/最小權(quán)重精彩文檔實(shí)用標(biāo)準(zhǔn)文案for( inti = 0; i < length; i+) intweight = getWeight(invokers.get(i), invocation);maxWeight = Math.max(maxWeight, weight);/累計(jì)最大權(quán)重minWeight = Math.min(minWeight, weight);/累計(jì)最小權(quán)重if(maxWeight > 0 && minWeight < maxWei

21、ght) /權(quán)重不一樣AtomicPositiveInteger weightSequence =weightSequences .get(key);if(weightSequence =null ) weightSequences .putIfAbsent(key,new AtomicPositiveInteger();weightSequence =weightSequences.get(key);intcurrentWeight = weightSequence.getAndIncrement() % maxWeight;List<Invoker<T>> weig

22、htInvokers =new ArrayList<Invoker<T>>();for(Invoker<T>invoker: invokers) /篩選權(quán)重大于當(dāng)前權(quán)重基數(shù)的Invokerif(getWeight(invoker, invocation) > currentWeight) weightInvokers.add(invoker);intweightLength = weightInvokers.size();if(weightLength = 1) returnweightInvokers.get(0);elseif(weightLeng

23、th > 1) invokers = weightInvokers;length = invokers.size();AtomicPositiveInteger sequence =sequences .get(key);if(sequence =null) sequences .putIfAbsent(key,new AtomicPositiveInteger();sequence =sequences .get(key);/ 取模輪循returninvokers.get(sequence.getAndIncrement() % length);3、LeastActionLoadBal

24、ance算法publicclassLeastActiveLoadBalanceextendsAbstractLoadBalance publicstaticfinalStringNAME="leastactive"privatefinalRandom random =new Random();protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) intlength = invokers.size(

25、);/總個(gè)數(shù)精彩文檔實(shí)用標(biāo)準(zhǔn)文案intleastActive = -1;/ 最小的活躍數(shù)intleastCount = 0;/相同最小活躍數(shù)的個(gè)數(shù)int leastIndexs =new int length;/ 相同最小活躍數(shù)的下標(biāo)inttotalWeight = 0;/總權(quán)重intfirstWeight = 0;/第一個(gè)權(quán)重，用于于計(jì)算是否相同booleansameWeight =true ;/是否所有權(quán)重相同for( inti = 0; i < length; i+) Invoker<T> invoker = invokers.get(i);intactive = Rp

26、cStatus.getStatus (invoker.getUrl(),invocation.getMethodName().getActive();/活躍數(shù)intweight =invoker.getUrl().getMethodParameter(invocation.getMethodName(),Constants.WEIGHT_KEY,Constants.DEFAULT_WEIGHT);/權(quán)重if(leastActive = -1 | active < leastActive) /發(fā)現(xiàn)更小的活躍數(shù)，重新開始leastActive = active;/記錄最小活躍數(shù)leastCo

27、unt = 1;/重新統(tǒng)計(jì)相同最小活躍數(shù)的個(gè)數(shù)leastIndexs0 = i;/重新記錄最小活躍數(shù)下標(biāo)totalWeight = weight;/重新累計(jì)總權(quán)重firstWeight = weight;/記錄第一個(gè)權(quán)重sameWeight =true ;/還原權(quán)重相同標(biāo)識(shí)elseif(active = leastActive) /累計(jì)相同最小的活躍數(shù)leastIndexsleastCount + = i;/累計(jì)相同最小活躍數(shù)下標(biāo)totalWeight += weight;/累計(jì)總權(quán)重/ 判斷所有權(quán)重是否一樣if(sameWeight && i > 0&&

28、 weight != firstWeight) sameWeight =false;/ assert(leastCount > 0)if(leastCount = 1) / 如果只有一個(gè)最小則直接返回returninvokers.get(leastIndexs0);if(! sameWeight && totalWeight > 0) / 如果權(quán)重不相同且權(quán)重大于0則按總權(quán)重?cái)?shù)隨機(jī)intoffsetWeight =random.nextInt(totalWeight);/ 并確定隨機(jī)值落在哪個(gè)片斷上for ( inti = 0; i < leastCount;

29、 i+) intleastIndex = leastIndexsi;offsetWeight -= getWeight(invokers.get(leastIndex), invocation);if(offsetWeight <= 0)精彩文檔實(shí)用標(biāo)準(zhǔn)文案returninvokers.get(leastIndex);/ 如果權(quán)重相同或權(quán)重為 0則均等隨機(jī)returninvokers.get(leastIndexsrandom.nextInt(leastCount);4、ConsistentHashLoadBalance算法publicclassConsistentHashLoadBal

30、anceextendsAbstractLoadBalance privatefinalConcurrentMap<String, ConsistentHashSelector<?>>selectors=newConcurrentHashMap<String, ConsistentHashSelector<?>>();SuppressWarnings ( "unchecked" )Overrideprotected <T> Invoker<T> doSelect(List<Invoker<T&

31、gt;> invokers, URL url, Invocation invocation) String key = invokers.get(0).getUrl().getServiceKey() +"."+invocation.getMethodName();intidentityHashCode = System.identityHashCode (invokers);ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>)selectors.get(key);if

32、(selector =null| selector.getIdentityHashCode() != identityHashCode)selectors.put(key,new ConsistentHashSelector<T>(invokers,invocation.getMethodName(), identityHashCode);selector = (ConsistentHashSelector<T>)selectors.get(key);returnselector.select(invocation);privatestaticfinalclassCon

33、sistentHashSelector<T> privatefinalTreeMap<Long, Invoker<T>>virtualInvokers;privatefinalintreplicaNumber;privatefinalintidentityHashCode;privatefinalint argumentIndex ;publicConsistentHashSelector(List<Invoker<T>> invokers, String methodName,intidentityHashCode) this .

34、virtualInvokers=new TreeMap<Long, Invoker<T>>();this . identityHashCode = System. identityHashCode (invokers); URL url = invokers.get(0).getUrl();this . replicaNumber= url.getMethodParameter(methodName,"hash.nodes",160);String index =Constants.COMMA_SPLIT_PATTERN.split(url.getM

35、ethodParameter(methodName,"hash.arguments","0" );精彩文檔實(shí)用標(biāo)準(zhǔn)文案argumentIndex=new int index.length;for ( inti = 0; i < index.length ; i +) argumentIndex i = Integer.parseInt (indexi);for (Invoker<T> invoker : invokers) for( inti = 0; i <replicaNumber/ 4; i+) byte digest =

36、md5(invoker.getUrl().toFullString() + i);for( inth = 0; h < 4; h+) long m = hash(digest, h);virtualInvokers.put(m, invoker);publicintgetIdentityHashCode() returnidentityHashCode;publicInvoker<T> select(Invocation invocation) String key = toKey(invocation.getArguments();byte digest = md5(key);Invoker<T> invoker = sekectForKey(hash(diges