開篇

這篇文章的目的是為了講解清楚dubbo負(fù)載均衡的底層實(shí)現(xiàn)機(jī)制，根據(jù)瀏覽的網(wǎng)上資料來(lái)看似乎隨著dubbo的版本更新有一些變化，不過(guò)大概分類就是那么多，感興趣的可以自行閱讀。

負(fù)載均衡類依賴圖

LoadBalance.jpg

RoundRobinLoadBalance

說(shuō)明

• RoundRobinLoadBalance基于權(quán)重的輪詢

• 如果所有provider的權(quán)重都是一致的，那么就變成輪詢的狀態(tài)，invokers.get(currentSequence % length)。

• 如果所有provider的權(quán)重并不完全一致，那么就計(jì)算權(quán)重和并通過(guò)currentSequence % weightSum生成隨機(jī)數(shù)。通過(guò)雙層for循環(huán)直至mod值為0后返回。內(nèi)層for負(fù)責(zé)每次都把所有的provider的權(quán)重減一，通過(guò)外層for循環(huán)控制，直到mod為0返回對(duì)應(yīng)的provider。

• 假設(shè)有服務(wù)器集合（服務(wù)器名：其權(quán)重值）：A(S0:1, S1:5, S2:5, S3:1, S4:3)，權(quán)重值不同，使用基于權(quán)重值的輪詢算法。計(jì)算權(quán)重值總和（15），初始化一個(gè)原子性整數(shù)的序列并構(gòu)建服務(wù)器與其權(quán)重值的映射集合，只要遍歷一次映射集合。若當(dāng)前所在的序列值為20，與15取模得5，開始遍歷映射集合， mod = 5。
  第一輪過(guò)后，服務(wù)器集合改變?yōu)锳(S0:0, S1:4, S2:4, S3:0, S4:2)，mod=0，
  第二輪過(guò)后，S1符合mod=0且S1的value=4>0的條件，所以會(huì)選擇 S1 服務(wù)器。

public class RoundRobinLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "roundrobin";

    private final ConcurrentMap<String, AtomicPositiveInteger> sequences = new ConcurrentHashMap<String, AtomicPositiveInteger>();

    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(); // Number of invokers
        int maxWeight = 0; // The maximum weight
        int minWeight = Integer.MAX_VALUE; // The minimum weight
        final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
        int weightSum = 0;
        // 遍歷invoker，記錄權(quán)重最大值和最小值；如果權(quán)重值大于0，將invoker及其權(quán)重值包裝類放入map集合，并累加權(quán)重值。
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight
            minWeight = Math.min(minWeight, weight); // Choose the minimum weight
            if (weight > 0) {
                invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
                weightSum += weight;
            }
        }

        // 每個(gè)key維持一個(gè)sequence對(duì)象
        AtomicPositiveInteger sequence = sequences.get(key);
        if (sequence == null) {
            sequences.putIfAbsent(key, new AtomicPositiveInteger());
            sequence = sequences.get(key);
        }

        // 基于每個(gè)sequence自增然后求余然后進(jìn)行選擇
        int currentSequence = sequence.getAndIncrement();
        if (maxWeight > 0 && minWeight < maxWeight) {
            int mod = currentSequence % weightSum;
            for (int i = 0; i < maxWeight; i++) {
                for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) {
                    final Invoker<T> k = each.getKey();
                    final IntegerWrapper v = each.getValue();
                    if (mod == 0 && v.getValue() > 0) {
                        return k;
                    }
                    if (v.getValue() > 0) {
                        v.decrement();
                        mod--;
                    }
                }
            }
        }
        // 權(quán)重一致就蛻化為輪詢操作
        return invokers.get(currentSequence % length);
    }
}

RandomLoadBalance

• RandomLoadBalance的實(shí)現(xiàn)邏輯分為權(quán)重相同和權(quán)重不同的情況。
• 權(quán)重相同的情況下通過(guò)random.nextInt(provider的個(gè)數(shù))隨機(jī)選取一個(gè)。
• 權(quán)重不同的情況下通過(guò)累加權(quán)重得到totalWeight，然后random.nextInt(totalWeight)獲取隨機(jī)數(shù)offset，基于offset開始遍歷所有provider的權(quán)重找到第一個(gè)讓offset的值為0的provider。
• 這種策略大概率能夠讓權(quán)重大的provider獲取更多機(jī)會(huì)同時(shí)兼顧了權(quán)重小的接口。

public class RandomLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "random";

    private final Random random = new Random();

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // Number of invokers
        int totalWeight = 0; // The sum of weights
        boolean sameWeight = true; // Every invoker has the same weight?
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            totalWeight += weight; // Sum
            if (sameWeight && i > 0
                    && weight != getWeight(invokers.get(i - 1), invocation)) {
                sameWeight = false;
            }
        }
        if (totalWeight > 0 && !sameWeight) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
            int offset = random.nextInt(totalWeight);
            // Return a invoker based on the random value.
            for (int i = 0; i < length; i++) {
                offset -= getWeight(invokers.get(i), invocation);
                if (offset < 0) {
                    return invokers.get(i);
                }
            }
        }
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        return invokers.get(random.nextInt(length));
    }
}

LeastActiveLoadBalance

• LeastActiveLoadBalance就是選擇活躍數(shù)最少的provider，活躍數(shù)指代的就是調(diào)用次數(shù)-響應(yīng)次數(shù)，活躍數(shù)越少說(shuō)明響應(yīng)越快。
• LeastActiveLoadBalance的配置某種意義上來(lái)說(shuō)選擇性能最優(yōu)的機(jī)器來(lái)提供更快的服務(wù)。
• LeastActiveLoadBalance的選擇leastActive的邏輯很簡(jiǎn)單，每次重啟或者遇到更小的Active數(shù)的時(shí)候重新開始計(jì)數(shù)，然后基于重新計(jì)數(shù)的基礎(chǔ)之上統(tǒng)計(jì)相同的leastActive進(jìn)行選擇。
• 如果leastActive只有一個(gè)就直接返回，如果有多個(gè)那么按照權(quán)重方式進(jìn)行返回，權(quán)重的方式就是計(jì)算總權(quán)重然后基于總權(quán)重生成隨機(jī)數(shù)，通過(guò)遍歷leastActive的provider找除第一個(gè)讓隨機(jī)數(shù)為0的provider。

public class LeastActiveLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "leastactive";

    private final Random random = new Random();

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        int length = invokers.size(); // Number of invokers
        int leastActive = -1; // The least active value of all invokers
        int leastCount = 0; // The number of invokers having the same least active value (leastActive)
        int[] leastIndexs = new int[length]; // The index of invokers having the same least active value (leastActive)
        int totalWeight = 0; // The sum of weights
        int firstWeight = 0; // Initial value, used for comparision
        boolean sameWeight = true; // Every invoker has the same weight value?
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // Active number
            int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT); // Weight
            if (leastActive == -1 || active < leastActive) { // Restart, when find a invoker having smaller least active value.
                leastActive = active; // Record the current least active value
                leastCount = 1; // Reset leastCount, count again based on current leastCount
                leastIndexs[0] = i; // Reset
                totalWeight = weight; // Reset
                firstWeight = weight; // Record the weight the first invoker
                sameWeight = true; // Reset, every invoker has the same weight value?
            } else if (active == leastActive) { // If current invoker's active value equals with leaseActive, then accumulating.
                leastIndexs[leastCount++] = i; // Record index number of this invoker
                totalWeight += weight; // Add this invoker's weight to totalWeight.
                // If every invoker has the same weight?
                if (sameWeight && i > 0
                        && weight != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // assert(leastCount > 0)
        if (leastCount == 1) {
            // If we got exactly one invoker having the least active value, return this invoker directly.
            return invokers.get(leastIndexs[0]);
        }
        if (!sameWeight && totalWeight > 0) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
            int offsetWeight = random.nextInt(totalWeight);
            // Return a invoker based on the random value.
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
                if (offsetWeight <= 0)
                    return invokers.get(leastIndex);
            }
        }
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }
}

最小活躍數(shù)統(tǒng)計(jì)

• 在ActiveLimitFilter的攔截器當(dāng)中，每次調(diào)用前RpcStatus.beginCount()增加活躍數(shù)，在返回結(jié)果后RpcStatus.endCount()減少活躍數(shù)。
• 如果系統(tǒng)響應(yīng)慢，那么對(duì)應(yīng)的活躍數(shù)就會(huì)多，活躍數(shù)說(shuō)明系統(tǒng)比較慢，那么就會(huì)少分配請(qǐng)求保持系統(tǒng)響應(yīng)。

public class ActiveLimitFilter implements Filter {

    public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
        URL url = invoker.getUrl();
        String methodName = invocation.getMethodName();
        int max = invoker.getUrl().getMethodParameter(methodName, Constants.ACTIVES_KEY, 0);
        RpcStatus count = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
        // 省略相關(guān)代碼
        try {
            long begin = System.currentTimeMillis();
            // 增加計(jì)數(shù)也就是增加活躍數(shù)
            RpcStatus.beginCount(url, methodName);
            try {
                Result result = invoker.invoke(invocation);
                // 減少計(jì)數(shù)也就是減少活躍數(shù)
                RpcStatus.endCount(url, methodName, System.currentTimeMillis() - begin, true);
                return result;
            } catch (RuntimeException t) {
                RpcStatus.endCount(url, methodName, System.currentTimeMillis() - begin, false);
                throw t;
            }
        } finally {
            if (max > 0) {
                synchronized (count) {
                    count.notify();
                }
            }
        }
    }
}




public class RpcStatus {

    public static void beginCount(URL url, String methodName) {
        beginCount(getStatus(url));
        beginCount(getStatus(url, methodName));
    }

    private static void beginCount(RpcStatus status) {
        status.active.incrementAndGet();
    }

    public static void endCount(URL url, String methodName, long elapsed, boolean succeeded) {
        endCount(getStatus(url), elapsed, succeeded);
        endCount(getStatus(url, methodName), elapsed, succeeded);
    }

    private static void endCount(RpcStatus status, long elapsed, boolean succeeded) {
        status.active.decrementAndGet();
        status.total.incrementAndGet();
        status.totalElapsed.addAndGet(elapsed);
        if (status.maxElapsed.get() < elapsed) {
            status.maxElapsed.set(elapsed);
        }
        if (succeeded) {
            if (status.succeededMaxElapsed.get() < elapsed) {
                status.succeededMaxElapsed.set(elapsed);
            }
        } else {
            status.failed.incrementAndGet();
            status.failedElapsed.addAndGet(elapsed);
            if (status.failedMaxElapsed.get() < elapsed) {
                status.failedMaxElapsed.set(elapsed);
            }
        }
    }
}

ConsistentHashLoadBalance

說(shuō)明：

• 一致性hash算法核心的關(guān)鍵點(diǎn)有兩個(gè)：一致性hashMap的構(gòu)建，一致性hashMap的select操作。

• 構(gòu)建過(guò)程：一致性hash的虛擬節(jié)點(diǎn)采用了TreeMap對(duì)象，針對(duì)每個(gè)provider根據(jù)url的address字段加虛擬節(jié)點(diǎn)個(gè)數(shù)/4的偏移量生成128的digest字段，針對(duì)128位的digest字段（16個(gè)字節(jié)）按照每4個(gè)字節(jié)進(jìn)行進(jìn)行計(jì)算生成4個(gè)虛擬節(jié)點(diǎn)放到TreeMap當(dāng)中。假設(shè)有160個(gè)虛擬節(jié)點(diǎn)，160/4=40個(gè)待處理虛擬節(jié)點(diǎn)，針對(duì)40個(gè)待處理虛擬節(jié)點(diǎn)中的每個(gè)節(jié)點(diǎn)生成16個(gè)字節(jié)的digest，16個(gè)字節(jié)中digest分為4份進(jìn)行保存，最終依然是160個(gè)虛擬節(jié)點(diǎn)。

• 查詢過(guò)程：查詢過(guò)程根據(jù)指定參數(shù)進(jìn)行md5+hash()計(jì)算hash值，找到比hash值小的treeMap然后選擇treeMap的根節(jié)點(diǎn)選擇provider，如果找不到比hash小的treeMap就選擇treeMap的最小根節(jié)點(diǎn)。

public class ConsistentHashLoadBalance extends AbstractLoadBalance {

    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<String, ConsistentHashSelector<?>>();

    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        if (selector == null || selector.identityHashCode != identityHashCode) {
            selectors.put(key, new ConsistentHashSelector<T>(invokers, invocation.getMethodName(), identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        return selector.select(invocation);
    }

    private static final class ConsistentHashSelector<T> {

        private final TreeMap<Long, Invoker<T>> virtualInvokers;

        private final int replicaNumber;

        private final int identityHashCode;

        private final int[] argumentIndex;

        ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
            this.identityHashCode = identityHashCode;
            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) {
                String address = invoker.getUrl().getAddress();
                for (int i = 0; i < replicaNumber / 4; i++) {
                    byte[] digest = md5(address + 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);
            return selectForKey(hash(digest, 0));
        }

        private String toKey(Object[] args) {
            StringBuilder buf = new StringBuilder();
            for (int i : argumentIndex) {
                if (i >= 0 && i < args.length) {
                    buf.append(args[i]);
                }
            }
            return buf.toString();
        }

        private Invoker<T> selectForKey(long hash) {
            Invoker<T> invoker;
            Long key = hash;
            if (!virtualInvokers.containsKey(key)) {
                SortedMap<Long, Invoker<T>> tailMap = virtualInvokers.tailMap(key);
                if (tailMap.isEmpty()) {
                    key = virtualInvokers.firstKey();
                } else {
                    key = tailMap.firstKey();
                }
            }
            invoker = virtualInvokers.get(key);
            return invoker;
        }

        private long hash(byte[] digest, int number) {
            return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                    | (digest[number * 4] & 0xFF))
                    & 0xFFFFFFFFL;
        }

        private byte[] md5(String value) {
            MessageDigest md5;
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.reset();
            byte[] bytes;
            try {
                bytes = value.getBytes("UTF-8");
            } catch (UnsupportedEncodingException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.update(bytes);
            return md5.digest();
        }

    }

}