wangjiacai666 opened a new pull request, #16544:
URL: https://github.com/apache/dubbo/pull/16544
## What is the purpose of the change
`RandomLoadBalance#doSelect` accumulates weights with an index-based loop
(`invokers.get(i)`).
When the invoker list comes from the router chain it is a `BitList`, and
`BitList#get(int)` is
O(index): every call walks the bitset with `BitSet#nextSetBit` from the
beginning (the method is
also `synchronized`). The loop therefore degrades to O(N^2), which becomes
significant with large
provider address lists.
This PR iterates the list directly instead of by index. `BitList`'s
iteration order is identical
to its `get(i)` order (ascending bit index, then the tail list), so
selection semantics are
unchanged, while the weight accumulation becomes O(N) on both `BitList` and
ordinary lists.
The remaining `invokers.get(...)` calls in the selection phase are bounded
(at most 4 in the
small-list branch, one in the binary-search branch), so the whole method is
O(N).
## Performance
Measured on a 3125-address `BitList` (JDK 21, single thread):
| | before | after |
|---|---|---|
| `doSelect` (weighted path) | 33.5 ms | < 1 ms |
In a production consumer with ~3000 provider addresses, the average RT of a
downstream call
dropped from ~38 ms to ~14 ms after switching to an equivalent O(N)
implementation.
## Related
`LeastActiveLoadBalance` and `ShortestResponseLoadBalance` contain the same
index-based pattern
(`invokers.get(i)` inside a `for (int i = 0; i < length; i++)` loop), so
they degrade the same way
on a `BitList`. I kept this PR focused on `RandomLoadBalance`; happy to
handle the other two in a
follow-up if you prefer.
## Tests
- Added `testSelectByWeightWithBitList`: runs weighted selection (weights
1:9:6) on a `BitList`
and asserts the resulting distribution.
- `mvn -pl dubbo-cluster -Dtest=RandomLoadBalanceTest test`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]