作者：vivo 互聯網中間件團隊- Wang Xiaochuang

本文主要介紹在vivo內部針對Dubbo路由模塊及負載均衡的一些優化手段，主要是異步化+緩存，可減少在RPC調用過程中路由及負載均衡的CPU消耗，極大提升調用效率。

一、概要

vivo內部Java技術棧業務使用的是Apache Dubbo框架，基于開源社區2.7.x版本定制化開發。在海量微服務集群的業務實踐中，我們發現Dubbo有一些性能瓶頸的問題會極大影響業務邏輯的執行效率，尤其是在集群規模數量較大時(提供方數量>100)，路由及負載均衡方面有著較大的CPU消耗，從采集的火焰圖分析高達30%。為此我們針對vivo內部常用路由策略及負載均衡進行相關優化，并取得了較好的效果。接下來主要跟大家分析一下相關問題產生的根源，以及我們采用怎樣的方式來解決這些問題。（當前vivo內部使用的Dubbo的主流版本是基于2.7.x進行相關定制化開發。）

二、背景知識

2.1 Dubbo客戶端調用流程

1.相關術語介紹

2.主要流程

客戶端通過本地代理Proxy調用ClusterInvoker，ClusterInvoker從服務目錄Directory獲取服務列表后經過路由鏈獲取新的服務列表、負載均衡從路由后的服務列表中根據不同的負載均衡策略選取一個遠端Invoker后再發起遠程RPC調用。

2.2 Dubbo路由機制

Dubbo的路由機制實際是基于簡單的責任鏈模式實現，同時Router繼承了Comparable接口，自定義的路由可以設置不同的優先級進而定制化責任鏈上Router的順序?；谪熑捂溎Ｊ娇梢灾С侄喾N路由策略串行執行如就近路由+標簽路由，或條件路由+就近路由等，且路由的配置支持基于接口級的配置也支持基于應用級的配置。常見的路由方式主要有：就近路由，條件路由，標簽路由等。具體的執行過程如下圖所示：

1. 核心類

Dubbo路由的核心類主要有：RouterChain、RouterFactory 與 Router 。

（1）RouterChain

RouterChain是路由鏈的入口，其核心字段有

invokers（List 類型）

初始服務列表由服務目錄Directory設置，當前RouterChain要過濾的Invoker集合

builtinRouters（List類型）

當前RouterChain包含的自動激活的Router集合

routers（List類型）

包括所有要使用的路由由builtinRouters加上通過addRouters()方法添加的Router對象

RouterChain核心邏輯

public class RouterChain {


    // 注冊中心最后一次推送的服務列表
    private List> invokers = Collections.emptyList();


    // 所有路由,包括原生Dubbo基于注冊中心的路由規則如“route://” urls .
    private volatile List routers = Collections.emptyList();


    // 初始化自動激活的路由
    private List builtinRouters = Collections.emptyList();
  
   private RouterChain(URL url) {
    //通過ExtensionLoader加載可自動激活的RouterFactory
        List extensionFactories = ExtensionLoader.getExtensionLoader(RouterFactory.class)
                .getActivateExtension(url, ROUTER_KEY);
    // 由工廠類生成自動激活的路由策略
        List routers = extensionFactories.stream()
                .map(factory -> factory.getRouter(url))
                .collect(Collectors.toList());


        initWithRouters(routers);
    }
  
    // 添加額外路由
    public void addRouters(List routers) {
        List newRouters = new ArrayList<>();
        newRouters.addAll(builtinRouters);
        newRouters.addAll(routers);
        Collections.sort(newRouters, comparator);
        this.routers = newRouters;
    }
  
   public List> route(URL url, Invocation invocation) {
        List> finalInvokers = invokers;
    // 遍歷全部的Router對象，執行路由規則
        for (Router router : routers) {
            finalInvokers = router.route(finalInvokers, url, invocation);
        }
        return finalInvokers;
    }
}

（2）RouterFactory為Router的工廠類

RouterFactory接口定義

@SPI
public interface RouterFactory {


    @Adaptive("protocol")
    Router getRouter(URL url);
}

（3）Router

Router是真正的路由實現策略，由RouterChain進行調用，同時Router繼承了Compareable接口，可以根據業務邏輯設置不同的優先級。

Router主要接口定義

public interface Router extends Comparable {


   
    /**
     *
     * @param invokers   帶過濾實例列表
     * @param url        消費方url
     * @param invocation 會話信息
     * @return routed invokers
     * @throws RpcException
     */
     List> route(List> invokers, URL url, Invocation invocation) throws RpcException;




    /**
     * 當注冊中心的服務列表發現變化，或有動態配置變更會觸發實例信息的變化
     * 當時2.7.x的Dubbo并沒有真正使用這個方法，可基于此方法進行路由緩存
     * @param invokers invoker list
     * @param       invoker's type
     */
    default  void notify(List> invokers) {


    }


}

2.同機房優先路由的實現

為方便大家了解路由的實現，給大家展示一下就近路由的核心代碼邏輯

public  List> route(List> invokers, URL consumerUrl, Invocation invocation) throws RpcException {
        if (!this.enabled) {
            return invokers;
        }


      
    // 獲取本地機房信息
        String local = getSystemProperty(LOC);
        if (invokers == null || invokers.size() == 0) {
            return invokers;
        }
        List> result = new ArrayList>();
        for (Invoker invoker: invokers) {
      // 獲取與本地機房一致的invoker并加入列表中
            String invokerLoc = getProperty(invoker, invocation, LOC);
            if (local.equals(invokerLoc)) {
                result.add(invoker);
            }
        }


        if (result.size() > 0) {
            if (fallback){
                // 開啟服務降級，available.ratio = 當前機房可用服務節點數量 ／ 集群可用服務節點數量
                int curAvailableRatio = (int) Math.floor(result.size() * 100.0d / invokers.size());
                if (curAvailableRatio <= availableRatio) {
                    return invokers;
                }
            }


            return result;
        } else if (force) {
            return result;
        } else {
            return invokers;
        }


    }

2.3 Dubbo負載均衡

Dubbo的負載均衡實現比較簡單基本都是繼承抽象類進行實現，主要作用就是根據具體的策略在路由之后的服務列表中篩選一個實例進行遠程RPC調用，默認的負載均衡策略是隨機。

整體類圖如下所示：

LoadBalance接口定義

@SPI(RandomLoadBalance.NAME)
public interface LoadBalance {


    /**
     * 從服務列表中篩選一個.
     *
     * @param invokers   invokers.
     * @param url        refer url
     * @param invocation invocation.
     * @return selected invoker.
     */
    @Adaptive("loadbalance")
     Invoker select(List> invokers, URL url, Invocation invocation) throws RpcException;


}

隨機負載均衡核心代碼解析

   // 預熱過程權重計算
   static int calculateWarmupWeight(int uptime, int warmup, int weight) {
        int ww = (int) (uptime / ((float) warmup / weight));
        return ww < 1 ? 1 : (Math.min(ww, weight));
    }


int getWeight(Invoker invoker, Invocation invocation) {
       int weight;
       URL url = invoker.getUrl();
       // 多注冊中心場景下的，注冊中心權重獲取
       if (UrlUtils.isRegistryService(url)) {
           weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
       } else {
           weight = url.getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT);
           if (weight > 0) {
               // 獲取實例啟動時間
               long timestamp = invoker.getUrl().getParameter(TIMESTAMP_KEY, 0L);
               if (timestamp > 0L) {
                   long uptime = System.currentTimeMillis() - timestamp;
                   if (uptime < 0) {
                       return 1;
                   }
                   // 獲取預熱時間
                   int warmup = invoker.getUrl().getParameter(WARMUP_KEY, DEFAULT_WARMUP);
                   if (uptime > 0 && uptime < warmup) {
                       weight = calculateWarmupWeight((int)uptime, warmup, weight);
                   }
               }
           }
       }
       return Math.max(weight, 0);
   }


@Override
    protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
        // Number of invokers
        int length = invokers.size();
        // Every invoker has the same weight?
        boolean sameWeight = true;
        // the weight of every invokers
        int[] weights = new int[length];
        // the first invoker's weight
        int firstWeight = getWeight(invokers.get(0), invocation);
        weights[0] = firstWeight;
        // The sum of weights
        int totalWeight = firstWeight;
        for (int i = 1; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            // save for later use
            weights[i] = weight;
            // Sum
            totalWeight += weight;
            if (sameWeight && weight != firstWeight) {
                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 = ThreadLocalRandom.current().nextInt(totalWeight);
            // Return a invoker based on the random value.
            for (int i = 0; i < length; i++) {
                offset -= weights[i];
                if (offset < 0) {
                    return invokers.get(i);
                }
            }
        }
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }

預熱解釋

預熱是為了讓剛啟動的實例流量緩慢增加,因為實例剛啟動時各種資源可能還沒建立連接，相關代碼可能還是處于解釋執行，仍未變為JIT執行，此時業務邏輯較慢，不應該加載過大的流量，否則有可能造成較多的超時。Dubbo默認預熱時間為10分鐘，新部署的實例的流量會在預熱時間段內層線性增長，最終與其他實例保持一致。Dubbo預熱機制的實現就是通過控制權重來實現。如默認權重100，預熱時間10分鐘，則第一分鐘權重為10，第二分鐘為20，以此類推。

具體預熱效果圖如下：

三、問題分析

使用Dubbo的業務方反饋，他們通過火焰圖分析發現Dubbo的負載均衡模塊+路由模塊占用CPU超過了30%，框架層面的使用率嚴重影響了業務邏輯的執行效率急需進行優化。通過火焰圖分析，具體占比如下圖，其中該機器在業務忙時的CPU使用率在60%左右，閑時在30%左右。

通過火焰圖分析，負載均衡主要的消耗是在 getWeight方法。

路由的主要消耗是在route方法：

同機房優先路由

接口級標簽路由+應用級標簽路由

這些方法都有一個特點，那就是遍歷執行。如負載均衡，針對每一個invoker都需要通過getWeight方法進行權重的計算；就近路由的router方法對于每一個invoker都需要通過url獲取及機房信息進行匹配計算。

我們分析一下getWeight及router時間復雜度，發現是O(n)的時間復雜度，而且路由是由路由鏈組成的，每次每個 Router的route方法調用邏輯都會遍歷實例列表，那么當實例列表數量過大時，每次匹配的計算的邏輯過大，那么就會造成大量的計算成本，導致占用大量cpu，同時也導致路由負載均衡效率低下。

綜上所述，罪惡的的根源就是遍歷導致的，當服務提供方數量越多，影響越大。

四、優化方案

知道了問題所在，我們來分析一下是否有優化空間。

4.1 路由優化

1. 優化一：關閉無效路由

通過火焰圖分析，我們發現有部分業務即使完全不使用應用級的標簽路由，原生的TagRouter也存在遍歷邏輯，原因是為了支持靜態的標簽路由，其實這部分的開銷也不少，那對于根本不會使用應用級標簽路由的可以手動進行關閉。關閉方式如下：

客戶端統一關閉

dubbo.consumer.router=-tag

服務級別關閉

注解方式：

@DubboReference(parameters = {"router","-tag"})

xml方式：

2. 優化二：提前計算路由結果并進行緩存

每次路由目前都是進行實時計算，但是在大多數情況下，我們的實例列表是穩定不變的，只有在發布窗口或配置變更窗口內實例列表才會發生變更，那我們是否可以考慮緩存呢。如就近路由，可以以機房為key進行機房實例的全量緩存。針對接口級標簽路由可以緩存不同標簽值指定的實例信息。

我們知道路由的執行過程是責任鏈模式，每一個Router的實例列表入參實際上是一個Router的結果，可參考公式：target = rn(…r3(r2(r1(src))))。那么所有的路由可以基于注冊中心推送的原始服務列表進行路由計算并緩存，然后不同的路由結果相互取交集就能得到最終的結果，當實例信息發生變更時，緩存失效并重新計算。

3. 緩存更新時機

當注冊中心或者動態配置有變更時，相關通知會給到服務目錄Directory,Directory收到通知后會重新創建服務列表，并把服務列表同步到路由鏈RouterChain，RouterChain再按順序通知其鏈上的Router,各個Router再進行緩存清除并重新進行路由結果的計算及進行緩存。相關時序圖如下所示：

4. 具體路由流程

進入具體路由方法時，先判斷是否存在緩存的路由值，且緩存值的epoch必須與上一個路由的epoch需一致，此時緩存才生效，然后緩存值與上個Router的結果取交集。

如果不存在緩存或epoch不一致則重新進行實時的路由計算。

引入epoch的原因主要是保證各個路由策略緩存信息的一致性，保證所有的緩存計算都是基于同一份原始數據。當實例信息發生變更時，epoch會自動進行更新。

5. BitMap引入

上文我們說到，不同的路由策略之間的結果是取交集的，然后最終的結果才送入負載均衡流程。那如何在緩存的同時，加快交集的計算呢。答案就是基于位圖：BitMap。

BitMap的基本原理就是用一個bit位來存放某種狀態，適用于大規模數據的查找及位運算操作。如在路由場景，先基于全量的推送數據進行計算緩存。如果某個實例被路由選中，則其值為1，若兩個路由的結果要取交集，那直接對BitMap進行"&"運行即可。

全量緩存示意圖：

路由交集計算示步驟：

按照路由鏈依次計算，

tagRouter->vivoTag->vivoNearestRouter

（1）tagRouter計算邏輯：

按照Invocation計算出目標的Tag,假設是tag1

然后從緩存Cache根據key:tag1,取出對應的targetAddrPool

將原始傳入的addrPool

與targetAddrPool

得到結果resultAddrPool

將resultAddrPool傳入vivoTagRouter

（2）vivoTag計算邏輯：

按照Invocation計算出目標的Tag,假設是tabB

然后從緩存Cache根據key:tag1，取出對應的targetAddrPool

將上一次傳入的addrPool

與targetAddrPool

得到結果resultAddrPooll

將resultAddrPool傳入

vivoNearestRouter

（3）vivoNearestRouter計算邏輯

從環境變量取出當前機房，假設是bj01

然后從緩存Cache根據key:bj01，取出對應的targetAddrPool

將上一次傳入的addrPool

與targetAddrPool

取出resultAddrPool

將上一次傳入的addrPool

與targetAddrPool

得到結果resultAddrPool

將resultAddrPool為最終路由結果，傳遞給LoadBalance

6. 基于緩存的同機房優先路由源碼解析

緩存刷新

 /**
     * Notify router chain of the initial addresses from registry at the first time.
     * Notify whenever addresses in registry change.
     */
    public void setInvokers(List> invokers) {
    // 創建帶epoch的BitList
        this.invokers = new BitList>(invokers == null ? Collections.emptyList() : invokers,createBitListEpoch());
        routers.forEach(router -> router.notify(this.invokers));
    }

同機房優先路由源碼解讀

public  List> route(List> invokers, URL consumerUrl, Invocation invocation) throws RpcException {
        …………//省略非核心代碼
        BitList> bitList = (BitList>) invokers;
    //獲取路由結果
        BitList> result = getNearestInvokersWithCache(bitList);
        if (result.size() > 0) {
            if (fallback) {
                // 開啟服務降級，available.ratio = 當前機房可用服務節點數量 ／ 集群可用服務節點數量
                int curAvailableRatio = (int) Math.floor(result.size() * 100.0d / invokers.size());
                if (curAvailableRatio <= availableRatio) {
                    return invokers;
                }
            }


            return result;
        } else if (force) {
            return result;
        } else {
            return invokers;
        }


    }   
   /**
     * 獲取緩存列表
     * @param invokers
     * @param 
     * @return
     */
    private  BitList> getNearestInvokersWithCache(BitList> invokers) {
        ValueWrapper valueWrapper = getCache(getSystemProperty(LOC));
        // 是否存在緩存
        if (valueWrapper != null) {
            BitList> invokerBitList = (BitList>) valueWrapper.get();
            // 緩存的epoch與源列表是否一致
            if (invokers.isSameEpoch(invokerBitList)) {
                BitList> tmp = invokers.clone();
                // 結果取交集
                return tmp.and(invokerBitList);
            }
        }
        // 緩存不存在 實時計算放回
        return getNearestInvokers(invokers);
    }
  
  /**
     * 新服務列表通知
     * @param invokers
     * @param 
     */
 @Override
    public  void notify(List> invokers) {
        clear();
        if (invokers != null && invokers instanceof BitList) {
            BitList> bitList = (BitList>) invokers;
      // 設置最后一次更新的服務列表
            lastNotify = bitList.clone();
            if (!CollectionUtils.isEmpty(invokers) && this.enabled) {
        // 獲取機房相同的服務列表并進行緩存
                setCache(getSystemProperty(LOC), getNearestInvokers(lastNotify));
            }
        }
    }

4.2 負載均衡優化

1.優化一

針對getWeight方法，我們發現有部分業務邏輯較為消耗cpu,但是在大多數場景下業務方并不會使用到，于是進行優化。

getWeight方法優化

優化前：
//這里主要要用多注冊中心場景下，注冊中心權重的獲取，絕大多數情況下并不會有這個邏輯
 if (UrlUtils.isRegistryService(url)) {
           weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
       }  
優化后：
 if (invoker instanceof ClusterInvoker && UrlUtils.isRegistryService(url)) {
            weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
   }

2.優化二

遍歷是罪惡的源泉，而實例的數量決定這罪惡的深淺，我們有什么辦法減少負載均衡過程中的遍歷呢。一是根據group及version劃分不同的集群，但是這需要涉及到業務方代碼或配置層面的改動，會帶來額外的成本。所以我們放棄了。

二是沒有什么是加一層解決不了的問題，為了盡量減少進入負載均衡的節點數量，考慮新增一個墊底的路由策略，在走完所有的路由策略后，若節點數量>自定義數量后，進行虛擬分組，虛擬分組的策略也可進行自定義，然后隨機篩選一組進入負載均衡。此時進入負載均衡的實例數量就會有倍數的下降。

需要注意的是分組路由必須保證是在路由鏈的最后一環，否則會導致其他路由計算錯誤。

分組路由示意

  /**
     * 
     * @param invokers 待分組實例列表
     * @param groupNum 分組數量
     * @param 
     * @return
     */
    public  List> doGroup(List> invokers, int groupNum) {
        int listLength = invokers.size() / groupNum;
        List> result = new ArrayList<>(listLength);
        int random = ThreadLocalRandom.current().nextInt(groupNum);
        for (int i = random; i < invokers.size(); i = i + groupNum) {
            result.add(invokers.get(i));
        }
        return result;
    }

五、優化效果

針對優化前和優化后，我們編寫Demo工程分別壓測了不配置路由/配置就近+標簽路由場景。Provider節點梯度設置100/500/1000/2000/5000，TPS在1000左右，記錄了主機的cpu等性能指標，并打印火焰圖。發現，配置路由后，采用相同并發，優化后的版本tps明顯高于優化前版本，且新版本相較于沒有配置路由時tps顯著提高，下游節點數大于2000時，tps提升達到100%以上，下游節點數越多，AvgCpu優化效果越明顯，并且路由及負載均衡CPU占比明顯更低，詳細數據可見下表：

備注：-tag，表示顯式禁用原生Dubbo應用級標簽路由。該路由默認開啟。

六、總結

經過我們關閉不必要的路由邏輯、對路由緩存+異步化計算、新增分組路由等優化后，Dubbo在負載均衡及路由模塊整體的性能有了顯著的提升，為業務方節省了不少CPU資源。在正常業務場景下當提供方數量達到2000及以上時，tps提升可達100%以上，消費方平均CPU使用率下降約27%，且提供方數量越多優化效果越明顯。但是我們也發現當前的隨機負載均衡依然還是會消耗一定的CPU資源，且只能保證流量是均衡的。當前我們的應用基本部署在虛擬機及容器上。這兩者均存在超賣的狀況，且同等配置的宿主機性能存在較大差異等問題。最終會導致部分請求超時、無法最大化利用提供方的資源。我們下一步將會引入Dubbo 3.2的自適應負載均衡并進行調優減少其CPU使用率波動較大的問題，其次我們自身也擴展了基于CPU負載均衡的單一因子算法，最終實現不同性能的機器CPU負載趨于均衡，最大程度發揮集群整體的性能。