首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >sofa-rpc负载均衡之随机算法分析(Random)

sofa-rpc负载均衡之随机算法分析(Random)

作者头像
克虏伯
发布2019-04-15 14:45:14
5530
发布2019-04-15 14:45:14
举报

注意:我们分析的sofa-rpc版本是5.4.0。

                                             图1 RandomLoadBanlancer的类继承图

1.分析的核心重点

    RandomLoadBalancer的方法doSelect(SofaRequest,List<ProviderInfo>)是该算法的核心,下面我们重点来分析该方法的实现。doSelect方法中的源码如下,建议读者自己从github上down源码下来自己看源码。

ProviderInfo providerInfo = null;
int size = providerInfos.size(); // 总个数
int totalWeight = 0; // 总权重
boolean isWeightSame = true; // 权重是否都一样
for (int i = 0; i < size; i++) {
    int weight = getWeight(providerInfos.get(i));
    totalWeight += weight; // 累计总权重
    if (isWeightSame && i > 0 && weight != getWeight(providerInfos.get(i - 1))) {
        isWeightSame = false; // 计算所有权重是否一样
    }
}
if (totalWeight > 0 && !isWeightSame) {
    int offset = random.nextInt(totalWeight);
    for (int i = 0; i < size; i++) {
        offset -= getWeight(providerInfos.get(i));
        if (offset < 0) {
            providerInfo = providerInfos.get(i);
            break;
        }
    }
} else {
    // 如果权重相同或权重为0则均等随机
    providerInfo = providerInfos.get(random.nextInt(size));
}
return providerInfo;

doSelect(SofaRequest,List<ProviderInfo>)的第二个参数List<ProviderInfo>是服务提供者列表信息。ProvideInfo中含有服务提供者的信息,其中有个属性是weight,代表权重,是int类型。

2.累加服务提供者的权重

    最开始的for循环,看下面的代码段,循环服务提供者列表,将所有服务提供者的权重累加得到totalWeight。在循环处理中,如果发现俩个服务提供者的权重不一样就将isWeightSame设置为false。假设服务提供者为A、B、C、D四个,它们的权重分别是3、2、1、4,所以totalWeight是10;由于ABCD的权重不相同,所以isWeightSame为false。

for (int i = 0; i < size; i++) {
    int weight = getWeight(providerInfos.get(i));
    totalWeight += weight; // 累计总权重
    if (isWeightSame && i > 0 && weight != getWeight(providerInfos.get(i - 1))) {
        isWeightSame = false; // 计算所有权重是否一样
    }
}

3.以totalWeight为上限的随机数值逐个减去服务提供者的权重,从而获得服务提供者

    如果totalWeight的值大于0且isWeightSame的值为false。则进入下面的代码段中,首先以totalWeight为上限,生成一个随机正整数,即offset的值。循环服务提供者列表,用offset的值逐个减去每个服务提供者的权重,如果此时offset的值小于0,则取当前的这个服务提供者。步骤2之后,得到的totalWeight(值为10)大于0,且四个服务提供者的权重不相同,所以isWeightSame为false,所以进入下面代码段中的逻辑。首先以totalWeight为上限,生成一个随机正整数,假设这个生成的随机正整数为8,即变量offset的值是8,那么此时取D作为服务提供者——8减去3,再减去2,再减去1,之后值为2,不小于0,再减去4之后的值才小于0。

if (totalWeight > 0 && !isWeightSame) {
    int offset = random.nextInt(totalWeight);
    for (int i = 0; i < size; i++) {
        offset -= getWeight(providerInfos.get(i));
        if (offset < 0) {
            providerInfo = providerInfos.get(i);
            break;
        }
    }
}

4.如果所有服务提供者的权重都一样,则随机取任意一个服务提供者

    与步骤3并列的还有种情况,即所有服务提供者的权重都相同,此时步骤2中得到的isWeightSame为true,所以进入下面的代码段,即以服务提供者的个数为上限,生成一个随机数,假设为i,之后以i为下标,从服务提供者列表中取得服务提供者。

else {
    // 如果权重相同或权重为0则均等随机
    providerInfo = providerInfos.get(random.nextInt(size));
}

5.思考

    为什么会有步骤3中的考虑,为什么没有像步骤4中那样直接随机从服务提供者列表中取一个?

    解答:Good question! 我们以步骤2中的A、B、C、D为例子来解答。如步骤4所示,随机从服务提供者列表取一个,每一个服务提供者被取到的概率是1/4,这种不一定是对的,要分情况。因为A、B、C、D的权重不一致(分别是3、2、1、4),所以A被取到的概率应该是3/(3+2+1+4),B被取到的概率应该是2(3+2+1+4),C被取到的概率应该是1/(3+2+1+4),D被取到的概率应该是4(3+2+1+4)。所以我们可以看出在权重不一致的情况下,直接随机从服务提供者列表中取一个的算法是不对,这就是为什么会有步骤3中的代码。

(adsbygoogle = window.adsbygoogle || []).push({});

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018/05/17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.分析的核心重点
  • 2.累加服务提供者的权重
  • 3.以totalWeight为上限的随机数值逐个减去服务提供者的权重,从而获得服务提供者
  • 4.如果所有服务提供者的权重都一样,则随机取任意一个服务提供者
  • 5.思考
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档