[MEDIUM] backend: implement consistent hashing variation
Consistent hashing provides some interesting advantages over common
hashing. It avoids full redistribution in case of a server failure,
or when expanding the farm. This has a cost however, the hashing is
far from being perfect, as we associate a server to a request by
searching the server with the closest key in a tree. Since servers
appear multiple times based on their weights, it is recommended to
use weights larger than approximately 10-20 in order to smoothen
the distribution a bit.
In some cases, playing with weights will be the only solution to
make a server appear more often and increase chances of being picked,
so stats are very important with consistent hashing.
In order to indicate the type of hashing, use :
hash-type map-based (default, old one)
hash-type consistent (new one)
Consistent hashing can make sense in a cache farm, in order not
to redistribute everyone when a cache changes state. It could also
probably be used for long sessions such as terminal sessions, though
that has not be attempted yet.
More details on this method of hashing here :
http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
diff --git a/Makefile b/Makefile
index ed8cb27..14586dc 100644
--- a/Makefile
+++ b/Makefile
@@ -459,7 +459,7 @@
src/time.o src/fd.o src/pipe.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/client.o src/proxy.o src/proto_uxst.o \
src/proto_http.o src/stream_sock.o src/appsession.o src/backend.o \
- src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
+ src/lb_chash.o src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
src/stream_interface.o src/dumpstats.o src/proto_tcp.o \
src/session.o src/hdr_idx.o src/ev_select.o src/signal.o \
src/acl.o src/memory.o src/freq_ctr.o \
diff --git a/Makefile.bsd b/Makefile.bsd
index eb2b6b0..7957f94 100644
--- a/Makefile.bsd
+++ b/Makefile.bsd
@@ -105,7 +105,7 @@
src/proto_http.o src/stream_sock.o src/appsession.o src/backend.o \
src/stream_interface.o src/dumpstats.o src/proto_tcp.o \
src/session.o src/hdr_idx.o src/ev_select.o src/signal.o \
- src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
+ src/lb_chash.o src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
src/ev_poll.o src/ev_kqueue.o \
src/acl.o src/memory.o src/freq_ctr.o \
src/ebtree.o src/eb32tree.o
diff --git a/Makefile.osx b/Makefile.osx
index 9ba146b..19fb720 100644
--- a/Makefile.osx
+++ b/Makefile.osx
@@ -102,7 +102,7 @@
src/proto_http.o src/stream_sock.o src/appsession.o src/backend.o \
src/stream_interface.o src/dumpstats.o src/proto_tcp.o \
src/session.o src/hdr_idx.o src/ev_select.o src/signal.o \
- src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
+ src/lb_chash.o src/lb_fwlc.o src/lb_fwrr.o src/lb_map.o \
src/ev_poll.o \
src/acl.o src/memory.o src/freq_ctr.o \
src/ebtree.o src/eb32tree.o
diff --git a/doc/configuration.txt b/doc/configuration.txt
index 6fe6e95..fecab81 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -723,6 +723,7 @@
errorloc303 X X X X
fullconn X - X X
grace - X X X
+hash-type X - X X
http-check disable-on-404 X - X X
id - X X X
log X X X X
@@ -956,8 +957,9 @@
used in TCP mode where no cookie may be inserted. It may also
be used on the Internet to provide a best-effort stickyness
to clients which refuse session cookies. This algorithm is
- static, which means that changing a server's weight on the
- fly will have no effect.
+ static by default, which means that changing a server's
+ weight on the fly will have no effect, but this can be
+ changed using "hash-type".
uri The left part of the URI (before the question mark) is hashed
and divided by the total weight of the running servers. The
@@ -966,9 +968,9 @@
server as long as no server goes up or down. This is used
with proxy caches and anti-virus proxies in order to maximize
the cache hit rate. Note that this algorithm may only be used
- in an HTTP backend. This algorithm is static, which means
- that changing a server's weight on the fly will have no
- effect.
+ in an HTTP backend. This algorithm is static by default,
+ which means that changing a server's weight on the fly will
+ have no effect, but this can be changed using "hash-type".
This algorithm support two optional parameters "len" and
"depth", both followed by a positive integer number. These
@@ -1018,8 +1020,9 @@
long as no server goes up or down. If no value is found or if
the parameter is not found, then a round robin algorithm is
applied. Note that this algorithm may only be used in an HTTP
- backend. This algorithm is static, which means that changing a
- server's weight on the fly will have no effect.
+ backend. This algorithm is static by default, which means
+ that changing a server's weight on the fly will have no
+ effect, but this can be changed using "hash-type".
hdr(name) The HTTP header <name> will be looked up in each HTTP request.
Just as with the equivalent ACL 'hdr()' function, the header
@@ -1032,6 +1035,10 @@
specific headers such as 'Host'. For instance, in the Host
value "haproxy.1wt.eu", only "1wt" will be considered.
+ This algorithm is static by default, which means that
+ changing a server's weight on the fly will have no effect,
+ but this can be changed using "hash-type".
+
rdp-cookie
rdp-cookie(name)
The RDP cookie <name> (or "mstshash" if omitted) will be
@@ -1048,6 +1055,10 @@
you must use 'tcp-request content accept' rule combined with
a 'req_rdp_cookie_cnt' ACL.
+ This algorithm is static by default, which means that
+ changing a server's weight on the fly will have no effect,
+ but this can be changed using "hash-type".
+
<arguments> is an optional list of arguments which may be needed by some
algorithms. Right now, only "url_param" and "uri" support an
optional argument.
@@ -1099,7 +1110,8 @@
might be a URL parameter list. This is probably not a concern with SGML
type message bodies.
- See also : "dispatch", "cookie", "appsession", "transparent" and "http_proxy".
+ See also : "dispatch", "cookie", "appsession", "transparent", "hash-type" and
+ "http_proxy".
bind [<address>]:<port> [, ...]
@@ -1729,6 +1741,40 @@
simplify it.
+hash-type <method>
+ Specify a method to use for mapping hashes to servers
+ May be used in sections : defaults | frontend | listen | backend
+ yes | no | yes | yes
+ Arguments :
+ map-based the hash table is a static array containing all alive servers.
+ The hashes will be very smooth, will consider weights, but will
+ be static in that weight changes while a server is up will be
+ ignored. This means that there will be no slow start. Also,
+ since a server is selected by its position in the array, most
+ mappings are changed when the server count changes. This means
+ that when a server goes up or down, or when a server is added
+ to a farm, most connections will be redistributed to different
+ servers. This can be inconvenient with caches for instance.
+
+ consistent the hash table is a tree filled with many occurrences of each
+ server. The hash key is looked up in the tree and the closest
+ server is chosen. This hash is dynamic, it supports changing
+ weights while the servers are up, so it is compatible with the
+ slow start feature. It has the advantage that when a server
+ goes up or down, only its associations are moved. When a server
+ is added to the farm, only a few part of the mappings are
+ redistributed, making it an ideal algorithm for caches.
+ However, due to its principle, the algorithm will never be very
+ smooth and it may sometimes be necessary to adjust a server's
+ weight or its ID to get a more balanced distribution. In order
+ to get the same distribution on multiple load balancers, it is
+ important that all servers have the same IDs.
+
+ The default hash type is "map-based" and is recommended for most usages.
+
+ See also : "balance", "server"
+
+
http-check disable-on-404
Enable a maintenance mode upon HTTP/404 response to health-checks
May be used in sections : defaults | frontend | listen | backend
diff --git a/include/proto/lb_chash.h b/include/proto/lb_chash.h
new file mode 100644
index 0000000..a0ebf69
--- /dev/null
+++ b/include/proto/lb_chash.h
@@ -0,0 +1,40 @@
+/*
+ * include/proto/lb_chash.h
+ * Function declarations for Consistent Hash LB algorithm.
+ *
+ * Copyright (C) 2000-2009 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
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _PROTO_LB_CHASH_H
+#define _PROTO_LB_CHASH_H
+
+#include <common/config.h>
+#include <types/proxy.h>
+#include <types/server.h>
+
+void chash_init_server_tree(struct proxy *p);
+struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid);
+struct server *chash_get_server_hash(struct proxy *p, unsigned int hash);
+
+#endif /* _PROTO_LB_CHASH_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */
diff --git a/include/types/backend.h b/include/types/backend.h
index a8f8586..91d95b1 100644
--- a/include/types/backend.h
+++ b/include/types/backend.h
@@ -23,6 +23,7 @@
#define _TYPES_BACKEND_H
#include <common/config.h>
+#include <types/lb_chash.h>
#include <types/lb_fwlc.h>
#include <types/lb_fwrr.h>
#include <types/lb_map.h>
@@ -59,7 +60,7 @@
#define BE_LB_KIND_NONE 0x00000 /* algorithm not set */
#define BE_LB_KIND_RR 0x01000 /* round-robin */
#define BE_LB_KIND_LC 0x02000 /* least connections */
-#define BE_LB_KIND_HI 0x03000 /* hash of input (see hash inputs below) */
+#define BE_LB_KIND_HI 0x03000 /* hash of input (see hash inputs above) */
#define BE_LB_KIND 0x07000 /* mask to get/clear LB algorithm */
/* All known variants of load balancing algorithms. These can be cleared using
@@ -84,12 +85,16 @@
#define BE_LB_LKUP_MAP 0x10000 /* static map based lookup */
#define BE_LB_LKUP_RRTREE 0x20000 /* FWRR tree lookup */
#define BE_LB_LKUP_LCTREE 0x30000 /* FWLC tree lookup */
+#define BE_LB_LKUP_CHTREE 0x40000 /* consistent hash */
#define BE_LB_LKUP 0x70000 /* mask to get just the LKUP value */
/* additional properties */
#define BE_LB_PROP_DYN 0x80000 /* bit to indicate a dynamic algorithm */
-
+/* hash types */
+#define BE_LB_HASH_MAP 0x000000 /* map-based hash (default) */
+#define BE_LB_HASH_CONS 0x100000 /* consistent hashbit to indicate a dynamic algorithm */
+#define BE_LB_HASH_TYPE 0x100000 /* get/clear hash types */
/* various constants */
@@ -115,6 +120,7 @@
struct lb_map map; /* LB parameters for map-based algorithms */
struct lb_fwrr fwrr;
struct lb_fwlc fwlc;
+ struct lb_chash chash;
/* Call backs for some actions. Some may be NULL (thus should be ignored). */
void (*update_server_eweight)(struct server *); /* to be called after eweight change */
void (*set_server_status_up)(struct server *); /* to be called after status changes to UP */
diff --git a/include/types/lb_chash.h b/include/types/lb_chash.h
new file mode 100644
index 0000000..3eee12c
--- /dev/null
+++ b/include/types/lb_chash.h
@@ -0,0 +1,42 @@
+/*
+ * include/types/lb_chash.h
+ * Types for Consistent Hash LB algorithm.
+ *
+ * Copyright (C) 2000-2009 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
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _TYPES_LB_CHASH_H
+#define _TYPES_LB_CHASH_H
+
+#include <common/config.h>
+#include <common/ebtree.h>
+#include <common/eb32tree.h>
+
+struct lb_chash {
+ struct eb_root act; /* weighted chash entries of active servers */
+ struct eb_root bck; /* weighted chash entries of backup servers */
+ struct eb32_node *last; /* last node found in case of round robin (or NULL) */
+};
+
+#endif /* _TYPES_LB_CHASH_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */
diff --git a/include/types/server.h b/include/types/server.h
index dae1a71..d7e6da0 100644
--- a/include/types/server.h
+++ b/include/types/server.h
@@ -72,6 +72,15 @@
#define SRV_EWGHT_RANGE (SRV_UWGHT_RANGE * BE_WEIGHT_SCALE)
#define SRV_EWGHT_MAX (SRV_UWGHT_MAX * BE_WEIGHT_SCALE)
+/* A tree occurrence is a descriptor of a place in a tree, with a pointer back
+ * to the server itself.
+ */
+struct server;
+struct tree_occ {
+ struct server *server;
+ struct eb32_node node;
+};
+
struct server {
struct server *next;
int state; /* server state (SRV_*) */
@@ -121,6 +130,9 @@
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 lb_nodes_tot; /* number of allocated lb_nodes (C-HASH) */
+ unsigned lb_nodes_now; /* number of lb_nodes placed in the tree (C-HASH) */
+ struct tree_occ *lb_nodes; /* lb_nodes_tot * struct tree_occ */
unsigned down_time; /* total time the server was down */
time_t last_change; /* last time, when the state was changed */
diff --git a/src/backend.c b/src/backend.c
index ec83205..77c5a92 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -30,6 +30,7 @@
#include <proto/acl.h>
#include <proto/backend.h>
#include <proto/client.h>
+#include <proto/lb_chash.h>
#include <proto/lb_fwlc.h>
#include <proto/lb_fwrr.h>
#include <proto/lb_map.h>
@@ -117,7 +118,10 @@
l += sizeof (int);
}
hash_done:
- return map_get_server_hash(px, h);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, h);
+ else
+ return map_get_server_hash(px, h);
}
/*
@@ -161,7 +165,10 @@
hash = c + (hash << 6) + (hash << 16) - hash;
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
/*
@@ -209,7 +216,10 @@
uri_len--;
p++;
}
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
}
/* skip to next parameter */
@@ -308,7 +318,10 @@
p++;
/* should we break if vlen exceeds limit? */
}
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
}
/* skip to next parameter */
@@ -395,7 +408,10 @@
}
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
struct server *get_server_rch(struct session *s)
@@ -437,7 +453,10 @@
p++;
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
/*
@@ -515,9 +534,13 @@
s->srv = fwlc_get_next_server(s->be, s->prev_srv);
break;
+ case BE_LB_LKUP_CHTREE:
case BE_LB_LKUP_MAP:
if ((s->be->lbprm.algo & BE_LB_KIND) == BE_LB_KIND_RR) {
- s->srv = map_get_server_rr(s->be, s->prev_srv);
+ if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
+ s->srv = chash_get_next_server(s->be, s->prev_srv);
+ else
+ s->srv = map_get_server_rr(s->be, s->prev_srv);
break;
}
else if ((s->be->lbprm.algo & BE_LB_KIND) != BE_LB_KIND_HI) {
@@ -581,8 +604,12 @@
/* If the hashing parameter was not found, let's fall
* back to round robin on the map.
*/
- if (!s->srv)
- s->srv = map_get_server_rr(s->be, s->prev_srv);
+ if (!s->srv) {
+ if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
+ s->srv = chash_get_next_server(s->be, s->prev_srv);
+ else
+ s->srv = map_get_server_rr(s->be, s->prev_srv);
+ }
/* end of map-based LB */
break;
diff --git a/src/cfgparse.c b/src/cfgparse.c
index 9868b05..4eade38 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -1,7 +1,7 @@
/*
* Configuration parser
*
- * Copyright 2000-2008 Willy Tarreau <w@1wt.eu>
+ * Copyright 2000-2009 Willy Tarreau <w@1wt.eu>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
@@ -42,6 +42,7 @@
#include <proto/checks.h>
#include <proto/dumpstats.h>
#include <proto/httperr.h>
+#include <proto/lb_chash.h>
#include <proto/lb_fwlc.h>
#include <proto/lb_fwrr.h>
#include <proto/lb_map.h>
@@ -2440,6 +2441,24 @@
goto out;
}
}
+ else if (!strcmp(args[0], "hash-type")) { /* set hashing method */
+ if (warnifnotcap(curproxy, PR_CAP_BE, file, linenum, args[0], NULL))
+ err_code |= ERR_WARN;
+
+ if (strcmp(args[1], "consistent") == 0) { /* use consistent hashing */
+ curproxy->lbprm.algo &= ~BE_LB_HASH_TYPE;
+ curproxy->lbprm.algo |= BE_LB_HASH_CONS;
+ }
+ else if (strcmp(args[1], "map-based") == 0) { /* use map-based hashing */
+ curproxy->lbprm.algo &= ~BE_LB_HASH_TYPE;
+ curproxy->lbprm.algo |= BE_LB_HASH_MAP;
+ }
+ else {
+ Alert("parsing [%s:%d] : '%s' only supports 'consistent' and 'map-based'.\n", file, linenum, args[0]);
+ err_code |= ERR_ALERT | ERR_FATAL;
+ goto out;
+ }
+ }
else if (!strcmp(args[0], "server")) { /* server address */
int cur_arg;
char *rport;
@@ -4298,13 +4317,20 @@
fwrr_init_server_groups(curproxy);
}
break;
+
case BE_LB_KIND_LC:
curproxy->lbprm.algo |= BE_LB_LKUP_LCTREE | BE_LB_PROP_DYN;
fwlc_init_server_tree(curproxy);
break;
+
case BE_LB_KIND_HI:
- curproxy->lbprm.algo |= BE_LB_LKUP_MAP;
- init_server_map(curproxy);
+ if ((curproxy->lbprm.algo & BE_LB_HASH_TYPE) == BE_LB_HASH_CONS) {
+ curproxy->lbprm.algo |= BE_LB_LKUP_CHTREE | BE_LB_PROP_DYN;
+ chash_init_server_tree(curproxy);
+ } else {
+ curproxy->lbprm.algo |= BE_LB_LKUP_MAP;
+ init_server_map(curproxy);
+ }
break;
}
diff --git a/src/lb_chash.c b/src/lb_chash.c
new file mode 100644
index 0000000..bfd4cd0
--- /dev/null
+++ b/src/lb_chash.c
@@ -0,0 +1,427 @@
+/*
+ * Consistent Hash implementation
+ * Please consult this very well detailed article for more information :
+ * http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
+ *
+ * Our implementation has to support both weighted hashing and weighted round
+ * robin because we'll use it to replace the previous map-based implementation
+ * which offered both algorithms.
+ *
+ * Copyright 2000-2009 Willy Tarreau <w@1wt.eu>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ *
+ */
+
+#include <common/compat.h>
+#include <common/config.h>
+#include <common/debug.h>
+#include <common/eb32tree.h>
+
+#include <types/global.h>
+#include <types/server.h>
+
+#include <proto/backend.h>
+#include <proto/queue.h>
+
+static inline unsigned int chash_hash(unsigned int a)
+{
+ /* This function is one of Bob Jenkins' full avalanche hashing
+ * functions, which when provides quite a good distribution for little
+ * input variations. The result is quite suited to fit over a 32-bit
+ * space with enough variations so that a randomly picked number falls
+ * equally before any server position.
+ * Check http://burtleburtle.net/bob/hash/integer.html for more info.
+ */
+ a = (a+0x7ed55d16) + (a<<12);
+ a = (a^0xc761c23c) ^ (a>>19);
+ a = (a+0x165667b1) + (a<<5);
+ a = (a+0xd3a2646c) ^ (a<<9);
+ a = (a+0xfd7046c5) + (a<<3);
+ a = (a^0xb55a4f09) ^ (a>>16);
+
+ /* ensure values are better spread all around the tree by multiplying
+ * by a large prime close to 3/4 of the tree.
+ */
+ return a * 3221225473U;
+}
+
+/* Return next tree node after <node> which must still be in the tree, or be
+ * NULL. Lookup wraps around the end to the beginning. If the next node is the
+ * same node, return NULL. This is designed to find a valid next node before
+ * deleting one from the tree.
+ */
+static inline struct eb32_node *chash_skip_node(struct eb_root *root, struct eb32_node *node)
+{
+ struct eb32_node *stop = node;
+
+ if (!node)
+ return NULL;
+ node = eb32_next(node);
+ if (!node)
+ node = eb32_first(root);
+ if (node == stop)
+ return NULL;
+ return node;
+}
+
+/* Remove all of a server's entries from its tree. This may be used when
+ * setting a server down.
+ */
+static inline void chash_dequeue_srv(struct server *s)
+{
+ while (s->lb_nodes_now > 0) {
+ if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
+ s->lb_nodes_now = s->lb_nodes_tot;
+ s->lb_nodes_now--;
+ if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
+ s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
+ eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
+ }
+}
+
+/* Adjust the number of entries of a server in its tree. The server must appear
+ * as many times as its weight indicates it. If it's there too often, we remove
+ * the last occurrences. If it's not there enough, we add more occurrences. To
+ * remove a server from the tree, normally call this with eweight=0.
+ */
+static inline void chash_queue_dequeue_srv(struct server *s)
+{
+ while (s->lb_nodes_now > s->eweight) {
+ if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
+ s->lb_nodes_now = s->lb_nodes_tot;
+ s->lb_nodes_now--;
+ if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
+ s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
+ eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
+ }
+
+ while (s->lb_nodes_now < s->eweight) {
+ if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
+ break;
+ if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
+ s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
+ eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node);
+ s->lb_nodes_now++;
+ }
+}
+
+/* This function updates the server trees according to server <srv>'s new
+ * state. It should be called when server <srv>'s status changes to down.
+ * It is not important whether the server was already down or not. It is not
+ * important either that the new state is completely down (the caller may not
+ * know all the variables of a server's state).
+ */
+static void chash_set_server_status_down(struct server *srv)
+{
+ struct proxy *p = srv->proxy;
+
+ if (srv->state == srv->prev_state &&
+ srv->eweight == srv->prev_eweight)
+ return;
+
+ if (srv_is_usable(srv->state, srv->eweight))
+ goto out_update_state;
+
+ if (!srv_is_usable(srv->prev_state, srv->prev_eweight))
+ /* server was already down */
+ goto out_update_backend;
+
+ if (srv->state & SRV_BACKUP) {
+ p->lbprm.tot_wbck -= srv->prev_eweight;
+ p->srv_bck--;
+
+ if (srv == p->lbprm.fbck) {
+ /* we lost the first backup server in a single-backup
+ * configuration, we must search another one.
+ */
+ struct server *srv2 = p->lbprm.fbck;
+ do {
+ srv2 = srv2->next;
+ } while (srv2 &&
+ !((srv2->state & SRV_BACKUP) &&
+ srv_is_usable(srv2->state, srv2->eweight)));
+ p->lbprm.fbck = srv2;
+ }
+ } else {
+ p->lbprm.tot_wact -= srv->prev_eweight;
+ p->srv_act--;
+ }
+
+ chash_dequeue_srv(srv);
+
+out_update_backend:
+ /* check/update tot_used, tot_weight */
+ update_backend_weight(p);
+ out_update_state:
+ srv->prev_state = srv->state;
+ srv->prev_eweight = srv->eweight;
+}
+
+/* This function updates the server trees according to server <srv>'s new
+ * state. It should be called when server <srv>'s status changes to up.
+ * It is not important whether the server was already down or not. It is not
+ * important either that the new state is completely UP (the caller may not
+ * know all the variables of a server's state). This function will not change
+ * the weight of a server which was already up.
+ */
+static void chash_set_server_status_up(struct server *srv)
+{
+ struct proxy *p = srv->proxy;
+
+ if (srv->state == srv->prev_state &&
+ srv->eweight == srv->prev_eweight)
+ return;
+
+ if (!srv_is_usable(srv->state, srv->eweight))
+ goto out_update_state;
+
+ if (srv_is_usable(srv->prev_state, srv->prev_eweight))
+ /* server was already up */
+ goto out_update_backend;
+
+ if (srv->state & SRV_BACKUP) {
+ p->lbprm.tot_wbck += srv->eweight;
+ p->srv_bck++;
+
+ if (!(p->options & PR_O_USE_ALL_BK)) {
+ if (!p->lbprm.fbck) {
+ /* there was no backup server anymore */
+ p->lbprm.fbck = srv;
+ } else {
+ /* we may have restored a backup server prior to fbck,
+ * in which case it should replace it.
+ */
+ struct server *srv2 = srv;
+ do {
+ srv2 = srv2->next;
+ } while (srv2 && (srv2 != p->lbprm.fbck));
+ if (srv2)
+ p->lbprm.fbck = srv;
+ }
+ }
+ } else {
+ p->lbprm.tot_wact += srv->eweight;
+ p->srv_act++;
+ }
+
+ /* note that eweight cannot be 0 here */
+ chash_queue_dequeue_srv(srv);
+
+ out_update_backend:
+ /* check/update tot_used, tot_weight */
+ update_backend_weight(p);
+ out_update_state:
+ srv->prev_state = srv->state;
+ srv->prev_eweight = srv->eweight;
+}
+
+/* This function must be called after an update to server <srv>'s effective
+ * weight. It may be called after a state change too.
+ */
+static void chash_update_server_weight(struct server *srv)
+{
+ int old_state, new_state;
+ struct proxy *p = srv->proxy;
+
+ if (srv->state == srv->prev_state &&
+ srv->eweight == srv->prev_eweight)
+ return;
+
+ /* If changing the server's weight changes its state, we simply apply
+ * the procedures we already have for status change. If the state
+ * remains down, the server is not in any tree, so it's as easy as
+ * updating its values. If the state remains up with different weights,
+ * there are some computations to perform to find a new place and
+ * possibly a new tree for this server.
+ */
+
+ old_state = srv_is_usable(srv->prev_state, srv->prev_eweight);
+ new_state = srv_is_usable(srv->state, srv->eweight);
+
+ if (!old_state && !new_state) {
+ srv->prev_state = srv->state;
+ srv->prev_eweight = srv->eweight;
+ return;
+ }
+ else if (!old_state && new_state) {
+ chash_set_server_status_up(srv);
+ return;
+ }
+ else if (old_state && !new_state) {
+ chash_set_server_status_down(srv);
+ return;
+ }
+
+ /* only adjust the server's presence in the tree */
+ chash_queue_dequeue_srv(srv);
+
+ if (srv->state & SRV_BACKUP)
+ p->lbprm.tot_wbck += srv->eweight - srv->prev_eweight;
+ else
+ p->lbprm.tot_wact += srv->eweight - srv->prev_eweight;
+
+ update_backend_weight(p);
+ srv->prev_state = srv->state;
+ srv->prev_eweight = srv->eweight;
+}
+
+/*
+ * This function returns the running server from the CHASH tree, which is at
+ * the closest distance from the value of <hash>. Doing so ensures that even
+ * with a well imbalanced hash, if some servers are close to each other, they
+ * will still both receive traffic. If any server is found, it will be returned.
+ * If no valid server is found, NULL is returned.
+ */
+struct server *chash_get_server_hash(struct proxy *p, unsigned int hash)
+{
+ struct eb32_node *next, *prev;
+ struct server *nsrv, *psrv;
+ struct eb_root *root;
+ unsigned int dn, dp;
+
+ if (p->srv_act)
+ root = &p->lbprm.chash.act;
+ else if (p->lbprm.fbck)
+ return p->lbprm.fbck;
+ else if (p->srv_bck)
+ root = &p->lbprm.chash.bck;
+ else
+ return NULL;
+
+ hash = chash_hash(hash);
+
+ /* find the node after and the node before */
+ next = eb32_lookup_ge(root, hash);
+ if (!next)
+ next = eb32_first(root);
+ if (!next)
+ return NULL; /* tree is empty */
+
+ prev = eb32_prev(next);
+ if (!prev)
+ prev = eb32_last(root);
+
+ nsrv = eb32_entry(next, struct tree_occ, node)->server;
+ psrv = eb32_entry(prev, struct tree_occ, node)->server;
+ if (nsrv == psrv)
+ return nsrv;
+
+ /* OK we're located between two distinct servers, let's
+ * compare distances between hash and the two servers
+ * and select the closest server.
+ */
+ dp = hash - prev->key;
+ dn = next->key - hash;
+
+ return (dp <= dn) ? psrv : nsrv;
+}
+
+/* Return next server from the CHASH tree in backend <p>. If the tree is empty,
+ * return NULL. Saturated servers are skipped.
+ */
+struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid)
+{
+ struct server *srv, *avoided;
+ struct eb32_node *node, *stop, *avoided_node;
+ struct eb_root *root;
+
+ srv = avoided = NULL;
+ avoided_node = NULL;
+
+ if (p->srv_act)
+ root = &p->lbprm.chash.act;
+ else if (p->lbprm.fbck)
+ return p->lbprm.fbck;
+ else if (p->srv_bck)
+ root = &p->lbprm.chash.bck;
+ else
+ return NULL;
+
+ stop = node = p->lbprm.chash.last;
+ do {
+ struct server *s;
+
+ if (node)
+ node = eb32_next(node);
+ if (!node)
+ node = eb32_first(root);
+
+ p->lbprm.chash.last = node;
+ if (!node)
+ /* no node is available */
+ return NULL;
+
+ /* OK, we have a server. However, it may be saturated, in which
+ * case we don't want to reconsider it for now, so we'll simply
+ * skip it. Same if it's the server we try to avoid, in which
+ * case we simply remember it for later use if needed.
+ */
+ s = eb32_entry(node, struct tree_occ, node)->server;
+ if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
+ if (s != srvtoavoid) {
+ srv = s;
+ break;
+ }
+ avoided = s;
+ avoided_node = node;
+ }
+ } while (node != stop);
+
+ if (!srv) {
+ srv = avoided;
+ p->lbprm.chash.last = avoided_node;
+ }
+
+ return srv;
+}
+
+/* This function is responsible for building the active and backup trees for
+ * constistent hashing. The servers receive an array of initialized nodes
+ * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to
+ * uweight ratio.
+ */
+void chash_init_server_tree(struct proxy *p)
+{
+ struct server *srv;
+ struct eb_root init_head = EB_ROOT;
+ int node;
+
+ p->lbprm.set_server_status_up = chash_set_server_status_up;
+ p->lbprm.set_server_status_down = chash_set_server_status_down;
+ p->lbprm.update_server_eweight = chash_update_server_weight;
+ p->lbprm.server_take_conn = NULL;
+ p->lbprm.server_drop_conn = NULL;
+
+ p->lbprm.wdiv = BE_WEIGHT_SCALE;
+ for (srv = p->srv; srv; srv = srv->next) {
+ srv->prev_eweight = srv->eweight = srv->uweight * BE_WEIGHT_SCALE;
+ srv->prev_state = srv->state;
+ }
+
+ recount_servers(p);
+ update_backend_weight(p);
+
+ p->lbprm.chash.act = init_head;
+ p->lbprm.chash.bck = init_head;
+ p->lbprm.chash.last = NULL;
+
+ /* queue active and backup servers in two distinct groups */
+ for (srv = p->srv; srv; srv = srv->next) {
+ srv->lb_tree = (srv->state & SRV_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act;
+ srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;
+ srv->lb_nodes_now = 0;
+ srv->lb_nodes = (struct tree_occ *)calloc(srv->lb_nodes_tot, sizeof(struct tree_occ));
+
+ for (node = 0; node < srv->lb_nodes_tot; node++) {
+ srv->lb_nodes[node].server = srv;
+ srv->lb_nodes[node].node.key = chash_hash(srv->puid * SRV_EWGHT_RANGE + node);
+ }
+
+ if (srv_is_usable(srv->state, srv->eweight))
+ chash_queue_dequeue_srv(srv);
+ }
+}