This is an automated email from the ASF dual-hosted git repository.
chenBright pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/brpc.git
The following commit(s) were added to refs/heads/master by this push:
new 7f646631 Fix WeightedRandomizedLoadBalancer skipping the last server
(#3426)
7f646631 is described below
commit 7f6466313574b7e9159f3a81fddc1d1288400003
Author: nas <[email protected]>
AuthorDate: Sun Aug 16 05:39:37 2026 -0400
Fix WeightedRandomizedLoadBalancer skipping the last server (#3426)
* fix WeightedRandomizedLoadBalancer skipping the last server
SelectServer() draws random_weight from fast_rand_less_than(weight_sum),
i.e. from [0, weight_sum - 1], and then lower_bound()s it against
Server::current_weight_sum, which Add() fills with an inclusive prefix
sum. 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.
Because of that the first server in the list also serves
random_weight == prefix(0) and the last server never serves anything at
all, since 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.
Search for random_weight + 1 so that lower_bound() lands on the first
prefix sum strictly greater than random_weight.
The existing weighted_randomized test does not catch this: its servers
have weights 3/2/5/10 and it only asserts that each rate is within
0.5x~2x of the expected one. The weight-10 server measures 0.448 before
this change and 0.494 after it, both inside that band. Add
weighted_randomized_equal_weight, which uses equal weights so that a
single misplaced slot is visible, and check the rates within 0.9x~1.1x.
Signed-off-by: Anas <[email protected]>
* use upper_bound for the weighted prefix-sum search
upper_bound(random_weight) states the intent directly: the first server
whose
inclusive prefix sum is strictly greater than random_weight. It is the same
search as lower_bound(random_weight + 1) without the increment.
Also correct the tolerance comment in the unit test: with run_times=40000
and
p=0.25 the count has sigma ~= 86.6, so the 0.9x~1.1x band is about 11 sigma,
not more than 20.
---------
Signed-off-by: Anas <[email protected]>
---
.../policy/weighted_randomized_load_balancer.cpp | 4 +-
test/brpc_load_balancer_unittest.cpp | 50 ++++++++++++++++++++++
2 files changed, 53 insertions(+), 1 deletion(-)
diff --git a/src/brpc/policy/weighted_randomized_load_balancer.cpp
b/src/brpc/policy/weighted_randomized_load_balancer.cpp
index 46923acb..d2786ed8 100644
--- a/src/brpc/policy/weighted_randomized_load_balancer.cpp
+++ b/src/brpc/policy/weighted_randomized_load_balancer.cpp
@@ -131,9 +131,11 @@ int WeightedRandomizedLoadBalancer::SelectServer(const
SelectIn& in, SelectOut*
uint64_t weight_sum = s->weight_sum;
for (size_t i = 0; i < n; ++i) {
uint64_t random_weight = butil::fast_rand_less_than(weight_sum);
+ // current_weight_sum is an inclusive prefix sum, so random_weight
belongs
+ // to the first server whose prefix sum is strictly greater than it.
const Server random_server(0, 0, random_weight);
const auto& server =
- std::lower_bound(s->server_list.begin(), s->server_list.end(),
+ std::upper_bound(s->server_list.begin(), s->server_list.end(),
random_server, server_compare);
const SocketId id = server->id;
if (ExcludedServers::IsExcluded(in.excluded, id)) {
diff --git a/test/brpc_load_balancer_unittest.cpp
b/test/brpc_load_balancer_unittest.cpp
index 0f0ecccc..1b326a8f 100644
--- a/test/brpc_load_balancer_unittest.cpp
+++ b/test/brpc_load_balancer_unittest.cpp
@@ -1026,6 +1026,56 @@ TEST_F(LoadBalancerTest, weighted_randomized) {
}
}
+TEST_F(LoadBalancerTest, weighted_randomized_equal_weight) {
+ // With equal weights every server must get the same share of the traffic.
+ // The tolerance of `weighted_randomized` above is +/-2x, which is too
loose
+ // to catch a single misplaced slot, so check the distribution tightly
here.
+ const char* servers[] = {
+ "10.92.115.19:8831",
+ "10.42.108.25:8832",
+ "10.36.150.31:8833",
+ "10.36.150.32:8899"
+ };
+ brpc::policy::WeightedRandomizedLoadBalancer wrlb;
+ for (size_t i = 0; i < ARRAY_SIZE(servers); ++i) {
+ butil::EndPoint dummy;
+ ASSERT_EQ(0, str2endpoint(servers[i], &dummy));
+ brpc::ServerId id(8888);
+ brpc::SocketOptions options;
+ options.remote_side = dummy;
+ options.user = new SaveRecycle;
+ ASSERT_EQ(0, brpc::Socket::Create(options, &id.id));
+ id.tag = "1";
+ ASSERT_TRUE(wrlb.AddServer(id));
+ }
+
+ std::map<butil::EndPoint, size_t> select_result;
+ brpc::SocketUniquePtr ptr;
+ brpc::LoadBalancer::SelectIn in = { 0, false, false, 0u, NULL };
+ brpc::LoadBalancer::SelectOut out(&ptr);
+ const int run_times = 40000;
+ for (int i = 0; i < run_times; ++i) {
+ ASSERT_EQ(0, wrlb.SelectServer(in, &out));
+ ++select_result[ptr->remote_side()];
+ }
+
+ // Every server must be selected at least once, in particular the one added
+ // last, which owns the largest prefix sum.
+ ASSERT_EQ(ARRAY_SIZE(servers), select_result.size());
+ const double expect_rate = 1.0 / ARRAY_SIZE(servers);
+ for (const auto& result : select_result) {
+ const double actual_rate = result.second * 1.0 / run_times;
+ std::cout << result.first << " select_times=" << result.second
+ << " actual_rate=" << actual_rate
+ << " expect_rate=" << expect_rate << std::endl;
+ // 0.9x ~ 1.1x of the expected rate. With n=40000 and p=0.25 the count
has
+ // sigma = sqrt(n*p*(1-p)) ~= 86.6, so the +-10% band is about 11 sigma
+ // wide and a passing run is not luck.
+ ASSERT_GE(actual_rate, expect_rate * 0.9);
+ ASSERT_LE(actual_rate, expect_rate * 1.1);
+ }
+}
+
TEST_F(LoadBalancerTest, health_check_no_valid_server) {
const char* servers[] = {
"10.92.115.19:8832",
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
