The fastest request is not always the one that finishes first. Sometimes it is the one that begins before the user starts waiting.
Wirewiki’s domain autocomplete is built around that distinction. Its index covers roughly 240 million names, the application runs on one server in Europe, and every uncached request travels through Cloudflare, Nginx, and an API. Yet for the system’s author, suggestions were ready before key release at the 99th percentile of his typing sample.
The headline number is “0 ms,” but no packet crosses a network in zero time. The measurement starts at keyup, when the interface owes the user a visible answer. Work begins earlier, at keydown, and the response includes not only matches for the current prefix but prepared matches for every possible next character. When the next key arrives, the browser usually selects an answer it already has.
That is the first half of the design: move work into time the user is already spending. The second half makes the speculation affordable. A small, popular “head” stays in an in-memory trie. A much larger “tail” lives in delta-compressed, memory-mapped blocks on SSD. The API searches the head first, touches the tail only when needed, and returns the eight most useful names.
Together, those choices form a practical lesson in perceived performance. Make the deadline explicit, predict a bounded amount of likely future work, and give each part of the data set a representation that matches how often it is touched.
Zero milliseconds is a product definition
Latency needs two timestamps. Backend dashboards usually choose request received and response sent. Network tools measure round-trip time. A person using autocomplete experiences a different interval: the time between completing an input action and seeing the interface react.
For this design, the clock begins when a key is released. If suggestions are ready by then, measured wait is zero even though the browser, network, and server have already done real work.
The browser starts a request on keydown. Suppose the current text becomes wi. The API returns the best matches for wi, plus separate result lists for wi-, wi., wi0 through wi9, and wia through wiz. If the next key is k, the browser can take the prepared wik branch from its cache instead of waiting for another round trip.
The browser keyup event is fired when a key is released. That makes the measurement concrete, but it is not universal human truth. Touch keyboards, paste, speech input, input method editors, accessibility tools, and programmatic changes do not all follow the same simple physical-key sequence. A production implementation still needs an input-driven correctness path. Key events are an optimization opportunity, not the only source of state.
The author’s test involved typing 100 domain names at a reasonably fast pace. The 99th-percentile interval from one key press to the next release was 121 ms. That became the working end-to-end budget.
At 60 Hz, a display produces a new frame every 16.7 ms. Rendering within the next frame can add a little scheduling slack, but not much at the tail. The important number is therefore not an abstract “fast API” target. It is: can the complete path finish before the next key release for almost every measured interaction?
Speculation is cheap when the future is bounded
Prefetching can easily become waste. Search systems with a large alphabet, rich filters, or long result objects might multiply bandwidth by dozens of branches that are never used. Domain autocomplete has unusually helpful constraints.
Wirewiki uses 38 next characters: a-z, 0-9, hyphen, and dot. With eight suggestions for the current prefix and eight for each possible continuation, one response contains at most 312 domain names:
(38 possible next characters + current prefix) × 8 suggestions = 312 names
The uncompressed response is at most about 5 KB in the author’s measurements and roughly 2.5 KB over the wire after compression. This is deliberate overfetching, but it is capped. The client exchanges a few kilobytes for the chance to remove an entire future round trip.
That trade works because the response contains small strings, the branch factor is fixed, and typing provides immediate evidence about which branch will be used. Apply the same pattern to product cards with images and it could be ruinous. The general rule is not “prefetch everything.” It is prefetch a small, bounded set whose cost is lower than the delay it can hide.
Client caching also needs discipline:
- Cache entries must be keyed by the exact normalized prefix and query options.
- Stale requests should be cancelled with
AbortControlleror ignored by sequence number, so an older response cannot replace newer suggestions. - Backspace can often reuse a parent prefix already held in memory.
- Composition events need special handling so an incomplete IME sequence is not treated as committed input.
- Result lists should remain accessible with correct combobox semantics, keyboard selection, and screen-reader announcements.
Speculation changes when work happens. It must not change which input wins.
Popularity and completeness need different structures
A single data structure is rarely ideal for both the most popular million domains and the other hundreds of millions. The first group is small enough to keep hot and important enough to deserve the fastest path. The second group provides completeness, but most names will rarely be requested.
Wirewiki builds its popular head from Tranco, a research-oriented ranking of one million domains. Tranco combines multiple source lists over a 30-day window to improve stability and resistance to manipulation; its methodology also documents the biases in each underlying source. That makes it more useful than treating any one traffic list as an unquestionable measure of popularity.
The long tail comes mainly from generic top-level-domain zone files. ICANN’s Centralized Zone Data Service provides a common place to request zone files from participating registries. It covers many gTLDs such as .com, .net, and .org, but it does not provide the same broad access to country-code TLDs. Popular ccTLD names still appear through Tranco, while certificate-transparency logs and web archives are possible future sources for broader coverage.
This data split is semantic before it is technical:
- The head answers “what are people most likely trying to reach?”
- The tail answers “does a matching active name exist even if it is obscure?”
Autocomplete needs both. A popularity-only index feels fast but incomplete. An alphabetical list of everything can return obscure names ahead of the destination a person probably intended.
The head: precompute the answer at every prefix
The top one million names live in a character trie. Each edge represents the next character and each node represents a prefix. A lookup walks the characters the user typed, so its cost grows with the query length rather than the total number of domains.
The more important optimization is stored at the nodes: every prefix already has its top eight suggestions. A request for wik does not descend through all matching names, gather candidates, and sort them on demand. It reaches the wik node and reads the answer prepared when the index was built.
That shifts work from request time to build time and trades memory for predictable latency. It is a strong fit because:
- The popular set changes much more slowly than users type.
- Eight results are enough for the interface.
- Every query needs the same operation: retrieve the best completions for a prefix.
The complexity is often written as O(length of prefix). More usefully, the request path is a short chain of dependent memory reads with no scan proportional to the million-name corpus and no per-request ranking pass.
The tail: a small directory over compressed blocks
Keeping 240 million strings in ordinary heap objects would spend heavily on pointers, allocation metadata, string headers, and repeated prefixes. The tail instead uses a sorted, delta-compressed file divided into fixed blocks of 256 names.
A 27 MB in-memory directory identifies the block that may contain a prefix. The API binary-searches that directory, then scans one small block. Because adjacent sorted domain names tend to share leading characters, delta compression stores the common prefix once and records only the changing suffix for later entries.
The complete 240-million-name data set occupies about 2.5 GB on disk in the author’s implementation. The file is memory-mapped, so the program can address it like memory while the operating system loads pages on demand. Linux readahead brings file content into the page cache before every byte is explicitly requested, and it avoids repeating I/O for pages already present; the kernel’s memory-management documentation describes that mechanism. Hot tail blocks naturally remain resident, while cold blocks cost SSD access only when needed.
The tail lookup is described as O(length of prefix × log number of domains), followed by a bounded block scan. Both query length and corpus size are capped in the deployed system, so the practical goal is not an asymptotic breakthrough. It is a narrow worst-case path: one directory search, one block, and at most 256 decoded names.
Fixed-size blocks are the quiet hero. A huge compressed stream might achieve a slightly better ratio but require decoding from a distant checkpoint. Very small blocks add directory overhead. A block of 256 names limits work and gives the page cache a useful chunk to retain.
Search the head first, use the tail to fill gaps
The two indexes are not peers. Popular results should always win. The API searches the in-memory trie first and consults the tail only when the head cannot fill the result list. It then deduplicates and preserves rank order.
That order encodes product policy directly into the query plan. A popular domain that matches a prefix must not be displaced by an alphabetically earlier but unknown registration. The head provides relevance; the tail provides recall.
There is a broader pattern here:
| Layer | Optimized for | Representation |
|---|---|---|
| Browser | Next interaction | Small speculative prefix cache |
| Popular head | Relevance and latency | In-memory trie with precomputed top eight |
| Long tail | Coverage and density | Sorted delta-compressed blocks on SSD |
| Operating system | Locality | Memory mapping, page cache, and readahead |
Each layer predicts at a different horizon. The browser predicts the next character. The trie predicts which names matter for a prefix. The page cache predicts which nearby disk pages will be touched again.
The API became cheaper than the network
The author generated 720,000 keystroke queries from 60,000 simulated domain-name typing sessions and replayed them open-loop: requests were fired at a fixed rate rather than waiting for earlier responses. That matters because closed-loop load tests can accidentally reduce pressure when the server slows down.
Most API-only requests completed within 2 ms. At 1,600 requests per second, Nginx plus the API stayed within 15 ms at p99 in the reported production-server test. The benchmark also exercised the end-to-end route through Cloudflare.
Those are the author’s measurements, not an independent benchmark, and the workload is shaped like his own product. Still, the ordering of costs is instructive. Once index lookup falls to a few milliseconds, the network dominates. Further micro-optimization at the origin cannot recover 100 ms of geographic round-trip time.
In practice, end-to-end autocomplete latency was roughly the browser-to-origin round trip through Cloudflare plus another 10 ms. Cloudflare can absorb repeated traffic and cache hot requests, but it cannot repeal distance for a miss.
The asterisk is geography
The single origin is in Europe. For users in the United States, the author observed an additional 100–200 ms—enough to exceed his 121 ms p99 typing budget. The system can feel instant locally without delivering the same tail latency globally.
Multiple regional replicas plus geographic routing would reduce that distance. The read-only index is a friendly replication workload: build an immutable artifact, distribute it, and swap versions atomically. The hard parts would be operational rather than algorithmic—deployment, health checks, routing, observability, cache behavior, and keeping measurements comparable across regions.
Wirewiki stops before that complexity because autocomplete is a feature, not currently a standalone business. This is sound engineering restraint. The goal is not the lowest number a distributed system could possibly achieve. The goal is the best experience worth operating for the product that exists.
The asterisk therefore improves the lesson. “P99 0 ms” is true for a specific definition, client behavior, typing sample, and geography. Performance claims become useful when their boundaries are explicit.
A repeatable design process
This system can be reduced to six decisions that apply beyond domain search.
1. Define the human deadline
Choose the event after which delay becomes visible. It may be key release, pointer release, viewport entry, or the opening of a panel. Measure from that boundary, while still recording real end-to-end time separately.
2. Look for work that can begin earlier
Hover, focus, keydown, partial input, and navigation intent can create safe speculation windows. Start only work that remains correct if the prediction is wrong.
3. Bound the speculative bill
Estimate branch count, response bytes, server work, cancellation rate, and cache reuse. Prefetching is a budget, not a ritual.
4. Split data by access frequency
Do not force the hot million and cold hundreds of millions through the same representation. Give the head more memory and precomputation; give the tail density and bounded access.
5. Make the slow path narrow
A tail lookup should touch one small directory and one small block, not wake an unbounded scan. Fixed work is easier to reason about at p99.
6. Stop when another layer dominates
When network distance costs two orders of magnitude more than lookup, optimize placement or accept the boundary. Shaving microseconds from the trie is no longer the highest-value move.
Instant interfaces are scheduled, not magical
This autocomplete does not defeat latency. It schedules around it.
The browser borrows time from the physical act of typing. The response speculates over a fixed 38-character future. The in-memory trie makes popular queries a short prefix walk. The compressed block index keeps 240 million names affordable. Memory mapping lets the operating system decide which tail pages deserve RAM. Finally, the product accepts that one European server cannot deliver the same p99 experience everywhere.
That stack is more interesting than any single data structure. Perceived speed emerges when client timing, payload shape, ranking policy, storage layout, operating-system behavior, and geography agree on the same deadline.
The useful question is not “how can this API return in zero milliseconds?” It is: what must already be true when the user expects the next frame?
Top comments (0)