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

[Rachel Llorenna]

Hrm, I thought it might be something like that. I'll recompile without
--enable-small-net and try again. But, I've enabled that on both
ircd-ratbox and ircd-hybrid; but as AndroSyn mentioned on the
ircd-ratbox mailing list, it currently does not reduce the table size
even when that flag is used. I'll resubmit my new results to both
lists.

On 4/24/05, Michael Wobst <michael at elite-web.de> wrote:
> The current algorithm we use is by far not the best one, but it looks
> like you enabled the small-net feature.  The size of the table is then
> 4096 instead of 32768, that's why you have such long chains.
> 
> -Michael
> 
> 
> Rachel Llorenna wrote:
> > I connected several (150,000) fake clients via siege.pl, a lightweight ircd
> > stress testing script I wrote. Drones were connected with very similar nicknames
> > (userXXXXXX where XXXXXX is the client number that ranged between 1 and 150000).
> > The UID's were pretty similar too, sequentially they went from 0AZAAAAAA to
> > 0AZAAINXF, but this is expected behavior. Although nicknames are not expected to
> > be too close to each other during normal operation, UID's can reasonably assumed
> > as such.
> >
> > The main hub (hybrid/bin/ircd) ran ircd-hybrid-7.1beta. The test leaves utilized
> > ircd-hybrid-7.1beta (hybrid2/bin/ircd) and ircd-ratbox-2.0.8 (ratbox/bin/ircd)
> >
> > 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.
> >
> > 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.
> >
> > cerberus used by far the most memory but presumably had almost no collisions
> > (with 150,000 clients, 113,000 nodes in use meant that most contained one or two
> > clients). Perl's hashing algorithm (from 5.8 and on) has an extra shift to avoid
> > collisions, at the expense of much more memory consumption. As well, the number
> > in %MEM includes other hashes, like nickname hashes and server hashes, too.
> >
> > Evidence:
> > USER       PID %CPU %MEM   VSZ  RSS TTY      STAT START   TIME COMMAND
> > frequen    767  0.0  7.9 74424 22748 ?       Ss   Apr14   4:13 hybrid/bin/ircd
> > entries: 150010 buckets: 1565 max chain: 237
> >
> > frequen    773  0.0  1.1 74280 3400 ?        Ss   Apr14   2:09 hybrid2/bin/ircd
> > entries: 150007 buckets: 1586 max chain: 212
> >
> > frequen  31505  0.0 25.7 82288 73248 ?       Ss   Apr22   0:03 ratbox/bin/ircd
> > Size: 65536 Empty: 5967 (9.105%)
> > Average depth: 2.000/2.000 Highest depth: 11
> > Nodes with 0 entries: 5967
> > Nodes with 1 entries: 15259
> > Nodes with 2 entries: 18075
> > Nodes with 3 entries: 13697
> > Nodes with 4 entries: 7565
> > Nodes with 5 entries: 3287
> > Nodes with 6 entries: 1174
> > Nodes with 7 entries: 364
> > Nodes with 8 entries: 118
> > Nodes with 9 entries: 23
> > Nodes with 10 entries: 7
> >
> > frequen  31532  0.2 40.1 122468 114460 pts/2 S+   Apr22   2:26
> > cerberus: cerberus.int
> > 113269 of 262144 buckets in use
> >
> > 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)
> >
> > If you have any comments or anything to add (maybe I just happened to
> > find a particularly bad test case?), feel free to reply back to the
> > list. I would especially appreciate commentary from the developers of
> > ircd-hybrid in case this issue has been fixed for new versions.
> 


-- 
Regards,

Rachel Llorenna (frequency)