[ircd-ratbox] ircd-hybrid-7.1beta1 vs ircd-ratbox-2.0.8 hash algorithm comparisons

Aaron Sethman androsyn at ratbox.org
Sat Apr 23 22:58:09 UTC 2005



On Sat, 23 Apr 2005, Rachel Llorenna wrote:
>
> Conclusions:
> ircd-hybrid showed the least memory consumption, but was extremely slow in terms
> of being able to generate statistics (one server took 351.56 seconds to respond
> and the other took 442.25). With such similar UID's, the distribution became
> extremely poor, indicating a potential denial of service attack. I don't think
> that ircd-hybrid7.1beta is suitable for EFnet at time of writing for this
> reason. UID's are similar by their nature, so the creation of such large chains
> (the maximum chain length was 237 client pointers), which would have to be
> walked when seeking a specific client. Hopefully this will be corrected before
> 7.1 becomes a release candidate; it's definitely not ready for a stable release
> with its current algorithm.

With ircd-ratbox we've made a number of decisions to waste a little memory 
in favor of speed.  One of them being larger hash tables, which will 
reduce collisions quite a bit.

>
> ircd-ratbox's distribution is much better, at the cost of consuming substantial
> amounts of memory compared to ircd-hybrid (about 3.5 times more, in fact). Most
> nodes end up having only one or two entries. It should be noted that ircd-ratbox
> uses the Fowler/Noll/Vo (FNV) hashing algorithm, which is proven to be fast
> while maintaining a low collision rate, even with keys that are as similar as
> UID's are. With such short chains, the FNV algorithm seems to be working nicely
> for EFnet.

FNV was chosen for exactly this reason, because the old hash function was 
absolutely miserable on the UID hash.  We could reduce the collision rate 
by doubling the size of the table, but you reach a point of diminishing 
returns where it starts making little difference.  Currently on the 
largest TS6 portion of EFnet the max depth of the UID hash is 4 and the 
nick hash is only 9 deep.  Both tables have 65535 buckets.

> Suitability:
> ircd-ratbox seems well geared towards TS6-compatible networks such as EFnet,
> while ircd-hybrid seems to have several features geared towards smaller IRC
> networks, where such a collision rate is acceptable. ircd-hybrid might be
> desirable when memory consumption is a concern (public shell providers, etc)

To reduce memory usage with ratbox for smaller networks it would be just a 
matter of making the --enable-small-net configure option use smaller hash 
tables.  I've just been too lazy to actually do it.  There are probably a 
handful of other memory reducing tweaks that could be done, its just a 
matter of doing them(feel free to submit a patch if you want)

-Aaron



More information about the ircd-ratbox mailing list