Optimization, based on TreeMap to optimize ShortestResponseLoadBalance when there are multiple services with the same shortest response time and different weights
- Dominant language
- Java
- Stars
- 41.6k
- Forks
- 26.4k
- Avg merge
- 15h 13m
- Merged PRs (30d)
- 4
Description
- [ ] I have searched the [issues](https://github.com/apache/dubbo/issues) of this repository and believe that this is not a duplicate.
- [ ] I have checked the [FAQ](https://github.com/apache/dubbo/blob/master/FAQ.md) of this repository and believe that this is not a duplicate.
### Environment
* Dubbo version: 2.7.8
* Operating System version: macos
* Java version: 1.8
dubbo2.7.8 ShortestResponseLoadBalance source code:
```
protected Invoker doSelect(List> invokers, URL url, Invocation invocation) {
.....
if (shortestCount == 1) {
return invokers.get(shortestIndexes[0]);
}
if (!sameWeight && totalWeight > 0) {
int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0; i < shortestCount; i++) {
int shortestIndex = shortestIndexes[i];
offsetWeight -= weights[shortestIndex];
if (offsetWeight < 0) {
return invokers.get(shortestIndex);
}
}
}
return invokers.get(shortestIndexes[ThreadLocalRandom.current().nextInt(shortestCount)]);
}
```
I think we can use TreeMap to store the weight of the same shortest response time, and then directly select the invoker based on offsetWeight.
for example:
```
protected Invoker doSelect(List> invokers, URL url, Invocation invocation) {
.....
TreeMap shortestWeightMap = new TreeMap();
for (int i = 0; i < length; i++) {
Invoker invoker = invokers.get(i);
RpcStatus rpcStatus = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
// Calculate the estimated response time from the product of active connections and succeeded average elapsed time.
long succeededAverageElapsed = rpcStatus.getSucceededAverageElapsed();
int active = rpcStatus.getActive();
long estimateResponse = succeededAverageElapsed * active;
int afterWarmup = getWeight(invoker, invocation);
weights[i] = afterWarmup;
// Same as LeastActiveLoadBalance
if (estimateResponse < shortestResponse) {
shortestResponse = estimateResponse;
shortestCount = 1;
shortestIndexes[0] = i;
totalWeight = afterWarmup;
firstWeight = afterWarmup;
sameWeight = true;
shortestWeightMap.clear();
shortestWeightMap.put(totalWeight, invoker);
} else if (estimateResponse == shortestResponse) {
shortestIndexes[shortestCount++] = i;
totalWeight += afterWarmup;
shortestWeightMap.put(totalWeight, invoker);
if (sameWeight && i > 0
&& afterWarmup != firstWeight) {
sameWeight = false;
}
}
}
if (shortestCount == 1) {
return invokers.get(shortestIndexes[0]);
}
if (!sameWeight && totalWeight > 0) {
int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
Invoker invoker = shortestWeightMap.ceilingEntry(offsetWeight);
if(null != invoker){
return invoker.
}
}
return invokers.get(shortestIndexes[ThreadLocalRandom.current().nextInt(shortestCount)]);
}
```
Contributor guide
Assessment
This issue has not been assessed yet.