Networking

DNS Service

Resolve names to addresses: a recursive resolver built as a TTL-bound cache over the delegation walk, with negative caching, anycast PoPs, and serve-stale to keep the cold path off the network.

~35 min · intermediate

Problem & Requirements

Turn a name like api.example.com into an address. The name space is a delegated tree: the root knows where com lives, the com servers know where example.com lives, and example.com's authoritative servers hold the actual A and AAAA records. A resolver answers a client by walking that delegation chain from the root down until some server returns the records — or returns proof that the name does not exist. Queries vastly outnumber zone changes, most queries repeat a small set of popular names, and an answer is valid until its TTL says otherwise.

That ratio is the whole design. A resolver is a cache that occasionally walks the tree, not a tree-walker that occasionally caches. The delegation walk costs several network round trips to servers spread across the planet; a cache hit costs an in-memory lookup. So correctness is governed by TTLs, throughput by multi-tier caching, survival of the miss path by negative caching, and global latency by anycast routing putting a resolver replica near every client. Each principle exists to keep the slow delegation walk off the hot path or to make it cheaper when it happens.

Functional

resolve(name, type) returns the matching RRset, or a negative answer (NXDOMAIN for "no such name", NODATA for "name exists, no record of this type").
Recursive resolution: on a cache miss, follow NS delegations root → TLD → authoritative until an answer or a negative.
Cache both positive and negative answers, each expiring per the TTL the authority assigned it.

Non-functional (back-of-envelope, single resolver node)

Quantity	Target	What it forces
Query rate	~100k qps/node	The cache absorbs the bulk; recursion is the slow exception, not the norm
Cache hit ratio	~85–95%	The cache is the data path; the delegation walk is the cold path
Cache-hit latency	< 1 ms	In-memory keyed lookup, no network on the hot path
Cold-resolution latency	20–200 ms	Several RTTs (root → TLD → auth); anycast shortens each one
TTL range	1 s – several days	Per-record expiry, not one global cache policy
Negative-cache TTL	capped, from SOA minimum (RFC 2308)	Failures must be cached too, or the miss path collapses
Anycast PoPs	tens–hundreds	One service IP announced via BGP; each PoP an independent cache

The dangerous row is the negative-cache TTL. Positive load is easy — popular names cache and serve from memory. The failure mode is the miss path: a flood of distinct names, most of them nonexistent, defeats the cache and turns every query into a full recursive walk that bursts onto the root, TLD, and authoritative servers. This is the DNS "water torture" pattern — random subdomains of a victim zone, none cacheable as a positive answer. Caching the negatives is the first defense and is build step four.

Design

Six components, each tied to the principle it applies:

Message and record model — a query is (name, type); an answer is an RRset with a TTL, or an rcode (NXDOMAIN) plus the zone's SOA. Everything keys on (name, type).
Recursive resolution — the delegation walk from the root following NS records down to the authoritative servers. This is the cold path the rest of the design works to avoid.
Resolver cache — a keyed store of answers so a repeated query never re-walks the tree. This is multi-tier caching: the client's stub resolver caches, the recursive resolver caches, and forwarders chain caches in front of each other.
TTL expiry — every cached RRset carries the authority's TTL and is treated as a miss once it expires, so the cache converges on zone changes without any invalidation protocol. This is TTLs as the sole consistency mechanism.
Negative cache — NXDOMAIN and NODATA responses are cached too, bounded by the SOA minimum and a hard cap, so repeated and adversarial misses are served from memory. This is negative caching.
Anycast deployment — every PoP announces the same service IP over BGP; the network delivers each client to its nearest PoP, and each PoP runs an independent cache. This is anycast routing.

The recursive-resolver loop and its caching are best read in open-source code: Unbound (NLnet Labs), Knot Resolver (CZ.NIC), and PowerDNS Recursor all implement the walk-plus-cache plus negative caching and serve-stale described below. At production scale the two named systems split along the authoritative/recursive line. Cloudflare's 1.1.1.1 is a public recursive resolver: anycast across hundreds of PoPs, aggressive positive and negative caching, QNAME minimization, and encrypted transport — it is the reference for steps two through six. Route 53 is an authoritative service: anycast nameservers answering for hosted zones, with health-checked failover and latency/geo/weighted routing policies layered on top; its recursion-for-clients piece is the separate Route 53 Resolver. Holding those apart matters — the caching principles here live in the resolver, while Route 53's distinctive work is on the authoritative and routing-policy side.

Build it

Start with a resolver that does the literal thing: walk the delegation chain from the root on every query. Ask a root server, get a referral to the TLD servers, ask those, get a referral to the authoritative servers, ask those, return the answer. It is correct, and it establishes the recursive contract the rest preserves. Its failure is that it re-walks the entire tree for every query — several round trips per lookup and a constant pounding of the root and TLD servers — which the next step removes with a cache.

The walk repeats identically for every client asking the same popular name, so cache the result keyed by (name, type) and serve future hits from memory. The recursion path is now the exception rather than the rule, and this single resolver is one tier in a chain of caches — the client's stub resolver and any forwarders cache in front of it, which is multi-tier caching. The new failure: cached entries never expire, so a record that changes at the authority stays wrong in the cache forever.

A DNS answer is only valid for the TTL the authority stamped on it, so an entry that never expires diverges silently from the zone. Store each record's TTL as an absolute expiry and treat an expired entry as a miss, which forces a fresh walk and re-caches the current answer. This is TTLs doing the entire job of consistency — there is no invalidation message, the data just ages out. The remaining failure: a query for a name that does not exist returns NXDOMAIN, but a negative answer isn't a record, so nothing caches it; every repeat (and every random-subdomain probe) re-walks the whole chain.

Nonexistent names are not rare — typos, stale links, and deliberate floods of random subdomains all produce NXDOMAIN, and right now each one costs a full recursive walk. Cache the negative answer too, with a TTL drawn from the zone's SOA minimum and clamped to a hard cap, exactly as RFC 2308 specifies. This is negative caching, and it is the defense against the water-torture miss storm called out in the requirements: once a bad name is known-bad, repeats are served from memory instead of hammering the authority. The failure left standing is physical — a single resolver is one box, far from most of the world, so latency is high and one outage takes everyone down.

One resolver is a single point of failure and a single point in space, so clients on another continent eat the latency of reaching it before recursion even starts. Run the resolver at many PoPs, each announcing the same service IP over BGP; the network routes each client to its nearest PoP, and each PoP keeps its own cache. This is anycast routing — the same mechanism behind 1.1.1.1 and Route 53's nameservers, which also lets the fleet absorb volumetric DDoS by spreading it across PoPs. Anycast is a network-layer property, so the code just shows a PoP node owning a cache and announcing the shared IP. The failure it introduces: caches are per-PoP and cold independently, so when a hot record's TTL expires, every PoP takes a synchronous miss at once and bursts load onto the authority.

A popular record expiring causes a latency cliff: the next client to ask waits out a full recursive walk while the cache is briefly empty, and at scale many clients hit that gap together. Two refinements smooth it, both real resolver behavior. Prefetch refreshes a record in the background once it is near expiry, so the cache stays warm and no client waits. Serve-stale (RFC 8767) returns a recently-expired answer immediately while a refresh runs, trading a little staleness for availability when the authority is slow or unreachable. Both keep the hot path off the network and shield the authoritative servers, extending the same multi-tier caching and TTL machinery the cache already has.

import time

ROOT_HINTS = [...]   # addresses of the 13 root server letters, hardcoded

class Resolver:
    def resolve(self, name, qtype):
        servers = ROOT_HINTS
        while True:
            resp = self._ask(servers[0], name, qtype)   # one UDP round trip
            if resp.answer:                              # authoritative records
                return resp.answer
            if resp.delegation:                          # NS referral → go deeper
                servers = self._glue_addrs(resp.delegation)
                continue                                 # root → TLD → auth
            return None                                  # no such name

    def _ask(self, server, name, qtype):
        ...   # build a DNS query packet, send, parse the reply; elided

Tradeoffs

Decision	What it buys	What it costs
Multi-tier caching	The recursion walk runs only on a true miss; ~90% of queries never touch the network	Cache and authority diverge for up to a TTL; bugs hide behind hits
TTL expiry as the only consistency	No invalidation protocol; the cache self-corrects on zone change	Change propagation is bounded by the largest TTL in the chain; emergencies wait
Negative caching	Repeated and adversarial misses served from memory; the water-torture path defanged	A name that is created after a negative is cached stays "missing" until that TTL ends
Anycast routing	Nearest-PoP latency, DDoS spread across PoPs, failure drains via BGP	Per-PoP cold caches; TCP/DoT sessions can break on a routing change mid-flow
Serve-stale + prefetch	No latency cliff on expiry; answers survive an unreachable authority	Returns knowingly-stale data; extra background queries to keep records warm

Scaling it up

The toy answers names; it does not prove the answers are authentic. DNSSEC makes the resolver a validating resolver: it walks a chain of signatures from the root's trust anchor down to the answer, rejecting anything that fails. That adds CPU per cold lookup and complicates negative caching, because "this name does not exist" must itself be a signed proof (NSEC/NSEC3 records). RFC 8198 turns those proofs into a caching win — aggressive NSEC caching lets the resolver answer many nonexistent names from a single cached range proof, which strengthens exactly the miss-path defense step four started.

Privacy and transport are now table stakes for a public resolver. QNAME minimization (RFC 9156) sends each server only the part of the name it needs to delegate, rather than leaking the full name to the root and every TLD on the way down. Encrypted transport — DoT (RFC 7858) and DoH (RFC 8484) — hides queries from the network between client and resolver. Cloudflare built 1.1.1.1 around both, which changes the connection model: DoH and DoT are stateful TCP/TLS sessions, so anycast routing changes that would silently re-home a UDP query can break a session mid-connection and have to be handled.

Defending the miss path takes more than caching negatives. Authoritative servers add Response Rate Limiting to throttle floods of identical or near-identical queries, recursive resolvers cap outstanding work per client and per target zone, and operators run cardinality-style analysis to spot which zone or label is being attacked. Anycast itself is a volumetric defense — a flood lands on the PoP nearest each attacker and is absorbed locally rather than concentrating on one site — but it only buys time, not immunity.

Anycast is operationally subtle once it carries real traffic. PoPs are drained and filled by announcing and withdrawing BGP routes, route flaps can shift a client between PoPs and cold caches, and ECMP hashing has to keep a given flow pinned so stateful DoT/DoH sessions survive. Route 53 layers routing policy on top of plain nearest-PoP anycast — latency-based, geolocation, weighted, and health-checked failover routing — so the authoritative answer a client gets depends on where it is and what is healthy, which is a different problem from the resolver caching this lesson built.

The authoritative half is its own system and the natural next prototype: zone storage, signing, and propagation to the edge via AXFR/IXFR zone transfers, which is what Route 53 operates and what 1.1.1.1 queries. From here the concrete follow-ons are an authoritative-server prototype (zone files, SOA/serial-driven AXFR/IXFR, and anycast publication), a DNSSEC-validation prototype that builds the trust-chain walk and aggressive NSEC caching sketched above, and a load-shedding / response-rate-limiting prototype that hardens the miss path beyond a negative cache. Each extends this resolver without re-treading the cache-over-delegation-walk core.

References

Mockapetris, Domain Names — Concepts and Facilities / Implementation and Specification, RFC 1034 / RFC 1035: https://www.rfc-editor.org/rfc/rfc1034 · https://www.rfc-editor.org/rfc/rfc1035
Andrews, Negative Caching of DNS Queries (DNS NCACHE), RFC 2308: https://www.rfc-editor.org/rfc/rfc2308
Lawrence et al., Serving Stale Data to Improve DNS Resiliency, RFC 8767: https://www.rfc-editor.org/rfc/rfc8767
Bortzmeyer & Dolmans, DNS Query Name Minimisation to Improve Privacy, RFC 9156: https://www.rfc-editor.org/rfc/rfc9156
Fujiwara et al., Aggressive Use of DNSSEC-Validated Cache, RFC 8198: https://www.rfc-editor.org/rfc/rfc8198
Unbound (NLnet Labs) — open-source validating recursive resolver: https://www.nlnetlabs.nl/projects/unbound/about/
Knot Resolver (CZ.NIC) and PowerDNS Recursor — recursion, caching, serve-stale in production code: https://www.knot-resolver.cz/ · https://doc.powerdns.com/recursor/
Cloudflare 1.1.1.1 — public anycast recursive resolver, QNAME minimization, DoH/DoT: https://developers.cloudflare.com/1.1.1.1/
Amazon Route 53 — anycast authoritative DNS, routing policies, health checks: https://docs.aws.amazon.com/route53/
Foundations referenced inline: multi-tier caching · TTLs · negative caching · anycast routing