[MAJOR] implement the Fast Weighted Round Robin (FWRR) algo
This round robin algorithm was written from trees, so that we
do not have to recompute any table when changing server weights.
This solution allows on-the-fly weight adjustments with immediate
effect on the load distribution.
There is still a limitation due to 32-bit computations, to about
2000 servers at full scale (weight 255), or more servers with
lower weights. Basically, sum(srv.weight)*4096 must be below 2^31.
Test configurations and an example program used to develop the
tree will be added next.
Many changes have been brought to the weights computations and
variables in order to accomodate for the possiblity of a server to
be running but disabled from load balancing due to a null weight.
diff --git a/include/proto/backend.h b/include/proto/backend.h
index 8fa8c83..444e53a 100644
--- a/include/proto/backend.h
+++ b/include/proto/backend.h
@@ -39,10 +39,10 @@
int backend_parse_balance(const char **args, char *err,
int errlen, struct proxy *curproxy);
-void recount_servers(struct proxy *px);
void recalc_server_map(struct proxy *px);
int be_downtime(struct proxy *px);
void init_server_map(struct proxy *p);
+void fwrr_init_server_groups(struct proxy *p);
/*
* This function tries to find a running server with free connection slots for
@@ -118,7 +118,9 @@
recalc_server_map(px);
l = h = 0;
- if (px->srv_act > 1 || (px->srv_act == 0 && px->srv_bck > 1)) {
+
+ /* note: we won't hash if there's only one server left */
+ if (px->lbprm.tot_used > 1) {
while ((l + sizeof (int)) <= len) {
h ^= ntohl(*(unsigned int *)(&addr[l]));
l += sizeof (int);
diff --git a/include/types/backend.h b/include/types/backend.h
index c0c0809..a71db69 100644
--- a/include/types/backend.h
+++ b/include/types/backend.h
@@ -71,6 +71,10 @@
#define PR_O_CONTSTATS 0x80000000 /* continous counters */
+
+/* various constants */
+#define BE_WEIGHT_SCALE 256 /* scale between user weight and effective weight */
+
#endif /* _TYPES_BACKEND_H */
/*
diff --git a/include/types/proxy.h b/include/types/proxy.h
index 53de513..6d27a9b 100644
--- a/include/types/proxy.h
+++ b/include/types/proxy.h
@@ -29,6 +29,7 @@
#include <common/appsession.h>
#include <common/config.h>
+#include <common/ebtree.h>
#include <common/mini-clist.h>
#include <common/regex.h>
#include <common/sessionhash.h>
@@ -64,6 +65,17 @@
#define PR_CAP_RS 0x0004
#define PR_CAP_LISTEN (PR_CAP_FE|PR_CAP_BE|PR_CAP_RS)
+/* This structure is used to apply fast weighted round robin on a server group */
+struct fwrr_group {
+ struct eb_root curr; /* tree for servers in "current" time range */
+ struct eb_root t0, t1; /* "init" and "next" servers */
+ struct eb_root *init; /* servers waiting to be placed */
+ struct eb_root *next; /* servers to be placed at next run */
+ int curr_pos; /* current position in the tree */
+ int curr_weight; /* total weight of the current time range */
+ int next_weight; /* total weight of the next time range */
+};
+
struct proxy {
struct listener *listen; /* the listen addresses and sockets */
struct in_addr mon_net, mon_mask; /* don't forward connections from this net (network order) FIXME: should support IPv6 */
@@ -79,7 +91,7 @@
struct list block_cond; /* early blocking conditions (chained) */
struct list switching_rules; /* content switching rules (chained) */
struct server *srv; /* known servers */
- int srv_act, srv_bck; /* # of running servers */
+ int srv_act, srv_bck; /* # of servers eligible for LB (UP|!checked) AND (enabled+weight!=0) */
struct {
int tot_wact, tot_wbck; /* total effective weights of active and backup servers */
@@ -87,11 +99,19 @@
int tot_used; /* total number of servers used for LB */
int wmult; /* ratio between user weight and effective weight */
int wdiv; /* ratio between effective weight and user weight */
+ struct server *fbck; /* first backup server when !PR_O_USE_ALL_BK, or NULL */
struct {
struct server **srv; /* the server map used to apply weights */
int rr_idx; /* next server to be elected in round robin mode */
int state; /* PR_MAP_RECALC */
} map; /* LB parameters for map-based algorithms */
+ struct {
+ struct fwrr_group act; /* weighted round robin on the active servers */
+ struct fwrr_group bck; /* weighted round robin on the backup servers */
+ } fwrr;
+ void (*update_server_eweight)(struct server *);/* if non-NULL, to be called after eweight change */
+ void (*set_server_status_up)(struct server *);/* to be called after status changes to UP */
+ void (*set_server_status_down)(struct server *);/* to be called after status changes to DOWN */
} lbprm; /* LB parameters for all algorithms */
char *cookie_name; /* name of the cookie to look for */
diff --git a/include/types/server.h b/include/types/server.h
index 3553fc0..4258502 100644
--- a/include/types/server.h
+++ b/include/types/server.h
@@ -2,7 +2,7 @@
include/types/server.h
This file defines everything related to servers.
- Copyright (C) 2000-2006 Willy Tarreau - w@1wt.eu
+ Copyright (C) 2000-2007 Willy Tarreau - w@1wt.eu
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@@ -26,6 +26,7 @@
#include <arpa/inet.h>
#include <common/config.h>
+#include <common/eb32tree.h>
#include <common/mini-clist.h>
#include <types/buffers.h>
@@ -57,6 +58,7 @@
struct server {
struct server *next;
int state; /* server state (SRV_*) */
+ int prev_state; /* server state before last change (SRV_*) */
int cklen; /* the len of the cookie, to speed up checks */
char *cookie; /* the id set in the cookie */
@@ -85,6 +87,12 @@
char *id; /* just for identification */
unsigned uweight, eweight; /* user-specified weight, and effective weight */
unsigned wscore; /* weight score, used during srv map computation */
+ unsigned prev_eweight; /* eweight before last change */
+ unsigned rweight; /* remainer of weight in the current LB tree */
+ unsigned npos, lpos; /* next and last positions in the LB tree */
+ struct eb32_node lb_node; /* node used for tree-based load balancing */
+ struct eb_root *lb_tree; /* we want to know in what tree the server is */
+ struct server *next_full; /* next server in the temporary full list */
unsigned failed_checks, down_trans; /* failed checks and up-down transitions */
unsigned down_time; /* total time the server was down */