Dubbo学习之负载均衡策略

相关阅读

• Dubbo学习之自动配置
• Dubbo学习之PostProcessor
• Dubbo学习之DubboReference
• Dubbo学习之DubboService

简介

本文基于Spring Boot 2.6.6，dubbo-spring-boot-starter 3.0.6环境。

本文主要分析Dubbo中负载均衡的不同实现；

那么什么是负载均衡呢？
负载均衡改善了跨多个计算资源（例如计算机，计算机集群，网络链接，中央处理单元或磁盘驱动）的工作负载分布。负载平衡旨在优化资源使用，最大化吞吐量，最小化响应时间，并避免任何单个资源的过载。使用具有负载平衡而不是单个组件的多个组件可以通过冗余提高可靠性和可用性。负载平衡通常涉及专用软件或硬件。

Dubbo中提供的负载均衡策略有哪些？

1. RandomLoadBalance：根据权重随机选择，Dubbo默认采用的策略；
2. RoundRobinLoadBalance：加权轮询负载均衡；
3. LeastActiveLoadBalance：最小活跃数负载均衡；
4. ShortestResponseLoadBalance：
5. ConsistentHashLoadBalance：一致性Hash负载均衡策略；

除了以上Dubbo提供的负载均衡策略，Dubbo还通过SPI机制支持自行扩展的负载均衡策略；

源码 LoadBalance 简介

负载均衡接口，定义了从若干个服务中挑选调用服务的接口；

核心方法

@Adaptive("loadbalance")
 Invoker select(List> invokers, URL url, Invocation invocation) throws RpcException;

AbstractLoadBalance 简介

负载均衡接口的抽象实现，各种负载均衡策略实现类的父类，封装了公共的逻辑，实现了select方法的算法模板；

核心方法

public  Invoker select(List> invokers, URL url, Invocation invocation) {
    if (CollectionUtils.isEmpty(invokers)) {
        return null;
    }
    if (invokers.size() == 1) {
        return invokers.get(0);
    }
    // 从多个服务中挑选一个
    return doSelect(invokers, url, invocation);
}

// 算法细节，由子类实现
protected abstract  Invoker doSelect(List> invokers, URL url, Invocation invocation);

// 根据正常运行时间和预热时间比例计算新的权重值
static int calculateWarmupWeight(int uptime, int warmup, int weight) {
    // 计算权重，下面代码逻辑上形似于 (uptime / warmup) * weight。
    // 随着服务运行时间 uptime 增大，权重计算值 ww 会慢慢接近配置值 weight
    int ww = (int) ( uptime / ((float) warmup / weight));
    return ww < 1 ? 1 : (Math.min(ww, weight));
}

// 考虑预热时间的权重
protected int getWeight(Invoker invoker, Invocation invocation) {
    int weight;
    URL url = invoker.getUrl();
    // Multiple registry scenario, load balance among multiple registries.
    if (REGISTRY_SERVICE_REFERENCE_PATH.equals(url.getServiceInterface())) {
        weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
    } else {
        // 从 url 中获取权重 weight 配置值
        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);
}

RandomLoadBalance 简介

加权随机算法的具体实现，它的算法思想很简单。
假设我们有一组服务器servers = [A, B, C]，他们对应的权重为weights = [5, 3, 2]，权重总和为10。现在把这些权重值平铺在一维坐标值上，[0, 5)区间属于服务器A，[5, 8)区间属于服务器B，[8, 10)区间属于服务器C。接下来通过随机数生成器生成一个范围在[0, 10)之间的随机数，然后计算这个随机数会落到哪个区间上。比如数字3会落到服务器A对应的区间上，此时返回服务器A即可。权重越大的机器，在坐标轴上对应的区间范围就越大，因此随机数生成器生成的数字就会有更大的概率落到此区间内。只要随机数生成器产生的随机数分布性很好，在经过多次选择后，每个服务器被选中的次数比例接近其权重比例。比如，经过一万次选择后，服务器A被选中的次数大约为5000次，服务器B被选中的次数约为3000次，服务器C被选中的次数约为2000次。
RandomLoadBalance是一个简单、高效的负载均衡实现，因此Dubbo选择它作为缺省实现。

核心方法

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    int length = invokers.size();

    if (!needWeightLoadBalance(invokers,invocation)){
        // 不需要考虑权重，那么直接随机挑选
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }

    boolean sameWeight = true;
    int[] weights = new int[length];
    // 统计权重总值
    int totalWeight = 0;
    for (int i = 0; i < length; i++) {
        int weight = getWeight(invokers.get(i), invocation);
        totalWeight += weight;
        weights[i] = totalWeight;
        if (sameWeight && totalWeight != weight * (i + 1)) {
            // 存在权重不一致的invoker
            sameWeight = false;
        }
    }
    if (totalWeight > 0 && !sameWeight) {
        // 存在权重值，且所有的invoker的权重值有差异

        // 基于总权重值产生随机值
        int offset = ThreadLocalRandom.current().nextInt(totalWeight);
        // 挑选出随机值落在对应权重范围的invoker
        for (int i = 0; i < length; i++) {
            if (offset < weights[i]) {
                return invokers.get(i);
            }
        }
    }

    // 每个invoker权重相同，那么无需考虑权重，直接随机挑选
    return invokers.get(ThreadLocalRandom.current().nextInt(length));
}

private  boolean needWeightLoadBalance(List> invokers, Invocation invocation) {
    // 选取第一个invokerUrl
    Invoker invoker = invokers.get(0);
    URL invokerUrl = invoker.getUrl();
    if (REGISTRY_SERVICE_REFERENCE_PATH.equals(invokerUrl.getServiceInterface())) {
        String weight = invokerUrl.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY);
        if (StringUtils.isNotEmpty(weight)) {
            return true;
        }
    } else {
        String weight = invokerUrl.getMethodParameter(invocation.getMethodName(), WEIGHT_KEY);
        if (StringUtils.isNotEmpty(weight)) {
            return true;
        }else {
            String timeStamp = invoker.getUrl().getParameter(TIMESTAMP_KEY);
            if (StringUtils.isNotEmpty(timeStamp)) {
                return true;
            }
        }
    }
    return false;
}

RoundRobinLoadBalance 简介

RoundRobinLoadBalance是加权轮询负载均衡的实现；
何为加权轮询？
所谓轮询是指将请求轮流分配给每台服务器。举个例子，我们有三台服务器A、B、C。我们将第一个请求分配给服务器A，第二个请求分配给服务器B，第三个请求分配给服务器C，第四个请求再次分配给服务器A；这个过程就叫做轮询。轮询是一种无状态负载均衡算法，实现简单，适用于每台服务器性能相近的场景下。但现实情况下，我们并不能保证每台服务器性能均相近。如果我们将等量的请求分配给性能较差的服务器，这显然是不合理的。因此，这个时候我们需要对轮询过程进行加权，以调控每台服务器的负载。经过加权后，每台服务器能够得到的请求数比例，接近或等于他们的权重比。比如服务器 A、B、C 权重比为：5:2:1。那么在8次请求中，服务器A将收到其中的5次请求，服务器B会收到其中的2次请求，服务器C则收到其中的1次请求。

核心方法

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
    // 获取 url 到 WeightedRoundRobin 映射表，如果为空，则创建一个新的
    ConcurrentMap map = methodWeightMap.computeIfAbsent(key, k -> new ConcurrentHashMap<>());
    int totalWeight = 0;
    long maxCurrent = Long.MIN_VALUE;
    long now = System.currentTimeMillis();
    Invoker selectedInvoker = null;
    WeightedRoundRobin selectedWRR = null;
    // 下面这个循环主要做了这样几件事情：
    // 1. 遍历 Invoker 列表，检测当前 Invoker 是否有相应的 WeightedRoundRobin，没有则创建
    // 2. 检测 Invoker 权重是否发生了变化，若变化了，则更新 WeightedRoundRobin 的 weight 字段
    // 3. 让 current 字段加上自身权重，等价于 current += weight
    // 4. 设置 lastUpdate 字段，即 lastUpdate = now
    // 5. 寻找具有最大 current 的 Invoker，以及 Invoker 对应的WeightedRoundRobin，暂存起来，留作后用
    // 6. 计算权重总和
    for (Invoker invoker : invokers) {
        String identifyString = invoker.getUrl().toIdentityString();
        int weight = getWeight(invoker, invocation);
        // 检测当前 Invoker 是否有对应的 WeightedRoundRobin，没有则创建
        WeightedRoundRobin weightedRoundRobin = map.computeIfAbsent(identifyString, k -> {
            WeightedRoundRobin wrr = new WeightedRoundRobin();
            wrr.setWeight(weight);
            return wrr;
        });

        if (weight != weightedRoundRobin.getWeight()) {
            weightedRoundRobin.setWeight(weight);
        }
        
        // 让 current 加上自身权重，等价于 current += weight
        long cur = weightedRoundRobin.increaseCurrent();
        // 设置 lastUpdate，表示近期更新过
        weightedRoundRobin.setLastUpdate(now);
        // 找出最大的 current 
        if (cur > maxCurrent) {
            maxCurrent = cur;
            // 将具有最大 current 权重的 Invoker 赋值给 selectedInvoker
            selectedInvoker = invoker;
            // 将 Invoker 对应的 weightedRoundRobin 赋值给 selectedWRR，留作后用
            selectedWRR = weightedRoundRobin;
        }
        // 计算权重总和
        totalWeight += weight;
    }
    
    // 对  进行检查，过滤掉长时间未被更新的节点。
    // 该节点可能挂了，invokers 中不包含该节点，所以该节点的 lastUpdate 长时间无法被更新。
    // 若未更新时长超过阈值后，就会被移除掉，默认阈值为60秒。
    if (invokers.size() != map.size()) {
        map.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
    }
    if (selectedInvoker != null) {
        // 让 current 减去权重总和，等价于 current -= totalWeight
        selectedWRR.sel(totalWeight);
        // 返回具有最大 current 的 Invoker
        return selectedInvoker;
    }
    // should not happen here
    return invokers.get(0);
}


// 内部类WeightedRoundRobin
protected static class WeightedRoundRobin {
    // 服务提供者权重
    private int weight;
    // 当前权重
    private AtomicLong current = new AtomicLong(0);
    // 最后一次更新时间
    private long lastUpdate;

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
        // 初始情况下，current = 0
        current.set(0);
    }

    public long increaseCurrent() {
        // current = current + weight；
        return current.addAndGet(weight);
    }

    public void sel(int total) {
        // current = current - total;
        current.addAndGet(-1 * total);
    }

    public long getLastUpdate() {
        return lastUpdate;
    }

    public void setLastUpdate(long lastUpdate) {
        this.lastUpdate = lastUpdate;
    }
}

参考自Nginx的平滑加权轮询负载均衡，每个服务器对应两个权重，分别为weight和currentWeight，其中weight是固定的，currentWeight会动态调整，初始值为0。当有新的请求进来时，遍历服务器列表，让它的currentWeight加上自身权重；遍历完成后，找到最大的currentWeight，并将其减去权重总和，然后返回相应的服务器即可。
假设我们有一组服务器servers = [A, B, C]，他们对应的权重为weights = [5, 1, 1]，权重总和为7，现在有7个请求依次进入负载均衡逻辑，选择过程如下：

请求编号	currentWeight数组	选择结果	减去权重总和后的currentWeight数组
1	[5, 1, 1]	A	[-2, 1, 1]
2	[3, 2, 2]	A	[-4, 2, 2]
3	[1, 3, 3]	B	[ 1, -4, 3]
4	[6,-3, 4]	A	[-1, -3, 4]
5	[4,-2, 5]	C	[ 4, -2, -2]
6	[9,-1,-1]	A	[ 2, -1, -1]
7	[7, 0, 0]	A	[ 0, 0, 0]

LeastActiveLoadBalance 简介

最小活跃数负载均衡。活跃调用数越小，表明该服务提供者效率越高，单位时间内可处理更多的请求，此时应优先将请求分配给该服务提供者。
在具体实现中，每个服务提供者对应一个活跃数active。初始情况下，所有服务提供者活跃数均为0。每收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求，这就是最小活跃数负载均衡算法的基本思想。
除了最小活跃数，LeastActiveLoadBalance在实现上还引入了权重值，所以准确的来说，LeastActiveLoadBalance是基于加权最小活跃数算法实现的。举个例子说明一下，在一个服务提供者集群中，有两个性能优异的服务提供者。某一时刻它们的活跃数相同，此时Dubbo会根据它们的权重去分配请求，权重越大，获取到新请求的概率就越大；如果两个服务提供者权重相同，此时随机选择一个即可。

核心方法

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    int length = invokers.size();
    // 最小的活跃数
    int leastActive = -1;
    // 具有相同“最小活跃数”的服务者提供者（以下用 Invoker 代称）数量
    int leastCount = 0;
    // leastIndexs 用于记录具有相同“最小活跃数”的 Invoker 在 invokers 列表中的下标信息
    int[] leastIndexes = new int[length];
    // 缓存每个invoker的权重
    int[] weights = new int[length];
    // The sum of the warmup weights of all the least active invokers
    int totalWeight = 0;
    // 第一个最小活跃数的 Invoker 权重值，用于与其他具有相同最小活跃数的 Invoker 的权重进行对比，
    int firstWeight = 0;
    // 以检测是否“所有具有相同最小活跃数的 Invoker 的权重”均相等
    boolean sameWeight = true;


    // 遍历 invokers 列表
    for (int i = 0; i < length; i++) {
        Invoker invoker = invokers.get(i);
        // 获取 Invoker 对应的活跃数
        int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
        // 获取权重，默认值为100
        int afterWarmup = getWeight(invoker, invocation);
        // 缓存权重值
        weights[i] = afterWarmup;
        // 发现更小的活跃数，重新开始
        if (leastActive == -1 || active < leastActive) {
            // 使用当前活跃数 active 更新最小活跃数 leastActive
            leastActive = active;
            // 更新 leastCount 为 1
            leastCount = 1;
            // 记录当前下标值到 leastIndexs 中
            leastIndexes[0] = i;
            // 重设总权重值
            totalWeight = afterWarmup;
            // Record the weight the first least active invoker
            firstWeight = afterWarmup;
            // 设置权重相等标识
            sameWeight = true;
        } else if (active == leastActive) {
            // 当前 Invoker 的活跃数 active 与最小活跃数 leastActive 相同 

            // 在 leastIndexs 中记录下当前 Invoker 在 invokers 集合中的下标
            leastIndexes[leastCount++] = i;
            // 累加权重
            totalWeight += afterWarmup;
            // 检测当前 Invoker 的权重与 firstWeight 是否相等，
            if (sameWeight && afterWarmup != firstWeight) {
                // 不相等则将 sameWeight 置为 false
                sameWeight = false;
            }
        }
        // 当前invoker权重值大于最小权重，则无需处理
    }
    // 当只有一个 Invoker 具有最小活跃数，此时直接返回该 Invoker 即可
    if (leastCount == 1) {
        return invokers.get(leastIndexes[0]);
    }
    
    // 有多个 Invoker 具有相同的最小活跃数，但它们之间的权重不同
    if (!sameWeight && totalWeight > 0) {
        // 随机生成一个 [0, totalWeight) 之间的数字
        int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
        // 循环让随机数减去具有最小活跃数的 Invoker 的权重值，
        // 当 offset 小于等于0时，返回相应的 Invoker
        for (int i = 0; i < leastCount; i++) {
            int leastIndex = leastIndexes[i];
            offsetWeight -= weights[leastIndex];
            if (offsetWeight < 0) {
                return invokers.get(leastIndex);
            }
        }
    }
    // 如果权重相同或总权重为0时，随机返回一个Invoker
    return invokers.get(leastIndexes[ThreadLocalRandom.current().nextInt(leastCount)]);
}


// RpcStatus.java
private static final ConcurrentMap> METHOD_STATISTICS = new ConcurrentHashMap>();

public static RpcStatus getStatus(URL url, String methodName) {
    String uri = url.toIdentityString();
    ConcurrentMap map = METHOD_STATISTICS.computeIfAbsent(uri, k -> new ConcurrentHashMap<>());
    return map.computeIfAbsent(methodName, k -> new RpcStatus());
}

主要逻辑如下：

1. 遍历invokers列表，寻找活跃数最小的Invoker；
2. 如果有多个Invoker具有相同的最小活跃数，此时记录下这些Invoker在invokers集合中的下标，并累加它们的权重，比较它们的权重值是否相等；
3. 如果只有一个Invoker具有最小的活跃数，此时直接返回该Invoker即可；
4. 如果有多个Invoker具有最小活跃数，且它们的权重不相等，此时处理方式和RandomLoadBalance一致；
5. 如果有多个Invoker具有最小活跃数，但它们的权重相等，此时随机返回一个即可；

ShortestResponseLoadBalance 简介

最短响应时间负载均衡，和最小活跃数负载均衡类似，响应时间越短，表明该服务提供者效率越高，此时应优先将请求分配给该服务提供者。
在具体实现中，每个服务提供者对应一个统计数据SlideWindowData，用于预估该Invoker处理本次请求所要的响应时间。
除了最短响应时间，ShortestResponseLoadBalance在实现上还引入了权重值，所以准确的来说，ShortestResponseLoadBalance是基于加权最短响应时间算法实现的。举个例子说明一下，在一个服务提供者集群中，有两个性能优异的服务提供者。对于某个请求它们预估所需的响应时间相同，此时Dubbo会根据它们的权重去分配请求，权重越大，获取到新请求的概率就越大；如果两个服务提供者权重相同，此时随机选择一个即可。

核心方法

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    int length = invokers.size();
    // 最短响应时间
    long shortestResponse = Long.MAX_VALUE;
    // 具有相同“最短响应时间”的服务者提供者（以下用 Invoker 代称）数量
    int shortestCount = 0;
    // 用于记录具有相同“最短响应时间”的 Invoker 在 invokers 列表中的下标信息
    int[] shortestIndexes = new int[length];
    // 记录权重
    int[] weights = new int[length];
    // 记录总权重
    int totalWeight = 0;
    // 记录第一个具有“最短响应时间”的Invoker的权重
    int firstWeight = 0;
    // 以检测是否“所有具有相同最短响应时间的 Invoker 的权重”均相等
    boolean sameWeight = true;

    // 遍历 invokers 列表
    for (int i = 0; i < length; i++) {
        Invoker invoker = invokers.get(i);
        RpcStatus rpcStatus = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
        // 获取 Invoker 对应的统计数据
        SlideWindowData slideWindowData = methodMap.computeIfAbsent(rpcStatus, SlideWindowData::new);

        // 计算响应时间
        long estimateResponse = slideWindowData.getEstimateResponse();
        int afterWarmup = getWeight(invoker, invocation);
        weights[i] = afterWarmup;
        // 发现更短的响应时间，重新开始
        if (estimateResponse < shortestResponse) {
            // 使用当前响应时间更新最短相应时间
            shortestResponse = estimateResponse;
            // 更新 shortestCount 为1
            shortestCount = 1;
            // 记录当前下标值到 shortestIndexes 中
            shortestIndexes[0] = i;
            totalWeight = afterWarmup;
            firstWeight = afterWarmup;
            sameWeight = true;
        } else if (estimateResponse == shortestResponse) {
            // 当前 Invoker 的响应时间与最短响应时间相同

            // 在 shortestIndexes 中记录下当前 Invoker 在 invokers 集合中的下标
            shortestIndexes[shortestCount++] = i;
            // 累加权重
            totalWeight += afterWarmup;
            // 检测当前 Invoker 的权重与 firstWeight 是否相等，
            // 不相等则将 sameWeight 置为 false
            if (sameWeight && i > 0
                && afterWarmup != firstWeight) {
                sameWeight = false;
            }
        }
    }

    // 检查是否需要重设滑动窗口数据
    if (System.currentTimeMillis() - lastUpdateTime > slidePeriod
        && onResetSlideWindow.compareAndSet(false, true)) {
        // 异步方式
        executorService.execute(() -> {
            methodMap.values().forEach(SlideWindowData::reset);
            lastUpdateTime = System.currentTimeMillis();
            onResetSlideWindow.set(false);
        });
    }

    // 当只有一个 Invoker 具有最小活跃数，此时直接返回该 Invoker 即可
    if (shortestCount == 1) {
        return invokers.get(shortestIndexes[0]);
    }
    
    // 有多个 Invoker 具有相同的最小活跃数，但它们之间的权重不同
    if (!sameWeight && totalWeight > 0) {
        // 随机生成一个 [0, totalWeight) 之间的数字
        int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
        // 循环让随机数减去具有最小活跃数的 Invoker 的权重值，
        // 当 offsetWeight 小于等于0时，返回相应的 Invoker
        for (int i = 0; i < shortestCount; i++) {
            int shortestIndex = shortestIndexes[i];
            // 获取权重值，并让随机数减去权重值
            offsetWeight -= weights[shortestIndex];
            if (offsetWeight < 0) {
                return invokers.get(shortestIndex);
            }
        }
    }
    // 如果权重相同或权重为0时，随机返回一个 Invoker
    return invokers.get(shortestIndexes[ThreadLocalRandom.current().nextInt(shortestCount)]);
}


// 内部类，滑动窗口数据
protected static class SlideWindowData {

    private long succeededOffset;
    private long succeededElapsedOffset;
    private RpcStatus rpcStatus;

    public SlideWindowData(RpcStatus rpcStatus) {
        this.rpcStatus = rpcStatus;
        this.succeededOffset = 0;
        this.succeededElapsedOffset = 0;
    }

    public void reset() {
        this.succeededOffset = rpcStatus.getSucceeded();
        this.succeededElapsedOffset = rpcStatus.getSucceededElapsed();
    }

    private long getSucceededAverageElapsed() {
        long succeed = this.rpcStatus.getSucceeded() - this.succeededOffset;
        if (succeed == 0) {
            return 0;
        }
        return (this.rpcStatus.getSucceededElapsed() - this.succeededElapsedOffset) / succeed;
    }

    public long getEstimateResponse() {
        int active = this.rpcStatus.getActive() + 1;
        return getSucceededAverageElapsed() * active;
    }
}

ConsistentHashLoadBalance 简介

一致性hash算法提出之初是用于大规模缓存系统的负载均衡。它的工作过程是这样的，首先根据ip或者其他的信息为缓存节点生成一个hash，并将这个hash投射到[0, 2^32 - 1]的圆环上；当有查询或写入请求时，则为缓存项的key生成一个hash值。然后查找第一个大于或等于该hash值的缓存节点，并到这个节点中查询或写入缓存项。如果当前节点挂了，则在下一次查询或写入缓存时，为缓存项查找另一个大于其hash值的缓存节点即可。
大致效果如下图所示，每个缓存节点在圆环上占据一个位置。如果缓存项的key的hash值小于缓存节点hash值，则到该缓存节点中存储或读取缓存项。比如下面绿色点对应的缓存项将会被存储到 cache-2节点中。由于cache-3挂了，原本应该存到该节点中的缓存项最终会存储到cache-4节点中。

在Dubbo中，把上图的缓存节点替换成Dubbo的服务提供者，于是得到了下图：

这里相同颜色的节点均属于同一个服务提供者，比如Invoker1-1、Invoker1-2、……, Invoker1-160，这样做的目的是通过引入虚拟节点，让Invoker在圆环上分散开来，避免数据倾斜问题。所谓数据倾斜是指，由于节点不够分散，导致大量请求落到了同一个节点上，而其他节点只会接收到了少量请求的情况。

核心方法

protected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {
    String methodName = RpcUtils.getMethodName(invocation);
    String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
    // 获取 invokers 原始的 hashcode
    int invokersHashCode = getCorrespondingHashCode(invokers);
    ConsistentHashSelector selector = (ConsistentHashSelector) selectors.get(key);
    // 如果 invokers 是一个新的 List 对象，意味着服务提供者数量发生了变化，可能新增也可能减少了。
    // 此时 selector.identityHashCode != identityHashCode 条件成立
    if (selector == null || selector.identityHashCode != invokersHashCode) {
        // 创建新的 ConsistentHashSelector
        selectors.put(key, new ConsistentHashSelector(invokers, methodName, invokersHashCode));
        selector = (ConsistentHashSelector) selectors.get(key);
    }
    // 调用 ConsistentHashSelector 的 select 方法选择 Invoker
    return selector.select(invocation);
}

ConsistentHashLoadBalance使用了内部类ConsistentHashSelector，先分析其初始化过程，代码如下：

private static final class ConsistentHashSelector {

    // 使用 TreeMap 存储 Invoker 虚拟节点
    private final TreeMap> virtualInvokers;
    private final int replicaNumber;
    private final int identityHashCode;
    private final int[] argumentIndex;
    private Map serverRequestCountMap = new ConcurrentHashMap<>();
    private AtomicLong totalRequestCount;
    private int serverCount;
    private static final double OVERLOAD_RATIO_THREAD = 1.5F;

    ConsistentHashSelector(List> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        // 获取虚拟节点数，默认为160
        this.replicaNumber = url.getMethodParameter(methodName, HASH_NODES, 160);
        // 获取参与 hash 计算的参数下标值，默认对第一个参数进行 hash 运算
        String[] index = 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 invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                // 对 address + i 进行 md5 运算，得到一个长度为16的字节数组
                byte[] digest = Bytes.getMD5(address + i);
                // 对 digest 部分字节进行4次 hash 运算，得到四个不同的 long 型正整数
                for (int h = 0; h < 4; h++) {
                    // h = 0 时，取 digest 中下标为 0 ~ 3 的4个字节进行位运算
                    // h = 1 时，取 digest 中下标为 4 ~ 7 的4个字节进行位运算
                    // h = 2, h = 3 时过程同上
                    long m = hash(digest, h);
                    // 将 hash 到 invoker 的映射关系存储到 virtualInvokers 中，
                    // virtualInvokers 需要提供高效的查询操作，因此选用 TreeMap 作为存储结构
                    virtualInvokers.put(m, invoker);
                }
            }
        }

        totalRequestCount = new AtomicLong(0);
        serverCount = invokers.size();
        serverRequestCountMap.clear();
    }
}

ConsistentHashSelector的构造方法执行了一系列的初始化逻辑，比如从配置中获取虚拟节点数以及参与hash计算的参数下标，默认情况下只使用第一个参数进行hash。需要特别说明的是，ConsistentHashLoadBalance的负载均衡逻辑只受参数值影响，具有相同参数值的请求将会被分配给同一个服务提供者。

在获取虚拟节点数和参数下标配置后，接下来要做的事情是计算虚拟节点hash值，并将虚拟节点存储到TreeMap中。
到此，ConsistentHashSelector初始化工作就完成了，接下来，分析select方法，代码如下：

public Invoker select(Invocation invocation) {
    // 将参数转为 key
    String key = toKey(invocation.getArguments());
    // 对参数 key 进行 md5 运算
    byte[] digest = Bytes.getMD5(key);
    // 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 方法，
    // 寻找合适的 Invoker
    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 selectForKey(long hash) {
    // 到 TreeMap 中查找第一个节点值大于或等于当前 hash 的 Invoker
    Map.Entry> entry = virtualInvokers.ceilingEntry(hash);
    // 如果 hash 大于 Invoker 在圆环上最大的位置，此时 entry = null，
    // 需要将 TreeMap 的头节点赋值给 entry
    if (entry == null) {
        entry = virtualInvokers.firstEntry();
    }

    String serverAddress = entry.getValue().getUrl().getAddress();

    // 请求上限
    double overloadThread = ((double) totalRequestCount.get() / (double) serverCount) * OVERLOAD_RATIO_THREAD;

    while (serverRequestCountMap.containsKey(serverAddress)
        && serverRequestCountMap.get(serverAddress).get() >= overloadThread) {
        // 如果找到的Invoker当前的请求量已超过请求上限，那么寻找下一个invoker
        entry = getNextInvokerNode(virtualInvokers, entry);
        serverAddress = entry.getValue().getUrl().getAddress();
    }
    // 保存当前serverAddress的请求量信息
    if (!serverRequestCountMap.containsKey(serverAddress)) {
        serverRequestCountMap.put(serverAddress, new AtomicLong(1));
    } else {
        serverRequestCountMap.get(serverAddress).incrementAndGet();
    }
    // 记录请求总数
    totalRequestCount.incrementAndGet();

    return entry.getValue();
}