DNS

The problem

"Design DNS." Before a device can connect to shop.com, it needs the address, like 203.0.113.7. DNS answers that question for every device on the internet, for hundreds of millions of names whose owners each change their own records, and it must keep answering through failures and attacks.

This practice problem reuses the pattern of Design a Key-Value Store, with the Caching and Replication lessons: DNS is a huge key-value store, name → records, read far more than it is written, cached everywhere and copied on several servers. Buying a domain and signing answers so they can't be faked (DNSSEC) come later.

The numbers

From the interviewer: devices look up shop.com about 1 million times a second, through about 100,000 resolvers, the DNS servers that look names up for devices and cache the answers. Its records have a TTL of a day, about 100,000 seconds for a quick estimate (86,400 really).

A resolver asks shop.com's own servers once per TTL and answers everyone else from its copy, so 100,000 resolvers once a day is about 1 lookup a second (1.2 with 86,400), out of a million. The busy work happens in the resolvers' caches; shop.com's servers mostly need to stay reachable.

TTL     lookups reaching shop.com's servers
a day   100,000 ÷ 86,400 ≈ 1 a second
60 s    100,000 ÷ 60     ≈ 1,700 a second

The lookup path

A resolver with an empty cache knows only the addresses of the 13 root servers, built in. To find shop.com it walks down the tree of names:

1. It asks a root server, which answers: ask the .com servers, at these addresses.
2. It asks a .com server, which answers: ask ns1.shop.com, at this address.
3. It asks ns1.shop.com, shop.com's own server, which answers 203.0.113.7.

Each level knows only the next one down: that is delegation, and each owner runs (or picks) the servers for their own names. Every answer is cached for its TTL. The root's answer about .com is kept for 2 days, so resolvers seldom ask a root server, and the next lookup of shop.com skips all three.

Each question and answer is one small UDP packet: no connection to set up, and a lost packet is simply asked again. Answers too big for one packet, and the copies between servers, use TCP. The root has 13 names because their addresses had to fit in one 512-byte UDP answer.

TTLs: fast changes or few lookups

A long TTL means few lookups; a short one, fast changes. Say shop.com moves to a new server. Resolvers keep the old address until their copy runs out, and a copy saved just before the switch keeps its day-long TTL, so lowering the TTL at the moment of the move is too late: some visitors would reach the old server for up to a day.

when             what
today, noon      lower the TTL from a day to 60 s
tomorrow, noon   point shop.com at the new address
by about 12:01   every resolver has the new address
after the move   raise the TTL back to a day

Lower it at least one old TTL ahead, here a day, and keep the old server running for a while after the switch, since a few resolvers keep answers longer than they should. Then raise the TTL again: at 60 s, shop.com's servers get about 1,700 lookups a second instead of about 1.

Copies: a primary and secondaries

One machine holding shop.com's records is a single point of failure. So shop.com keeps a primary, where changes are made, and secondaries that copy it. The .com servers list them all, and a resolver that gets no answer asks the next. Changes are rare, so one primary takes them all, as a leader does in Replication; it tells the secondaries, which copy a change within seconds to minutes. If every copy took changes, two of them could take different changes to one name at once.

Put the copies on different networks, even with two DNS providers. Three servers in one data center fall together with one power cut or one attack, and even a whole provider can fall: in 2016 an attack on one provider, Dyn, left many well-known sites unreachable for hours.

Anycast: one address, many sites

An attack floods shop.com's servers with fake lookups from bots everywhere. More servers in the same data centers don't help, because the network links fill first, and a longer TTL doesn't slow bots, which never cache. Anycast does: many machines in many sites share one address, and the network delivers each packet to the nearest one. Each bot's flood lands at the site nearest to it, so the attack splits over all of them, and real lookups get faster too. One small UDP packet each way makes it safe: a route that changes between two lookups breaks nothing. The 13 root server names are served this way, by more than a thousand machines around the world.

Same pattern as the Key-Value Store

DNS is a key-value store with the name as the key: reads by key, rare writes, many copies. Caching's TTL works unchanged in every resolver, now as a trade-off you tune before a change. Replication's leader and followers become the primary and its secondaries, with the same lag: a change takes the copying time plus one TTL to reach everyone. What DNS adds is delegation: no machine holds every name.

Summary

• Scope: names to addresses for the whole internet; each owner answers for their own names.
• Numbers: 1 million lookups a second, about 1 reaching shop.com's servers.
• Busy path: the resolver's cache; on a miss, root, .com, then shop.com's server.
• TTL: lower it to 60 s a day before a move, raise it back after.
• Copies: a primary and secondaries on other networks; any copy answers.
• Scale: anycast spreads lookups and attacks over many sites.