超大规模域名列表存储及主域名关联子域名查询最优方案探讨

Hey Joe, let's tackle your 10^9-scale domain list problem—this is all about efficiently handling hierarchical domain data, so I'll split this into storage strategies and query implementations that play well together.

First, the key insight here is that domains are hierarchical, so we need to leverage that structure instead of treating each domain as a random string. Here are the top approaches:

• Reverse Domain Prefix Storage
  This is the most common trick for this use case. Reverse each domain string so that the top-level domain comes first. For example:

  • site.com → com.site
  • ns1.site.com → com.site.ns1
  • test.main.site.com → com.site.main.test
    By storing reversed domains, all subdomains of site.com will share the prefix com.site. (note the trailing dot to avoid matching site.com itself). This turns a "find all children of a parent" problem into a simple prefix query.

• Choose the Right Storage Engine
  Depending on your read/write ratio and latency needs:

  • Columnar Databases (ClickHouse, BigQuery) : Great for large-scale analytical queries. ClickHouse, in particular, supports efficient prefix queries with its LowCardinality string type and built-in prefix indexes. You can create a table with a reversed domain column and run fast LIKE queries or use startsWith() for lookups.
  • Key-Value Stores with Prefix Support (RocksDB, Redis Sorted Sets) : RocksDB allows prefix scans directly on sorted keys, which is perfect for reversed domains. For Redis, store reversed domains in a sorted set—you can use ZREVRANGEBYLEX to fetch all entries with the com.site. prefix.
  • Distributed Search Engines (Elasticsearch) : If you need more flexible queries (like partial matches), Elasticsearch's keyword fields with prefix queries work, but it's overkill if you only need exact prefix matches. However, it scales well for distributed setups.

• Sharding for Scale
  With 10^9 entries, you'll need to split data across nodes. Shard based on the first few characters of the reversed domain (e.g., split by com., net., org. or even the first 2-3 characters of the reversed string). This ensures that all subdomains of a parent live on the same shard, avoiding cross-shard queries.

Once you have the reversed storage set up, the query logic becomes straightforward:

1. Preprocess the Query Domain
   Take the target main domain (e.g., site.com), reverse it, and append a trailing dot to get the prefix: com.site.. The trailing dot ensures you don't match the main domain itself (since its reversed form is com.site, no trailing dot).

2. Run the Prefix Query

   • ClickHouse Example:

     SELECT reverse(reversed_domain) AS subdomain
     FROM domain_table
     WHERE reversed_domain LIKE 'com.site.%'
     

     (Pro tip: Use startsWith(reversed_domain, 'com.site.') for even faster performance if your column has a prefix index.)
   • Redis Sorted Set Example:

     ZREVRANGEBYLEX domains_set "[com.site." "(com.site/"
     

     The [ denotes inclusive start, and ( denotes exclusive end (using a character higher than . like / ensures we capture all entries starting with com.site.). Then reverse each result string to get the original subdomains.
   • RocksDB Example:
     Use a prefix iterator to scan all keys starting with com.site., then reverse each key to get the subdomains.

3. Post-Processing (Optional)
   If you need to exclude any invalid entries or deduplicate (though you should deduplicate during ingestion), you can filter results after fetching.

• Deduplication During Ingestion: Use a hash set or bloom filter to avoid storing duplicate domains—this reduces storage size and query time.
• Cache Hot Queries: If certain main domains are queried frequently, cache their subdomain lists in Redis or an in-memory cache to avoid hitting the main storage every time.
• Compression: Columnar databases like ClickHouse automatically compress string columns, but for key-value stores, consider using dictionary compression for reversed domains to save space.

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