jizhuozhi
commented
5 months ago Sorry, I seem to have misunderstood the usage of Weighted here. It seems to be only used to weight the starting position of a sequence, and then fallback to an unweighted Round Robin. Why is it designed like this?
In addition, if you only for weighted selecting the starting position, the weighted expansion method is too cumbersome (O(sigma(w)) memory). Random methods such as CDF (cumulative density function, O(logn) time and O(n) memory cost) or alias method (O(1) time and O(n) memory cost) may be more suitable.
What is the problem your feature solves, or the need it fulfills?
The current WRR algorithm will have additional memory overhead when the weights are not mutually prime, and because the current implementation is not smooth, extreme situations will occur, causing the backend to be overloaded or starved.
For example, it is common for everyone to set the weight to 100 or 1000 to facilitate weight adjustment. Then there will be a situation where the first 100 are all A, and the next 100 are all B (smooth WRR or shuffling is another topic).
Describe the solution you'd like
Use GCD to reduce memory overhead and reduce load balancing cycles
Describe alternatives you've considered
What other solutions, features, or workarounds have you considered that might also solve the issue? What are the tradeoffs for these alternatives compared to what you're proposing?
Additional context
Already implemented in the following RPC or gateway https://github.com/cloudwego/kitex/issues/1014 https://github.com/alibaba/tengine/issues/1667