Imagine typing a domain name into a search box and seeing suggestions appear before your finger lifts off the key. For a dataset of 240 million domain names, that’s a massive technical challenge. A naive approach would scan every entry for each keystroke impossible at this scale. Yet some engineers claim to achieve P99 latency of 0 milliseconds (with an asterisk). How is that possible?
This article breaks down the engineering behind such a feat, explaining the data structures, caching strategies, and trade-offs. We’ll explore what the asterisk means, why 0ms is both a real achievement and a clever marketing move, and whether you need such speed for your own autocomplete system.
The Scale of the Problem
240 million domain names is not just a big number—it’s about 70% of all registered domains across every TLD. To put it in perspective, imagine a phonebook with 240 million entries. If you wanted to find all names starting with “ab”, you’d have to scan every single page. That would take seconds, not milliseconds.
For autocomplete, you need results in under 100ms for a human to perceive it as instant. But the challenge is worse: each keystroke changes the prefix, so you need to handle new queries in real time. A naive approach would be hopeless.
The Classic Solutions and Their Limits
Most autocomplete systems use one of these approaches:
- Trie (prefix tree): A tree where each node represents a character. Traversing from root to a node gives a prefix. This is memory-hungry at scale—each node holds pointers to children, easily ballooning to tens of gigabytes.
- Inverted index: A map from prefixes to lists of matching entries. Building this for all possible prefixes is expensive but makes lookup fast.
- Finite State Transducers (FSTs): A compact automaton that encodes a set of strings efficiently. Lucene uses FSTs for its suggest feature, but even FSTs require traversing nodes, which takes microseconds.
At 240 million entries, even a well-optimized trie traversal might take 1-10 milliseconds. To get to 0ms, you need a fundamentally different approach.
The 0ms Trick: Precomputation and Caching
The only way to achieve true 0ms server-side processing is to avoid computation altogether. The solution: precompute the results for every possible prefix (or a large subset) and store them in a hash map. Then, a lookup is O(1)—just a hash table read.
For domain names, the prefixes you need to support are typically 1-3 characters long. There are 26^3 = 17,576 possible 3-letter prefixes. For each prefix, you precompute the top 10 most popular domain names starting with that prefix. Store these in a JSON file or a key-value store like Redis.
When a user types “ab”, the server simply looks up the key “ab” and returns the precomputed list. No traversal, no ranking logic—just a hash lookup. That’s why the server-side time can be 0ms.
But wait—where does the asterisk come in? The 0ms measurement excludes network time. The actual request still travels from the user’s browser to your server and back. That network round-trip might take 20-50ms. So the user doesn’t experience true 0ms, but the server processing is effectively instantaneous.
The Memory Trade-Off
Precomputing all prefixes is memory-intensive. For each of the 17,576 prefixes, you store a list of up to 10 domain names. If each domain name averages 15 characters, that’s about 150 characters per prefix. Multiply by 17,576, and you get roughly 2.6 million characters—about 2.6 MB of raw text. That’s surprisingly small! Even with overhead for data structures, you’re looking at maybe 10 MB.
But what if you want to support longer prefixes, like “abou”? The number of possible 4-letter prefixes is 26^4 = 456,976. That’s still manageable—about 68 MB of raw text. For 5-letter prefixes, you’d have 11.8 million possibilities, which balloons to 1.7 GB. So you need to decide where to draw the line.
Most autocomplete systems only need to handle prefixes up to 3 or 4 characters because users typically type a few letters before seeing results. For longer queries, you can fall back to a trie or a sorted array with binary search, which is still fast enough.
The Cold Start Problem
Precomputing results works great once the data is loaded into memory. But what happens on the first request after deployment? If you’re loading a 10 MB JSON file into a hash map, that might take a few hundred milliseconds. But that’s a one-time cost. After that, all lookups are fast.
However, if you’re precomputing on the fly, you’d have a problem. The solution is to precompute offline, during deployment, and load the precomputed data into memory. This is a common pattern in high-performance systems.
The Benchmark Caveat
When the author writes “P99 0 ms*”, the asterisk typically points to a footnote: “Measured server-side, excluding network time.” This is a fair caveat because the user’s perceived latency includes network. But it’s also a bit of a marketing trick—0ms sounds amazing, but it’s not the full story.
Moreover, P99 of 0ms means that 99% of requests were processed in under 1 millisecond (if the timer resolution is 1ms). That’s still incredibly fast, but it’s not literally zero. The point is that the server processing is so fast that it’s below the measurement threshold.
Is 0ms Necessary?
From a user experience perspective, 0ms is overkill. Human perception of instant is around 100ms. If your autocomplete responds in 50ms, users won’t notice any delay. The pursuit of 0ms is more about engineering bragging rights than practical need.
However, there are scenarios where every millisecond counts, such as high-frequency trading interfaces or real-time collaborative tools. But for a domain name search, 100ms is perfectly fine.
How to Implement This Yourself
If you want to build a similar system, here’s a step-by-step approach:
- Collect your dataset: For domain names, you can get a list from public sources like Verisign’s COM/NET zone files or use a service like DomainIQ.
- Build a prefix map: For each prefix from 1 to 3 characters (or more if you wish), compute the top N suggestions. You can do this by sorting all domains and then extracting prefixes.
- Store the map: Save it as a JSON file or in a key-value store. If you’re using a CDN, you can serve static JSON files for each prefix, letting the CDN handle caching.
- Serve requests: When a user types a prefix, look up the key and return the list. If the prefix is longer than your precomputed limit, fall back to a secondary index (like a trie).
- Measure: Use high-resolution timers to measure server-side latency. You’ll likely see P99 of 0-1ms.
The Trade-Offs and Limitations
This approach sacrifices freshness. If you add new domains, you need to rebuild the precomputed map. For a domain name registrar, that might be acceptable if you update daily. But for a dynamic dataset, you’d need a more complex solution.
Also, precomputing only top-N results means you might miss less popular matches. If a user types a rare prefix, you might not have any suggestions. But for autocomplete, you typically want popular results anyway.
Finally, the memory footprint grows exponentially with prefix length. You need to choose a cutoff that balances coverage and memory.
Conclusion
Achieving P99 0ms autocomplete for 240 million domain names is possible through aggressive precomputation and caching. The asterisk reminds us that network time is excluded, but the server processing is genuinely instantaneous. While 0ms might be overkill for most applications, the techniques used—precomputation, hash maps, and CDN caching—are valuable for any high-performance autocomplete system. By understanding the trade-offs, you can decide how far to go in optimizing your own search features.
The 0ms autocomplete is a testament to clever engineering—precomputing results for every possible prefix turns a computation problem into a simple lookup. While the asterisk hides the network latency, the server-side speed is real. For most builders, a 50ms response is plenty, but the principles of precomputation and caching can scale down to any dataset. If you’re looking to improve your autocomplete, consider whether you need 0ms or just fast enough.
Summary
- 240 million domain names is a massive dataset that rules out naive autocomplete.
- The 0ms trick is to precompute results for every prefix and use a hash map for O(1) lookups.
- The asterisk means the measurement excludes network time; server processing is truly near-zero.
- Memory trade-offs: precomputing all 1-3 letter prefixes costs only ~10 MB, but longer prefixes balloon exponentially.
- For most users, 50ms is imperceptible, so 0ms is a nice-to-have, not a necessity.
FAQ
Q: How can server processing be 0ms?
A: By precomputing the results for every possible prefix and storing them in a hash map. Lookup is a simple hash read, which takes nanoseconds.
Q: What does the asterisk () mean in ‘P99 0 ms‘?
A: It usually means the measurement excludes network time. The server processing is 0ms, but the user still experiences network latency of 20-50ms.
Q: Is 0ms necessary for a good user experience?
A: No. Human perception of ‘instant’ is around 100ms. A 50ms response is indistinguishable from 0ms for most users.
Q: What are the memory requirements?
A: For all 1-3 letter prefixes (17,576 prefixes) with top 10 results each, you need about 10 MB. For 4-letter prefixes, it grows to ~70 MB.
Q: How do I handle updates to the dataset?
A: You need to rebuild the precomputed map whenever the dataset changes. This is fine for static data but less practical for highly dynamic data.