PowerDNS recursor deployments do not age like wine
Posted by bert hubert Fri, 31 Mar 2006 09:22:00 GMT
In a break from tradition, I’ll start with the ‘life’ stuff. It has been very busy lately and I hope to relax some more. I’ve finished some non-PowerDNS work and should be under less pressure the coming weeks.
Tomorrow, Saturday, I’ll be a ‘VIP guest’ (wow) at the Dataman ISP Kart Competition. I hope and expect this to be fun. I’ve heard of a number of PowerDNS users that will be there, it should be good to meet them (once more) in real life!
Ok, PowerDNS. To start with a quote from one of my favorite movies, Pulp Fiction:
The thing is, Butch, right now you got ability. But painful as it may be, ability don’t last.
(…)
M.therf.ckers who thought their ass would age like wine. If you mean it turns to vinegar, it does. If you mean it gets better with age, it don’t.
A typical high-load PowerDNS recursor installation does not age like wine.
The past few days I’ve ploughed through the PowerDNS code and found many worthwhile micro-optimizations, totalling up to about a 20% performance increase, at the cost of some code obfuscation. See the PowerDNS timeline for details.
However, 20% is not what I am looking for. Dan Bernstein’s dnscache, part of DJBDNS is reportedly a lot faster on many loads than PowerDNS. It should be said that the actual user experience of PowerDNS is probably better though, as it is generally quicker to react to broken domains and broken queries.
It turns out that the footprint of a busy recursor is around 2 to 3 million cache entries. Internally, these entries are almost always stored in a tree, although I’m pondering moving back to a hashed list, as such a structure should excell at making lookups for things which aren’t there, which happens a lot in DNS.
Anyhow, currently things are in a red black tree, which will have around 2*log2(2500000) levels, which is in the order of 42. An average lookup can be expected to find its record 35 levels deep or so. I’m no computer science theorist, but these numbers aren’t very far off the mark.
A lookup in a full cache will then take 35 comparisons, one for every level we have to descend. Each DNS query takes at least two lookups, which makes 70 comparisons. A query for which we have no answer (yet) takes at least 6 lookups right now, for a stunning 210 comparisons.
If we look at these internal lookups, they look something like this:
1.0.0.127.in-addr.arpa CNAME
1.0.0.127.in-addr.arpa PTR
1.0.0.127.in-addr.arpa NS
0.0.127.in-addr.arpa NS
0.127.in-addr.arpa NS
127.in-addr.arpa NS
a.root-servers.net CNAME
a.root-servers.net A
etc. What we find is that the first three queries are very closely alike, and very likely all to return nothing from the cache.
So I’ve now implemented a tiny ‘cache cache’ that should help fold the initial three lookups into one, as well as the last two.
There is some further room for improvement, but measurements already show a large performance jump.
Back to the initial comments regaring wine and vinegar, why is that relevant? When the cache is small, PowerDNS doesn’t have to walk that many levels, what we’ve found is that any slowdowns start to happen after many hours.
Stay tuned for further updates - it’ll take quite some hours before the current PowerDNS users can confirm the hopefully spectacular performance gains :-)
