In this exercise, you will build your own version of a Domain Name System (DNS) resolver, the system your computer uses to translate a domain name into an IP address. You are not expected to know anything about DNS; everything is explained in the directions.
Implement each step in order so the provided unit tests pass. It is normal not to complete all the steps.
Step 0 – Normalize
In DNS, names are case insensitive, and by convention always end in a trailing dot. For example, "Anthropic.COM" normalizes to "anthropic.com.".
Implement normalize() in dns_exercise.py.
Step 1 – Annotated Example
Suppose you type "Anthropic.COM" into your web browser. With your normalize() function, the normalized name is anthropic.com..
You are provided with a function send_query(normalized_name, server_ip) that simulates the network call to server_ip, and the IP address of a “root server” which is the starting point of any DNS query.
Finally, the answer field holds a type A record, and we return its rdata.
Step 2 – CNAME records
Sometimes, instead of containing an A record, the answer section will contain a CNAME record.
CNAME chains can be longer than one hop. Implement handling for this case in resolve().
Step 3 – Missing glue records
Sometimes we are directed to a nameserver whose IP isn’t in the additional section. When there is no matching glue record, you must resolve the nameserver’s IP address before continuing.
Step 4 – Error handling and NS fallback
In the authority section, there can be multiple NS records, and each NS record may or may not have a matching glue record. Try each nameserver in order until one succeeds.
NXDOMAIN means the name definitely doesn’t exist in this zone, so return None.
REFUSED means the server can’t help you and does not know about this name. Try the next nameserver if available.
Step 5 – Cycle Handling
Implement a basic form of cycle detection: if you haven’t succeeded after max_queries calls to send_query, assume you’re caught in a cycle and return None.
Step 6 – Cached batch resolution
Implement resolve_all(). Given a list of domains, resolve each one and return a mapping from each input domain (note that inputs are not necessarily normalized) to its resolved IP or None if it couldn’t be resolved.
Cache the result of every send_query call so that no (name, server) pair is queried twice across the batch. NXDOMAIN and REFUSED responses should also be cached.
max_queries is the limit per domain. A cache hit does not call send_query, but still counts against the limit for that domain.
The cache must be scoped to each resolve_all() call and not persisted globally.
Step 7 – Parallel resolution
Make resolve_all() resolve domains concurrently to complete faster in wall-clock time.
At most max_workers (default 5) calls to send_query may be in flight at any time.
If a query is already in flight from another domain’s resolution, wait for it rather than sending a duplicate.
[execution time limit] 30 seconds
[memory limit] 4g
这题本质上是一个带缓存和并发控制的 DNS 解析器实现：先按规则处理大小写和尾点归一化，再沿着根服务器、NS 记录、glue 记录和 CNAME 链逐步向下解析，遇到 NXDOMAIN 直接返回 None，遇到 REFUSED 则尝试下一个 nameserver。难点在于批量解析时要把每一次 (name, server) 查询结果做成调用级缓存，避免同一对键重复请求；同时还要支持并发解析，但必须限制同时进行的 send_query 数量，并且当多个域名需要同一个查询时要复用同一个正在进行中的结果，而不是重复发起请求。
