DNS缓存实现：如何用单一数据结构实现正向与反向查询？

Great question—this is a common optimization goal when building DNS caches, since maintaining duplicate records adds unnecessary overhead and opens the door to consistency issues. Let’s break down practical, battle-tested approaches to handle both forward (domain → IP) and reverse (IP → domain) lookups with a single underlying dataset:

1. Shared Data Nodes with Dual Hash Indexes #

This is the most straightforward approach for hash-based caches:

• First, define a unified DNSCacheEntry struct/object that holds all critical data: domain name, list of associated IPs, TTL timestamp, cache status (e.g., fresh/stale), and any other metadata.
• Maintain two separate hash maps (not duplicate records):
  • Forward map: Key is the domain string (e.g., example.com), value is a reference to the corresponding DNSCacheEntry.
  • Reverse map: Key is the IP address string (e.g., 192.168.1.1), value is a list of references to DNSCacheEntry objects (since one IP can map to multiple domains like virtual hosts).
• When you add or update a cache entry:
  1. Create or modify the single DNSCacheEntry object.
  2. Update the forward map to point to this entry.
  3. Update the reverse map to add this entry to the IP's associated list (or replace if it's a single-domain mapping).
• Pros:
  • All cache data is stored once—no duplication means lower memory usage and no sync issues when updating/expiring entries.
  • Hash maps provide O(1) average lookup time, which is perfect for high-throughput DNS caches.
• Gotchas: Remember to handle multi-domain-to-one-IP scenarios by using lists in the reverse map, and clean up both maps when an entry expires.

2. Extended Trie with Reverse Hash Index #

If you’re leaning toward a Trie structure (great for handling wildcard domains and prefix-based lookups), you can pair it with a lightweight reverse index:

• Build your forward Trie as usual: split domains into reversed segments (e.g., example.com becomes com → example) and store the DNSCacheEntry at the leaf node.
• Add a reverse hash map where the key is the IP address, and the value is a reference to the corresponding Trie leaf node(s) that contain that IP.
• For lookups:
  • Forward: Traverse the Trie using the domain segments to find the leaf node and retrieve the IPs.
  • Reverse: Look up the IP in the reverse hash map to get the Trie leaf node, then extract the associated domain name(s).
• An advanced alternative: If you need to handle standard reverse DNS queries (like 1.1.168.192.in-addr.arpa), you can extend the Trie to accept both domain segments and reversed IP segments, linking both paths to the same DNSCacheEntry. This is more complex but aligns with DNS's native reverse query format.

3. Object-Based Storage with Dynamic Reverse Index #

For an object-oriented design:

• Use a primary dictionary (hash map) to map domain names to DNSCacheEntry objects.
• Maintain a global ip_to_entries dictionary that maps IP addresses to sets of DNSCacheEntry objects.
• When modifying a cache entry:
  • Update the primary domain-to-entry map.
  • For each IP in the entry's IP list, add/remove the entry from the corresponding set in ip_to_entries.
• When an entry expires, delete it from both the primary map and all relevant sets in ip_to_entries.
• Pros: This keeps your data model clean, with all business logic tied to the DNSCacheEntry object rather than the indexes.

Key Universal Considerations #

• TTL Sync: Always ensure that when an entry expires, you remove references to it from both forward and reverse indexes. Leaving stale references can lead to incorrect lookup results.
• Multi-Map Handling: Never assume one-to-one mappings—domains can have multiple IPs (load balancing) and IPs can have multiple domains (virtual hosting). Your reverse index must support collections (lists/sets) to avoid data loss.
• Memory Efficiency: All these approaches use a single copy of the cache data, so they’ll use less memory than maintaining two separate record sets—this is a huge win for large-scale caches.

内容的提问来源于stack exchange，提问作者thelearner