Hi.
While testing a latency aware variant of "balance random" (an RFC will
follow), I noticed that the comparison of the draws is skipped more
often than expected. random(<draws>) draws the servers on the
consistent hash ring with replacement, so a draw can return the best
server found so far. There is nothing to compare then, and the draw is
lost. With 4 servers and 2 draws, this happens for one choice out of
four, which then behaves like random(1).
The first patch draws again in this case, at most <draws> extra times
so that a farm with a single usable server does not loop. It is a few
lines in get_server_rnd(), plus one sentence in the documentation.
Measured locally with ideal servers (fixed delays, 30000 requests after
a warm-up), share of the requests sent to the slow servers:
farm random(2) before -> after
4 servers, 1 at 50ms 8.73% -> 5.16%
8 servers, 2 at 50ms 7.5% -> 6.80%
The second patch documents the other source of unevenness I found:
with the default weight of 1, each server only gets 16 points on the
ring, so the shares of the servers vary between about 2% and 4% with
32 servers. The same higher weight for all servers, such as 100, makes
them almost even. I only documented it, as changing the number of
points would change the distribution of the existing setups.
I would be glad about any feedback, also if you would prefer to keep
the current behavior of random for some reason I did not think of.
Regards,
Aleksandar
Aleksandar Lazic (2):
MINOR: backend: don't waste the draws of random on the same server
DOC: config: explain the effect of the weights on random's draws
doc/configuration.txt | 13 +++++++++++++
src/backend.c | 11 +++++++++++
2 files changed, 24 insertions(+)From d2563a3496143e016018ec39e5d2edc9ff4be3e5 Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Sat, 31 Oct 2026 00:31:38 +0100
Subject: [PATCH 2/2] DOC: config: explain the effect of the weights on
random's draws
"balance random" draws the servers on the consistent hash ring, where a
server gets 16 points per unit of weight. With the default weight of 1,
the shares of the ring are uneven (between about 2% and 4% for 32
servers, computed from the ring), so some servers are drawn twice as
often as others. Using the same higher weight for all servers, such as
100, makes the shares almost even.
Measured on 32 servers with 4 slow ones (with the peak EWMA option under
review, which compares the response times of the drawn servers), raising
the weight of all servers from 1 to 100 brought the share of the
requests sent to the slow servers from 2.0% to 1.5%, the same as a
uniform draw.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
doc/configuration.txt | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/doc/configuration.txt b/doc/configuration.txt
index 0ef4590fd..e4e145af8 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -6913,6 +6913,16 @@ balance url_param <param> [check_post]
A draw returning the best server found so far is repeated,
so that the draws compare different servers.
+ The servers are drawn on the consistent hash ring, where
+ each server gets 16 points per unit of weight. With the
+ default weight of 1, the share of the ring of each server
+ is uneven: in a farm of 32 servers it varies between about
+ 2% and 4%, and the servers with a larger share are drawn
+ more often. Using the same higher weight for all servers,
+ such as 100, makes the shares almost even and the
+ distribution closer to a uniform draw, at the expense of a
+ larger tree.
+
For backends in LOG mode, the number of draws is ignored and
a single random is picked since there is no notion of server
load. Random log balancing can be useful with large farms or
--
2.56.0
From 62eded609e81d376098aa2493a72b18e449557db Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Sat, 31 Oct 2026 00:23:28 +0100
Subject: [PATCH 1/2] MINOR: backend: don't waste the draws of random on the
same server
"balance random(<draws>)" draws <draws> servers from the consistent hash
ring and keeps the least loaded one. When a draw returns the best server
found so far, there is nothing to compare and the draw is lost. This is
frequent with small farms: with 4 servers of the same weight and 2
draws, one choice out of four is made on a single server, as with
"random(1)".
Now when the best server is drawn again, another draw is made instead,
at most <draws> extra times so that a farm with a single usable server
does not loop.
The documentation of "random" mentions it.
Measured locally with ideal servers (fixed delays, 30000 requests after
a warm-up, share of the requests sent to the slow servers):
farm random(2) before -> after
4 servers, 1 at 50ms 8.73% -> 5.16%
8 servers, 2 at 50ms 7.5% -> 6.80%
The extra cost is one more random draw and ring lookup in the rare cases
where the same server is drawn again.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
doc/configuration.txt | 3 +++
src/backend.c | 11 +++++++++++
2 files changed, 14 insertions(+)
diff --git a/doc/configuration.txt b/doc/configuration.txt
index 9cc9f174b..0ef4590fd 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -6910,6 +6910,9 @@ balance url_param <param> [check_post]
the Power of Two Random Choices and is described here :
http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
+ A draw returning the best server found so far is repeated,
+ so that the draws compare different servers.
+
For backends in LOG mode, the number of draws is ignored and
a single random is picked since there is no notion of server
load. Random log balancing can be useful with large farms or
diff --git a/src/backend.c b/src/backend.c
index 2f0fe7ea2..8231d01c7 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -575,6 +575,7 @@ struct server *get_server_rnd(struct stream *s, const struct server *avoid)
struct proxy *px = s->be;
struct server *prev, *curr;
int draws = px->lbprm.arg_opt1; // number of draws
+ int redraws = px->lbprm.arg_opt1; // max number of extra draws
/* tot_weight appears to mean srv_count */
if (px->lbprm.tot_weight == 0)
@@ -588,6 +589,16 @@ struct server *get_server_rnd(struct stream *s, const struct server *avoid)
if (!curr)
break;
+ /* drawing the best server again would waste the draw without
+ * any comparison, which is frequent with small farms (one time
+ * out of four with 4 servers and 2 draws): draw again instead,
+ * a limited number of times in case only one server is left.
+ */
+ if (prev == curr && redraws-- > 0) {
+ draws++; // compensates the decrement of the loop
+ continue;
+ }
+
/* compare the new server to the previous best choice and pick
* the one with the least currently served requests.
*/
--
2.56.0
