Exercise: Build a DNS Resolver Cache

Build the mental model

DNS does not work because the root servers are fast. It works because almost nobody asks them anything. There are thirteen root name server addresses for the entire internet, and if every browser tab resolved every hostname from the root downward, the system would have collapsed decades ago. Caching is not an optimisation bolted onto DNS afterwards -- it is the load-shedding mechanism that makes a hierarchy this shallow survivable at all. A resolver answering a million queries a day out of a few thousand cached records is doing exactly what the protocol was designed around.

The thing that makes reuse safe is the TTL, and the TTL is easy to misread. It is not a countdown the server maintains on your behalf, and it is not a promise that the record will change when it expires. It is a one-way contract: the zone owner is telling you "you may reuse this answer for the next N seconds, and I accept that I have no way to reach you and correct it during that window." That is why lowering a TTL is the first step before any planned migration. You are shrinking the blast radius of your own staleness before you go and create some.

Because nothing can push an update to you, the expiry check has to happen when you read, not on a timer. A cache that only sweeps expired entries in a background pass will serve a stale address in the gap between sweeps. Store an absolute expires_at at insert time, then compare it against the current time on every single lookup. Read-time expiry is what turns a dictionary into a cache.

DNS CACHE LOOKUP PATH
---------------------
             lookup(name, now)
                    |
                    v
          +---------------------+
          | name in cache?      |
          +----+-----------+----+
            no |           | yes
               |           v
               |   +---------------------+
               |   | now < expires_at ?  |  <-- TODO (b)
               |   +----+-----------+----+
               |    yes |           | no
               |        v           v
               |    +-------+   +----------+
               |    | HIT   |   |  evict   |
               |    +-------+   |  entry   |
               |     TODO (a)   +----+-----+
               |                     |
               +----------+----------+
                          v
              +-------------------------+
              | fetch_from_zone(name)   |   zone_queries += 1
              +-------------------------+
                          |
                          v
              +-------------------------+
              | cache[name] =           |
              |   (addr, now + ttl)     |   store ABSOLUTE expiry
              +-------------------------+
                          |
                          v
                        MISS

Connect it to a real scenario

The scaffold below is a resolver with its plumbing already in place and its two interesting decisions left out. ZONE is the authoritative data: three names, each with an address and a TTL of 60, 30 and 300 seconds. cache maps a name to a tuple of (address, expires_at). zone_queries counts every trip to the authoritative server, which is the number you are ultimately trying to drive down.

Time never comes from the clock. Every lookup takes an explicit now in seconds, and TRACE is a fixed script of six queries at t = 0, 10, 12, 75, 80 and 100. That is what makes the exercise checkable: the same input always produces the same trace, so you can diff your output against the expected one instead of squinting at wall-clock timings that shift on every run.

lookup() is already finished for the cache-miss path. It fetches from the zone, stores the address with an absolute expiry of now + ttl, and reports a miss. The branch where an entry already exists is deliberately hollow. Rather than quietly returning something plausible, it reports MISS (cache hit not implemented) so the trace tells you exactly which decisions are still missing. Run it once before you write anything and read that status column top to bottom.

• DNS scales because caches answer, not because root servers are fast
• TTL is a contract you cannot revoke mid-window, not a countdown
• Check expiry at read time; background sweeps still serve stale answers

Try the working example

"""DNS resolver cache -- STARTER SCAFFOLD.

The clock is passed in as an explicit integer `now` (seconds since the
trace started) so that every run gives the same result. Two pieces are
left for you to write: the cache-hit path and the TTL expiry check.
"""

# The "authoritative" zone: name -> (address, ttl in seconds)
ZONE = {
    "www.example.com": ("93.184.216.34", 60),
    "api.example.com": ("93.184.216.35", 30),
    "cdn.example.com": ("93.184.216.36", 300),
}

# name -> (address, expires_at)
cache = {}

zone_queries = 0


def fetch_from_zone(name):
    """Stand-in for asking the authoritative server. Counts the traffic."""
    global zone_queries
    zone_queries += 1
    return ZONE[name]


def lookup(name, now):
    """Resolve `name` at time `now`. Returns (status, address)."""
    entry = cache.get(name)

    if entry is not None:
        # TODO (b): if now >= entry[1] the entry has expired -- evict it
        #           from the cache and fall through to the fetch below.
        # TODO (a): otherwise this is a HIT: return the cached address
        #           without touching the zone table at all.
        return ("MISS (cache hit not implemented)", entry[0])

    address, ttl = fetch_from_zone(name)
    cache[name] = (address, now + ttl)
    return ("MISS (fetched from zone)", address)


TRACE = [
    ("www.example.com", 0),
    ("www.example.com", 10),
    ("api.example.com", 12),
    ("www.example.com", 75),
    ("api.example.com", 80),
    ("cdn.example.com", 100),
]

print("{:<5} {:<18} {:<34} {}".format("t", "name", "status", "address"))
print("-" * 74)
for query_name, query_time in TRACE:
    status, address = lookup(query_name, query_time)
    print("{:<5} {:<18} {:<34} {}".format(query_time, query_name, status, address))

print("-" * 74)
print("zone queries: {}".format(zone_queries))
print("cached names: {}".format(len(cache)))

t     name               status                             address
--------------------------------------------------------------------------
0     www.example.com    MISS (fetched from zone)           93.184.216.34
10    www.example.com    MISS (cache hit not implemented)   93.184.216.34
12    api.example.com    MISS (fetched from zone)           93.184.216.35
75    www.example.com    MISS (cache hit not implemented)   93.184.216.34
80    api.example.com    MISS (cache hit not implemented)   93.184.216.35
100   cdn.example.com    MISS (fetched from zone)           93.184.216.36
--------------------------------------------------------------------------
zone queries: 3
cached names: 3

RFC 1035 - Domain Names: Implementation and Specification — Computer Networking