DNS Resolution Algorithm: Protocol Implementation Deep Dive

1. Introduction and Core Concepts

The dns resolution algorithm is the fundamental protocol mechanism that translates human-readable domain names like www.example.com into machine-routable IP addresses such as 93.184.216.34. Without this algorithm, the modern internet as we know it would be unusable, requiring users to memorize numerical addresses for every service they wish to access. At its core, DNS resolution is a hierarchical, distributed lookup algorithm that operates as the phonebook of the internet, providing a fault-tolerant and scalable mapping between names and addresses.

From an algorithmic perspective, DNS resolution is not a single algorithm but a family of coordinated procedures involving caching, iterative querying, recursive querying, and hierarchical delegation. The system is designed to handle over a trillion queries per day globally while maintaining low latency, high availability, and eventual consistency. Its distributed nature means there is no single central database; instead, authority is delegated across millions of name servers organized in a tree structure that mirrors the domain namespace itself.

Understanding the dns resolution algorithm matters for every networking professional, backend engineer, and systems architect. Performance of DNS directly impacts page load times, email delivery, API reliability, and even security posture. A poorly implemented resolver can add hundreds of milliseconds to every connection, leak privacy, or become vulnerable to cache poisoning and spoofing attacks. Conversely, an optimized implementation with intelligent caching, prefetching, and parallel queries can dramatically improve application responsiveness and resilience. This deep dive explores the protocol theory, practical implementation in Python, complexity characteristics, and real-world engineering trade-offs.

Why DNS Resolution Is Algorithmically Interesting

Unlike simple key-value lookups in a hash table, DNS resolution must operate over an unreliable network (UDP primarily), handle partial failures, respect time-to-live (TTL) semantics, and navigate a globally distributed hierarchy. The algorithm must decide when to query iteratively versus recursively, how to cache and evict entries, how to handle CNAME chains, and how to fall back from UDP to TCP when responses are truncated.

Furthermore, modern extensions like DNSSEC, DNS over HTTPS (DoH), and DNS over TLS (DoT) add cryptographic validation and privacy layers that change the algorithmic flow. The resolver must now validate signatures, manage encrypted channels, and balance security against latency, making DNS resolution a rich case study in distributed systems design.

2. How It Works

The DNS namespace is an inverted tree with the root zone (".") at the top, followed by Top-Level Domains (TLDs) like .com, .org, and .net, then second-level domains like example.com, and finally subdomains like www.example.com. Each node in this tree may be delegated to an authoritative name server that holds the definitive records for that zone. The dns resolution algorithm traverses this tree to find the authoritative answer for a query.

There are two primary query modes. In recursive resolution, the client (stub resolver) asks a recursive resolver (typically provided by an ISP or public DNS like 8.8.8.8) to do all the work and return a final answer. The recursive resolver then performs iterative resolution on behalf of the client: it queries the root servers, then the TLD servers, then the authoritative servers, following referrals at each step until it obtains the answer. This separation allows clients to remain simple while pushing complexity and caching to dedicated resolvers.

A standard resolution flow involves several record types and steps. When a user requests blog.example.com, the stub resolver first checks its local cache and /etc/hosts file. On a cache miss, it sends a UDP query to the configured recursive resolver. That resolver checks its own cache. If still a miss, it begins iterative queries: it asks a root server (e.g., a.root-servers.net) for blog.example.com, receives a referral to the .com TLD servers, asks a .com server and receives a referral to example.com's authoritative servers, and finally asks the authoritative server which returns the A record (IPv4) or AAAA record (IPv6).

Protocol Mechanics: Messages, Transport, and Caching

DNS messages are defined in RFC 1035 and consist of a 12-byte header followed by question, answer, authority, and additional sections. The header contains an ID for matching queries and responses, flags (QR, RD, RA, AA, TC), and counts for each section. Most queries use UDP port 53 for speed, with a 512-byte limit for classic DNS (extended to 4096 bytes via EDNS0). If the TC (truncated) bit is set, the client retries over TCP.

Caching is central to performance. Every resource record (RR) carries a TTL value in seconds, dictating how long a resolver may cache it. The algorithm must implement a TTL-aware cache with eviction, often using an LRU or TTL-priority queue. Negative caching (caching NXDOMAIN responses per RFC 2308) is equally important to avoid repeatedly querying for non-existent names. Proper cache management reduces upstream load by over 90% in production resolvers.

Recursive vs. Iterative Resolution Flow

In iterative mode, each server responds with the best information it has: either the final answer or a referral to a more specific server. The querying resolver is responsible for following the chain. In recursive mode, the server takes responsibility for walking the chain itself. Most public resolvers support recursion for clients but use iterative queries upstream to distribute load and avoid amplifying attacks. Understanding this distinction is critical when implementing a resolver from scratch, as your code must handle referral chasing, loop detection, and timeout handling.

3. Implementation

Implementing the dns resolution algorithm in Python requires handling low-level protocol parsing, network I/O, and caching. While production systems use highly optimized C or Rust implementations like BIND, Unbound, or PowerDNS, a Python implementation is excellent for learning and for building custom service discovery or monitoring tools. Below are four progressively more complete implementations.

The first example shows a minimal iterative resolver simulation that models the hierarchical delegation without actual network calls. This is useful for understanding the logic before dealing with sockets and byte parsing.

import random
import time
from typing import Dict, Optional, List

# Simulated DNS hierarchy for demonstration
DNS_HIERARCHY = {
    ".": {"ns": "a.root-servers.net", "referral": "com"},
    "com": {"ns": "a.gtld-servers.net", "referral": "example.com"},
    "example.com": {"ns": "ns1.example.com", "records": {"www.example.com": "93.184.216.34"}},
}

class SimpleIterativeResolver:
    def __init__(self):
        self.query_count = 0
        self.cache: Dict[str, tuple] = {}  # name -> (ip, expiry)

    def resolve(self, domain: str) -> Optional[str]:
        # 1. Check cache first (TTL-aware)
        if domain in self.cache:
            ip, expiry = self.cache[domain]
            if time.time() < expiry:
                print(f"[CACHE HIT] {domain} -> {ip}")
                return ip
            else:
                del self.cache[domain]

        # 2. Walk hierarchy iteratively
        labels = domain.split(".")
        current_zone = "."
        path = []

        for i in range(len(labels)):
            self.query_count += 1
            zone = ".".join(labels[-(i+1):]) if i > 0 else "."
            # Simulate referral chasing
            if zone in DNS_HIERARCHY and "referral" in DNS_HIERARCHY[zone]:
                path.append(f"Query {DNS_HIERARCHY[zone]['ns']} for {domain} -> referral to {DNS_HIERARCHY[zone]['referral']}")
            elif zone in DNS_HIERARCHY and "records" in DNS_HIERARCHY[zone]:
                records = DNS_HIERARCHY[zone]["records"]
                if domain in records:
                    ip = records[domain]
                    # Cache with TTL 300s
                    self.cache[domain] = (ip, time.time() + 300)
                    path.append(f"Query {DNS_HIERARCHY[zone]['ns']} -> ANSWER {ip}")
                    for p in path:
                        print(p)
                    return ip

        print(f"[NXDOMAIN] {domain} not found after {self.query_count} queries")
        return None

resolver = SimpleIterativeResolver()
print(resolver.resolve("www.example.com"))
print(resolver.resolve("www.example.com"))  # Second call hits cache

The second example implements a TTL-aware cache with proper eviction and negative caching. This component is reused by any production-grade resolver and demonstrates the importance of time-based invalidation.

import time
import threading
from collections import OrderedDict

class DNSCache:
    def __init__(self, max_size: int = 10000):
        self.max_size = max_size
        self.store: OrderedDict[str, dict] = OrderedDict()
        self.lock = threading.Lock()

    def get(self, key: str):
        with self.lock:
            entry = self.store.get(key)
            if not entry:
                return None
            # Check TTL expiry
            if time.time() > entry["expiry"]:
                del self.store[key]
                return None
            # Move to end for LRU
            self.store.move_to_end(key)
            return entry["value"]

    def put(self, key: str, value: str, ttl: int, is_negative: bool = False):
        with self.lock:
            # Enforce max size with LRU eviction
            if len(self.store) >= self.max_size:
                self.store.popitem(last=False)
            expiry = time.time() + ttl
            # Negative caching uses smaller TTL per RFC 2308 (e.g., 60s)
            if is_negative and ttl > 300:
                expiry = time.time() + 60
            self.store[key] = {"value": value, "expiry": expiry, "ttl": ttl}
            self.store.move_to_end(key)

    def get_ttl_remaining(self, key: str) -> int:
        entry = self.store.get(key)
        if not entry:
            return 0
        remaining = entry["expiry"] - time.time()
        return int(remaining) if remaining > 0 else 0

# Example usage
cache = DNSCache(max_size=3)
cache.put("www.example.com", "93.184.216.34", ttl=300)
cache.put("nx.example.com", None, ttl=60, is_negative=True)
print(f"Hit: {cache.get('www.example.com')}")  # 93.184.216.34
print(f"Negative hit: {cache.get('nx.example.com')}")  # None but cached
time.sleep(1)
print(f"TTL remaining: {cache.get_ttl_remaining('www.example.com')}s")

The third example shows how to construct and parse raw DNS wire-format messages using Python's struct and socket modules. This is the core of protocol implementation, handling header flags, QNAME encoding, and record parsing with proper escaping for HTML safety.

import struct
import socket
import random

def encode_qname(domain: str) -> bytes:
    """Encode domain like 'www.example.com' into DNS label format."""
    parts = domain.split(".")
    result = b""
    for part in parts:
        result += struct.pack("!B", len(part)) + part.encode()
    result += b"\x00"
    return result

def build_dns_query(domain: str, qtype: int = 1) -> bytes:
    """Build a DNS query packet (RFC 1035 Section 4.1)."""
    tx_id = random.randint(0, 65535)
    flags = 0x0100  # Standard query, recursion desired
    qdcount = 1
    ancount = nscount = arcount = 0
    header = struct.pack("!HHHHHH", tx_id, flags, qdcount, ancount, nscount, arcount)
    qname = encode_qname(domain)
    # QTYPE 1 = A, QCLASS 1 = IN
    question = qname + struct.pack("!HH", qtype, 1)
    return header + question

def parse_dns_header(data: bytes) -> dict:
    """Parse 12-byte DNS header."""
    if len(data) < 12:
        raise ValueError("Packet too short")
    tx_id, flags, qdcount, ancount, nscount, arcount = struct.unpack("!HHHHHH", data[:12])
    return {
        "id": tx_id,
        "qr": (flags >> 15) & 0x1,
        "opcode": (flags >> 11) & 0xF,
        "tc": (flags >> 9) & 0x1,  # Truncated
        "rd": (flags >> 8) & 0x1,
        "ra": (flags >> 7) & 0x1,
        "rcode": flags & 0xF,
        "qdcount": qdcount,
        "ancount": ancount,
    }

def send_dns_query(domain: str, server: str = "8.8.8.8", timeout: int = 2):
    query = build_dns_query(domain)
    sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    sock.settimeout(timeout)
    try:
        sock.sendto(query, (server, 53))
        data, _ = sock.recvfrom(512)
        header = parse_dns_header(data)
        if header["tc"] == 1:
            print("Response truncated, should retry over TCP")
        print(f"Response for {domain}: RCODE={header['rcode']}, Answers={header['ancount']}")
        return data
    except socket.timeout:
        print(f"Timeout querying {server} for {domain}")
        return None
    finally:
        sock.close()

# Uncomment to test live (requires network):
# send_dns_query("example.com")

The fourth example demonstrates a concurrent resolver that parallelizes queries for multiple domains and handles CNAME chaining, which is essential for modern web performance where a single page may require resolving dozens of domains.

import concurrent.futures
import time
from typing import List, Dict

# Mock function to simulate network latency
def mock_resolve_with_cname(domain: str) -> str:
    cname_map = {
        "www.example.com": "example.com",
        "cdn.example.com": "example.net",
    }
    a_records = {
        "example.com": "93.184.216.34",
        "example.net": "93.184.216.35",
        "api.example.com": "93.184.216.36",
    }
    # Simulate CNAME chain resolution
    visited = set()
    current = domain
    chain = []
    while current in cname_map:
        if current in visited:
            raise ValueError(f"CNAME loop detected for {domain}")
        visited.add(current)
        chain.append(current)
        current = cname_map[current]
        time.sleep(0.05)  # Simulate network delay

    if current in a_records:
        if chain:
            print(f"CNAME chain {' -> '.join(chain)} -> {current} -> {a_records[current]}")
        return a_records[current]
    raise ValueError(f"NXDOMAIN for {domain}")

def concurrent_resolve(domains: List[str], max_workers: int = 5) -> Dict[str, str]:
    results = {}
    start = time.time()
    with concurrent.futures.ThreadPoolExecutor(max_workers=max_workers) as executor:
        future_to_domain = {executor.submit(mock_resolve_with_cname, d): d for d in domains}
        for future in concurrent.futures.as_completed(future_to_domain):
            domain = future_to_domain[future]
            try:
                ip = future.result()
                results[domain] = ip
            except Exception as e:
                results[domain] = f"ERROR: {e}"
    elapsed = time.time() - start
    print(f"Resolved {len(domains)} domains in {elapsed:.3f}s with {max_workers} workers")
    return results

domains = ["www.example.com", "cdn.example.com", "api.example.com", "unknown.example.com"]
print(concurrent_resolve(domains))

4. Step-by-Step Example

Let us walk through a complete resolution of www.example.com as performed by a recursive resolver like Cloudflare's 1.1.1.1 or Google's 8.8.8.8. Assume the client has just booted, so all caches are cold, and the resolver also has an empty cache. The client application calls getaddrinfo("www.example.com"), which triggers the stub resolver.

Step 1: Stub Resolver Checks Local Cache. The operating system's stub resolver first checks its local cache and hosts file. Finding no entry, it constructs a DNS query with RD (Recursion Desired) = 1 and sends it via UDP to its configured recursive resolver at 8.8.8.8:53. The query contains QNAME=www.example.com, QTYPE=A, QCLASS=IN, and a random 16-bit transaction ID for matching.

Step 2: Recursive Resolver Queries Root. The recursive resolver receives the query, checks its cache (miss), and begins iterative resolution. It has a hard-coded hints file with the 13 root server addresses (e.g., 198.41.0.4 for a.root-servers.net). It sends a query for www.example.com to a root server. The root server is not authoritative for example.com, so it responds with a referral: authority section lists com name servers (a.gtld-servers.net etc.) and additional section provides their glue A records. No answer section is present.

Step 3: Query TLD Servers. The resolver picks one of the .com TLD servers and queries it for www.example.com. The TLD server consults its zone for com and finds a delegation for example.com with NS records pointing to ns1.example.com and ns2.example.com plus glue records. It returns another referral. The resolver caches this delegation with its TTL (typically 172800 seconds for TLD NS).

Step 4: Query Authoritative Server and Return. The resolver now queries ns1.example.com (e.g., 192.0.2.1) for www.example.com. This server is authoritative and holds the zone file for example.com. It finds an A record: www.example.com. 300 IN A 93.184.216.34 and returns it with AA (Authoritative Answer) flag set. The recursive resolver caches this record for 300 seconds, then forwards the answer to the original stub resolver, which caches it locally and returns the IP to the application. The application can now open a TCP connection to 93.184.216.34:443.

Tracing CNAME and TTL Behavior

If the authoritative server instead returned www.example.com. 300 IN CNAME example.com. plus example.com. 300 IN A 93.184.216.34, the resolver must follow the CNAME chain. It would need to resolve example.com if not already included in the additional section. Each record's TTL is respected independently. On a subsequent query within 300 seconds, the entire chain is served from cache with no upstream queries, reducing latency from ~80ms to <1ms.

5. Complexity Analysis

Analyzing the dns resolution algorithm requires distinguishing between cache performance and hierarchical traversal. Unlike traditional algorithmic complexity measured in input size, DNS complexity is measured in network round trips, cache hit rates, and label depth. The depth of the domain name (number of labels) determines the worst-case number of iterative queries.

In the best case, the answer is in the local stub cache or the recursive resolver's cache, requiring O(1) time and a single cache lookup with no network I/O. This is the common case in production, where cache hit rates exceed 85-95% for popular domains. The average case involves one or two upstream queries due to partial cache hits (e.g., TLD delegation is cached but authoritative record is not). The worst case is a full cold-cache traversal from root to authoritative server, plus CNAME chain following and potential TCP fallback.

Space complexity is dominated by cache size. A resolver serving thousands of clients may cache millions of records, each with metadata (name, type, value, TTL, expiry). Implementations use bounded caches with LRU eviction to cap memory. The message parsing itself is O(n) in packet size, where n is typically <512 bytes for UDP, so it is negligible compared to network latency.

Practically, network latency dominates. Each RTT to an authoritative server may be 20-100ms depending on geography and anycast routing. Therefore, optimization focuses on minimizing RTTs via aggressive caching, prefetching, and parallel queries rather than micro-optimizing CPU cycles. A resolver that reduces average RTTs from 3 to 1 via caching effectively cuts resolution time by 66%.

6. Variations and Optimizations

Production resolvers employ numerous optimizations beyond the basic RFC 1035 flow. One of the most impactful is QNAME minimization (RFC 7816), where the resolver sends only the minimal label needed at each step. Instead of asking the root for www.example.com, it asks only for com, then asks the TLD for example.com, reducing privacy leakage and sometimes improving cache utilization.

Prefetching and predictive resolution anticipates future queries. If a resolver sees a query for example.com, it may proactively refresh NS records before they expire or prefetch common subdomains like www. Browsers also implement DNS prefetching by parsing HTML and resolving domains for links before the user clicks, hiding latency.

Parallel querying and hedging improves tail latency. Instead of querying one authoritative server at a time, a resolver may query multiple NS records for the same zone in parallel and use the fastest response, similar to hedged requests in distributed systems. This is particularly effective when one authoritative server is slow or overloaded. Some resolvers also implement 0-RTT connection reuse for DNS over TLS/HTTPS.

Modern Protocol Variants

DNS over HTTPS (DoH, RFC 8484) and DNS over TLS (DoT, RFC 7858) encapsulate DNS messages in encrypted channels to prevent eavesdropping and tampering. Algorithmically, they add a TLS handshake (1-2 RTTs) but enable session resumption and connection multiplexing. DNS over QUIC (DoQ) further reduces handshake latency using QUIC's 0-RTT. Another optimization is EDNS0 Client Subnet (ECS), which forwards a truncated client subnet to authoritative servers for geo-aware responses, improving CDN routing at the cost of some privacy.

For large-scale deployments, anycast routing and response rate limiting (RRL) are critical. Anycast allows the same IP (e.g., 8.8.8.8) to be announced from hundreds of PoPs globally, so queries are routed to the nearest resolver via BGP. RRL prevents amplification attacks by limiting identical responses per second. On the caching side, adaptive TTL and stale-while-revalidate (serve expired cache while refreshing in background) improve resilience during authoritative outages.

7. Real-World Applications

The dns resolution algorithm underpins nearly every internet-connected application. In web browsing, a single page load may trigger 20-50 DNS resolutions for the main domain, CDN assets, analytics, fonts, and third-party scripts. Browsers maintain an internal DNS cache (typically 60 seconds) and OS-level caches further reduce lookups. Content Delivery Networks (CDNs) like Cloudflare and Akamai rely heavily on DNS for global load balancing: authoritative servers return different A records based on client geography, server health, and load, using low TTLs (30-60s) to enable rapid failover.

In microservices and service discovery, DNS is used as a lightweight service registry. Kubernetes' CoreDNS resolves service names like payments.default.svc.cluster.local to cluster IPs, handling thousands of resolutions per second within a data center. Consul and Eureka also use DNS interfaces for service lookup, where TTLs are kept very low (5-10s) to reflect rapid scaling events. The algorithm's ability to return multiple A records enables client-side round-robin load balancing without a dedicated load balancer.

Email delivery depends on MX record resolution. When sending mail to [email protected], the mail transfer agent queries for example.com MX, receives a prioritized list of mail servers, and then resolves each MX hostname to an IP. SPF, DKIM, and DMARC anti-spoofing mechanisms also use TXT record lookups, making DNS critical for email security. A failure in MX resolution directly causes mail deferral or bounce.

Beyond these, DNS is used for security filtering (DNS firewalls like Quad9 block malicious domains by returning NXDOMAIN or 0.0.0.0 for known bad names), IoT device onboarding (devices resolve manufacturer domains to fetch configuration), and database connection bootstrapping (applications resolve database hostnames that may be backed by failover clusters). In each case, the resolution algorithm's caching, retry, and timeout behavior directly impacts application availability.

8. Comparison with Alternatives

While DNS is the dominant name resolution system, several alternatives exist for specific environments. Understanding their trade-offs helps architects choose the right mechanism for local networks, privacy-sensitive applications, or decentralized systems.

Multicast DNS (mDNS) and Link-Local Multicast Name Resolution (LLMNR) provide zero-configuration resolution on local networks without a central server, ideal for printers, smart home devices, and peer-to-peer discovery. Hosts files and static configuration offer deterministic, offline resolution but do not scale. More recently, blockchain-based systems like Ethereum Name Service (ENS) and Handshake offer decentralized, censorship-resistant naming.

For most internet applications, DNS remains optimal due to its maturity, caching efficiency, and global delegation model. mDNS complements DNS for local discovery (e.g., printer.local), while DoH/DoT are increasingly becoming the default for privacy rather than outright replacements. Hosts files are still used for development and for overriding DNS in testing. Blockchain naming remains niche but illustrates an alternative trust model where names are owned via private keys rather than leased from registrars.

9. Common Mistakes and Best Practices

Even experienced engineers make subtle errors when implementing or operating DNS resolution. One frequent mistake is ignoring TTL semantics. Hard-coding cache durations or ignoring the TTL returned by authoritative servers violates the protocol and causes stale data or excessive load. For example, caching an A record for 24 hours when its TTL is 60 seconds will prevent failover to a new IP during an outage. Always respect the minimum TTL and implement negative caching with appropriate short TTLs for NXDOMAIN.

Another pitfall is not handling truncated responses and TCP fallback. Large responses (e.g., DNSSEC or many TXT records) exceed UDP limits and set the TC bit. A naive resolver that discards truncated responses will fail intermittently. The correct behavior is to retry the same query over TCP, which has no size limit. Similarly, failing to handle CNAME loops or excessive chain length can cause infinite loops; implement a max chain depth (e.g., 8-16) and loop detection via visited set.

Blocking DNS in the application thread is a common performance anti-pattern. Synchronous getaddrinfo calls block the entire thread, causing latency spikes in web servers. Best practice is to use asynchronous resolution (e.g., c-ares, asyncio with aiodns, or dedicated resolver threads) and to cache results at the application layer with TTL awareness. Additionally, always configure multiple resolver IPs and implement timeout and retry with exponential backoff and jitter to avoid thundering herds.

Best Practices Checklist

• Respect TTLs exactly; use LRU + TTL eviction and serve stale-while-revalidate for resilience.
• Implement both UDP and TCP transport; retry truncated UDP over TCP automatically.
• Validate and limit CNAME/DNAME chains; detect loops and enforce max depth.
• Use QNAME minimization and disable ECS unless geo-routing is required, to preserve privacy.
• Deploy DNSSEC validation where possible, but handle validation failures gracefully (fail open vs closed per policy).
• Monitor cache hit rate, resolution latency (p50/p95/p99), and NXDOMAIN rate; alert on spikes indicating misconfiguration or attacks.
• Randomize transaction IDs and source ports to mitigate spoofing; prefer DNS cookies (RFC 7873) for additional protection.
• For high-throughput services, use connection reuse for DoT/DoH and prefetch popular names before expiry.

Security best practices also include rate limiting, response rate limiting (RRL) on authoritative servers, and filtering of private IP responses (DNS rebinding protection) when resolving untrusted names in browsers or server-side request forgery (SSRF) contexts.

10. Interview Questions

DNS resolution is a favorite topic in systems design and networking interviews because it touches distributed systems, caching, and protocol design. Below are common questions with guidance on what interviewers expect.

Q1: Explain the difference between recursive and iterative DNS queries. When would you use each?

Answer: In a recursive query, the client asks a resolver to fully resolve the name and return the final answer; the resolver does all iterative work upstream. In an iterative query, the server returns a referral to the next best server, and the client (or recursive resolver) is responsible for following it. Stub resolvers use recursive queries for simplicity, while recursive resolvers use iterative queries upstream to distribute load, improve caching, and avoid amplification. Mention that most public resolvers support recursion for clients but disable it for arbitrary internet clients to prevent DDoS abuse.

Q2: How would you design a DNS cache? What eviction policy and data structures would you use?

Answer: Use a hash map (dictionary) for O(1) lookups keyed by (QNAME, QTYPE, QCLASS), with each entry storing value, expiry time (now + TTL), and TTL. For bounded memory, combine with LRU via OrderedDict or doubly-linked list + hash map. On get, check expiry and evict if stale; on put, evict LRU if over capacity. For TTL handling, use a priority queue or lazy expiration. Also discuss negative caching for NXDOMAIN, separate cache for delegations (NS records), and thread safety. Mention metrics like hit rate and memory usage.

Q3: What happens when you type https://www.example.com in a browser? Detail the DNS steps.

Answer: Walk through: 1) Browser cache → OS cache → hosts file → recursive resolver query (RD=1). 2) Recursive resolver iterative walk: root → TLD → authoritative, with caching at each level. 3) Handling of CNAME, A/AAAA, and HTTPS records. 4) Return IP to browser, then TCP + TLS handshake. Emphasize that DNS is just the first step before connection establishment, and note optimizations like DNS prefetch, 0-RTT, and Happy Eyeballs (parallel A/AAAA).

Q4: How does DNS handle failure and what are common attack vectors? How would you mitigate them?

Answer: Failures include timeout, NXDOMAIN, SERVFAIL, and truncated responses. Mitigations: retry with exponential backoff, try multiple NS records, fallback to TCP, serve stale cache. Attacks: cache poisoning (spoofed responses), Kaminsky attack, amplification DDoS, and DNS tunneling. Mitigations: randomize TXID + source port, DNSSEC validation, DNS cookies, response rate limiting, and encrypted transport (DoH/DoT). Discuss trade-offs of DNSSEC validation failure handling.

Q5: Compare DNS caching at different layers (browser, OS, recursive resolver). Why do we need multiple layers?

Answer: Each layer optimizes for different scope and TTL. Browser cache (minutes) is per-process and fastest. OS stub cache is system-wide and respects TTL. Recursive resolver cache is shared across many clients and provides the biggest hit rate improvement, reducing upstream load. Authoritative servers also have caches for delegations. Multiple layers reduce latency (browser <1ms vs 50ms upstream) and provide resilience if one layer fails. However, multi-layer caching can cause inconsistency if TTLs are not respected uniformly; hence the importance of honoring TTL at each layer.