[MEDIUM] hash: add support for an 'avalanche' hash-type
When the number of servers is a multiple of the size of the input set,
map-based hash can be inefficient. This typically happens with 64
servers when doing URI hashing. The "avalanche" hash-type applies an
avalanche hash before performing a map lookup in order to smooth the
distribution. The result is slightly less smooth than the map for small
numbers of servers, but still better than the consistent hashing.
diff --git a/doc/configuration.txt b/doc/configuration.txt
index a15b035..7794e19 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -2235,6 +2235,15 @@
to a farm, most connections will be redistributed to different
servers. This can be inconvenient with caches for instance.
+ avalanche this mechanism uses the default map-based hashing described
+ above but applies a full avalanche hash before performing the
+ mapping. The result is a slightly less smooth hash for most
+ situations, but the hash becomes better than pure map-based
+ hashes when the number of servers is a multiple of the size of
+ the input set. When using URI hash with a number of servers
+ multiple of 64, it's desirable to change the hash type to
+ this value.
+
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
diff --git a/include/types/backend.h b/include/types/backend.h
index 91d95b1..a3237ff 100644
--- a/include/types/backend.h
+++ b/include/types/backend.h
@@ -94,7 +94,8 @@
/* 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 */
+#define BE_LB_HASH_AVAL 0x200000 /* run an avalanche hash before a map */
+#define BE_LB_HASH_TYPE 0x300000 /* get/clear hash types */
/* various constants */
diff --git a/src/backend.c b/src/backend.c
index 26bc882..ff06d2c 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -118,6 +118,8 @@
h ^= ntohl(*(unsigned int *)(&addr[l]));
l += sizeof (int);
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ h = full_hash(h);
hash_done:
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, h);
@@ -165,6 +167,8 @@
hash = c + (hash << 6) + (hash << 16) - hash;
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ hash = full_hash(hash);
hash_done:
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, hash);
@@ -217,6 +221,8 @@
uri_len--;
p++;
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ hash = full_hash(hash);
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, hash);
else
@@ -285,6 +291,8 @@
p++;
/* should we break if vlen exceeds limit? */
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ hash = full_hash(hash);
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, hash);
else
@@ -374,6 +382,8 @@
p--;
}
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ hash = full_hash(hash);
hash_done:
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, hash);
@@ -419,6 +429,8 @@
len--;
p++;
}
+ if ((px->lbprm.algo & BE_LB_HASH_TYPE) != BE_LB_HASH_MAP)
+ hash = full_hash(hash);
hash_done:
if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
return chash_get_server_hash(px, hash);
diff --git a/src/cfgparse.c b/src/cfgparse.c
index d3223ff..124e599 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -3788,8 +3788,12 @@
curproxy->lbprm.algo &= ~BE_LB_HASH_TYPE;
curproxy->lbprm.algo |= BE_LB_HASH_MAP;
}
+ else if (strcmp(args[1], "avalanche") == 0) { /* use full hash before map-based hashing */
+ curproxy->lbprm.algo &= ~BE_LB_HASH_TYPE;
+ curproxy->lbprm.algo |= BE_LB_HASH_AVAL;
+ }
else {
- Alert("parsing [%s:%d] : '%s' only supports 'consistent' and 'map-based'.\n", file, linenum, args[0]);
+ Alert("parsing [%s:%d] : '%s' only supports 'avalanche', 'consistent' and 'map-based'.\n", file, linenum, args[0]);
err_code |= ERR_ALERT | ERR_FATAL;
goto out;
}
diff --git a/src/lb_chash.c b/src/lb_chash.c
index a2582f0..58f1c9e 100644
--- a/src/lb_chash.c
+++ b/src/lb_chash.c
@@ -271,8 +271,6 @@
else
return NULL;
- hash = full_hash(hash);
-
/* find the node after and the node before */
next = eb32_lookup_ge(root, hash);
if (!next)