[Libevent-users] [patch] replace linear search in evdns with hashed list and add support of listening on unix sockets for evhttp

[Vsevolod Stakhov]

nickm at freehaven.net wrote:
> On Fri, Feb 15, 2008 at 07:22:34PM +0300, Vsevolod Stakhov wrote:
>> Hi,
>>
>> We found a problem with list requests_inflight while using evdns on 
>> highly loaded system (about 2000 DNS requests per second). First of all 
>> linear search is slow and second is that this list is not big enough to 
>> handle all requests, so many requests were in requests_waiting list, 
>> that has no limits on length. Due to this application grows in size 
>> constantly and is not able to serve requests. I've replaced linear list 
>> with hashed list, that improves performance.
> 
> Hi!  This looks pretty good.  I'd like to apply it for trunk to apply
> it to the next release after 1.4.  (I want to avoid applying anything
> but straight bugfixes to 1.4 at this point, so that it can get out of
> beta soon.)  A few comments and questions:
> 
>   - Instead of changing global_max_request_inflight in the code manually,
>     you can just call
>         evdns_set_option("max-inflight:", "2048", DNS_OPTIONS_ALL).

Yes, we are using this method, but setting big value for this was a real 
pain in case of linear search. I've just changed this value for our 
default, but it is not useful for the most cases (not so much load).

>   - Do you have profileing or benchmarking numbers to show how much this
>     helps?  I'd like to be able to confirm that this helps, that "2048" is
>     a good value for MAX_NESTS, etc.

Maybe this value should be calculated as global_max_request_inflighs/10 
to have not more than 10 items in each nest.

>   - It looks like we walk the whole inflight list on nameserver_failed(),
>     evdns_transmit(), evdns_clear_nameservers_and_suspend(), and
>     evdns_shutdown().  Of these, evdns_transmit() still worries me a
>     little: unlike the others, it is frequently called during
>     non-exceptional conditions.  Does it show up in your profiles?

Well, walking through the whole inflight list in case of hashed list is 
not much harder than walking through linear list. If MAX_NESTS would be 
global variable, calculated from global_max_request_inflighs it would 
not be pain at all for most cases.

>> The one thing that is not 
>> logical (but I don't know how to make it better) is that I'm using bzero 
>> of hash nests array in reading resolv conf function.
> 
> Probably it's better to do this in some function called from both
> evdns_resolv_conf_parse() and evdns_config_windows_nameservers().  It
> should probably use a flag to make sure that it hasn't already zeroed the
> array.
> 
> Also, bzero() is deprecated in POSIX.1; you should probably use memset()
> instead.

Agreed.