Percentage based routing algorithm

Question

browsing around for percentage based routing, stumbled upon this thread.

per the algo proposed as below:

for a given model as below:

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

The initial value for percentageAccum is the value of percentageLoad.

When a request is received:

• choose the host with the largest percentageAccum
• subtract 100 from the percentageAccum for the chosen host
• add percentageLoad to percentageAccum for all hosts, including the chosen host

below is my implementation

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

---

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

---

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!!

Answer 1

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 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