BIND 10 zones in memory

on 22 Sep 2012 by Mukund (@muks)

BIND 10 is getting close to a formal alpha release soon. At ISC, we are going to blog about its features, how administrators can put it to use on their networks, and how developers can use its libraries. As a warm-up exercise, I want to write about how BIND 10 stores zones and zone data in memory. You'll follow this article easily if you are a programmer who knows about red-black trees and have set up your own DNS server. Let's begin with an explanation anyway. :)

A DNS zone contains (for the majority of us) the DNS configuration of a domain. System administrators create and maintain zone files containing a variety of data about a domain that are served by an authoritative DNS server. These may include records of various types such as A, AAAA, MX, etc. Here is a real zone file for (for the new Akira project), so that you can see what data is in it:

$TTL 3600
@       IN      SOA (
                        2012092202 ; serial
                        21600      ; refresh after 6 hours (for slaves)
                        3600       ; retry after 1 hour (for slaves)
                        604800     ; expire after 1 week (for slaves)
                        3600 )     ; minimum TTL of 1 hour (for resolvers)

                        IN NS
                        IN NS

                        IN A
                        IN AAAA 2a01:4f8:110:54e1::14

                        IN MX   10

www                     IN A
www                     IN AAAA 2a01:4f8:110:54e1::14

; SPF record              IN SPF  "v=spf1 a mx -all"


In this example, there are A and AAAA records for and that are used to find the IP address of a name. The MX record for points to where email for this name should be delivered. There are also other record types. A typical zone file in a company may contain hundreds of such records. Note that some names have a trailing dot (.). This indicates that they are absolute to the root of the DNS namespace. Others don't and these are relative to the zone's origin ( name. As an example, www by itself in this zone means the name.

An authoritative DNS server has to be able to deal with numerous zones, all of which take a place in the DNS hierarchy. It has to be able to efficiently traverse its zone storage data structure for DNS names in order, and quickly locate a particular domain or sub-domain's records. It also has to be careful about how much space such a data structure would occupy in memory.

In BIND 10, we use a modified red-black tree which we call a DomainTree. I will not describe the properties and performance of red-black trees here; you can read about them in the linked article. DomainTree is based on the concept of a red-black tree to inherit its search-tree properties. The main change that was made to the red-black tree was the addition of a down pointer to every node, to make it a tree of trees. There are some additional operations on the DomainTree to maintain its properties, but we'll get to it later. DomainTrees are used to map DNS names to other data.

There are two types of DomainTrees that we use in BIND 10 (three actually, but we'll ignore the third which is used for storing NSEC3 data for now).

If this is confusing, ignore all of it. Just pick up ZoneTree which represents a single zone such as above. A ZoneTree is a DomainTree where keys are names and values are record data (a pointer to a RdataSet).

Here is what the ZoneTree of the zone presented above looks like (just the keys are shown): zone

Dry, right? That's because it has records for only two names in that zone ( and It gets pretty when it gets full. :)

I'll explain the legend used and tree's structure in a moment, but first you have to see some examples. Here is the ZoneTree for a sample root (.) zone:

root zone

Download to see its records.

Here is the ZoneTree for a sample zone (click to zoom): zone

Download to see its records.

Now, the properties of this tree:

Now let's look at ZoneTableTree. Whereas ZoneTree is a tree that contains everything in a single zone, ZoneTableTree is a singleton global tree where the key is the origin name and the value is a pointer to the corresponding ZoneTree (which contains that origin's zone). So when we want to lookup something, we first find the corresponding origin's node in the ZoneTableTree, go to its ZoneTree and find the RDATA (record data) there. The RDATA itself is stored in a linked-list class called RdataSet which is a straightforward list of RRs separated by their types (A, AAAA, MX, SOA and so on).

Having populated the root zone (.), and with the zone files above, the ZoneTableTree looks like this:

the ZoneTableTree

The graphs in this post were generated by BIND 10 and rendered using GraphViz.