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/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;