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