Nginx's hashtable key hash function

Server NGINX
1

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
[email protected] | (c) 617.905.2208 | (w) 978.296.5231

“Get a free, hosted Drupal 7 site: http://www.drupalgardens.com”