[[418899]]

前面我們講了Nacos客戶端如何獲取實(shí)例列表，如何進(jìn)行緩存處理，以及如何訂閱實(shí)例列表的變更。在獲取到一個(gè)實(shí)例列表之后，你是否想過(guò)一個(gè)問(wèn)題：如果實(shí)例列表有100個(gè)實(shí)例，Nacos客戶端是如何從中選擇一個(gè)呢?

這篇文章，就帶大家從源碼層面分析一下，Nacos客戶端采用了如何的算法來(lái)從實(shí)例列表中獲取一個(gè)實(shí)例進(jìn)行請(qǐng)求的。也可以稱作是Nacos客戶端的負(fù)載均衡算法。

單個(gè)實(shí)例獲取

NamingService不僅提供了獲取實(shí)例列表的方法，也提供了獲取單個(gè)實(shí)例的方法，比如：

Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters, boolean subscribe) 
        throws NacosException; 

該方法會(huì)根據(jù)預(yù)定義的負(fù)載算法，從實(shí)例列表中獲得一個(gè)健康的實(shí)例。其他重載的方法功能類似，最終都會(huì)調(diào)用該方法，我們就以此方法為例來(lái)分析一下具體的算法。

具體實(shí)現(xiàn)代碼：

@Override 
public Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters, 
        boolean subscribe) throws NacosException { 
    String clusterString = StringUtils.join(clusters, ","); 
    if (subscribe) { 
        // 獲取ServiceInfo 
        ServiceInfo serviceInfo = serviceInfoHolder.getServiceInfo(serviceName, groupName, clusterString); 
        if (null == serviceInfo) { 
            serviceInfo = clientProxy.subscribe(serviceName, groupName, clusterString); 
        } 
        // 通過(guò)負(fù)載均衡算法獲得其中一個(gè)實(shí)例 
        return Balancer.RandomByWeight.selectHost(serviceInfo); 
    } else { 
        // 獲取ServiceInfo 
        ServiceInfo serviceInfo = clientProxy 
                .queryInstancesOfService(serviceName, groupName, clusterString, 0, false); 
        // 通過(guò)負(fù)載均衡算法獲得其中一個(gè)實(shí)例 
        return Balancer.RandomByWeight.selectHost(serviceInfo); 
    } 
} 

selectOneHealthyInstance方法邏輯很簡(jiǎn)單，調(diào)用我們之前講到的方法獲取ServiceInfo對(duì)象，然后作為參數(shù)傳遞給負(fù)載均衡算法，由負(fù)載均衡算法計(jì)算出最終使用哪個(gè)實(shí)例(Instance)。

算法參數(shù)封裝

先跟蹤一下代碼實(shí)現(xiàn)，非核心業(yè)務(wù)邏輯，只簡(jiǎn)單提一下。

上面的代碼可以看出調(diào)用的是Balancer內(nèi)部類RandomByWeight的selectHost方法：

public static Instance selectHost(ServiceInfo dom) { 
    // ServiceInfo中獲去實(shí)例列表 
    List<Instance> hosts = selectAll(dom); 
    // ... 
    return getHostByRandomWeight(hosts); 
} 

selectHost方法核心邏輯是從ServiceInfo中獲取實(shí)例列表，然后調(diào)用getHostByRandomWeight方法：

protected static Instance getHostByRandomWeight(List<Instance> hosts) { 
    // ... 判斷邏輯 
    // 重新組織數(shù)據(jù)格式 
    List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>(); 
    for (Instance host : hosts) { 
        if (host.isHealthy()) { 
            hostsWithWeight.add(new Pair<Instance>(host, host.getWeight())); 
        } 
    } 
    // 通過(guò)Chooser來(lái)實(shí)現(xiàn)隨機(jī)權(quán)重負(fù)載均衡算法 
    Chooser<String, Instance> vipChooser = new Chooser<String, Instance>("www.taobao.com"); 
    vipChooser.refresh(hostsWithWeight); 
    return vipChooser.randomWithWeight(); 
} 

getHostByRandomWeight前半部分是將Instance列表及其中的權(quán)重?cái)?shù)據(jù)進(jìn)行轉(zhuǎn)換，封裝成一個(gè)Pair，也就是建立成對(duì)的關(guān)系。在此過(guò)程中只使用了健康的節(jié)點(diǎn)。

真正的算法實(shí)現(xiàn)則是通過(guò)Chooser類來(lái)實(shí)現(xiàn)的，看名字基本上知道實(shí)現(xiàn)的策略是基于權(quán)重的隨機(jī)算法。

負(fù)載均衡算法實(shí)現(xiàn)

所有的負(fù)載均衡算法實(shí)現(xiàn)均位于Chooser類中，Chooser類的提供了兩個(gè)方法refresh和randomWithWeight。

refresh方法用于篩選數(shù)據(jù)、檢查數(shù)據(jù)合法性和建立算法所需數(shù)據(jù)模型。

randomWithWeight方法基于前面的數(shù)據(jù)來(lái)進(jìn)行隨機(jī)算法處理。

先看refresh方法：

public void refresh(List<Pair<T>> itemsWithWeight) { 
    Ref<T> newRef = new Ref<T>(itemsWithWeight); 
    // 準(zhǔn)備數(shù)據(jù)，檢查數(shù)據(jù) 
    newRef.refresh(); 
    // 上面數(shù)據(jù)刷新之后，這里重新初始化一個(gè)GenericPoller 
    newRef.poller = this.ref.poller.refresh(newRef.items); 
    this.ref = newRef; 
} 

基本步驟：

• 創(chuàng)建Ref類，該類為Chooser的內(nèi)部類;
• 調(diào)用Ref的refresh方法，用于準(zhǔn)備數(shù)據(jù)、檢查數(shù)據(jù)等;
• 數(shù)據(jù)篩選完成，調(diào)用poller#refresh方法，本質(zhì)上就是創(chuàng)建一個(gè)GenericPoller對(duì)象;
• 成員變量重新賦值;

這里重點(diǎn)看Ref#refresh方法：

/** 
 * 獲取參與計(jì)算的實(shí)例列表、計(jì)算遞增數(shù)組數(shù)總和并進(jìn)行檢查 
 */ 
public void refresh() { 
    // 實(shí)例權(quán)重總和 
    Double originWeightSum = (double) 0; 
     
    // 所有健康權(quán)重求和 
    for (Pair<T> item : itemsWithWeight) { 
         
        double weight = item.weight(); 
        //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
        // 權(quán)重小于等于0則不參與計(jì)算 
        if (weight <= 0) { 
            continue; 
        } 
        // 有效實(shí)例放入列表 
        items.add(item.item()); 
        // 如果值無(wú)限大 
        if (Double.isInfinite(weight)) { 
            weight = 10000.0D; 
        } 
        // 如果值為非數(shù)字 
        if (Double.isNaN(weight)) { 
            weight = 1.0D; 
        } 
        // 權(quán)重值累加 
        originWeightSum += weight; 
    } 
     
    double[] exactWeights = new double[items.size()]; 
    int index = 0; 
    // 計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重占比，放入數(shù)組 
    for (Pair<T> item : itemsWithWeight) { 
        double singleWeight = item.weight(); 
        //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
        if (singleWeight <= 0) { 
            continue; 
        } 
        // 計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重占比 
        exactWeights[index++] = singleWeight / originWeightSum; 
    } 
     
    // 初始化遞增數(shù)組 
    weights = new double[items.size()]; 
    double randomRange = 0D; 
    for (int i = 0; i < index; i++) { 
        // 遞增數(shù)組第i項(xiàng)值為items前i個(gè)值總和 
        weights[i] = randomRange + exactWeights[i]; 
        randomRange += exactWeights[i]; 
    } 
     
    double doublePrecisionDelta = 0.0001; 
    // index遍歷完則返回； 
    // 或weights最后一位值與1相比，誤差小于0.0001，則返回 
    if (index == 0 || (Math.abs(weights[index - 1] - 1) < doublePrecisionDelta)) { 
        return; 
    } 
    throw new IllegalStateException( 
            "Cumulative Weight calculate wrong , the sum of probabilities does not equals 1."); 
} 

可結(jié)合上面代碼中的注釋來(lái)理解，核心步驟包括以下：

• 遍歷itemsWithWeight，計(jì)算權(quán)重總和數(shù)據(jù);非健康節(jié)點(diǎn)會(huì)被剔除掉;
• 計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)重值在總權(quán)重值中的占比，并存儲(chǔ)在exactWeights數(shù)組當(dāng)中;
• 將exactWeights數(shù)組當(dāng)中值進(jìn)行數(shù)據(jù)重構(gòu)，形成一個(gè)遞增數(shù)組weights(每個(gè)值都是exactWeights坐標(biāo)值的總和)，后面用于隨機(jī)算法;
• 判斷是否循環(huán)完成或誤差在指定范圍內(nèi)(0.0001)，符合則返回。

所有數(shù)據(jù)準(zhǔn)備完成，調(diào)用隨機(jī)算法方法randomWithWeight：

public T randomWithWeight() { 
    Ref<T> ref = this.ref; 
    // 生成0-1之間的隨機(jī)數(shù) 
    double random = ThreadLocalRandom.current().nextDouble(0, 1); 
    // 采用二分法查找數(shù)組中指定值，如果不存在則返回（-(插入點(diǎn)) - 1），插入點(diǎn)即隨機(jī)數(shù)將要插入數(shù)組的位置，即第一個(gè)大于此鍵的元素索引。 
    int index = Arrays.binarySearch(ref.weights, random); 
    // 如果沒(méi)有查詢到（返回-1或"-插入點(diǎn)"） 
    if (index < 0) { 
        index = -index - 1; 
    } else { 
        // 命中直接返回結(jié)果 
        return ref.items.get(index); 
    } 
     
    // 判斷坐標(biāo)未越界 
    if (index < ref.weights.length) { 
        // 隨機(jī)數(shù)小于指定坐標(biāo)的數(shù)值，則返回坐標(biāo)值 
        if (random < ref.weights[index]) { 
            return ref.items.get(index); 
        } 
    } 
     
    // 此種情況不應(yīng)該發(fā)生，但如果發(fā)生則返回最后一個(gè)位置的值 
    /* This should never happen, but it ensures we will return a correct 
     * object in case there is some floating point inequality problem 
     * wrt the cumulative probabilities. */ 
    return ref.items.get(ref.items.size() - 1); 
} 

該方法的基本操作如下：

• 生成一個(gè)0-1的隨機(jī)數(shù);
• 使用Arrays#binarySearch在數(shù)組中進(jìn)行查找，也就是二分查找法。該方法會(huì)返回包含key的值，如果沒(méi)有則會(huì)返回”-1“或”-插入點(diǎn)“，插入點(diǎn)即隨機(jī)數(shù)將要插入數(shù)組的位置，即第一個(gè)大于此鍵的元素索引。
• 如果命中則直接返回;如果未命中則對(duì)返回值取反減1，獲得index值;
• 判斷index值，符合條件，則返回結(jié)果;

至此，關(guān)于Nacos客戶端實(shí)例獲取的負(fù)載均衡算法代碼層面追蹤完畢。

算法實(shí)例演示

下面用一個(gè)實(shí)例來(lái)演示一下，該算法中涉及的數(shù)據(jù)變化。為了數(shù)據(jù)美觀，這里采用4組數(shù)據(jù)，每組數(shù)據(jù)進(jìn)來(lái)確保能被整除;

節(jié)點(diǎn)及權(quán)重?cái)?shù)據(jù)(前面節(jié)點(diǎn)，后面權(quán)重)如下：

1 100 
2 25 
3 75 
4 200 

第一步，計(jì)算權(quán)重綜合：

originWeightSum = 100 + 25 + 75 + 200 = 400 

第二步，計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重比：

exactWeights = {0.25, 0.0625, 0.1875, 0.5} 

第三步，計(jì)算遞增數(shù)組weights：

weights = {0.25, 0.3125, 0.5, 1} 

第四步，生成0-1的隨機(jī)數(shù)：

random = 0.3049980013493817 

第五步，調(diào)用Arrays#binarySearch從weights中搜索random：

index = -2 

關(guān)于Arrays#binarySearch(double[] a, double key)方法這里再解釋一下，如果傳入的key恰好在數(shù)組中，比如1，則返回的index為3;如果key為上面的random值，則先找到插入點(diǎn)，取反，減一。

插入點(diǎn)即第一個(gè)大于此key的元素索引，那么上面第一個(gè)大于0.3049980013493817的值為0.3125，那么插入點(diǎn)值為1;

于是按照公式計(jì)算Arrays#binarySearch返回的index為：

index = - ( 1 ) - 1 = -2 

第六步，也就是沒(méi)有恰好命中的情況：

index = -( -2 ) - 1 = 1 

然后判斷index是否越界，很明顯 1 < 4，未越界，則返回坐標(biāo)為1的值。

算法的核心

上面演示了算法，但這個(gè)算法真的能夠做到按權(quán)重負(fù)載嗎?我們來(lái)分析一下這個(gè)問(wèn)題。

這個(gè)問(wèn)題的重點(diǎn)不在random值，這個(gè)值基本上是隨機(jī)的，那么怎么保證權(quán)重大的節(jié)點(diǎn)獲得的機(jī)會(huì)更多呢?

這里先把遞增數(shù)組weights用另外一個(gè)形式來(lái)表示：

上面的算法可以看出，weights與exactWeights為size相同的數(shù)組，對(duì)于同一坐標(biāo)(index)，weights的值是exactWeights包含當(dāng)前坐標(biāo)及前面所有坐標(biāo)值的和。

如果把weights理解成一條線，對(duì)應(yīng)節(jié)點(diǎn)的值是線上的一個(gè)個(gè)點(diǎn)，體現(xiàn)在圖中便是(圖2到圖5)有色(灰色+橘黃色)部分。

而Arrays#binarySearch算法的插入點(diǎn)獲取的是第一個(gè)大于key(也就是random)的坐標(biāo)，也就是說(shuō)每個(gè)節(jié)點(diǎn)享有的隨機(jī)范圍不同，它們的范圍由當(dāng)前點(diǎn)和前一個(gè)點(diǎn)的區(qū)間決定，而這個(gè)區(qū)間正好是權(quán)重比值。

權(quán)重比值大的節(jié)點(diǎn)，占有的區(qū)間就比較多，比如節(jié)點(diǎn)1占了1/4，節(jié)點(diǎn)4占了1/2。這樣，如果隨機(jī)數(shù)是均勻分布的，那么占有范圍比較大的節(jié)點(diǎn)更容易獲得青睞。也就達(dá)到了按照權(quán)重獲得被調(diào)用的機(jī)會(huì)了。

小結(jié)

本篇文章追蹤Nacos客戶端源碼，分析了從實(shí)例列表中獲得其中一個(gè)實(shí)例的算法，也就是隨機(jī)權(quán)重負(fù)載均衡算法。整體業(yè)務(wù)邏輯比較簡(jiǎn)單，從ServiceInfo中獲得實(shí)例列表，一路篩選，選中目標(biāo)實(shí)例，然后根據(jù)它們的權(quán)重進(jìn)行二次處理，數(shù)據(jù)結(jié)構(gòu)封裝，最后基于Arrays#binarySearch提供的二分查找法來(lái)獲得對(duì)應(yīng)的實(shí)例。

而我們需要注意和學(xué)習(xí)的重點(diǎn)便是權(quán)重獲取算法的思想及具體實(shí)現(xiàn)，最終達(dá)到能夠在實(shí)踐中進(jìn)行運(yùn)用。