負載均衡策略

Dubbo目前主要提供下列四種負載均衡算法：

1.RandomLoadBalance：

隨機負載均衡算法，Dubbo默認的負載均衡策略。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 總個數(shù)
        int totalWeight = 0; // 總權(quán)重
        boolean sameWeight = true; // 權(quán)重是否都一樣
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            totalWeight += weight; // 累計總權(quán)重
            if (sameWeight && i > 0
                    && weight != getWeight(invokers.get(i - 1), invocation)) {
                sameWeight = false; // 計算所有權(quán)重是否一樣
            }
        }
        if (totalWeight > 0 && ! sameWeight) {
            // 如果權(quán)重不相同且權(quán)重大于0則按總權(quán)重數(shù)隨機
            int offset = random.nextInt(totalWeight);
            // 并確定隨機值落在哪個片斷上
            for (int i = 0; i < length; i++) {
                offset -= getWeight(invokers.get(i), invocation);
                if (offset < 0) {
                    return invokers.get(i);
                }
            }
        }
        // 如果權(quán)重相同或權(quán)重為0則均等隨機
        return invokers.get(random.nextInt(length));
    }

我們現(xiàn)在假設(shè)集群有四個節(jié)點分別對應(yīng)的權(quán)重為{A:1,B:2,C:3,D:4｝，分別將權(quán)重套入到代碼中進行分析，該隨機算法按總權(quán)重進行加權(quán)隨機，A節(jié)點負載請求的概率為1/(1+2+3+4)，依次類推，B，C，D負載的請求概率分別是20%，30%，40%。在這種方式下，用戶可以根據(jù)機器的實際性能動態(tài)調(diào)整權(quán)重比率，如果發(fā)現(xiàn)機器D負載過大，請求堆積過多，通過調(diào)整權(quán)重可以緩解機器D處理請求的壓力。

2.RoundRobinLoadBalance：

輪詢負載均衡算法，按公約后的權(quán)重設(shè)置輪循比率。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        int length = invokers.size(); // 總個數(shù)
        int maxWeight = 0; // 最大權(quán)重
        int minWeight = Integer.MAX_VALUE; // 最小權(quán)重
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            maxWeight = Math.max(maxWeight, weight); // 累計最大權(quán)重
            minWeight = Math.min(minWeight, weight); // 累計最小權(quán)重
        }
        if (maxWeight > 0 && minWeight < maxWeight) { // 權(quán)重不一樣
            AtomicPositiveInteger weightSequence = weightSequences.get(key);
            if (weightSequence == null) {
                weightSequences.putIfAbsent(key, new AtomicPositiveInteger());
                weightSequence = weightSequences.get(key);
            }
            int currentWeight = weightSequence.getAndIncrement() % maxWeight;
            List<Invoker<T>> weightInvokers = new ArrayList<Invoker<T>>();
            for (Invoker<T> invoker : invokers) { // 篩選權(quán)重大于當前權(quán)重基數(shù)的Invoker
                if (getWeight(invoker, invocation) > currentWeight) {
                    weightInvokers.add(invoker);
                }
            }
            int weightLength = weightInvokers.size();
            if (weightLength == 1) {
                return weightInvokers.get(0);
            } else if (weightLength > 1) {
                invokers = weightInvokers;
                length = invokers.size();
            }
        }
        AtomicPositiveInteger sequence = sequences.get(key);
        if (sequence == null) {
            sequences.putIfAbsent(key, new AtomicPositiveInteger());
            sequence = sequences.get(key);
        }
        // 取模輪循
        return invokers.get(sequence.getAndIncrement() % length);
    }

分析算法我們能夠發(fā)現(xiàn)，新的請求默認均負載到一個節(jié)點上。后續(xù)分析主要是針對同一個服務(wù)的同一個方法。我們現(xiàn)在假設(shè)集群有四個節(jié)點分別對應(yīng)的權(quán)重為{A:1,B:3,C:5,D:7｝，分別將權(quán)重套入到代碼中進行分析，此時存在一個基礎(chǔ)權(quán)重集合，每次請求的時候?qū)⒋笥诋斍皺?quán)重基數(shù)的提供者放入到基礎(chǔ)權(quán)重集合中，然后從基礎(chǔ)權(quán)重集合中按照輪詢比率負載到實際的服務(wù)提供者上:

對于第一個請求， 此時基礎(chǔ)集合中有{A，B，C，D｝四個節(jié)點，此時按照實際的輪詢比率，獲取第invokers.get(0%4)個節(jié)點，即獲取節(jié)點A負載請求。

對于第二個請求，此時基礎(chǔ)集合中只包含{B，C，D｝三個節(jié)點，將獲取第invokers.get(1%3)個節(jié)點，即獲取節(jié)點C負載請求。

對于第三個請求，此時基礎(chǔ)集合中只包含{B，C，D｝三個節(jié)點，將獲取第invokers.get(2%3)個節(jié)點，即獲取節(jié)點D負載請求。

......

依次類推，能夠發(fā)現(xiàn)，這種模式下，在權(quán)重設(shè)置不合理的情況下，會導(dǎo)致某些節(jié)點無法負載請求，另外，如果有些機器性能比較低，會存在請求阻塞的情況。

3.LeastActiveLoadBalance：

最少活躍數(shù)負載均衡算法，對于同一個服務(wù)的同一個方法，會將請求負載到該請求活躍數(shù)最少的節(jié)點上，如果節(jié)點上活躍數(shù)相同，則隨機負載。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 總個數(shù)
        int leastActive = -1; // 最小的活躍數(shù)
        int leastCount = 0; // 相同最小活躍數(shù)的個數(shù)
        int[] leastIndexs = new int[length]; // 相同最小活躍數(shù)的下標
        int totalWeight = 0; // 總權(quán)重
        int firstWeight = 0; // 第一個權(quán)重，用于于計算是否相同
        boolean sameWeight = true; // 是否所有權(quán)重相同
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // 活躍數(shù)
            int weight = 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ù)
                leastCount = 1; // 重新統(tǒng)計相同最小活躍數(shù)的個數(shù)
                leastIndexs[0] = i; // 重新記錄最小活躍數(shù)下標
                totalWeight = weight; // 重新累計總權(quán)重
                firstWeight = weight; // 記錄第一個權(quán)重
                sameWeight = true; // 還原權(quán)重相同標識
            } else if (active == leastActive) { // 累計相同最小的活躍數(shù)
                leastIndexs[leastCount ++] = i; // 累計相同最小活躍數(shù)下標
                totalWeight += weight; // 累計總權(quán)重
                // 判斷所有權(quán)重是否一樣
                if (sameWeight && i > 0 
                        && weight != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // assert(leastCount > 0)
        if (leastCount == 1) {
            // 如果只有一個最小則直接返回
            return invokers.get(leastIndexs[0]);
        }
        if (! sameWeight && totalWeight > 0) {
            // 如果權(quán)重不相同且權(quán)重大于0則按總權(quán)重數(shù)隨機
            int offsetWeight = random.nextInt(totalWeight);
            // 并確定隨機值落在哪個片斷上
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
                if (offsetWeight <= 0)
                    return invokers.get(leastIndex);
            }
        }
        // 如果權(quán)重相同或權(quán)重為0則均等隨機
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }

思路主要是，獲取最小的活躍數(shù)，把活躍數(shù)等于最小活躍數(shù)的調(diào)用者維護成一個數(shù)組

如果權(quán)重一致隨機取出，如果不同則跟隨機負載均衡一致，累加權(quán)重，然后隨機取出。

即一共維護了兩個數(shù)組，假設(shè)最小活躍數(shù)數(shù)組為{A:2，B:2，C:3，D:4｝，權(quán)重數(shù)組為{A:2，B:3，C:4，D:5｝，那么最終將A節(jié)點負載的概率為40%，B節(jié)點負載的概率為60%

4.ConsistentHashLoadBalance:

一致性Hash，相同參數(shù)的請求總是發(fā)到同一提供者。

當某一臺提供者掛時，原本發(fā)往該提供者的請求，基于虛擬節(jié)點，平攤到其它提供者，不會引起劇烈變動。

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    private static final class ConsistentHashSelector<T> {
        public ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            this.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.getMethodParameter(methodName, "hash.arguments", "0"));
            argumentIndex = new int[index.length];
            for (int i = 0; i < index.length; i ++) {
                argumentIndex[i] = Integer.parseInt(index[i]);
            }
            for (Invoker<T> invoker : invokers) {
                for (int i = 0; i < replicaNumber / 4; i++) {
                    byte[] digest = md5(invoker.getUrl().toFullString() + i);
                    for (int h = 0; h < 4; h++) {
                        long m = hash(digest, h);
                        virtualInvokers.put(m, invoker);
                    }
                }
            }
        }
        public Invoker<T> select(Invocation invocation) {
            String key = toKey(invocation.getArguments());
            byte[] digest = md5(key);
            Invoker<T> invoker = sekectForKey(hash(digest, 0));
            return invoker;
        }
    }
}

構(gòu)造函數(shù)中，每個實際的提供者均有160個(默認值，可調(diào)整)虛擬節(jié)點，每個提供者對應(yīng)的虛擬節(jié)點將平均散列到哈希環(huán)上，當有請求時，先計算該請求參數(shù)對應(yīng)的哈希值，然后順時針尋找最近的虛擬節(jié)點，得到實際的提供者節(jié)點。

以上就是動力節(jié)點小編介紹的"Dubbo負載均衡算法實現(xiàn)"，希望對大家有幫助，想了解更多可查看Dubbo教程。動力節(jié)點在線學(xué)習(xí)教程，針對沒有任何Java基礎(chǔ)的讀者學(xué)習(xí),讓你從入門到精通,主要介紹了一些Java基礎(chǔ)的核心知識，讓同學(xué)們更好更方便的學(xué)習(xí)和了解Java編程，感興趣的同學(xué)可以關(guān)注一下。