.@ Tony Finch – blog


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 article is part of a series on optimizing DNS names:

nesting questing

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 tolower() (one of my most popular blog posts!)

compression

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.

decompression

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.)

zone transfers

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.

numbers

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 the current 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 runs.

    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.