基于百分比的路由算法

本文介绍了基于百分比的路由算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

浏览基于百分比的路由，偶然发现了这个主题.

根据以下提议的算法:

对于给定的模型如下:

public class Host { private String name; private int percentageLoad; private int percentageAccum; }

百分比Accum 的初始值是百分比负载的值.

The initial value for percentageAccum is the value of percentageLoad.

收到请求时:

• 选择Accum百分比最大的主机
• 从所选主机的百分比中减去 100
• 将所有主机(包括所选主机)的百分比负载添加到百分比数据

下面是我的实现

@Builder @Data @AllArgsConstructor @NoArgsConstructor public class HostWeightage{ private String hostId; private int weightage; private int accumulatedWeightageSoFar; }

示例 Java 执行程序

---

Sample Java executor

public String getRoutedHost(List<HostWeightage> hostWeightageList) { // assume 0th index as default HostWeightage hostWithMaxAccWeight = hostWeightageList.get(0); // choose the host with the largest percentageAccum for (int i = 1; i < hostWeightageList.size(); i++) { if (hostWeightageList.get(i).getAccumulatedWeightageSoFar() >= hostWithMaxAccWeight.getAccumulatedWeightageSoFar()){ hostWithMaxAccWeight = hostWeightageList.get(i); } } // subtract 100 from the percentageAccum for the chosen host int inverseAccWeight = hostWithMaxAccWeight.getAccumulatedWeightageSoFar() - 100; hostWithMaxAccWeight.setAccumulatedWeightageSoFar(inverseAccWeight); // add percentageLoad to percentageAccum for all hosts, including the chosen host int weight = hostWithMaxAccWeight.getWeightage(); for (HostWeightage wightedHost : hostWeightageList) { int accWeight = wightedHost.getAccumulatedWeightageSoFar(); wightedHost.setAccumulatedWeightageSoFar(weight + accWeight); } return hostWithMaxAccWeight.getHostId(); }

这是我每次运行 10 次调用的示例

---

here is my sample runs for 10 calls each

INFO: initial config HostWeightage(hostId=redirect_host_1, weightage=10, accumulatedWeightageSoFar=10), HostWeightage(hostId=redirect_host_2, weightage=40, accumulatedWeightageSoFar=40), HostWeightage(hostId=redirect_host_3, weightage=50, accumulatedWeightageSoFar=50) final distribution of 10 calls: INFO: host1 3 ( should have been 1) INFO: host2 3 ( should have been 4) INFO: host3 4 ( should have been 5) ------------------------- INFO: initial config HostWeightage(hostId=redirect_host_1, weightage=30, accumulatedWeightageSoFar=30), HostWeightage(hostId=redirect_host_2, weightage=30, accumulatedWeightageSoFar=30), HostWeightage(hostId=redirect_host_3, weightage=40, accumulatedWeightageSoFar=40) final distribution of 10 calls: INFO: host1 3 ( correct output ) INFO: host2 3 ( correct output ) INFO: host3 4 ( correct output ) ------------------------- INFO: initial config HostWeightage(hostId=redirect_host_1, weightage=10, accumulatedWeightageSoFar=10), HostWeightage(hostId=redirect_host_2, weightage=20, accumulatedWeightageSoFar=20), HostWeightage(hostId=redirect_host_3, weightage=70, accumulatedWeightageSoFar=70) final distribution of 10 calls: INFO: host1 3 ( should have been 1 ) INFO: host2 3 ( should have been 2 ) INFO: host3 4 ( should have been 7 )

感谢任何指出算法实现错误的指针！！

any pointers to what is wrong in algo implementation is appreciated!!

推荐答案

问题出在代码末尾的循环中.由于以下行，它对所有主机使用相同的权重:

The problem is in the loop at the end of the code. It's using the same weight for all of the hosts, due to the line:

int weight = hostWithMaxAccWeight.getWeightage();

添加到每个主机的累加器的权重需要是该主机的权重，而不是所选主机的权重.所以循环应该是:

The weight that's added to each host's accumulator needs to be that host's weight, not the weight of the host that was chosen. So the loop should be:

for (HostWeightage weightedHost : hostWeightageList) { int weight = weightedHost.getWeightage(); int accWeight = weightedHost.getAccumulatedWeightageSoFar(); weightedHost.setAccumulatedWeightageSoFar(weight + accWeight); }

使用权重的算法运行示例 A:10 B:80 C:10 如下所示:

A sample run of the algorithm using weights A:10 B:80 C:10 looks like this:

accumulators A B C 10 80 10 choose B 20 60 20 choose B 30 40 30 choose B 40 20 40 choose A -50 100 50 choose B -40 80 60 choose B -30 60 70 choose C -20 140 -20 choose B -10 120 -10 choose B 0 100 0 choose B 10 80 10 back to start