Dubbo的负载均衡算法

Stella981
• 阅读 336

[toc]

1 简介

Dubbo提供了4种负载均衡机制:

  • 权重随机算法:RandomLoadBalance
  • 最少活跃调用数算法:LeastActiveLoadBalance
  • 一致性哈希算法:ConsistentHashLoadBalance
  • 加权轮询算法:RoundRobinLoadBalance

Dubbo的负载均衡算法均实现自LoadBalance接口,其类图结构如下:
Dubbo的负载均衡算法

1.1 自适应默认算法

Dubbo的负载均衡算法利用Dubbo的自适应机制,默认的实现为RandomLoadBalance(即:权重随机算法),接口如下:

// 默认为RandomLoadBalance算法
@SPI(RandomLoadBalance.NAME)
public interface LoadBalance {
    // 该方法为自适应方法
    @Adaptive("loadbalance")
    <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException;
}

1.2 抽象基类

1.2.1 选择Invoker

抽象基类针对select()方法判断invokers集合的数量,如果集合中只有一个Invoker,则无需使用算法,直接返回即可:

@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    if (invokers == null || invokers.isEmpty())
        return null;
    // 如果只有一个元素,无需负载均衡算法
    if (invokers.size() == 1)
        return invokers.get(0);
    // 负载均衡算法:该方法为抽象方法,由子类实现
    return doSelect(invokers, url, invocation);
}

1.2.2 计算权重

抽象基类除了对select()方法进行了重写,还封装了服务提供者的权重计算逻辑。Dubbo的权重计算,考虑到服务预热(服务器启动后,以低功率方式运行一段时间,当服务器运行效率逐渐达到最佳状态):

若当前的服务器运行时长小于服务预热时间,对服务器降权,让服务器的权重降低。

protected int getWeight(Invoker<?> invoker, Invocation invocation) {
    // 从URL中获取服务器Invoker的权重信息
    int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
    if (weight > 0) {
        // 获取服务器Invoker的启动时间戳
        long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L);
        if (timestamp > 0L) {
            int uptime = (int) (System.currentTimeMillis() - timestamp);
            // 获取服务器Invoker的预热时长(默认10分钟)
            int warmup = invoker.getUrl().getParameter(Constants.WARMUP_KEY, Constants.DEFAULT_WARMUP);
            if (uptime > 0 && uptime < warmup) {
                weight = calculateWarmupWeight(uptime, warmup, weight);
            }
        }
    }
    return weight;
}
// (uptime / warmup) * weight,即:(启动时长 / 预热时长) * 原权重值
static int calculateWarmupWeight(int uptime, int warmup, int weight) {
    int ww = (int) ((float) uptime / ((float) warmup / (float) weight));
    return ww < 1 ? 1 : (ww > weight ? weight : ww);
}

2 负载均衡算法实现

2.1 加权随机算法

该算法思想简单:假如有服务器:

  • A,权重weight=2
  • B,权重weight=3
  • C,权重weight=5

这些服务器totalWeight = AWeight + BWeight + CWeight = 10。这样生成10以内的随机数

  • [0, 2):属于服务器A
  • [2, 5):属于服务器B
  • [5, 10):属于服务器C

加权随机算法由RandomLoadBalance,其核心源码实现如下:

private final Random random = new Random();

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
    int length = invokers.size();
    // 总权重值
    int totalWeight = 0;
    // 是否所有的Invoker服务器的权重值都相等,若都相等,则在Invoker列表中随机选中一个即可
    boolean sameWeight = true;
    for (int i = 0; i < length; i++) {
        int weight = getWeight(invokers.get(i), invocation);
        totalWeight += weight; // Sum
        if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) {
            sameWeight = false;
        }
    }
    // 生成totalWeight以内的随机数offset,然后该offset挨个减Invoker的权重,一旦小于0,就选中当前的Invoker
    if (totalWeight > 0 && !sameWeight) {
        int offset = random.nextInt(totalWeight);
        for (int i = 0; i < length; i++) {
            offset -= getWeight(invokers.get(i), invocation);
            if (offset < 0) {
                return invokers.get(i);
            }
        }
    }
    return invokers.get(random.nextInt(length));
}

2.2 最小活跃数算法

活跃调用数越小,表明该Provider的效率越高,单位时间内可以处理更多的请求。此时如果有新的请求,应该将请求优先分配给该ProviderDubbo中,每个Provider都会保持一个active,表示该Provider的活跃数:

没收到一个请求,active的值加1,请求处理完成后,active的值减1。

Dubbo使用LeastActiveLoadBalance实现最小活跃数算法,LeastActiveLoadBalance引入了权重,若多个Provider的活跃数相同

则权重较高的Provider被选中的几率更大
若权重相同,则随机选取一个Provider

该算法的核心思想:

  • 循环遍历所有Invoker,找出活跃数最小的所有Invoker

  • 如果有多个Invoker具有多个相同的最小活跃数,此时需要记录这些Invoker。Dubbo使用额外的int数组,来记录这些Invoker在原invokers列表中的索引位置,这种情况下,则需要依据随机权重算法,最终决定该选择的Invoker

    private final Random random = new Random(); @Override protected Invoker doSelect(List<Invoker> invokers, URL url, Invocation invocation) { int length = invokers.size(); // Number of invokers // “最小活跃数”的值 int leastActive = -1; // 具有相同“最小活跃数”的Invoker(即Provider)的数量 int leastCount = 0; // “最小活跃数”的Invoker可能不止一个,因此需要记录所有具有“最小活跃数”的Invoker在invokers列表中的索引位置 int[] leastIndexs = new int[length]; // 记录所有“最小活跃数”的Invoker总的权重值 int totalWeight = 0; // 记录第一个“最小活跃数”的Invoker的权重值 int firstWeight = 0; // 所有的“最小活跃数”的Invoker的权重值是否都相等 boolean sameWeight = true; for (int i = 0; i < length; i++) { Invoker invoker = invokers.get(i); // 活跃数 int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // 权重 int afterWarmup = getWeight(invoker, invocation); if (leastActive == -1 || active < leastActive) { leastActive = active; leastCount = 1; leastIndexs[0] = i; totalWeight = afterWarmup; firstWeight = afterWarmup; sameWeight = true; } else if (active == leastActive) { leastIndexs[leastCount++] = i; totalWeight += afterWarmup; if (sameWeight && i > 0 && afterWarmup != firstWeight) { sameWeight = false; } } } if (leastCount == 1) { return invokers.get(leastIndexs[0]); } if (!sameWeight && totalWeight > 0) { int offsetWeight = random.nextInt(totalWeight) + 1; for (int i = 0; i < leastCount; i++) { int leastIndex = leastIndexs[i]; offsetWeight -= getWeight(invokers.get(leastIndex), invocation); if (offsetWeight <= 0) return invokers.get(leastIndex); } } return invokers.get(leastIndexs[random.nextInt(leastCount)]); }

2.3 一致性哈希

该算法起初用于缓存系统的负载均衡,算法过程如下:

① 根据IP或其他信息为缓存节点生成一个hash值,将该hash值映射到[0, 2^32-1]的圆环中。
② 当查询或写入缓存时,为缓存的key生成一个hash值,查找第一个大于等于该hash值的缓存节点,以应用该缓存
③ 若当前节点挂了,则依然可以计算得到一个新的缓存节点

Dubbo的负载均衡算法

Dubbo通过引入虚拟节点,让所有的Invoker在圆环上分散开,避免数据倾斜(由于节点不够分散,导致大量请求落在同一个节点,而其他节点只会接受到少量请求)。Dubbo对一个Invoker默认使用160个虚拟节点:

如:Invoker1-1, invoker1-2, invoker1-3... invoker1-160

Dubbo的负载均衡算法

Dubbo使用ConsistentHashLoadBalance来实现一致性哈希算法,其内部定义ConsistentHashSelector内部类完成节点选择。Dubbo中使用方法的入参数值进行哈希,来选择落点到哪一个Invoker上。

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    // key:group+version+methodName,即调用方法的完整名称
    // value:ConsistentHashSelector,利用该类完成节点选择
    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors =  new ConcurrentHashMap<>();

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // 获取调用方法名
        String methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;

        // 获取invokers的hashcode
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        // 如果 invokers 是一个新的 List 对象,意味着服务提供者数量发生了变化
        // 此时 selector.identityHashCode != identityHashCode 条件成立
        if (selector == null || selector.identityHashCode != identityHashCode) {
            // 创建新的 ConsistentHashSelector
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }

        // 利用选择器,选择节点
        return selector.select(invocation);
    }
    private static final class ConsistentHashSelector<T> {...}
}

ConsistentHashLoadBalance#doSelect()方法主要是做前置工作,每个方法的一致性哈希选择具体由ConsistentHashSelector来实现:

private static final class ConsistentHashSelector<T> {
    // 使用TreeMap存储Invoker虚拟节点,保证查询效率
    private final TreeMap<Long, Invoker<T>> virtualInvokers;
    // 虚拟节点数量
    private final int replicaNumber;
    // invokers的hashCode值
    private final int identityHashCode;
    // 参数索引数组
    private final int[] argumentIndex;

    ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
        // 获取参与 hash 计算的参数下标值,默认对方法的第一个参数进行 hash 运算
        String[] index = Constants.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]);
        }
        // 如下方法创建虚拟节点,每个invoker生成replicaNumber个虚拟结点,
        for (Invoker<T> invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                byte[] digest = md5(address + i);  // digest是一个长度为16的数组
                // 对 digest 部分字节进行4次 hash 运算,得到四个不同的 long 型正整数
                for (int h = 0; h < 4; h++) {
                    // 根据h的值,对digest进行位运算。h=0,则0~3字节位运算;h=1,则4~7字节位运算。
                    long m = hash(digest, h);  
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }
}    

选择节点,使用TreeMap#tailMap方法,可以获取到TreeMap中大于Key的子Map,子Map中第一个Entry即为选择的Invoker。因为TreeMap不是环形结构,因此如果没有取到任何值,则认为是第一个Key的值。如下: Dubbo的负载均衡算法

public Invoker<T> select(Invocation invocation) {
    // 根据argumentIndex,决定方法的哪几个参数值作为Key
    String key = toKey(invocation.getArguments());
    byte[] digest = md5(key);
    return selectForKey(hash(digest, 0));
}
private Invoker<T> selectForKey(long hash) {
    /*
        TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>();
        tree_map.put(10, "Geeks");
        tree_map.put(15, "4");
        tree_map.put(20, "Geeks");
        tree_map.put(25, "Welcomes");
        tree_map.put(30, "You");
        System.out.println("The tailMap is " + tree_map.tailMap(15));
        // The tailMap is {15=4, 20=Geeks, 25=Welcomes, 30=You}
    */
    Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
    if (entry == null) {
        entry = virtualInvokers.firstEntry();
    }
    return entry.getValue();
}

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();
}

2.4 加权轮询算法

待补充

点赞
收藏
评论区
推荐文章
技术小男生 技术小男生
4个月前
linux环境jdk环境变量配置
1:编辑系统配置文件vi/etc/profile2:按字母键i进入编辑模式,在最底部添加内容:JAVAHOME/opt/jdk1.8.0152CLASSPATH.:$JAVAHOME/lib/dt.jar:$JAVAHOME/lib/tools.jarPATH$JAVAHOME/bin:$PATH3:生效配置
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
小森森 小森森
4个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
晴空闲云 晴空闲云
4个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
3个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序selectfromtable_nameorderiddesc;2.按照指定(多个)字段排序selectfromtable_nameorderiddesc,statusdesc;3.按照指定字段和规则排序selec
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
helloworld_28799839 helloworld_28799839
4个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue