Lets look at some RRs

Like any open source developer, I like to jump the gun and think about future plans before finishing the work in front of me.

One thing I have been thinking about is how Deadwood should store non-recursive DNS records. An authoritative record is really quite different from a cached record, and needs to be stored in memory differently.

Here is how Deadwood (and MaraDNS) store a record in memory:

• A hash of a string containing both the hostname we are looking for (samiam.org, www.tagged.com, etc.) and the record type we want (A, NS, MX, AAAA, etc.) is made
• This hash is used to look up the string in memory
• A given slot can store multiple records
• We look at all the records in the slot until we find the one we are looking for

Note that the records are stored differently than the way the RFCs assume records are stored; the "A" and "CNAME" record for the same data is assumed to have the same slot in the hash (or BTREE or whatever).

While for a cache it's OK if the data for an A record is in a completely different location in memory than the CNAME record for the same hostname, this causes issues with an authoritative nameserver. Namely:

• For star records to be anally RFC compliant, the RFCs assume the DNS server stores all of the records for a given hostname in the same slot
• Whether to give a NXDOMAIN or "host not there" reply depends on whether there are some records for a given hostname
• We can more quickly find a corresponding CNAME record if the CNAME record is in the same hash slot as where the A/MX/whatever record would be

So, how should we store multiple records in the same structure?

Well, my current plan is to have an 8-element "mini-hash" for each hostname. Why 8 elements? Well, when I did some research in to what modulus works best for making it so the most common RR types have their own "slot" [1], I saw that a modulus of 8 is the best modulus under 10. The only "collision" (for A, NS, MX, CNAME, SOA, PTR, TXT, and AAAA records) is between AAAA and PTR records; however combined AAAA/PTR records are pretty uncommon.

So, my current plan is to have an 8-element array; each element of this array will point to a string, an RR number, and a "next" element (just in case they want to use some exotic record type). The string will be the data for the record they want; the RR number the RR type, and next a linked list to allow collisions.

So, this will probably be how I store records once I give Deadwood the ability to have authoritative data.

- Sam

[1] awk '{for(a=3;a<=20;a++){delete(c);printf("a: %d ",a);for(b=1;b<=NF;b++){d=$b % a;printf("%d",d);c[d]++;if(c[d]>1){printf("*");}printf(" ");}print " "}}'