負(fù)載均衡策略

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

1.RandomLoadBalance：

隨機(jī)負(fù)載均衡算法，Dubbo默認(rèn)的負(fù)載均衡策略。

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // 總個(gè)數(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; // 累計(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)重大于0則按總權(quán)重?cái)?shù)隨機(jī)
            int offset = random.nextInt(totalWeight);
            // 并確定隨機(jī)值落在哪個(gè)片斷上
            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則均等隨機(jī)
        return invokers.get(random.nextInt(length));
    }

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

2.RoundRobinLoadBalance：

輪詢負(fù)載均衡算法，按公約后的權(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(); // 總個(gè)數(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); // 累計(jì)最大權(quán)重
            minWeight = Math.min(minWeight, weight); // 累計(jì)最小權(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)重大于當(dāng)前權(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)，新的請(qǐng)求默認(rèn)均負(fù)載到一個(gè)節(jié)點(diǎn)上。后續(xù)分析主要是針對(duì)同一個(gè)服務(wù)的同一個(gè)方法。我們現(xiàn)在假設(shè)集群有四個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)的權(quán)重為{A:1,B:3,C:5,D:7｝，分別將權(quán)重套入到代碼中進(jìn)行分析，此時(shí)存在一個(gè)基礎(chǔ)權(quán)重集合，每次請(qǐng)求的時(shí)候?qū)⒋笥诋?dāng)前權(quán)重基數(shù)的提供者放入到基礎(chǔ)權(quán)重集合中，然后從基礎(chǔ)權(quán)重集合中按照輪詢比率負(fù)載到實(shí)際的服務(wù)提供者上:

對(duì)于第一個(gè)請(qǐng)求， 此時(shí)基礎(chǔ)集合中有{A，B，C，D｝四個(gè)節(jié)點(diǎn)，此時(shí)按照實(shí)際的輪詢比率，獲取第invokers.get(0%4)個(gè)節(jié)點(diǎn)，即獲取節(jié)點(diǎn)A負(fù)載請(qǐng)求。

對(duì)于第二個(gè)請(qǐng)求，此時(shí)基礎(chǔ)集合中只包含{B，C，D｝三個(gè)節(jié)點(diǎn)，將獲取第invokers.get(1%3)個(gè)節(jié)點(diǎn)，即獲取節(jié)點(diǎn)C負(fù)載請(qǐng)求。

對(duì)于第三個(gè)請(qǐng)求，此時(shí)基礎(chǔ)集合中只包含{B，C，D｝三個(gè)節(jié)點(diǎn)，將獲取第invokers.get(2%3)個(gè)節(jié)點(diǎn)，即獲取節(jié)點(diǎn)D負(fù)載請(qǐng)求。

......

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

3.LeastActiveLoadBalance：

最少活躍數(shù)負(fù)載均衡算法，對(duì)于同一個(gè)服務(wù)的同一個(gè)方法，會(huì)將請(qǐng)求負(fù)載到該請(qǐng)求活躍數(shù)最少的節(jié)點(diǎn)上，如果節(jié)點(diǎn)上活躍數(shù)相同，則隨機(jī)負(fù)載。

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

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

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

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

4.ConsistentHashLoadBalance:

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

當(dāng)某一臺(tái)提供者掛時(shí)，原本發(fā)往該提供者的請(qǐng)求，基于虛擬節(jié)點(diǎn)，平攤到其它提供者，不會(huì)引起劇烈變動(dòng)。

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ù)中，每個(gè)實(shí)際的提供者均有160個(gè)(默認(rèn)值，可調(diào)整)虛擬節(jié)點(diǎn)，每個(gè)提供者對(duì)應(yīng)的虛擬節(jié)點(diǎn)將平均散列到哈希環(huán)上，當(dāng)有請(qǐng)求時(shí)，先計(jì)算該請(qǐng)求參數(shù)對(duì)應(yīng)的哈希值，然后順時(shí)針尋找最近的虛擬節(jié)點(diǎn)，得到實(shí)際的提供者節(jié)點(diǎn)。

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