# Nginx's hashtable key hash function **URL:** \ **Category:** NGINX\ **Created:** [July 28, 2010, 8:17pm UTC](https://www.ruby-forum.com/t/nginxs-hashtable-key-hash-function/192348 "2010-07-28T20:17:15Z")\ **Posts on this page:** 1\ **Page:** 1
**Author:** ![Barry\_Jaspan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f1d935/32.png) [@Barry\_Jaspan](https://www.ruby-forum.com/u/Barry_Jaspan)\ **Post date:** [July 28, 2010, 8:17pm UTC](https://www.ruby-forum.com/t/nginxs-hashtable-key-hash-function/192348/1 "2010-07-28T20:17:15Z")
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](http://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](http://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: 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](http://acquia.com) removed\_email\_address@domain.invalid | (c) 617.905.2208 | (w) 978.296.5231 “Get a free, hosted Drupal 7 site: [http://www.drupalgardens.com](http://www.drupalgardens.com)”