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