nginx's hashtable key hash function

[Barry Jaspan]

This message assumes some understanding of nginx's hash table algorithms in
ngx_hash.c.

I'm having some problems with nginx's server_names hash table. I've dug into
the code and believe I have found the issue. I'm currently using 0.7.65 but
a quick check in the 0.8 code does not appear to show any changes to this
part of the code.

For Drupal Gardens (www.drupalgardens.com), we currently have about 15,000
domain names in our nginx conf file, and new domain names coming in all the
time. We are unable to use a single virtual host for all sites, so we really
do need to list that many domain names explicitly (and our hope is to list
at least 10x more on a single nginx server). The vast majority of the names
are somename.drupalgardens.com, though some customers set up their own
custom somename.tld.

Until recently, when we had about 10-12,000 domains, our
server_names_hash_max_size was up to 131072, with
server_names_hash_bucket_size of 128 (we're using 64-bit EC2 instances so I
think the cache line size is 64 bytes, but see below for why that probably
isn't relevant). Obviously 131k is a lot more than 12k but the documentation
says you should only need the max size to be about the same as the number of
domain names. Somewhere around 13,000 domains we got the error message
"could not build the server_names_hash, increase max_size or bucket_size"
again, so bumped max size up to 196608. That's working for now but just begs
the question: Why does it have to be so large?

So, I dug into the code, and this is what I found:

* Each hash table entry consumes space in a bucket. The space required is
the length of the domain name, rounded up to sizeof(void *) (8 on a 64-bit
machine), with some overhead to store the domain's actual length as well.
Since ".drupalgardens.com" is 18 characters, all entries consume at least 24
bytes in a bucket, and most consume 32 bytes or more.

* With a hash bucket size of 64 or 128, a bucket is full after 4 or 5
entries hash to it.

* The hash algorithm isn't that great. The hash key algorithm, from
ngx_hash.h, is:

#define ngx_hash(key, c)   ((ngx_uint_t) key * 31 + c)

In ngx_hash_init() in ngx_hash.c, I removed the #if 0 to enable logging of
the hash keys. In a test environment with about 11k domains and max_size of
196608 (ngx_hash_init() choose 195609 as the actual hash size), I found that
there were about 11k unique hash keys (which is good), but that the most
popular keys had 4 collisions, and a decent number had 2-3 collisions.
Despite the fact that 95% of the hash table entries were empty, one more
collision on a "most popular key" would force us to increase the max_size
again.

* I increased the max_size to 1,000,000 (ngx_hash_init() choose 999000 as
the actual hash size) and found that there were *still* keys that had 4
collisions, despite the fact that now 99.5% of the hash table entries were
empty.

* For ha-ha's, I then set max_size to 10,000,000... and broke the heuristic
in ngx_hash_init() that controls the hash size search space:

    if (hinit->max_size > 10000 && hinit->max_size / nelts < 100) {
        start = hinit->max_size - 1000;
    }

With max_size of 10,000,000 and nelts of 11kk, max_size/nelts is greater
than 100, so start remained as set by the previous code:

    start = nelts / (bucket_size / (2 * sizeof(void *)));

Oh a 64-bit machine, that means that start = 11k / (128 / 16) =~ 1500. So
ngx_hash_init() tried to create the server names hash with a max_size
starting at 1500 and increasing by 1 until it got to somewhere in the 64k
range, the first value that got lucky enough to avoid enough hash collisions
to actually work. However, under these conditions it took nginx 15 seconds
to start since it tried to re-create the hashtable so many times!

So, the question of course is: What is my best course of action? Options
include:

1. Keep making the hash table bigger. I don't think that will really help
since it is already 95% empty and too many collisions are still occurring.

2. Make the bucket size bigger. This impacts performance for every hash
table entry that has many collisions, but even though some keys have many
collisions most seem not to, so the impact won't be much that often. Of
course, this also means that a hash bucket will no longer fit into a CPU
cache entry, but I think that level of optimization is way beyond what I
need to be worrying about right now.

3. Rebuild nginx with a better hash algorithm. Of course, the hash algorithm
has to run on every request, so it needs to be fast.

4. Change ngx_hash.c to have a different collision-handling strategy, e.g.
increment the key on a collision.

It seems pretty clear that #2 is the most expedient choice for me. It also
seems like ngx_hash_init()'s strategy of trying to find the minimum possible
hash table size could be improved. Perhaps instead of start++ each time
through the loop, you could binary search between start and max_size. Or
just always create the hash table to have max_size entries.

I'm just curious for feedback from the nginx developers about whether my
analysis is correct and whether nginx's server names hash table strategy can
be improved.

Thanks,

Barry



-- 
Barry Jaspan
Senior Architect | Acquia <http://acquia.com>
barry.jaspan at acquia.com | (c) 617.905.2208 | (w) 978.296.5231

"Get a free, hosted Drupal 7 site: http://www.drupalgardens.com"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://nginx.org/pipermail/nginx/attachments/20100728/4792b7e7/attachment-0001.html>