Misses are worth caching too. If a name doesn't resolve, remembering that "it didn't exist" for a short while stops a storm of repeated failing lookups (an NXDOMAIN flood).
negative_ttl (from the constructor) and a negative cacheresolve(name): if the name is in the negative cache and still fresh, return None immediately; on a real miss, record it in the negative cache for negative_ttl seconds before returning Noneimport time
class DNSResolver:
def __init__(self, zone=None, clock=time.time, negative_ttl=10):
self.zone = zone if zone is not None else {}
self.clock = clock
self.negative_ttl = negative_ttl
self._rr = {}
self._cache = {}
self._neg = {} # name -> expiry of the negative entry
def _lookup(self, name, seen=None):
seen = seen or set()
if name in seen:
return ([], 0)
seen.add(name)
records = self.zone.get(name, [])
a_records = [r for r in records if r["type"] == "A"]
if a_records:
return ([r["value"] for r in a_records], min(r["ttl"] for r in a_records))
for r in records:
if r["type"] == "CNAME":
return self._lookup(r["value"], seen)
return ([], 0)
def resolve(self, name):
now = self.clock()
# TODO: negative cache check, if name in self._neg and now < self._neg[name]: return None
cached = self._cache.get(name)
if cached and now < cached[1]:
values = cached[0]
else:
values, ttl = self._lookup(name)
if not values:
# TODO: record the miss: self._neg[name] = now + self.negative_ttl
return None
self._cache[name] = (values, now + ttl)
i = self._rr.get(name, 0) % len(values)
self._rr[name] = self._rr.get(name, 0) + 1
return values[i]
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Misses are worth caching too. If a name doesn't resolve, remembering that "it didn't exist" for a short while stops a storm of repeated failing lookups (an NXDOMAIN flood).
negative_ttl (from the constructor) and a negative cacheresolve(name): if the name is in the negative cache and still fresh, return None immediately; on a real miss, record it in the negative cache for negative_ttl seconds before returning NonePress Run Tests or ⌘↩ to check your solution.