MINOR: backend: make the random algorithm support a number of draws
When an argument <draws> is present, it must be an integer value one
or greater, indicating the number of draws before selecting the least
loaded of these servers. It was indeed demonstrated that picking the
least loaded of two servers is enough to significantly improve the
fairness of the algorithm, by always avoiding to pick the most loaded
server within a farm and getting rid of any bias that could be induced
by the unfair distribution of the consistent list. Higher values N will
take away N-1 of the highest loaded servers at the expense of performance.
With very high values, the algorithm will converge towards the leastconn's
result but much slower. The default value is 2, which generally shows very
good distribution and performance. This algorithm is also known as the
Power of Two Random Choices and is described here :
http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
diff --git a/doc/configuration.txt b/doc/configuration.txt
index d684294..5b6ab44 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -2541,15 +2541,33 @@
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
+ random
+ random(<draws>)
+ 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.
+ or removed as it may avoid the hammering effect that could
+ result from roundrobin or leastconn in this situation. 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. When an
+ argument <draws> is present, it must be an integer value one
+ or greater, indicating the number of draws before selecting
+ the least loaded of these servers. It was indeed demonstrated
+ that picking the least loaded of two servers is enough to
+ significantly improve the fairness of the algorithm, by
+ always avoiding to pick the most loaded server within a farm
+ and getting rid of any bias that could be induced by the
+ unfair distribution of the consistent list. Higher values N
+ will take away N-1 of the highest loaded servers at the
+ expense of performance. With very high values, the algorithm
+ will converge towards the leastconn's result but much slower.
+ The default value is 2, which generally shows very good
+ distribution and performance. This algorithm is also known as
+ the Power of Two Random Choices and is described here :
+ http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
rdp-cookie
rdp-cookie(<name>)
diff --git a/src/backend.c b/src/backend.c
index 6cca128..ab5a629 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -524,14 +524,31 @@
{
unsigned int hash = 0;
struct proxy *px = s->be;
+ struct server *prev, *curr;
+ int draws = px->lbprm.arg_opt1; // number of draws
/* 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, avoid);
+ curr = NULL;
+ do {
+ prev = curr;
+ /* ensure all 32 bits are covered as long as RAND_MAX >= 65535 */
+ hash = ((uint64_t)random() * ((uint64_t)RAND_MAX + 1)) ^ random();
+ curr = chash_get_server_hash(px, hash, avoid);
+ if (!curr)
+ break;
+
+ /* compare the new server to the previous best choice and pick
+ * the one with the least currently served requests.
+ */
+ if (prev && prev != curr &&
+ curr->served * prev->cur_eweight > prev->served * curr->cur_eweight)
+ curr = prev;
+ } while (--draws > 0);
+
+ return curr;
}
/*
@@ -1722,9 +1739,31 @@
curproxy->lbprm.algo &= ~BE_LB_ALGO;
curproxy->lbprm.algo |= BE_LB_ALGO_LC;
}
- else if (!strcmp(args[0], "random")) {
+ else if (!strncmp(args[0], "random", 6)) {
curproxy->lbprm.algo &= ~BE_LB_ALGO;
curproxy->lbprm.algo |= BE_LB_ALGO_RND;
+ curproxy->lbprm.arg_opt1 = 2;
+
+ if (*(args[0] + 6) == '(' && *(args[0] + 7) != ')') { /* number of draws */
+ const char *beg;
+ char *end;
+
+ beg = args[0] + 7;
+ curproxy->lbprm.arg_opt1 = strtol(beg, &end, 0);
+
+ if (*end != ')') {
+ if (!*end)
+ memprintf(err, "random : missing closing parenthesis.");
+ else
+ memprintf(err, "random : unexpected character '%c' after argument.", *end);
+ return -1;
+ }
+
+ if (curproxy->lbprm.arg_opt1 < 1) {
+ memprintf(err, "random : number of draws must be at least 1.");
+ return -1;
+ }
+ }
}
else if (!strcmp(args[0], "source")) {
curproxy->lbprm.algo &= ~BE_LB_ALGO;