Mesh Resolver: Caching, Wildcards and Safe Invalidation

Mesh Resolver: Caching, Wildcards and Safe Invalidation

You've joined the platform-networking team that runs mesh-dns, the small resolver every internal service uses to find its peers. It sits in front of the company's zone files: zone owners publish records, services query names, and the resolver answers by walking the zone. Today it has no cache at all, and three tickets are queued:

• RES-412: every lookup walks the zone and the zone host is melting. Add a TTL cache.
• RES-431: wildcard records (*.svc.internal) resolve names they must not, and NXDOMAIN answers are re-computed on every typo storm. Fix wildcards, then cache negative answers.
• RES-447: after the last migration, services kept dialing a decommissioned host for minutes because a cached answer outlived the record change. Publishing must invalidate exactly the cache entries it affects, and it must stay fast: the zone has thousands of names and is republished in bulk.

All times are integer seconds. ts is the only clock; there is no wall-clock anywhere.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh resolver and returns one result per operation. Every operation is [name, ts, ...args]; ts is an integer and never decreases. Errors are returned as "error: <code>" strings, never raised.

• An unknown (or non-string) operation name returns "error: unknown operation"; an operation that is not a list or has no ts, a wrong number of arguments, or a non-integer (or boolean) ts returns "error: invalid arguments" (see api.py).
• Names. The canonical form is lower case with exactly one trailing dot (API.Shop.Internal and api.shop.internal. are both api.shop.internal.). Syntax is defined in names.py::canonical: labels of 1-63 characters from a-z 0-9 - _ (not starting or ending with -), total length at most 253 excluding the optional trailing dot, no empty labels. A wildcard name has * as its *leftmost* label followed by at least one more label (*.svc.internal); it is allowed only as the name of publish and unpublish. Anywhere else (a query, a CNAME target) a * makes the name invalid.
• Records. type is exactly "A" or "CNAME". An A value is a dotted-quad IPv4 address (four decimal octets 0-255, no leading zeros). A CNAME value is a valid non-wildcard name; it is stored canonicalized. ttl is an integer in [1, 86400]. There is one record per name: publishing at a name that already has a record replaces it (A can replace CNAME and vice versa).
• Answers are dictionaries. Shapes (see answers.py):
• {"rcode": "NOERROR", "addr": <ip>, "chain": [<canonical names>], "ttl": <int>, "cached": <bool>}
• {"rcode": "NXDOMAIN", "ttl": <int>, "cached": <bool>}
• {"rcode": "SERVFAIL", "reason": "cname loop" | "chain too long", "ttl": 0, "cached": false}

How a query resolves (chain.follow)

Starting at the canonical queried name, repeat:

1. If the current name is already in the chain, the answer is SERVFAIL with reason cname loop.
2. Add the current name to the chain and look it up. No record: NXDOMAIN (also when the missing name is a CNAME target in the middle of the chain).
3. An A record ends the walk: NOERROR, addr is its value.
4. A CNAME: if this would be the 9th CNAME followed (MAX_CHAIN_HOPS is 8), the answer is SERVFAIL with reason chain too long; otherwise continue at its target.

So a chain of exactly 8 CNAMEs ending in an A resolves; the loop check runs before the length check, which means an 8-cycle is a loop while a 9-cycle is "too long". chain in a NOERROR answer lists every canonical name looked up, queried name first, address-holding name last.

Part 1: The TTL cache (RES-412)

Goal: answer repeated queries from a cache without changing any answer.

Rules

1. The TTL of a NOERROR answer is the smallest TTL among all the records it was built from (every CNAME on the chain and the final A). chain.follow is supposed to report that and does not.
2. chain.follow must detect loops as described above (today a loop is mistaken for a long chain).
3. A NOERROR answer computed at ts is cached under the canonical queried name with expires_at = ts + ttl. A query at ts' < expires_at is a hit: same addr and chain, cached: true, and ttl = expires_at - ts' (the remaining lifetime, always >= 1). A hit never extends the lifetime. At ts' == expires_at the entry is expired: the query re-resolves against the current zone, is a miss (cached: false, full TTL again) and is cached afresh with cached_at = ts'.
4. SERVFAIL answers are never cached. NXDOMAIN answers are not cached yet (Part 2); they already report ttl equal to the current negative TTL, which defaults to 30 and is changed with set_negative_ttl (seconds an integer in [0, 86400], else invalid ttl).
5. cache_size returns how many cache entries are live at its ts (an entry is live while ts < expires_at).
6. Part 1 and Part 2 tests never publish or unpublish a record that a live cache entry depends on, so invalidation can wait for Part 3.

Example

[["publish", 0, "API.Shop.Internal", "CNAME", "gw.shop.internal", 60],
 ["publish", 0, "gw.shop.internal.", "A", "10.0.4.2", 300],
 ["query", 10, "api.shop.internal"],
 ["query", 40, "API.SHOP.INTERNAL."],
 ["query", 70, "api.shop.internal"],
 ["cache_size", 70]]

returns

["ok", "ok",
 {"rcode": "NOERROR", "addr": "10.0.4.2", "chain": ["api.shop.internal.", "gw.shop.internal."], "ttl": 60, "cached": false},
 {"rcode": "NOERROR", "addr": "10.0.4.2", "chain": ["api.shop.internal.", "gw.shop.internal."], "ttl": 30, "cached": true},
 {"rcode": "NOERROR", "addr": "10.0.4.2", "chain": ["api.shop.internal.", "gw.shop.internal."], "ttl": 60, "cached": false},
 1]

The entry cached at 10 with TTL 60 expires at exactly 70, so the query at 70 is a fresh miss.

Part 2: Wildcards and negative caching (RES-431)

Goal: correct wildcard matching, then cache NXDOMAIN.

Wildcard rules (the lookup lives in zone.py)

1. A wildcard record *.s. answers a lookup of name x.s. only when x is exactly one label: it never answers a.x.s. (two labels below) and never answers s. itself.
2. An explicit record at the looked-up name always wins; the wildcard is consulted only when there is none. An explicit record at a.x.s. does not affect how x.s. is answered.
3. A wildcard may be an A or a CNAME. A wildcard CNAME's target is a fixed name (nothing is substituted from the queried label). Wildcards apply at every step of a chain, including CNAME targets.
4. The wildcard record's TTL counts toward the chain minimum like any other record. chain lists the names actually looked up (web.svc.internal.), never the wildcard record's own name.

Negative caching rules

1. An NXDOMAIN computed at ts is cached under the canonical queried name for the current negative TTL: expires_at = ts + negative_ttl. Hits behave as in Part 1 (cached: true, ttl = remaining, expiry at exactly expires_at) and they count in cache_size.
2. A negative TTL of 0 means NXDOMAIN is not cached at all (ttl 0, cached: false).
3. Changing the negative TTL affects only entries cached *after* the change; entries already cached keep the expires_at they were given.
4. The first answer reports ttl equal to the negative TTL and cached: false.

Example

[["publish", 0, "*.svc.internal", "A", "10.9.0.1", 120],
 ["publish", 0, "db.svc.internal", "A", "10.9.0.2", 60],
 ["query", 1, "web.svc.internal"],
 ["query", 1, "db.svc.internal"],
 ["query", 1, "a.web.svc.internal"],
 ["query", 5, "A.Web.Svc.Internal"]]

returns

["ok", "ok",
 {"rcode": "NOERROR", "addr": "10.9.0.1", "chain": ["web.svc.internal."], "ttl": 120, "cached": false},
 {"rcode": "NOERROR", "addr": "10.9.0.2", "chain": ["db.svc.internal."], "ttl": 60, "cached": false},
 {"rcode": "NXDOMAIN", "ttl": 30, "cached": false},
 {"rcode": "NXDOMAIN", "ttl": 26, "cached": true}]

Part 3: Invalidate exactly what a publish affects (RES-447)

Goal: publish and unpublish evict the cache entries whose answer could now be different, and only those. The Part 1/2 cache keyed by queried name is not enough: an entry for api.internal. that resolved through edge.internal. must go when edge.internal. changes.

Rules

1. A cache entry (positive or negative) *depends on every name in its chain*. The effective record of a name is what zone.lookup returns for it (the explicit record, else the wildcard record that covers it, else none), compared by (type, value, ttl), not by the name it sits at.
2. After a publish or unpublish, an entry is evicted if and only if the effective record of at least one name in its chain differs from what it was just before the operation. Everything else stays cached, with its original expires_at. Concretely this means:

• Publishing or unpublishing an explicit name n evicts entries whose chain contains n (the queried name, a CNAME hop, the final A, or a missing name that was answered NXDOMAIN), unless n's effective record did not change (for example it is replaced by an identical record, or an explicit record is published that equals what the covering wildcard already returned).
• Publishing or unpublishing a wildcard *.s. evicts entries whose chain contains a name exactly one label below s. that has no explicit record; names that have their own record are unaffected, as are names deeper than one label, and s. itself. If the wildcard record is replaced by an identical one, nothing is evicted.

1. A failed operation (any error) changes nothing and evicts nothing.
2. Changes take effect for queries at the same ts as the publish. Evicted entries no longer count in cache_size.
3. Changing the negative TTL never evicts anything (Part 2 rule 3 still applies).

Example

[["publish", 0, "api.internal", "CNAME", "edge.internal", 300],
 ["publish", 0, "edge.internal", "A", "10.0.0.1", 300],
 ["query", 1, "api.internal"],
 ["query", 2, "ghost.internal"],
 ["publish", 3, "edge.internal", "A", "10.0.0.2", 300],
 ["query", 4, "api.internal"],
 ["query", 5, "ghost.internal"],
 ["cache_size", 5]]

returns

["ok", "ok",
 {"rcode": "NOERROR", "addr": "10.0.0.1", "chain": ["api.internal.", "edge.internal."], "ttl": 300, "cached": false},
 {"rcode": "NXDOMAIN", "ttl": 30, "cached": false},
 "ok",
 {"rcode": "NOERROR", "addr": "10.0.0.2", "chain": ["api.internal.", "edge.internal."], "ttl": 300, "cached": false},
 {"rcode": "NXDOMAIN", "ttl": 27, "cached": true},
 2]

ghost.internal. is untouched by the publish and keeps its original expiry (2 + 30 = 32).

Part 4: Bulk operations at scale

Goal: the zone has thousands of generated names (host-0001...), is republished in bulk, and is queried in bulk. Two compact operations cover that; the hidden tests use them to build a warm cache of thousands of entries and then publish across it. Re-resolving, or scanning the whole cache for every changed name, is too slow.

Rules

1. For each n in start .. start+count-1 (in that order) the template is expanded: {n} becomes the decimal n in both templates; in value_template only, {hi} becomes n // 256 and {lo} becomes n % 256 (both decimal), so "10.4.{hi}.{lo}" generates addresses.
2. publish_many is exactly count individual publish operations at the same ts, in order, with all the Part 3 invalidation behaviour. query_many is exactly count individual query operations at the same ts in order; the returned counts tally their rcodes, and cached counts how many of them (any rcode) were cache hits. Cache contents afterwards are those the individual operations would have left.
3. Both operations are atomic with respect to validation: if anything is invalid, nothing is published or queried. Error order: invalid template (name_template not a string or lacking {n}; for publish_many also a non-string value_template), invalid range (start an integer >= 0, count an integer in [1, 50000]; booleans are not integers), then for publish_many invalid type, invalid ttl, and finally the first generated item (in index order) that fails a publish check, reported with that check's error (invalid name before invalid value). For query_many, any generated name that is invalid gives invalid name.
4. cache_size must also stay fast when called thousands of times over a large cache.
5. Hidden tests run publish_many over thousands of names with a warm cache of thousands of entries, and tens of thousands of cached lookups, in one run; the whole suite has a few seconds.

Example

[["publish_many", 0, "host-{n}.pool.internal", "10.4.{hi}.{lo}", 250, 3, "A", 120],
 ["publish_many", 0, "www-{n}.edge.internal", "host-{n}.pool.internal", 250, 3, "CNAME", 60],
 ["query_many", 1, "www-{n}.edge.internal", 249, 5],
 ["query_many", 2, "www-{n}.edge.internal", 249, 5],
 ["publish_many", 3, "host-{n}.pool.internal", "10.5.{hi}.{lo}", 251, 1, "A", 120],
 ["query", 4, "www-251.edge.internal"],
 ["cache_size", 4]]

returns

["ok", "ok",
 {"noerror": 3, "nxdomain": 2, "servfail": 0, "cached": 0},
 {"noerror": 3, "nxdomain": 2, "servfail": 0, "cached": 5},
 "ok",
 {"rcode": "NOERROR", "addr": "10.5.0.251", "chain": ["www-251.edge.internal.", "host-251.pool.internal."], "ttl": 60, "cached": false},
 5]

Notes

• names.py, records.py and answers.py are known-good; zone.py and chain.py are where Parts 1 and 2 live.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behavior (TTL boundaries, chain limits, wildcard matching) after the invalidation and bulk features are in.
• Parts 1-3 is a strong result. Part 4 is a stretch.