This year I have rewritten BIND’s DNS name compression and decompression code. I didn’t plan to, it just sort of happened! Anyway, last week my colleague Petr was doing some benchmarking, and he produced some numbers that seemed too good to be true, so I have re-done the measurement myself, and wow.
This side-quest started off as a small cleanup, getting rid of the remains of late-1990s IETF mistakes, such as extended label types and local compression. Nobody reading the BIND code should have to understand what GLOBAL14 means!
As a second-order side-quest, I also cleaned up all the duplicated
tolower implementations dotted around various parts of BIND. That
led to a third-order side-quest, optimizing
(one of my most popular blog posts!)
Then a bug was found in BIND’s DNS name compression code, so I looked at it in more detail. The bug was partly due to a poor API that separated the jobs of finding out if a name can be compressed, and adding a new name to the compression context. And the implementation used a lot more machinery than I thought necessary.
I happened to have a DNS name compression algorithm in the back of my mind, so I took the opportunity to turn it into code and see how well it works. As well as being much less code, with a less error-prone API, and using much less memory, it also performs nicely.
More recently, Petr determined that BIND’s DNS name decompression code
could do with being faster. (There was even a 20-year-old comment
saying so!) So I rewrote
dns_name_fromwire() as well,
getting speedups of between 1.4x for names with many compressed
labels, and 15x for names with a few large uncompressed labels.
(I also came up with a neat performance trick I haven’t seen before, ingesting many labels at a time instead of one at a time.)
Petr and I have been looking at BIND’s performance with a large real-world zone file. It is 2GB as a standard text DNS zone file, with nearly 35 million records.
Transferring a zone gives a DNS server’s compression and decompression code some good exercise: plenty of large DNS messages containing lots of names. (And plenty of the server’s other code gets a workout too, but that’s for another day.) So we would hope to see some visible improvements from my changes.
I ran some tests on my laptop, with two copies of BIND transferring
the big zone over the loopback interface. Both copies of were running
main branch (soon to be BIND 9.19.8) which I will call
“fast”, or both running
main with all my compression changes
reverted, which I will call “slow”. I’m only giving times accurate to
one second because that’s about how much they varied across different
slow 43s fast 41s
It turns out the speed of the zone transfer is mostly determined by the receiver: the elapsed time closely matches the secondary server’s CPU usage. The new decompression code has reduced the time by 5%, which isn’t bad when most of the work is ingesting records into BIND’s in-memory database.
slow bytes 1128753653 fast bytes 1108286489
The old compression code would give up for certain long names, whereas the new code compresses everything it can. This saves 2% of the bandwidth.
I’ve left the unexpectedly dramatic numbers till last. Here are the CPU times from the primary server:
slow 33s fast 20s
The new compression code reduces the time by more than 1/3! I am frankly astounded, and extremely pleased with myself.