Millisecond Autocomplete Over 240 Million Domains: An Extreme Performance Engineering Deep Dive

Introduction: When Autocomplete Meets Massive Scale

Autocomplete is one of the most common — and most performance-demanding — features in modern web applications. Every time a user types a character into a search box, the system needs to return relevant suggestions within milliseconds. With a few thousand records, this is almost a non-problem. But when the dataset grows to 240 million domain names, everything changes.

A recent technical post on Hacker News set a striking goal: autocomplete over 240 million domains with a P99 latency of 0 ms\*. That asterisk is worth noting — it hints at the clever engineering trade-offs and design tricks hiding behind that "0 ms" claim. This article explores the core ideas and engineering practices behind achieving millisecond-level autocomplete at massive scale.

Understanding the Challenge: Why 240 Million Is a Different Beast

The core operation in autocomplete is prefix search: given a user-typed prefix, quickly find all candidates that start with it, then rank and return them by relevance.

At small scale, a simple LIKE 'prefix%' database query does the job. But at hundreds of millions of records, the complexity changes qualitatively:

• Memory footprint: 240 million domain names, averaging just 20 bytes each, is nearly 5 GB of raw data — and index structures can double or triple that.
• Query latency: Traditional database indexes at this scale suffer from disk I/O and tree traversal costs that can push P99 latency into the tens or hundreds of milliseconds.
• P99, not average: P99 means 99% of all requests must meet the performance target. Optimizing average latency is relatively straightforward; flattening the long tail requires pushing data structures, memory layout, and caching strategy to their limits.

What Does "P99 0 ms" Actually Mean?

In practice, P99 0 ms means query latency falls below the measurement resolution — typically sub-millisecond. Reaching this threshold is virtually impossible with disk access or network round-trips. All data and indexes must live in memory, and the query path must be extremely short.

Core Technical Approach: Tries and Their Compressed Variants

Why a Trie Is the Natural Fit

The classic solution for prefix completion is a Trie (prefix tree). A Trie decomposes strings character by character, sharing common prefixes across all entries. Query complexity depends only on the prefix length, not on the total number of entries — which is exactly the property needed to handle hundreds of millions of records.

But a naive Trie has enormous memory overhead: each node must store pointers to child nodes, and 240 million entries can produce billions of nodes, blowing up memory immediately.

Three Key Compression and Compaction Strategies

To fit a massive dataset into available memory, engineers typically apply the following optimizations:

• Radix Tree (Patricia Trie): Merges paths with only a single child, dramatically reducing node count. This is the most fundamental and practical compression step.
• DAWG (Directed Acyclic Word Graph): Extends the Radix Tree by also merging common suffixes, transforming the tree into a graph. Especially effective for domain name datasets, which share many common suffixes like .com, .org, and .net.
• Succinct Data Structures: Encode the tree topology using bit vectors, reducing pointer overhead to near the theoretical lower bound. These structures compress memory usage close to the entropy limit of the data, while maintaining O(1) or O(log n) navigation speed.

Succinct data structures deserve a closer look, as they are the key breakthrough that makes full in-memory storage of hundreds of millions of entries feasible. A conventional Trie node stores multiple child pointers — on a 64-bit system, each pointer takes 8 bytes, and with billions of nodes the memory cost is staggering. The core idea of succinct structures is to describe the tree topology using a bit array. The classic encoding scheme is LOUDS (Level-Order Unary Degree Sequence): it records each node's degree in level-order traversal as a sequence of 0s and 1s, then uses two primitive operations — rank and select (both achievable in O(1)) — to navigate the tree without storing explicit pointers. For 240 million domain names, a Succinct Trie can compress memory usage to roughly 2–4 bits per character, keeping the total index within 1–2 GB and making a full in-memory approach genuinely practical.

DAWG solves a different dimension of redundancy. A normal Trie shares only prefixes; a DAWG merges identical subtrees into shared nodes, thereby sharing suffixes as well. In a domain name dataset, high-frequency suffixes like .com, .net, and .org are shared by enormous numbers of entries. DAWG folds these repeated structures into common graph nodes, reducing node count by an order of magnitude compared to a Trie — while leaving the prefix query path completely unchanged.

Four Engineering Pillars of Extreme Performance

Full In-Memory Storage + CPU Cache-Friendly Layout

To achieve sub-millisecond latency, all data must reside in memory, and the memory layout must be CPU cache-friendly. Contiguous array-based storage — as opposed to scattered pointer chasing — significantly reduces cache misses, which are typically the dominant source of long-tail latency.

Serializing the Trie into a compact byte array and replacing pointers with integer offsets both saves memory and improves data locality. This is standard practice in high-performance systems of this kind.

The impact of CPU caching on query latency is especially pronounced under high concurrency. A modern CPU's L1 cache is typically only 32–64 KB; the L3 cache tops out at a few dozen MB — yet even a compressed index for 240 million domains can reach gigabytes. A single cache miss incurs roughly 60–100 ns to access main memory, and a few consecutive misses can push a single query into the microsecond or even millisecond range.

When Trie nodes are serialized into a contiguous byte array in BFS (breadth-first) order, parent and child nodes are physically adjacent in memory. The downward traversal path during a prefix query aligns naturally with this layout, allowing the CPU prefetcher to load the next level of nodes into the cache line ahead of time. Additionally, compressing child node indexes from 64-bit pointers to 32-bit offsets saves memory and packs more index information into a single 64-byte cache line, further improving data locality. This is the fundamental reason why a compact array representation consistently outperforms traditional heap-allocated nodes by several times in measured latency.

Top-K Precomputation and Result Truncation

Users typically need only the top few suggestions. Precomputing and storing the Top-K results at each prefix node — ranked by domain popularity — avoids traversing all matching entries at query time. This is critical for flattening P99 latency: whether a prefix matches 10 entries or 1 million, the system always returns the same fixed Top-K list, so query cost is constant.

Top-K precomputation typically relies on domain popularity scores — for example, Tranco rankings, Common Crawl crawl frequency, or DNS query volume — as weights, sorted offline during index construction. During the build phase, each Trie node propagates the top-K highest-scoring entries from its subtree upward, and these results are compactly serialized and stored alongside that node. At query time, once the node corresponding to the prefix is located, the precomputed Top-K list is read directly and returned, completely bypassing subtree traversal.

The trade-off is that index size grows linearly with K, so K is typically kept small — between 5 and 20 — aligned with the number of suggestions displayed in the UI. A batch-rebuild architecture (rather than real-time updates) means precomputation has virtually no latency cost on the write side, which complements nicely with the lock-free, read-only design on the read side.

Lock-Free Reads to Eliminate Concurrency Bottlenecks

An autocomplete service is a classic read-heavy, write-rare workload. Using a read-only, immutable data structure combined with periodic batch rebuilds completely eliminates read/write lock contention, allowing concurrent queries to proceed independently and keeping long-tail latency stable.

Leveraging Domain-Specific Properties

Domain name data offers unique structural advantages: abundant common suffixes (.com, .org, .cn), precomputable popularity rankings, and a limited character set. All of these properties can be exploited to further compress data and accelerate queries.

Practical Takeaways for Engineers

Although this case study focuses specifically on domain autocomplete, the engineering principles apply broadly:

1. The right data structure beats throwing hardware at the problem. Trie/DAWG decouples query complexity from data size — that's the fundamental key to handling massive datasets.
2. Optimize for P99, not averages. Real user experience is determined by the long tail. Focus on eliminating cache misses, memory allocations, and lock contention — the primary long-tail killers.
3. Memory layout is performance. In the world of nanoseconds, CPU cache behavior often matters more than algorithmic complexity.
4. Mine your domain-specific structure. Common suffixes, a limited character set, and precomputable popularity rankings in domain data are all optimization opportunities worth fully exploiting.

Conclusion

"P99 0 ms autocomplete over 240 million domains" might sound like a marketing headline, but it's backed by solid systems engineering: choosing the right Trie variant and compression scheme, applying full in-memory layout, Top-K precomputation, and lock-free reads layer by layer. For any developer building real-time interactive experiences over massive datasets, this case study is a performance engineering reference worth studying carefully. True "0 ms" is never magic — it's the relentless elimination of latency at every layer of the design.