負載均衡策略

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

1.RandomLoadBalance：

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

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 總個數
        int totalWeight = 0; // 總權重
        boolean sameWeight = true; // 權重是否都一樣
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            totalWeight += weight; // 累計總權重
            if (sameWeight && i > 0
                    && weight != getWeight(invokers.get(i - 1), invocation)) {
                sameWeight = false; // 計算所有權重是否一樣
            }
        }
        if (totalWeight > 0 && ! sameWeight) {
            // 如果權重不相同且權重大于0則按總權重數隨機
            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);
                }
            }
        }
        // 如果權重相同或權重為0則均等隨機
        return invokers.get(random.nextInt(length));
    }

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

2.RoundRobinLoadBalance：

輪詢負載均衡算法，按公約后的權重設置輪循比率。

    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(); // 總個數
        int maxWeight = 0; // 最大權重
        int minWeight = Integer.MAX_VALUE; // 最小權重
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            maxWeight = Math.max(maxWeight, weight); // 累計最大權重
            minWeight = Math.min(minWeight, weight); // 累計最小權重
        }
        if (maxWeight > 0 && minWeight < maxWeight) { // 權重不一樣
            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) { // 篩選權重大于當前權重基數的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);
    }

分析算法我們能夠發現，新的請求默認均負載到一個節點上。后續分析主要是針對同一個服務的同一個方法。我們現在假設集群有四個節點分別對應的權重為{A:1,B:3,C:5,D:7｝，分別將權重套入到代碼中進行分析，此時存在一個基礎權重集合，每次請求的時候將大于當前權重基數的提供者放入到基礎權重集合中，然后從基礎權重集合中按照輪詢比率負載到實際的服務提供者上:

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

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

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

......

依次類推，能夠發現，這種模式下，在權重設置不合理的情況下，會導致某些節點無法負載請求，另外，如果有些機器性能比較低，會存在請求阻塞的情況。

3.LeastActiveLoadBalance：

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

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

思路主要是，獲取最小的活躍數，把活躍數等于最小活躍數的調用者維護成一個數組

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

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

4.ConsistentHashLoadBalance:

一致性Hash，相同參數的請求總是發到同一提供者。

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

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;
        }
    }
}

構造函數中，每個實際的提供者均有160個(默認值，可調整)虛擬節點，每個提供者對應的虛擬節點將平均散列到哈希環上，當有請求時，先計算該請求參數對應的哈希值，然后順時針尋找最近的虛擬節點，得到實際的提供者節點。

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