MEDIUM: backend: add support for the wt6 hash
This function was designed for haproxy while testing other functions
in the past. Initially it was not planned to be used given the not
very interesting numbers it showed on real URL data : it is not as
smooth as the other ones. But later tests showed that the other ones
are extremely sensible to the server count and the type of input data,
especially DJB2 which must not be used on numeric input. So in fact
this function is still a generally average performer and it can make
sense to merge it in the end, as it can provide an alternative to
sdbm+avalanche or djb2+avalanche for consistent hashing or when hashing
on numeric data such as a source IP address or a visitor identifier in
a URL parameter.
diff --git a/doc/configuration.txt b/doc/configuration.txt
index c430ec3..0b4844b 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -2548,6 +2548,14 @@
poorly with numeric-only input or when the total server weight is
a multiple of 33, unless the avalanche modifier is also used.
+ wt6 this function was designed for haproxy while testing other
+ functions in the past. It is not as smooth as the other ones, but
+ is much less sensible to the input data set or to the number of
+ servers. It can make sense as an alternative to sdbm+avalanche or
+ djb2+avalanche for consistent hashing or when hashing on numeric
+ data such as a source IP address or a visitor identifier in a URL
+ parameter.
+
<modifier> indicates an optional method applied after hashing the key :
avalanche This directive indicates that the result from the hash
diff --git a/include/common/hash.h b/include/common/hash.h
index f6875c9..379bf89 100644
--- a/include/common/hash.h
+++ b/include/common/hash.h
@@ -23,6 +23,7 @@
#define _COMMON_HASH_H_
unsigned long hash_djb2(const char *key, int len);
+unsigned long hash_wt6(const char *key, int len);
unsigned long hash_sdbm(const char *key, int len);
#endif /* _COMMON_HASH_H_ */
diff --git a/include/types/backend.h b/include/types/backend.h
index 57d17bd..6325be2 100644
--- a/include/types/backend.h
+++ b/include/types/backend.h
@@ -114,6 +114,7 @@
/* BE_LB_HFCN_* is the hash function, to be used with BE_LB_HASH_FUNC */
#define BE_LB_HFCN_SDBM 0x000000 /* sdbm hash */
#define BE_LB_HFCN_DJB2 0x400000 /* djb2 hash */
+#define BE_LB_HFCN_WT6 0x800000 /* wt6 hash */
#define BE_LB_HASH_FUNC 0xC00000 /* get/clear hash function */
diff --git a/src/backend.c b/src/backend.c
index e044430..7689cea 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -61,6 +61,9 @@
case BE_LB_HFCN_DJB2:
hash = hash_djb2(key, len);
break;
+ case BE_LB_HFCN_WT6:
+ hash = hash_wt6(key, len);
+ break;
case BE_LB_HFCN_SDBM:
/* this is the default hash function */
default:
diff --git a/src/cfgparse.c b/src/cfgparse.c
index bb79a34..28507dd 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -4128,9 +4128,11 @@
}
else if (!strcmp(args[2], "djb2")) {
curproxy->lbprm.algo |= BE_LB_HFCN_DJB2;
+ } else if (!strcmp(args[2], "wt6")) {
+ curproxy->lbprm.algo |= BE_LB_HFCN_WT6;
}
else {
- Alert("parsing [%s:%d] : '%s' only supports 'sdbm' and 'djb2' hash functions.\n", file, linenum, args[0]);
+ Alert("parsing [%s:%d] : '%s' only supports 'sdbm', 'djb2' or 'wt6' hash functions.\n", file, linenum, args[0]);
err_code |= ERR_ALERT | ERR_FATAL;
goto out;
}
diff --git a/src/hash.c b/src/hash.c
index 8da3003..034685e 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -17,6 +17,33 @@
#include <common/hash.h>
+unsigned long hash_wt6(const char *key, int len)
+{
+ unsigned h0 = 0xa53c965aUL;
+ unsigned h1 = 0x5ca6953aUL;
+ unsigned step0 = 6;
+ unsigned step1 = 18;
+
+ for (; len > 0; len--) {
+ unsigned int t;
+
+ t = ((unsigned int)*key);
+ key++;
+
+ h0 = ~(h0 ^ t);
+ h1 = ~(h1 + t);
+
+ t = (h1 << step0) | (h1 >> (32-step0));
+ h1 = (h0 << step1) | (h0 >> (32-step1));
+ h0 = t;
+
+ t = ((h0 >> 16) ^ h1) & 0xffff;
+ step0 = t & 0x1F;
+ step1 = t >> 11;
+ }
+ return h0 ^ h1;
+}
+
unsigned long hash_djb2(const char *key, int len)
{
unsigned long hash = 5381;