摘要：集群目標(biāo)介紹中集群的負(fù)載均衡，介紹下包的源碼。源碼分析一該類實(shí)現(xiàn)了接口，是負(fù)載均衡的抽象類，提供了權(quán)重計(jì)算的功能。四該類是負(fù)載均衡基于一致性的邏輯實(shí)現(xiàn)。

目標(biāo)：介紹dubbo中集群的負(fù)載均衡，介紹dubbo-cluster下loadBalance包的源碼。

負(fù)載均衡，說(shuō)的通俗點(diǎn)就是要一碗水端平。在這個(gè)時(shí)代，公平是很重要的，在網(wǎng)絡(luò)請(qǐng)求的時(shí)候同樣是這個(gè)道理，我們有很多機(jī)器，但是請(qǐng)求老是到某個(gè)服務(wù)器上，而某些服務(wù)器又常年空閑，導(dǎo)致了資源的浪費(fèi)，也增加了服務(wù)器因?yàn)閴毫^(guò)載而宕機(jī)的風(fēng)險(xiǎn)。這個(gè)時(shí)候就需要負(fù)載均衡的出現(xiàn)。它就相當(dāng)于是一個(gè)天秤，通過(guò)各種策略，可以讓每臺(tái)服務(wù)器獲取到適合自己處理能力的負(fù)載，這樣既能夠?yàn)楦哓?fù)載的服務(wù)器分流，還能避免資源浪費(fèi)。負(fù)載均衡分為軟件的負(fù)載均衡和硬件負(fù)載均衡，我們這里講到的是軟件負(fù)載均衡，在dubbo中，需要對(duì)消費(fèi)者的調(diào)用請(qǐng)求進(jìn)行分配，避免少數(shù)服務(wù)提供者負(fù)載過(guò)大，其他服務(wù)空閑的情況，因?yàn)樨?fù)載過(guò)大會(huì)導(dǎo)致服務(wù)請(qǐng)求超時(shí)。這個(gè)時(shí)候就需要負(fù)載均衡起作用了。Dubbo 提供了4種負(fù)載均衡實(shí)現(xiàn)：

RandomLoadBalance：基于權(quán)重隨機(jī)算法

LeastActiveLoadBalance：基于最少活躍調(diào)用數(shù)算法

ConsistentHashLoadBalance：基于 hash 一致性

RoundRobinLoadBalance：基于加權(quán)輪詢算法

具體的實(shí)現(xiàn)看下面解析。

該類實(shí)現(xiàn)了LoadBalance接口，是負(fù)載均衡的抽象類，提供了權(quán)重計(jì)算的功能。

@Override
public  Invoker select(List> invokers, URL url, Invocation invocation) {
    // 如果invokers為空則返回空
    if (invokers == null || invokers.isEmpty())
        return null;
    // 如果invokers只有一個(gè)服務(wù)提供者，則返回一個(gè)
    if (invokers.size() == 1)
        return invokers.get(0);
    // 調(diào)用doSelect進(jìn)行選擇
    return doSelect(invokers, url, invocation);
}

該方法是選擇一個(gè)invoker，關(guān)鍵的選擇還是調(diào)用了doSelect方法，不過(guò)doSelect是一個(gè)抽象方法，由上述四種負(fù)載均衡策略來(lái)各自實(shí)現(xiàn)。

protected int getWeight(Invoker invoker, Invocation invocation) {
    // 獲得 weight 配置，即服務(wù)權(quán)重。默認(rèn)為 100
    int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
    if (weight > 0) {
        // 獲得啟動(dòng)時(shí)間戳
        long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L);
        if (timestamp > 0L) {
            // 獲得啟動(dòng)總時(shí)長(zhǎng)
            int uptime = (int) (System.currentTimeMillis() - timestamp);
            // 獲得預(yù)熱需要總時(shí)長(zhǎng)。默認(rèn)為10分鐘
            int warmup = invoker.getUrl().getParameter(Constants.WARMUP_KEY, Constants.DEFAULT_WARMUP);
            // 如果服務(wù)運(yùn)行時(shí)間小于預(yù)熱時(shí)間，則重新計(jì)算服務(wù)權(quán)重，即降權(quán)
            if (uptime > 0 && uptime < warmup) {
                weight = calculateWarmupWeight(uptime, warmup, weight);
            }
        }
    }
    return weight;
}

該方法是獲得權(quán)重的方法，計(jì)算權(quán)重在calculateWarmupWeight方法中實(shí)現(xiàn)，該方法考慮到了jvm預(yù)熱的過(guò)程。

static int calculateWarmupWeight(int uptime, int warmup, int weight) {
    // 計(jì)算權(quán)重 (uptime / warmup) * weight，進(jìn)度百分比 * 權(quán)重
    int ww = (int) ((float) uptime / ((float) warmup / (float) weight));
    // 權(quán)重范圍為 [0, weight] 之間
    return ww < 1 ? 1 : (ww > weight ? weight : ww);
}

該方法是計(jì)算權(quán)重的方法，其中計(jì)算公式是(uptime / warmup) weight，含義就是進(jìn)度百分比 權(quán)重值。

該類是基于權(quán)重隨機(jī)算法的負(fù)載均衡實(shí)現(xiàn)類，我們先來(lái)講講原理，比如我有有一組服務(wù)器 servers = [A, B, C]，他們他們對(duì)應(yīng)的權(quán)重為 weights = [6, 3, 1]，權(quán)重總和為10，現(xiàn)在把這些權(quán)重值平鋪在一維坐標(biāo)值上，分別出現(xiàn)三個(gè)區(qū)域，A區(qū)域?yàn)閇0,6)，B區(qū)域?yàn)閇6,9)，C區(qū)域?yàn)閇9,10)，然后產(chǎn)生一個(gè)[0, 10)的隨機(jī)數(shù)，看該數(shù)字落在哪個(gè)區(qū)間內(nèi)，就用哪臺(tái)服務(wù)器，這樣權(quán)重越大的，被擊中的概率就越大。

public class RandomLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "random";

    /**
     * 隨機(jī)數(shù)產(chǎn)生器
     */
    private final Random random = new Random();

    @Override
    protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
        // 獲得服務(wù)長(zhǎng)度
        int length = invokers.size(); // Number of invokers
        // 總的權(quán)重
        int totalWeight = 0; // The sum of weights
        // 是否有相同的權(quán)重
        boolean sameWeight = true; // Every invoker has the same weight?
        // 遍歷每個(gè)服務(wù)，計(jì)算相應(yīng)權(quán)重
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            // 計(jì)算總的權(quán)重值
            totalWeight += weight; // Sum
            // 如果前一個(gè)服務(wù)的權(quán)重值不等于后一個(gè)則sameWeight為false
            if (sameWeight && i > 0
                    && weight != getWeight(invokers.get(i - 1), invocation)) {
                sameWeight = false;
            }
        }
        // 如果每個(gè)服務(wù)權(quán)重都不同，并且總的權(quán)重值不為0
        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.
            // 循環(huán)讓 offset 數(shù)減去服務(wù)提供者權(quán)重值，當(dāng) offset 小于0時(shí)，返回相應(yīng)的 Invoker。
            // 舉例說(shuō)明一下，我們有 servers = [A, B, C]，weights = [6, 3, 1]，offset = 7。
            // 第一次循環(huán)，offset - 6 = 1 > 0，即 offset > 6，
            // 表明其不會(huì)落在服務(wù)器 A 對(duì)應(yīng)的區(qū)間上。
            // 第二次循環(huán)，offset - 3 = -2 < 0，即 6 < offset < 9，
            // 表明其會(huì)落在服務(wù)器 B 對(duì)應(yīng)的區(qū)間上
            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.
        // 如果所有服務(wù)提供者權(quán)重值相同，此時(shí)直接隨機(jī)返回一個(gè)即可
        return invokers.get(random.nextInt(length));
    }

}

該算法比較好理解，當(dāng)然 RandomLoadBalance 也存在一定的缺點(diǎn)，當(dāng)調(diào)用次數(shù)比較少時(shí)，Random 產(chǎn)生的隨機(jī)數(shù)可能會(huì)比較集中，此時(shí)多數(shù)請(qǐng)求會(huì)落到同一臺(tái)服務(wù)器上，不過(guò)影響不大。

該負(fù)載均衡策略基于最少活躍調(diào)用數(shù)算法，某個(gè)服務(wù)活躍調(diào)用數(shù)越小，表明該服務(wù)提供者效率越高，也就表明單位時(shí)間內(nèi)能夠處理的請(qǐng)求更多。此時(shí)應(yīng)該選擇該類服務(wù)器。實(shí)現(xiàn)很簡(jiǎn)單，就是每一個(gè)服務(wù)都有一個(gè)活躍數(shù)active來(lái)記錄該服務(wù)的活躍值，每收到一個(gè)請(qǐng)求，該active就會(huì)加1，，沒(méi)完成一個(gè)請(qǐng)求，active就會(huì)減1。在服務(wù)運(yùn)行一段時(shí)間后，性能好的服務(wù)提供者處理請(qǐng)求的速度更快，因此活躍數(shù)下降的也越快，此時(shí)這樣的服務(wù)提供者能夠優(yōu)先獲取到新的服務(wù)請(qǐng)求。除了最小活躍數(shù)，還引入了權(quán)重值，也就是當(dāng)活躍數(shù)一樣的時(shí)候，選擇利用權(quán)重法來(lái)進(jìn)行選擇，如果權(quán)重也一樣，那么隨機(jī)選擇一個(gè)。

public class LeastActiveLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "leastactive";

    /**
     * 隨機(jī)器
     */
    private final Random random = new Random();

    @Override
    protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
        // 獲得服務(wù)長(zhǎng)度
        int length = invokers.size(); // Number of invokers
        // 最小的活躍數(shù)
        int leastActive = -1; // The least active value of all invokers
        // 具有相同“最小活躍數(shù)”的服務(wù)者提供者（以下用 Invoker 代稱）數(shù)量
        int leastCount = 0; // The number of invokers having the same least active value (leastActive)
        // leastIndexs 用于記錄具有相同“最小活躍數(shù)”的 Invoker 在 invokers 列表中的下標(biāo)信息
        int[] leastIndexs = new int[length]; // The index of invokers having the same least active value (leastActive)
        // 總的權(quán)重
        int totalWeight = 0; // The sum of with warmup weights
        // 第一個(gè)最小活躍數(shù)的 Invoker 權(quán)重值，用于與其他具有相同最小活躍數(shù)的 Invoker 的權(quán)重進(jìn)行對(duì)比，
        // 以檢測(cè)是否“所有具有相同最小活躍數(shù)的 Invoker 的權(quán)重”均相等
        int firstWeight = 0; // Initial value, used for comparision
        // 是否權(quán)重相同
        boolean sameWeight = true; // Every invoker has the same weight value?
        for (int i = 0; i < length; i++) {
            Invoker invoker = invokers.get(i);
            // 獲取 Invoker 對(duì)應(yīng)的活躍數(shù)
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // Active number
            // 獲得該服務(wù)的權(quán)重
            int afterWarmup = getWeight(invoker, invocation); // Weight
            // 發(fā)現(xiàn)更小的活躍數(shù)，重新開(kāi)始
            if (leastActive == -1 || active < leastActive) { // Restart, when find a invoker having smaller least active value.
                // 記錄當(dāng)前最小的活躍數(shù)
                leastActive = active; // Record the current least active value
                // 更新 leastCount 為 1
                leastCount = 1; // Reset leastCount, count again based on current leastCount
                // 記錄當(dāng)前下標(biāo)值到 leastIndexs 中
                leastIndexs[0] = i; // Reset
                totalWeight = afterWarmup; // Reset
                firstWeight = afterWarmup; // Record the weight the first invoker
                sameWeight = true; // Reset, every invoker has the same weight value?
                // 如果當(dāng)前 Invoker 的活躍數(shù) active 與最小活躍數(shù) leastActive 相同
            } else if (active == leastActive) { // If current invoker"s active value equals with leaseActive, then accumulating.
                // 在 leastIndexs 中記錄下當(dāng)前 Invoker 在 invokers 集合中的下標(biāo)
                leastIndexs[leastCount++] = i; // Record index number of this invoker
                // 累加權(quán)重
                totalWeight += afterWarmup; // Add this invoker"s weight to totalWeight.
                // If every invoker has the same weight?
                if (sameWeight && i > 0
                        && afterWarmup != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // assert(leastCount > 0)
        // 當(dāng)只有一個(gè) Invoker 具有最小活躍數(shù)，此時(shí)直接返回該 Invoker 即可
        if (leastCount == 1) {
            // If we got exactly one invoker having the least active value, return this invoker directly.
            return invokers.get(leastIndexs[0]);
        }
        // 有多個(gè) Invoker 具有相同的最小活躍數(shù)，但它們之間的權(quán)重不同
        if (!sameWeight && totalWeight > 0) {
            // If (not every invoker has the same weight & at least one invoker"s weight>0), select randomly based on totalWeight.
            // 隨機(jī)生成一個(gè)數(shù)字
            int offsetWeight = random.nextInt(totalWeight) + 1;
            // Return a invoker based on the random value.
            // 相關(guān)算法可以參考RandomLoadBalance
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
                if (offsetWeight <= 0)
                    return invokers.get(leastIndex);
            }
        }
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        // 如果權(quán)重一樣，則隨機(jī)取一個(gè)
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }
}

前半部分在進(jìn)行最小活躍數(shù)的策略，后半部分在進(jìn)行權(quán)重的隨機(jī)策略，可以參見(jiàn)RandomLoadBalance。

該類是負(fù)載均衡基于 hash 一致性的邏輯實(shí)現(xiàn)。一致性哈希算法由麻省理工學(xué)院的 Karger 及其合作者于1997年提供出的，一開(kāi)始被大量運(yùn)用于緩存系統(tǒng)的負(fù)載均衡。它的工作原理是這樣的：首先根據(jù) ip 或其他的信息為緩存節(jié)點(diǎn)生成一個(gè) hash，在dubbo中使用參數(shù)進(jìn)行計(jì)算hash。并將這個(gè) hash 投射到 [0, 232 - 1] 的圓環(huán)上，當(dāng)有查詢或?qū)懭胝?qǐng)求時(shí)，則生成一個(gè) hash 值。然后查找第一個(gè)大于或等于該 hash 值的緩存節(jié)點(diǎn)，并到這個(gè)節(jié)點(diǎn)中查詢或?qū)懭刖彺骓?xiàng)。如果當(dāng)前節(jié)點(diǎn)掛了，則在下一次查詢或?qū)懭刖彺鏁r(shí)，為緩存項(xiàng)查找另一個(gè)大于其 hash 值的緩存節(jié)點(diǎn)即可。大致效果如下圖所示（引用一下官網(wǎng)的圖）

每個(gè)緩存節(jié)點(diǎn)在圓環(huán)上占據(jù)一個(gè)位置。如果緩存項(xiàng)的 key 的 hash 值小于緩存節(jié)點(diǎn) hash 值，則到該緩存節(jié)點(diǎn)中存儲(chǔ)或讀取緩存項(xiàng)，這里有兩個(gè)概念不要弄混，緩存節(jié)點(diǎn)就好比dubbo中的服務(wù)提供者，會(huì)有很多的服務(wù)提供者，而緩存項(xiàng)就好比是服務(wù)引用的消費(fèi)者。比如下面綠色點(diǎn)對(duì)應(yīng)的緩存項(xiàng)也就是服務(wù)消費(fèi)者將會(huì)被存儲(chǔ)到 cache-2 節(jié)點(diǎn)中。由于 cache-3 掛了，原本應(yīng)該存到該節(jié)點(diǎn)中的緩存項(xiàng)也就是服務(wù)消費(fèi)者最終會(huì)存儲(chǔ)到 cache-4 節(jié)點(diǎn)中，也就是調(diào)用cache-4 這個(gè)服務(wù)提供者。

但是在hash一致性算法并不能夠保證hash算法的平衡性，就拿上面的例子來(lái)看，cache-3掛掉了，那該節(jié)點(diǎn)下的所有緩存項(xiàng)都要存儲(chǔ)到 cache-4 節(jié)點(diǎn)中，這就導(dǎo)致hash值低的一直往高的存儲(chǔ)，會(huì)面臨一個(gè)不平衡的現(xiàn)象，見(jiàn)下圖：

可以看到最后會(huì)變成類似不平衡的現(xiàn)象，那我們應(yīng)該怎么避免這樣的事情，做到平衡性，那就需要引入虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品，“虛擬節(jié)點(diǎn)”在 hash 空間中以hash值排列。比如下圖：

可以看到各個(gè)節(jié)點(diǎn)都被均勻分布在圓環(huán)上，而某一個(gè)服務(wù)提供者居然有多個(gè)節(jié)點(diǎn)存在，分別跟其他節(jié)點(diǎn)交錯(cuò)排列，這樣做的目的就是避免數(shù)據(jù)傾斜問(wèn)題，也就是由于節(jié)點(diǎn)不夠分散，導(dǎo)致大量請(qǐng)求落到了同一個(gè)節(jié)點(diǎn)上，而其他節(jié)點(diǎn)只會(huì)接收到了少量請(qǐng)求的情況。類似第二張圖的情況。

看完原理，接下來(lái)我們來(lái)看看代碼

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    // 獲得方法名
    String methodName = RpcUtils.getMethodName(invocation);
    // 獲得key
    String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
    // 獲取 invokers 原始的 hashcode
    int identityHashCode = System.identityHashCode(invokers);
    // 從一致性 hash 選擇器集合中獲得一致性 hash 選擇器
    ConsistentHashSelector selector = (ConsistentHashSelector) selectors.get(key);
    // 如果等于空或者選擇器的hash值不等于原始的值，則新建一個(gè)一致性 hash 選擇器，并且加入到集合
    if (selector == null || selector.identityHashCode != identityHashCode) {
        selectors.put(key, new ConsistentHashSelector(invokers, methodName, identityHashCode));
        selector = (ConsistentHashSelector) selectors.get(key);
    }
    // 選擇器選擇一個(gè)invoker
    return selector.select(invocation);
}

該方法也做了一些invokers 列表是不是變動(dòng)過(guò)，以及創(chuàng)建 ConsistentHashSelector等工作，然后調(diào)用selector.select來(lái)進(jìn)行選擇。

private static final class ConsistentHashSelector {

    /**
     * 存儲(chǔ) Invoker 虛擬節(jié)點(diǎn)
     */
    private final TreeMap> virtualInvokers;

    /**
     * 每個(gè)Invoker 對(duì)應(yīng)的虛擬節(jié)點(diǎn)數(shù)
     */
    private final int replicaNumber;

    /**
     * 原始哈希值
     */
    private final int identityHashCode;

    /**
     * 取值參數(shù)位置數(shù)組
     */
    private final int[] argumentIndex;

    ConsistentHashSelector(List> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        // 獲取虛擬節(jié)點(diǎn)數(shù)，默認(rèn)為160
        this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
        // 獲取參與 hash 計(jì)算的參數(shù)下標(biāo)值，默認(rèn)對(duì)第一個(gè)參數(shù)進(jìn)行 hash 運(yùn)算
        String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
        // 創(chuàng)建下標(biāo)數(shù)組
        argumentIndex = new int[index.length];
        // 遍歷
        for (int i = 0; i < index.length; i++) {
            // 記錄下標(biāo)
            argumentIndex[i] = Integer.parseInt(index[i]);
        }
        // 遍歷invokers
        for (Invoker invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                // 對(duì) address + i 進(jìn)行 md5 運(yùn)算，得到一個(gè)長(zhǎng)度為16的字節(jié)數(shù)組
                byte[] digest = md5(address + i);
                // // 對(duì) digest 部分字節(jié)進(jìn)行4次 hash 運(yùn)算，得到四個(gè)不同的 long 型正整數(shù)
                for (int h = 0; h < 4; h++) {
                    // h = 0 時(shí)，取 digest 中下標(biāo)為 0 ~ 3 的4個(gè)字節(jié)進(jìn)行位運(yùn)算
                    // h = 1 時(shí)，取 digest 中下標(biāo)為 4 ~ 7 的4個(gè)字節(jié)進(jìn)行位運(yùn)算
                    // h = 2, h = 3 時(shí)過(guò)程同上
                    long m = hash(digest, h);
                    // 將 hash 到 invoker 的映射關(guān)系存儲(chǔ)到 virtualInvokers 中，
                    // virtualInvokers 需要提供高效的查詢操作，因此選用 TreeMap 作為存儲(chǔ)結(jié)構(gòu)
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }

    /**
     * 選擇一個(gè)invoker
     * @param invocation
     * @return
     */
    public Invoker select(Invocation invocation) {
        // 將參數(shù)轉(zhuǎn)為 key
        String key = toKey(invocation.getArguments());
        // 對(duì)參數(shù) key 進(jìn)行 md5 運(yùn)算
        byte[] digest = md5(key);
        // 取 digest 數(shù)組的前四個(gè)字節(jié)進(jìn)行 hash 運(yùn)算，再將 hash 值傳給 selectForKey 方法，
        // 尋找合適的 Invoker
        return selectForKey(hash(digest, 0));
    }

    /**
     * 將參數(shù)轉(zhuǎn)為 key
     * @param args
     * @return
     */
    private String toKey(Object[] args) {
        StringBuilder buf = new StringBuilder();
        // 遍歷參數(shù)下標(biāo)
        for (int i : argumentIndex) {
            if (i >= 0 && i < args.length) {
                // 拼接參數(shù)，生成key
                buf.append(args[i]);
            }
        }
        return buf.toString();
    }

    /**
     * 通過(guò)hash選擇invoker
     * @param hash
     * @return
     */
    private Invoker selectForKey(long hash) {
        // 到 TreeMap 中查找第一個(gè)節(jié)點(diǎn)值大于或等于當(dāng)前 hash 的 Invoker
        Map.Entry> entry = virtualInvokers.tailMap(hash, true).firstEntry();
        // 如果 hash 大于 Invoker 在圓環(huán)上最大的位置，此時(shí) entry = null，
        // 需要將 TreeMap 的頭節(jié)點(diǎn)賦值給 entry
        if (entry == null) {
            entry = virtualInvokers.firstEntry();
        }
        // 返回選擇的invoker
        return entry.getValue();
    }

    /**
     * 計(jì)算hash值
     * @param digest
     * @param number
     * @return
     */
    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;
    }

    /**
     * md5
     * @param value
     * @return
     */
    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();
    }

}

該類是內(nèi)部類，是一致性 hash 選擇器，首先看它的屬性，利用TreeMap來(lái)存儲(chǔ) Invoker 虛擬節(jié)點(diǎn)，因?yàn)樾枰峁└咝У牟樵儾僮?。再看看它的?gòu)造方法，執(zhí)行了一系列的初始化邏輯，比如從配置中獲取虛擬節(jié)點(diǎn)數(shù)以及參與 hash 計(jì)算的參數(shù)下標(biāo)，默認(rèn)情況下只使用第一個(gè)參數(shù)進(jìn)行 hash，并且ConsistentHashLoadBalance 的負(fù)載均衡邏輯只受參數(shù)值影響，具有相同參數(shù)值的請(qǐng)求將會(huì)被分配給同一個(gè)服務(wù)提供者。還有一個(gè)select方法，比較簡(jiǎn)單，先進(jìn)行md5運(yùn)算。然后hash，最后選擇出對(duì)應(yīng)的invoker。

該類是負(fù)載均衡基于加權(quán)輪詢算法的實(shí)現(xiàn)。那么什么是加權(quán)輪詢，輪詢很好理解，比如我第一個(gè)請(qǐng)求分配給A服務(wù)器，第二個(gè)請(qǐng)求分配給B服務(wù)器，第三個(gè)請(qǐng)求分配給C服務(wù)器，第四個(gè)請(qǐng)求又分配給A服務(wù)器，這就是輪詢，但是這只適合每臺(tái)服務(wù)器性能相近的情況，這種是一種非常理想的情況，那更多的是每臺(tái)服務(wù)器的性能都會(huì)有所差異，這個(gè)時(shí)候性能差的服務(wù)器被分到等額的請(qǐng)求，就會(huì)需要承受壓力大宕機(jī)的情況，這個(gè)時(shí)候我們需要對(duì)輪詢加權(quán)，我舉個(gè)例子，服務(wù)器 A、B、C 權(quán)重比為 6:3:1，那么在10次請(qǐng)求中，服務(wù)器 A 將收到其中的6次請(qǐng)求，服務(wù)器 B 會(huì)收到其中的3次請(qǐng)求，服務(wù)器 C 則收到其中的1次請(qǐng)求，也就是說(shuō)每臺(tái)服務(wù)器能夠收到的請(qǐng)求歸結(jié)于它的權(quán)重。

/**
 * 回收間隔
 */
private static int RECYCLE_PERIOD = 60000;

protected static class WeightedRoundRobin {
    /**
     * 權(quán)重
     */
    private int weight;
    /**
     * 當(dāng)前已經(jīng)有多少請(qǐng)求落在該服務(wù)提供者身上，也可以看成是一個(gè)動(dòng)態(tài)的權(quán)重
     */
    private AtomicLong current = new AtomicLong(0);
    /**
     * 最后一次更新時(shí)間
     */
    private long lastUpdate;
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
        current.set(0);
    }
    public long increaseCurrent() {
        return current.addAndGet(weight);
    }
    public void sel(int total) {
        current.addAndGet(-1 * total);
    }
    public long getLastUpdate() {
        return lastUpdate;
    }
    public void setLastUpdate(long lastUpdate) {
        this.lastUpdate = lastUpdate;
    }
}

該內(nèi)部類是一個(gè)加權(quán)輪詢器，它記錄了某一個(gè)服務(wù)提供者的一些數(shù)據(jù)，比如權(quán)重、比如當(dāng)前已經(jīng)有多少請(qǐng)求落在該服務(wù)提供者上等。

@Override
protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    // key = 全限定類名 + "." + 方法名，比如 com.xxx.DemoService.sayHello
    String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
    ConcurrentMap map = methodWeightMap.get(key);
    if (map == null) {
        methodWeightMap.putIfAbsent(key, new ConcurrentHashMap());
        map = methodWeightMap.get(key);
    }
    // 權(quán)重總和
    int totalWeight = 0;
    // 最小權(quán)重
    long maxCurrent = Long.MIN_VALUE;
    // 獲得現(xiàn)在的時(shí)間戳
    long now = System.currentTimeMillis();
    // 創(chuàng)建已經(jīng)選擇的invoker
    Invoker selectedInvoker = null;
    // 創(chuàng)建加權(quán)輪詢器
    WeightedRoundRobin selectedWRR = null;

    // 下面這個(gè)循環(huán)主要做了這樣幾件事情：
    //   1. 遍歷 Invoker 列表，檢測(cè)當(dāng)前 Invoker 是否有
    //      相應(yīng)的 WeightedRoundRobin，沒(méi)有則創(chuàng)建
    //   2. 檢測(cè) Invoker 權(quán)重是否發(fā)生了變化，若變化了，
    //      則更新 WeightedRoundRobin 的 weight 字段
    //   3. 讓 current 字段加上自身權(quán)重，等價(jià)于 current += weight
    //   4. 設(shè)置 lastUpdate 字段，即 lastUpdate = now
    //   5. 尋找具有最大 current 的 Invoker，以及 Invoker 對(duì)應(yīng)的 WeightedRoundRobin，
    //      暫存起來(lái)，留作后用
    //   6. 計(jì)算權(quán)重總和
    for (Invoker invoker : invokers) {
        // 獲得identify的值
        String identifyString = invoker.getUrl().toIdentityString();
        // 獲得加權(quán)輪詢器
        WeightedRoundRobin weightedRoundRobin = map.get(identifyString);
        // 計(jì)算權(quán)重
        int weight = getWeight(invoker, invocation);
        // 如果權(quán)重小于0，則設(shè)置0
        if (weight < 0) {
            weight = 0;
        }
        // 如果加權(quán)輪詢器為空
        if (weightedRoundRobin == null) {
            // 創(chuàng)建加權(quán)輪詢器
            weightedRoundRobin = new WeightedRoundRobin();
            // 設(shè)置權(quán)重
            weightedRoundRobin.setWeight(weight);
            // 加入集合
            map.putIfAbsent(identifyString, weightedRoundRobin);
            weightedRoundRobin = map.get(identifyString);
        }
        // 如果權(quán)重跟之前的權(quán)重不一樣，則重新設(shè)置權(quán)重
        if (weight != weightedRoundRobin.getWeight()) {
            //weight changed
            weightedRoundRobin.setWeight(weight);
        }
        // 計(jì)數(shù)器加1
        long cur = weightedRoundRobin.increaseCurrent();
        // 更新最后一次更新時(shí)間
        weightedRoundRobin.setLastUpdate(now);
        // 當(dāng)落在該服務(wù)提供者的統(tǒng)計(jì)數(shù)大于最大可承受的數(shù)
        if (cur > maxCurrent) {
            // 賦值
            maxCurrent = cur;
            // 被選擇的selectedInvoker賦值
            selectedInvoker = invoker;
            // 被選擇的加權(quán)輪詢器賦值
            selectedWRR = weightedRoundRobin;
        }
        // 累加
        totalWeight += weight;
    }
    // 如果更新鎖不能獲得并且invokers的大小跟map大小不匹配
    // 對(duì)  進(jìn)行檢查，過(guò)濾掉長(zhǎng)時(shí)間未被更新的節(jié)點(diǎn)。
    // 該節(jié)點(diǎn)可能掛了，invokers 中不包含該節(jié)點(diǎn)，所以該節(jié)點(diǎn)的 lastUpdate 長(zhǎng)時(shí)間無(wú)法被更新。
    // 若未更新時(shí)長(zhǎng)超過(guò)閾值后，就會(huì)被移除掉，默認(rèn)閾值為60秒。
    if (!updateLock.get() && invokers.size() != map.size()) {
        if (updateLock.compareAndSet(false, true)) {
            try {
                // copy -> modify -> update reference
                ConcurrentMap newMap = new ConcurrentHashMap();
                // 復(fù)制
                newMap.putAll(map);
                Iterator> it = newMap.entrySet().iterator();
                // 輪詢
                while (it.hasNext()) {
                    Entry item = it.next();
                    // 如果大于回收時(shí)間，則進(jìn)行回收
                    if (now - item.getValue().getLastUpdate() > RECYCLE_PERIOD) {
                        // 從集合中移除
                        it.remove();
                    }
                }
                // 加入集合
                methodWeightMap.put(key, newMap);
            } finally {
                updateLock.set(false);
            }
        }
    }
    // 如果被選擇的selectedInvoker不為空
    if (selectedInvoker != null) {
        // 設(shè)置總的權(quán)重
        selectedWRR.sel(totalWeight);
        return selectedInvoker;
    }
    // should not happen here
    return invokers.get(0);
}

該方法是選擇的核心，其實(shí)關(guān)鍵是一些數(shù)據(jù)記錄，在每次請(qǐng)求都會(huì)記錄落在該服務(wù)上的請(qǐng)求數(shù)，然后在根據(jù)權(quán)重來(lái)分配，并且會(huì)有回收時(shí)間來(lái)處理一些長(zhǎng)時(shí)間未被更新的節(jié)點(diǎn)。

該部分相關(guān)的源碼解析地址：https://github.com/CrazyHZM/i...

該文章講解了集群中關(guān)于負(fù)載均衡實(shí)現(xiàn)的部分，每個(gè)算法都是現(xiàn)在很普遍的負(fù)載均衡算法，希望大家細(xì)細(xì)品味。接下來(lái)我將開(kāi)始對(duì)集群模塊關(guān)于分組聚合部分進(jìn)行講解。