Nas01010101 opened a new pull request, #3426: URL: https://github.com/apache/brpc/pull/3426
### What problem does this PR solve? `WeightedRandomizedLoadBalancer::SelectServer()` never selects the server that was added last, and over-selects the first one. `Add()` fills `Server::current_weight_sum` with an *inclusive* prefix sum. `SelectServer()` draws `random_weight` from `butil::fast_rand_less_than(weight_sum)`, i.e. from `[0, weight_sum - 1]`, and then `lower_bound()`s that value against those prefix sums. `lower_bound()` returns the first server whose prefix sum is `>= random_weight`, but a server owns the half-open range `[prefix(i-1), prefix(i))`, so the predicate has to be `> random_weight`. Two consequences: the first server also serves `random_weight == prefix(0)`, so it gets one slot too many; and the last server is never selected at all, because `random_weight` can never reach `weight_sum`. With four servers of equal weight the measured distribution is 49.8 / 25.1 / 25.1 / 0.0 percent instead of 25 percent each. The last server only receives traffic through the fallback loop, when every server picked at random happens to be unavailable. ### What is changed and the side effects? Changed: search for `random_weight + 1`, so `lower_bound()` lands on the first prefix sum strictly greater than `random_weight`. `random_weight + 1` is at most `weight_sum`, which is exactly the last prefix sum, so the iterator is still always valid. Side effects: - Performance effects: none, the comparison is unchanged. - Breaking backward compatibility: no. Traffic shifts towards the configured weights. The existing `weighted_randomized` test does not catch this. Its servers have weights 3/2/5/10 and it only asserts that every rate is within 0.5x~2x of the expected one. The weight-10 server measures 0.453 before this change and 0.5055 after it, and both are inside that band. The off-by-one predicts that number exactly: the server should own 10 of 20 slots but owns 9, i.e. 0.45. This PR adds `weighted_randomized_equal_weight`, which uses equal weights so a single misplaced slot is visible, and checks the rates within 0.9x~1.1x. On master the last server is selected 0 times out of 40000 and the test fails; with this change all four land within 0.2476~0.25435. ### Check List: - `brpc_load_balancer_unittest` passes in full: `[ PASSED ] 17 tests.` - The new test was run with `--gtest_repeat=40` without a failure. - Verified the new test fails without the one-line change and passes with it. Tested on macOS/arm64 with clang. I was not able to build on Linux/gcc locally; CI will cover that. -- 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]
