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