Building a Recursive DNS Resolver

Friday, 29 July 2022

Recently I’ve been thinking about how DNS really works under the hood. You ask a resolver for an IP, but how does the resolver know what IP maps to a domain? I figured the best way to learn was to build a resolver myself, and it turned out to be fairly simple and instructive.

But first, some background!

The Domain Name System

The domain name system (or DNS) underpins the internet, converting the domain names you’d typically use to connect to a website, to IP addresses for the servers those websites are hosted on. Conceptually you can think of the entire domain name system as a distributed key-value store mapping domains (and sub-domains) to IP addresses:

Domain IP Address
news.ycombinator.com 50.112.136.166
wikipedia.org 91.198.174.192
en.wikipedia.org 91.198.174.192
… …

When you type something like “google.com” into your browser and hit enter, your device must query a known recursive resolver to find google.com’s IP address. Recursive resolvers are provided by most ISPs, but resolvers like 1.1.1.1 or 8.8.8.8 exist as well.

You can query a resolver manually using something like dig or dog:

❯ dig @1.1.1.1 news.ycombinator.com

; <<>> DiG 9.18.4-2-Debian <<>> @1.1.1.1 news.ycombinator.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 9149
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 1232
;; QUESTION SECTION:
;news.ycombinator.com.		IN	A

;; ANSWER SECTION:
news.ycombinator.com.	0	IN	A	50.112.136.166

;; Query time: 24 msec
;; SERVER: 1.1.1.1#53(1.1.1.1) (UDP)
;; WHEN: Thu Jul 28 01:31:59 EDT 2022
;; MSG SIZE  rcvd: 65

The ANSWER SECTION contains an IP address for the domain we requested. How does this work? How does a recursive resolver know what IP a domain uses?

The short answer is that resolvers aren’t in charge of the domain->IP mapping at all. Resolvers are simply a querying interface to DNS' distributed database, which is stored on nameservers. If you think of the entire DNS namespace as a tree, each nameserver is an authority for a given subtree, and each such subtree is called a zone.

Any given domain has a single unique path through this tree, starting at any node and walking up to the root. Here’s news.ycombinator.com, for example:

Note that the root node is denoted by a ., so the fully-qualified version (or FQDN) of a domain name ends with a . – the FQDN for “news.ycombinator.com” is actually news.ycombinator.com.

Recursive resolvers must also walk this tree to resolve a given domain, but starting at the root node. 13 root nameservers exist (which have authority over the root zone .), and have well-known IPs:

Root Server IP
a.root-servers.net 198.41.0.4
b.root-servers.net 199.9.14.201
c.root-servers.net 192.33.4.12
d.root-servers.net 199.7.91.13
e.root-servers.net 192.203.230.10
f.root-servers.net 192.5.5.241
g.root-servers.net 192.112.36.4
h.root-servers.net 198.97.190.53
i.root-servers.net 192.36.148.17
j.root-servers.net 192.58.128.30
k.root-servers.net 193.0.14.129
l.root-servers.net 199.7.83.42
m.root-servers.net 202.12.27.33

Recursive Resolution By Hand

Let’s see if we can resolve news.ycombinator.com by walking this tree manually, starting at one of these root servers:

❯ dig @192.36.148.17 news.ycombinator.com

; <<>> DiG 9.18.4-2-Debian <<>> @192.36.148.17 news.ycombinator.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 57339
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 13, ADDITIONAL: 27
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 1232
; COOKIE: a4d4b6701afda21d0100000062e3db51b71dabe7bfe43d28 (good)
;; QUESTION SECTION:
;news.ycombinator.com.		IN	A

;; AUTHORITY SECTION:
com.			172800	IN	NS	f.gtld-servers.net.
com.			172800	IN	NS	g.gtld-servers.net.
com.			172800	IN	NS	e.gtld-servers.net.
com.			172800	IN	NS	k.gtld-servers.net.
com.			172800	IN	NS	j.gtld-servers.net.
com.			172800	IN	NS	b.gtld-servers.net.
com.			172800	IN	NS	a.gtld-servers.net.
com.			172800	IN	NS	m.gtld-servers.net.
com.			172800	IN	NS	d.gtld-servers.net.
com.			172800	IN	NS	i.gtld-servers.net.
com.			172800	IN	NS	h.gtld-servers.net.
com.			172800	IN	NS	c.gtld-servers.net.
com.			172800	IN	NS	l.gtld-servers.net.

;; ADDITIONAL SECTION:
m.gtld-servers.net.	172800	IN	A	192.55.83.30
l.gtld-servers.net.	172800	IN	A	192.41.162.30
k.gtld-servers.net.	172800	IN	A	192.52.178.30
j.gtld-servers.net.	172800	IN	A	192.48.79.30
i.gtld-servers.net.	172800	IN	A	192.43.172.30
h.gtld-servers.net.	172800	IN	A	192.54.112.30
g.gtld-servers.net.	172800	IN	A	192.42.93.30
f.gtld-servers.net.	172800	IN	A	192.35.51.30
e.gtld-servers.net.	172800	IN	A	192.12.94.30
d.gtld-servers.net.	172800	IN	A	192.31.80.30
c.gtld-servers.net.	172800	IN	A	192.26.92.30
b.gtld-servers.net.	172800	IN	A	192.33.14.30
a.gtld-servers.net.	172800	IN	A	192.5.6.30
m.gtld-servers.net.	172800	IN	AAAA	2001:501:b1f9::30
l.gtld-servers.net.	172800	IN	AAAA	2001:500:d937::30
k.gtld-servers.net.	172800	IN	AAAA	2001:503:d2d::30
j.gtld-servers.net.	172800	IN	AAAA	2001:502:7094::30
i.gtld-servers.net.	172800	IN	AAAA	2001:503:39c1::30
h.gtld-servers.net.	172800	IN	AAAA	2001:502:8cc::30
g.gtld-servers.net.	172800	IN	AAAA	2001:503:eea3::30
f.gtld-servers.net.	172800	IN	AAAA	2001:503:d414::30
e.gtld-servers.net.	172800	IN	AAAA	2001:502:1ca1::30
d.gtld-servers.net.	172800	IN	AAAA	2001:500:856e::30
c.gtld-servers.net.	172800	IN	AAAA	2001:503:83eb::30
b.gtld-servers.net.	172800	IN	AAAA	2001:503:231d::2:30
a.gtld-servers.net.	172800	IN	AAAA	2001:503:a83e::2:30

;; Query time: 28 msec
;; SERVER: 192.36.148.17#53(192.36.148.17) (UDP)
;; WHEN: Thu Jul 28 02:22:47 EDT 2022
;; MSG SIZE  rcvd: 876

The root nameserver has not provided us with an answer (no ANSWER SECTION). We’re provided instead with the names and IPs of the nameservers in charge of the com. zone. Let’s see if one of these nameservers knows the IP for news.ycombinator.com:

❯ dig @192.41.162.30 news.ycombinator.com

; <<>> DiG 9.18.4-2-Debian <<>> @192.41.162.30 news.ycombinator.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 52169
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 4, ADDITIONAL: 2
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;news.ycombinator.com.		IN	A

;; AUTHORITY SECTION:
ycombinator.com.	172800	IN	NS	ns-225.awsdns-28.com.
ycombinator.com.	172800	IN	NS	ns-556.awsdns-05.net.
ycombinator.com.	172800	IN	NS	ns-1914.awsdns-47.co.uk.
ycombinator.com.	172800	IN	NS	ns-1411.awsdns-48.org.

;; ADDITIONAL SECTION:
ns-225.awsdns-28.com.	172800	IN	A	205.251.192.225

;; Query time: 32 msec
;; SERVER: 192.41.162.30#53(192.41.162.30) (UDP)
;; WHEN: Thu Jul 28 02:23:25 EDT 2022
;; MSG SIZE  rcvd: 202

Still no ANSWER SECTION, but we’re getting closer! An authoritative nameserver for the zone com. has given us the names and IPs of nameservers that have authority over the ycombinator.com. zone. Let’s recurse one level deeper:

❯ dig @205.251.192.225 news.ycombinator.com

; <<>> DiG 9.18.4-2-Debian <<>> @205.251.192.225 news.ycombinator.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 17560
;; flags: qr aa rd; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;news.ycombinator.com.		IN	A

;; ANSWER SECTION:
news.ycombinator.com.	1	IN	A	50.112.136.166

;; AUTHORITY SECTION:
ycombinator.com.	172800	IN	NS	ns-1411.awsdns-48.org.
ycombinator.com.	172800	IN	NS	ns-1914.awsdns-47.co.uk.
ycombinator.com.	172800	IN	NS	ns-225.awsdns-28.com.
ycombinator.com.	172800	IN	NS	ns-556.awsdns-05.net.

;; Query time: 56 msec
;; SERVER: 205.251.192.225#53(205.251.192.225) (UDP)
;; WHEN: Thu Jul 28 02:24:33 EDT 2022
;; MSG SIZE  rcvd: 202

We now finally have an ANSWER SECTION, which tells us that 50.112.136.166 is the IP address for news.ycombinator.com.. Let’s compare by asking a known recursive resolver:

❯ dig +short @1.1.1.1 news.ycombinator.com
50.112.136.166

Here’s an illustration of what we just did:

Assuming no prior caching, we only know the IPs of the root servers, so we start from there and recurse downwards until we get to a nameserver that’s an authority for the zone the target domain is in.

Writing a Recursive Resolver

At its core, a recursive resolver does what we just did by hand: start at a root nameserver, and recurse downward until it receives an answer.

The best way to understand this properly is to actually build a simple recursive resolver; let’s do that using Go. We’ll use the dns library to serialize to/from the DNS wire format so we can focus on the actual recursive operation of the resolver.

To start, query a root nameserver, look in the response' ADDITIONAL SECTION for the IP addresses of the nameservers one level lower in the tree, and repeat until we receive an ANSWER SECTION:

func resolve(name string) ([]dns.RR, error) {
  nameserver := "198.41.0.4"
  c := new(dns.Client)

  for {
    // Prepare a message asking for an A record (an IP address) for `name`
    m := new(dns.Msg)
    m.SetQuestion(dns.Fqdn(name), dns.TypeA)

    // Send the DNS request to the IP in `nameserver`
    fmt.Printf("Asking %s about %s\n", nameserver, name)
    resp, _, err := c.Exchange(m, fmt.Sprintf("%s:53", nameserver))
    if err != nil {
      return nil, err
    }

    // If an ANSWER SECTION exists, we're done
    if len(resp.Answer) > 0 {
      return resp.Answer, nil
    }

    // If an ADDITIONAL SECTION exists, look in it for an A record for the
    // next-level nameserver. If one doesn't exist, we have to error out
    found := false
    for _, rr := range resp.Extra {
      record, ok := rr.(*dns.A)
      if ok {
        nameserver = record.A.String()
        found = true
        break
      }
    }
    if !found {
      return nil, fmt.Errorf("break in the chain")
    }

    // ... and recurse!
  }
}

And that’s pretty much it! There are some cases this doesn’t handle (which we’ll cover below), but this is all you need to recursively resolve basic DNS requests. Let’s wire this up by accepting CLI arguments:

func main() {
  if len(os.Args) != 2 {
    fmt.Fprintf(os.Stderr, "usage: dns <name>\n")
    os.Exit(1)
  }

  name := os.Args[1]
  answer, err := resolve(name)
  if err == nil {
    for _, record := range answer {
      fmt.Println(record)
    }
  } else {
    fmt.Fprintf(os.Stderr, "Failed to resolve %s\n", name)
    os.Exit(1)
  }
}

And give it a shot:

❯ go run dns.go news.ycombinator.com
Asking 198.41.0.4 about news.ycombinator.com
Asking 192.12.94.30 about news.ycombinator.com
Asking 205.251.192.225 about news.ycombinator.com
news.ycombinator.com.	1	IN	A	50.112.136.166

It works! The resolver found the IP address for news.ycombinator.com with no prior knowledge except the addresses of the root nameservers. Let’s address a couple of edge cases next.

Additional Sections and CNAMEs

In the example above, each nameserver in the chain provided the IP addresses (A records) of all the nameservers in the next level of the tree. This isn’t always the case, though:

❯ go run dns.go twitter.com
Asking 198.41.0.4 about twitter.com
Asking 192.12.94.30 about twitter.com
Failed to resolve twitter.com
exit status 1

Running the final query manually:

❯ dig @192.12.94.30 twitter.com

; <<>> DiG 9.18.4-2-Debian <<>> @192.12.94.30 twitter.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 27129
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 8, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;twitter.com.			IN	A

;; AUTHORITY SECTION:
twitter.com.		172800	IN	NS	ns3.p34.dynect.net.
twitter.com.		172800	IN	NS	ns4.p34.dynect.net.
twitter.com.		172800	IN	NS	d01-01.ns.twtrdns.net.
twitter.com.		172800	IN	NS	d01-02.ns.twtrdns.net.
twitter.com.		172800	IN	NS	a.r06.twtrdns.net.
twitter.com.		172800	IN	NS	b.r06.twtrdns.net.
twitter.com.		172800	IN	NS	c.r06.twtrdns.net.
twitter.com.		172800	IN	NS	d.r06.twtrdns.net.

;; Query time: 104 msec
;; SERVER: 192.12.94.30#53(192.12.94.30) (UDP)
;; WHEN: Thu Jul 28 02:57:55 EDT 2022
;; MSG SIZE  rcvd: 211

This nameserver sent us a list of nameservers that are authoritative for twitter.com., but didn’t include their IP addresses in an ADDITIONAL SECTION.

What do we do? Luckily, we just built a system to convert domain names to IP addresses! We can resolve one of these names to an IP address and use that as the next-level nameserver:

// If the ADDITIONAL SECTION is empty and the AUTHORITY SECTION is not, resolve
// one of the names in the AUTHORITY SECTION and have that be the nameserver
if len(resp.Extra) == 0 && len(resp.Ns) != 0 {
  ns := resp.Ns[0].(*dns.NS)
  nsIP, err := resolve(ns.Ns)
  if err != nil {
    return nil, fmt.Errorf("break in the chain")
  }
  nameserver = nsIP[0].(*dns.A).A.String()
}

Trying it out:

❯ go run dns.go twitter.com
Asking 198.41.0.4 about twitter.com
Asking 192.12.94.30 about twitter.com
Asking 198.41.0.4 about ns3.p34.dynect.net.
Asking 192.12.94.30 about ns3.p34.dynect.net.
Asking 108.59.161.136 about ns3.p34.dynect.net.
Asking 108.59.163.34 about twitter.com
twitter.com.	1800	IN	A	104.244.42.129
twitter.com.	1800	IN	A	104.244.42.65

So far so good. But what about CNAMEs? These DNS records allow aliasing one name to another name. Here pages.github.com is an alias for github.github.io:

❯ go run dns.go pages.github.com
Asking 198.41.0.4 about pages.github.com
Asking 192.12.94.30 about pages.github.com
Asking 205.251.193.165 about pages.github.com
pages.github.com.	3600	IN	CNAME	github.github.io.

A recursive resolver should resolve the CNAME and provide its IP addresses, so let’s implement that:

if len(resp.Answer) > 0 {
  // If an ANSWER SECTION exists and contains a CNAME, recurse
  if cname, ok := resp.Answer[0].(*dns.CNAME); ok {
    return resolve(cname.Target)
  }

  // If an ANSWER SECTION exists, we're done
  return resp.Answer, nil
}

And now we can resolve CNAMEs:

❯ go run dns.go pages.github.com
Asking 198.41.0.4 about pages.github.com
Asking 192.12.94.30 about pages.github.com
Asking 205.251.193.165 about pages.github.com
Asking 198.41.0.4 about github.github.io.
Asking 65.22.161.17 about github.github.io.
Asking 198.41.0.4 about dns1.p05.nsone.net.
Asking 192.12.94.30 about dns1.p05.nsone.net.
Asking 198.51.44.1 about dns1.p05.nsone.net.
Asking 198.51.44.5 about github.github.io.
github.github.io.	3600	IN	A	185.199.108.153
github.github.io.	3600	IN	A	185.199.109.153
github.github.io.	3600	IN	A	185.199.110.153
github.github.io.	3600	IN	A	185.199.111.153

Wrapping Up

That’s it! This resolver isn’t anywhere near complete (error handling, caching, other record types, and IPv6, to name just a few omissions), but I hope it helps you understand how DNS resolution really works under the hood!

You can find the code for the entire resolver here.

Edit