MINOR: backend: implement random-based load balancing
For large farms where servers are regularly added or removed, picking
a random server from the pool can ensure faster load transitions than
when using round-robin and less traffic surges on the newly added
servers than when using leastconn.
This commit introduces "balance random". It internally uses a random as
the key to the consistent hashing mechanism, thus all features available
in consistent hashing such as weights and bounded load via hash-balance-
factor are usable. It is extremely convenient because one common concern
when using random is what happens when a server is hammered a bit too
much. Here that can trivially be avoided, like in the configuration below :
backend bk0
balance random
hash-balance-factor 110
server-template s 1-100 127.0.0.1:8000 check inter 1s
Note that while "balance random" internally relies on a hash algorithm,
it holds the same properties as round-robin and as such is compatible with
reusing an existing server connection with "option prefer-last-server".
diff --git a/doc/configuration.txt b/doc/configuration.txt
index 3bea4d6..cbea330 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -2444,6 +2444,16 @@
changing a server's weight on the fly will have no effect,
but this can be changed using "hash-type".
+ random A random number will be used as the key for the consistent
+ hashing function. This means that the servers' weights are
+ respected, dynamic weight changes immediately take effect, as
+ well as new server additions. Random load balancing can be
+ useful with large farms or when servers are frequently added
+ or removed. The hash-balance-factor directive can be used to
+ further improve fairness of the load balancing, especially
+ in situations where servers show highly variable response
+ times.
+
rdp-cookie
rdp-cookie(<name>)
The RDP cookie <name> (or "mstshash" if omitted) will be
@@ -3642,6 +3652,9 @@
lower <factor> means that more servers will be checked on average, affecting
performance. Reasonable values are from 125 to 200.
+ This setting is also used by "balance random" which internally relies on the
+ consistent hashing mechanism.
+
See also : "balance" and "hash-type".
diff --git a/include/types/backend.h b/include/types/backend.h
index c7f9fa3..b36cd41 100644
--- a/include/types/backend.h
+++ b/include/types/backend.h
@@ -48,10 +48,12 @@
#define BE_LB_HASH_PRM 0x00002 /* hash HTTP URL parameter */
#define BE_LB_HASH_HDR 0x00003 /* hash HTTP header value */
#define BE_LB_HASH_RDP 0x00004 /* hash RDP cookie value */
+#define BE_LB_HASH_RND 0x00008 /* hash a random value */
/* BE_LB_RR_* is used with BE_LB_KIND_RR */
#define BE_LB_RR_DYN 0x00000 /* dynamic round robin (default) */
#define BE_LB_RR_STATIC 0x00001 /* static round robin */
+#define BE_LB_RR_RANDOM 0x00002 /* random round robin */
/* BE_LB_CB_* is used with BE_LB_KIND_CB */
#define BE_LB_CB_LC 0x00000 /* least-connections */
@@ -79,6 +81,7 @@
*/
#define BE_LB_ALGO_NONE (BE_LB_KIND_NONE | BE_LB_NEED_NONE) /* not defined */
#define BE_LB_ALGO_RR (BE_LB_KIND_RR | BE_LB_NEED_NONE) /* round robin */
+#define BE_LB_ALGO_RND (BE_LB_KIND_RR | BE_LB_NEED_NONE | BE_LB_RR_RANDOM) /* random value */
#define BE_LB_ALGO_LC (BE_LB_KIND_CB | BE_LB_NEED_NONE | BE_LB_CB_LC) /* least connections */
#define BE_LB_ALGO_FAS (BE_LB_KIND_CB | BE_LB_NEED_NONE | BE_LB_CB_FAS) /* first available server */
#define BE_LB_ALGO_SRR (BE_LB_KIND_RR | BE_LB_NEED_NONE | BE_LB_RR_STATIC) /* static round robin */
diff --git a/src/backend.c b/src/backend.c
index 2b6167d..8473efb 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -513,6 +513,21 @@
return map_get_server_hash(px, hash);
}
+/* random value */
+static struct server *get_server_rnd(struct stream *s)
+{
+ unsigned int hash = 0;
+ struct proxy *px = s->be;
+
+ /* tot_weight appears to mean srv_count */
+ if (px->lbprm.tot_weight == 0)
+ return NULL;
+
+ /* ensure all 32 bits are covered as long as RAND_MAX >= 65535 */
+ hash = ((uint64_t)random() * ((uint64_t)RAND_MAX + 1)) ^ random();
+ return chash_get_server_hash(px, hash);
+}
+
/*
* This function applies the load-balancing algorithm to the stream, as
* defined by the backend it is assigned to. The stream is then marked as
@@ -615,7 +630,9 @@
case BE_LB_LKUP_CHTREE:
case BE_LB_LKUP_MAP:
if ((s->be->lbprm.algo & BE_LB_KIND) == BE_LB_KIND_RR) {
- if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
+ if ((s->be->lbprm.algo & BE_LB_PARM) == BE_LB_RR_RANDOM)
+ srv = get_server_rnd(s);
+ else if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
srv = chash_get_next_server(s->be, prev_srv);
else
srv = map_get_server_rr(s->be, prev_srv);
@@ -1503,6 +1520,10 @@
curproxy->lbprm.algo &= ~BE_LB_ALGO;
curproxy->lbprm.algo |= BE_LB_ALGO_LC;
}
+ else if (!strcmp(args[0], "random")) {
+ curproxy->lbprm.algo &= ~BE_LB_ALGO;
+ curproxy->lbprm.algo |= BE_LB_ALGO_RND;
+ }
else if (!strcmp(args[0], "source")) {
curproxy->lbprm.algo &= ~BE_LB_ALGO;
curproxy->lbprm.algo |= BE_LB_ALGO_SH;
diff --git a/src/cfgparse.c b/src/cfgparse.c
index 7653536..024502c 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -8350,6 +8350,9 @@
if ((curproxy->lbprm.algo & BE_LB_PARM) == BE_LB_RR_STATIC) {
curproxy->lbprm.algo |= BE_LB_LKUP_MAP;
init_server_map(curproxy);
+ } else if ((curproxy->lbprm.algo & BE_LB_PARM) == BE_LB_RR_RANDOM) {
+ curproxy->lbprm.algo |= BE_LB_LKUP_CHTREE | BE_LB_PROP_DYN;
+ chash_init_server_tree(curproxy);
} else {
curproxy->lbprm.algo |= BE_LB_LKUP_RRTREE | BE_LB_PROP_DYN;
fwrr_init_server_groups(curproxy);