CODEWITHSUNDEEP
dictionarydns
karthiksatyanarayana
karthiksatyanarayana

Reputation: 109

How do Top level Name Servers handle huge map?

Typically top level domain name servers like "com" name server, need to have a map which gives out IP address of the name server for different domain names like "google","yahoo","facebook", etc.

I image this would have a very large number of key-value pairs. How is this huge map handled? Is it a unordered map, ordered map, or any other "special" implementation?

Upvotes: 0

Views: 46

Answers (1)

Patrick Mevzek
Patrick Mevzek

Reputation: 12615

Most of the major nameservers are open souce so you could study their sources:

  • bind
  • nsd
  • knot
  • yadifa
  • geodns

But it is of course far more complicated than just a "map". Even if you start with very old documents, like RFC 1035 that defines the protocol they are few details about implementation, as expected.

While name server implementations are free to use any internal data structures they choose, the suggested structure consists of three major parts:

  • A "catalog" data structure which lists the zones available to this server, and a "pointer" to the zone data structure. The main purpose of this structure is to find the nearest ancestor zone, if any, for arriving standard queries.

  • Separate data structures for each of the zones held by the name server.

  • A data structure for cached data. (or perhaps separate caches for different classes)

(and read the following sentences about various optimizations)

First, the task is different for an authoritative or a recursive nameserver. Some authoritative ones for example let you "compile" a zone into some kind of format before loading it. See zonec in nsd for example

You also need to remember that this data is dynamic: it can be remotely updated incrementally by DNS UPDATE messages, and in the presence of DNSSEC, the RRSIGs may get dynamically computed or at least need to change from time to time.

Hence, a simple key,value store is probably not enough for all those needs. But note that multiple nameservers allow different "backends" so that the data can be pulled from other sources, with some constraints or not, like an SQL database or even a program creating the DNS response when the DNS query comes.

For example, from memory, bind uses internally a "red back binary tree". See Wikipedia explanation at https://en.wikipedia.org/wiki/Red%E2%80%93black_tree, in short:

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Side note, about "need to have a map which gives out IP address of the name server" which is not 100% exact: the registry authoritative nameservers will have mostly NS records, associating domain names to other authoritative nameservers (a delegation) and will have some A and AAAA records called glues in that case. Some requests to them may not get you any IP addresses at all, see:

$ dig @a.gtld-servers.com NS afnic.com +noall +ans +auth

; <<>> DiG 9.12.0 <<>> @a.gtld-servers.com NS afnic.com +noall +ans +auth
; (1 server found)
;; global options: +cmd
afnic.com.      172800 IN NS ns1.nic.fr.
afnic.com.      172800 IN NS ns3.nic.fr.
afnic.com.      172800 IN NS ns2.nic.fr.

(no IP addresses whatsoever because nameservers are all out of zone, that is "out-of-bailiwick" for the true technical term)

Upvotes: 1

Related Questions