Hello Bhaskar,
On Sun, Oct 20, 2013 at 11:25:31AM -0400, Bhaskar Maddala wrote:
> Hello,
>
> I did mean djb2, typo on my end, and it is the same as as hash_djbx33.
OK thanks for confirming.
> I will take a look at 1.5 later today, and try to test it out
>
> Here [1] is a short page on the 2 functions.
Ah OK, yes indeed the current hash function is the same as sdbm. I
wasn't aware of this. I remember we did some experiments on hashes
with Aleks many years ago and I think the current function appeared
good enough in these tests.
> The config we have in
> production uses consistent hashing on the host header, the function
> "get_server_hh" is invoked we have patches that update backend.c [2] from
>
> hash = *p + (hash << 6) + (hash << 16) - hash;
>
> to
>
> hash = (px->lbprm.func & BE_LB_HASH_DJB2) ? 5381 : 0;
> hash = *p + (hash << 5) + hash;
>
>
> (the equivalent changes where required), when the "hash-func" option is
> specified. The choice to use host header, was an application design.
This is a common choice, typically if you put a cache such as varnish
behind haproxy.
I ran a few tests on an old program out of which I had to blow the dust,
we used it 6 years ago for some hash tests, and I've put it here :
http://1wt.eu/test-hash/hashcount.c
It supports the following hashes in argv[1] :
0 test_hash
1 wt_hash
2 wt_hash5
3 wt_hash6
4 hash_djbx33
5 haproxy_uri_hash (=sdbm)
The second argument is the number of buckets and if a third one is passed,
a final avalanche is applied after the hash.
I fed it with the top 1000 and top 10000 domains from alexa.com's top-1m :
http://www.alexa.com/topsites
It appears that haproxy_uri_hash and wt_hash5 produce the smoothest
distribution with a cleaner and longer gaussian bell.
But in our case, we're not looking for the cleanest distribution in
practice. What we want is to shorten the distance between the most
commonly used and the least commonly used server. And it appears in
tests that when hasing 1000 domains to 50 servers, djb33 provides a
minimum usage of 14 for a max of 28 when the current algo does (12,28)
and wt_hash even worse (8,32).
Applying the avalanche on the hash result further increases the
differences between the most and the least loaded servers in my
tests on djb33 and sdbm but improved the results with the others :
normal avalanche
min max ratio min max ratio
test_hash 8 32 0.25 !! 10 28 0.36
wt_hash 8 32 0.25 !! 9 30 0.30
wt_hash5 7 27 0.26 !! 12 29 0.41
wt_hash6 14 27 0.52 <- 14 27 0.52 <-
djb33 14 28 0.50 8 33 0.24 !!
sdbm 12 28 0.43 11 33 0.33
However, on a small number of servers (4), the results are the
opposite. Hashing 100 names to 4 servers gives a high discrepancy on
djb33 and the best for wt_hash5/6, both with and without avalanche :
normal avalanche
min max ratio min max ratio
test_hash 20 30 0.67 19 31 0.61
wt_hash 14 31 0.45 20 36 0.56
wt_hash5 20 29 0.69 21 28 0.75
wt_hash6 24 26 0.92 <- 23 28 0.82 <-
djb33 17 42 0.40 !! 19 35 0.54
sdbm 16 33 0.48 22 30 0.73
So first, it seems important not to apply the avalanche on top of djb33.
Second, on a small number of servers, sdbm+avalanche will be much better
than sdbm alone (so 1.5 is smoother than 1.4). However on a large number
of servers, djb33 alone seems better, than sdm alone or avalanched. It's
interesting to note that wt_hash6 outperforms all the other ones in both
small and large sets, with avalanche and normal modes, which makes me
happy :-)
I'm now wondering whether it would make sense to add both djb33 and wthash6
as options. We would also remove "avalanche" from hash-type and move it to
an option of the hash algo (it's not supported in 1.4 anyway). In the tests,
I also noticed that djb33 is very bad on server counts that are multiples of
33, so this must be considered carefully.
So maybe it can make sense to add a new "hash-algo" directive with a few
values such as "djb2", "sdbm", "wt6" and the same variants with "+avalanche".
> The
> choice of using DJB2 came about from testing load distribution on the
> backends. A little dated description is available at [3]. The number of
> haproxy, varnish and web nodes has grown substantially. I say this to make
> clear that this might be specific for larger deployments.
That's always when the number of servers increase that you face poor hash
distribution, so that's not surprizing.
Best regards,
Willy
