[[418899]]

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

這篇文章，就帶大家從源碼層面分析一下，Nacos客戶端采用了如何的算法來從實例列表中獲取一個實例進行請求的。也可以稱作是Nacos客戶端的負載均衡算法。

單個實例獲取

NamingService不僅提供了獲取實例列表的方法，也提供了獲取單個實例的方法，比如：

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

該方法會根據預定義的負載算法，從實例列表中獲得一個健康的實例。其他重載的方法功能類似，最終都會調用該方法，我們就以此方法為例來分析一下具體的算法。

具體實現代碼：

@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); 
        } 
        // 通過負載均衡算法獲得其中一個實例 
        return Balancer.RandomByWeight.selectHost(serviceInfo); 
    } else { 
        // 獲取ServiceInfo 
        ServiceInfo serviceInfo = clientProxy 
                .queryInstancesOfService(serviceName, groupName, clusterString, 0, false); 
        // 通過負載均衡算法獲得其中一個實例 
        return Balancer.RandomByWeight.selectHost(serviceInfo); 
    } 
} 

selectOneHealthyInstance方法邏輯很簡單，調用我們之前講到的方法獲取ServiceInfo對象，然后作為參數傳遞給負載均衡算法，由負載均衡算法計算出最終使用哪個實例(Instance)。

算法參數封裝

先跟蹤一下代碼實現，非核心業務邏輯，只簡單提一下。

上面的代碼可以看出調用的是Balancer內部類RandomByWeight的selectHost方法：

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

selectHost方法核心邏輯是從ServiceInfo中獲取實例列表，然后調用getHostByRandomWeight方法：

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

getHostByRandomWeight前半部分是將Instance列表及其中的權重數據進行轉換，封裝成一個Pair，也就是建立成對的關系。在此過程中只使用了健康的節點。

真正的算法實現則是通過Chooser類來實現的，看名字基本上知道實現的策略是基于權重的隨機算法。

負載均衡算法實現

所有的負載均衡算法實現均位于Chooser類中，Chooser類的提供了兩個方法refresh和randomWithWeight。

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

randomWithWeight方法基于前面的數據來進行隨機算法處理。

先看refresh方法：

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

基本步驟：

• 創建Ref類，該類為Chooser的內部類;
• 調用Ref的refresh方法，用于準備數據、檢查數據等;
• 數據篩選完成，調用poller#refresh方法，本質上就是創建一個GenericPoller對象;
• 成員變量重新賦值;

這里重點看Ref#refresh方法：

/** 
 * 獲取參與計算的實例列表、計算遞增數組數總和并進行檢查 
 */ 
public void refresh() { 
    // 實例權重總和 
    Double originWeightSum = (double) 0; 
     
    // 所有健康權重求和 
    for (Pair<T> item : itemsWithWeight) { 
         
        double weight = item.weight(); 
        //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
        // 權重小于等于0則不參與計算 
        if (weight <= 0) { 
            continue; 
        } 
        // 有效實例放入列表 
        items.add(item.item()); 
        // 如果值無限大 
        if (Double.isInfinite(weight)) { 
            weight = 10000.0D; 
        } 
        // 如果值為非數字 
        if (Double.isNaN(weight)) { 
            weight = 1.0D; 
        } 
        // 權重值累加 
        originWeightSum += weight; 
    } 
     
    double[] exactWeights = new double[items.size()]; 
    int index = 0; 
    // 計算每個節點權重占比，放入數組 
    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; 
        } 
        // 計算每個節點權重占比 
        exactWeights[index++] = singleWeight / originWeightSum; 
    } 
     
    // 初始化遞增數組 
    weights = new double[items.size()]; 
    double randomRange = 0D; 
    for (int i = 0; i < index; i++) { 
        // 遞增數組第i項值為items前i個值總和 
        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."); 
} 

可結合上面代碼中的注釋來理解，核心步驟包括以下：

• 遍歷itemsWithWeight，計算權重總和數據;非健康節點會被剔除掉;
• 計算每個節點的權重值在總權重值中的占比，并存儲在exactWeights數組當中;
• 將exactWeights數組當中值進行數據重構，形成一個遞增數組weights(每個值都是exactWeights坐標值的總和)，后面用于隨機算法;
• 判斷是否循環完成或誤差在指定范圍內(0.0001)，符合則返回。

所有數據準備完成，調用隨機算法方法randomWithWeight：

public T randomWithWeight() { 
    Ref<T> ref = this.ref; 
    // 生成0-1之間的隨機數 
    double random = ThreadLocalRandom.current().nextDouble(0, 1); 
    // 采用二分法查找數組中指定值，如果不存在則返回（-(插入點) - 1），插入點即隨機數將要插入數組的位置，即第一個大于此鍵的元素索引。 
    int index = Arrays.binarySearch(ref.weights, random); 
    // 如果沒有查詢到（返回-1或"-插入點"） 
    if (index < 0) { 
        index = -index - 1; 
    } else { 
        // 命中直接返回結果 
        return ref.items.get(index); 
    } 
     
    // 判斷坐標未越界 
    if (index < ref.weights.length) { 
        // 隨機數小于指定坐標的數值，則返回坐標值 
        if (random < ref.weights[index]) { 
            return ref.items.get(index); 
        } 
    } 
     
    // 此種情況不應該發生，但如果發生則返回最后一個位置的值 
    /* 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); 
} 

該方法的基本操作如下：

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

至此，關于Nacos客戶端實例獲取的負載均衡算法代碼層面追蹤完畢。

算法實例演示

下面用一個實例來演示一下，該算法中涉及的數據變化。為了數據美觀，這里采用4組數據，每組數據進來確保能被整除;

節點及權重數據(前面節點，后面權重)如下：

1 100 
2 25 
3 75 
4 200 

第一步，計算權重綜合：

originWeightSum = 100 + 25 + 75 + 200 = 400 

第二步，計算每個節點權重比：

exactWeights = {0.25, 0.0625, 0.1875, 0.5} 

第三步，計算遞增數組weights：

weights = {0.25, 0.3125, 0.5, 1} 

第四步，生成0-1的隨機數：

random = 0.3049980013493817 

第五步，調用Arrays#binarySearch從weights中搜索random：

index = -2 

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

插入點即第一個大于此key的元素索引，那么上面第一個大于0.3049980013493817的值為0.3125，那么插入點值為1;

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

index = - ( 1 ) - 1 = -2 

第六步，也就是沒有恰好命中的情況：

index = -( -2 ) - 1 = 1 

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

算法的核心

上面演示了算法，但這個算法真的能夠做到按權重負載嗎?我們來分析一下這個問題。

這個問題的重點不在random值，這個值基本上是隨機的，那么怎么保證權重大的節點獲得的機會更多呢?

這里先把遞增數組weights用另外一個形式來表示：

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

如果把weights理解成一條線，對應節點的值是線上的一個個點，體現在圖中便是(圖2到圖5)有色(灰色+橘黃色)部分。

而Arrays#binarySearch算法的插入點獲取的是第一個大于key(也就是random)的坐標，也就是說每個節點享有的隨機范圍不同，它們的范圍由當前點和前一個點的區間決定，而這個區間正好是權重比值。

權重比值大的節點，占有的區間就比較多，比如節點1占了1/4，節點4占了1/2。這樣，如果隨機數是均勻分布的，那么占有范圍比較大的節點更容易獲得青睞。也就達到了按照權重獲得被調用的機會了。

小結

本篇文章追蹤Nacos客戶端源碼，分析了從實例列表中獲得其中一個實例的算法，也就是隨機權重負載均衡算法。整體業務邏輯比較簡單，從ServiceInfo中獲得實例列表，一路篩選，選中目標實例，然后根據它們的權重進行二次處理，數據結構封裝，最后基于Arrays#binarySearch提供的二分查找法來獲得對應的實例。

而我們需要注意和學習的重點便是權重獲取算法的思想及具體實現，最終達到能夠在實踐中進行運用。