[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/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 */