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

注意:我们分析的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({});

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券