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
MX, etc. Here is
a real zone file for
akira.org (for the
new Akira project), so that you can see
what data is in it:
$ORIGIN akira.org. $TTL 3600 @ IN SOA ns1.banu.com. webmaster.banu.com. ( 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 ns1.banu.com. IN NS ns2.banu.com. IN A 220.127.116.11 IN AAAA 2a01:4f8:110:54e1::14 IN MX 10 messaging.banu.com. www IN A 18.104.22.168 www IN AAAA 2a01:4f8:110:54e1::14 ; SPF record akira.org. IN SPF "v=spf1 a mx -all"
In this example, there are
that are used to find the IP address of a name. The
akira.org. 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 (
akira.org.) name. As an
www by itself in this zone means
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
DomainTree to maintain its properties, but we'll get to
DomainTrees are used to map DNS names to other
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).
ZoneTableTreeused to map a DNS origin to its
ZoneTreeused to map a DNS domain name to its RDATA (record data)
If this is confusing, ignore all of it. Just pick
ZoneTree which represents a single zone such
akira.org. above. A
DomainTree where keys are names and values are record
data (a pointer to a
Here is what the
ZoneTree of the zone presented
above looks like (just the keys are shown):
Dry, right? That's because it has records for only two names in that
www.akira.org.). 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
for a sample root (
root.zone to see its records.
Here is the
ZoneTree for a
example.org. zone (click to zoom):
example.org.zone to see its
Now, the properties of this tree:
downpointer. They start a new sub-tree, and the node they point to is the root node of the sub-tree. Root nodes are outlined in thick black too. As an example, in the
downpointer points to node
foo, and node
foois a sub-tree root.
rightpointers. These work as usual.
.) in domain names.) This happens when no records exist for the labels to the right of the first one. As an example, in the
ns.deepnameexists because there were records for the
ns.deepname.example.org.name, but not for the
example.orgzone, no records for
wild.example.org.exist, but node
wildexists anyway because it has multiple children.
eis on the right of node
eis greater than
downnode of a tree too. The
rightpointer of a node may be
NULLbut there may be more right nodes in the sub-tree's parent. Finding names in the tree has more to it than a simple BST find, as more than one label may exist in a node and there's the
downnode to consider again. We may also be interested in partial matches (common ancestor labels). Insertion has to deal with splitting nodes (called node fission in BIND 10 code). And there are some other bits to consider .
Now let's look
ZoneTree is a tree
that contains everything in a single zone,
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
ZoneTree and find the RDATA (record data) there. The
RDATA itself is stored in a linked-list class
RdataSet which is a straightforward list of RRs
separated by their types
and so on).
Having populated the root zone
with the zone files above, the
ZoneTableTree looks like
The graphs in this post were generated by BIND 10 and rendered using GraphViz.