This message assumes some understanding of nginx's hash table algorithms in ngx_hash.c.<br><br>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.<br>
<br>For Drupal Gardens (<a href="http://www.drupalgardens.com">www.drupalgardens.com</a>), 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 <a href="http://somename.drupalgardens.com">somename.drupalgardens.com</a>, though some customers set up their own custom somename.tld.<br>
<br>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?<br>
<br>So, I dug into the code, and this is what I found:<br><br>* 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 ".<a href="http://drupalgardens.com">drupalgardens.com</a>" is 18 characters, all entries consume at least 24 bytes in a bucket, and most consume 32 bytes or more.<br>
<br>* With a hash bucket size of 64 or 128, a bucket is full after 4 or 5 entries hash to it.<br><br>* The hash algorithm isn't that great. The hash key algorithm, from ngx_hash.h, is:<br>
<br>
#define ngx_hash(key, c) ((ngx_uint_t) key * 31 + c)<br>
<br>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.<br>
<br>* 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.<br>
<br>* 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:<br><br> if (hinit->max_size > 10000 && hinit->max_size / nelts < 100) {<br>
start = hinit->max_size - 1000;<br> }<br><br>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:<br><br> start = nelts / (bucket_size / (2 * sizeof(void *)));<br>
<br>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!<br>
<br>So, the question of course is: What is my best course of action? Options include:<br><br>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.<br>
<br>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.<br>
<br>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.<br><br>4. Change ngx_hash.c to have a different collision-handling strategy, e.g. increment the key on a collision.<br>
<br>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.<br>
<br> 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.<br><br>Thanks,<br><br>Barry<br><br><br clear="all"><br>-- <br>Barry Jaspan<br><font size="1"><span style="color: rgb(102, 102, 102);">Senior Architect | </span><a style="color: rgb(102, 102, 102);" href="http://acquia.com" target="_blank">Acquia</a><br style="color: rgb(102, 102, 102);">
<a style="color: rgb(102, 102, 102);" href="mailto:barry.jaspan@acquia.com" target="_blank">barry.jaspan@acquia.com</a><span style="color: rgb(102, 102, 102);"> | (c) 617.905.2208 | (w) 978.296.5231</span><br style="color: rgb(102, 102, 102);">
<br style="color: rgb(102, 102, 102);"><span style="color: rgb(102, 102, 102);">"Get a free, hosted Drupal 7 site: </span><a style="color: rgb(102, 102, 102);" href="http://www.drupalgardens.com/" target="_blank">http://www.drupalgardens.com</a><span style="color: rgb(102, 102, 102);"><span style="color: rgb(102, 102, 102);">"</span></span></font><br>
<br>