Design Search Autocomplete / Typeahead

Search, Ranking & DiscoveryMediumdesign-typeahead-autocomplete

Design Search Autocomplete / Typeahead

Design suggestions that appear as the user types: a keystroke-latency budget, a precomputed prefix structure, and a ranking that reflects what people searched for an hour ago.

TriePrecomputed Top-KEdge CachingDebounced Queries

Traffic & Capacity Estimates:

5B searches/day · 4 suggestion requests per search · p99 under 60ms

Functional Requirements

•Return the top 5-10 completions for any prefix, ranked by popularity and personalization.
•Update rankings from live query traffic within an hour.
•Support typo tolerance and multi-word prefixes.
•Filter adult, abusive, and legally restricted suggestions before they are ever shown.

Non-Functional Requirements

•p99 under 60ms end-to-end — slower than the typist and the feature is useless.
•Serve from the edge where possible; a cross-continent round trip per keystroke is not viable.
•Suggestion quality must degrade gracefully rather than return nothing.

Back-of-the-Envelope Math

5B searches/day * 4 prefix requests = 20B requests/day (~230k QPS average, far higher at peak).
Precomputing top-10 for every prefix of every popular query inflates the index but turns each request into one lookup.

Key Architectural Trade-offs

Storing the top-K at every trie node makes lookup O(prefix length) and makes every update touch many nodes — read-optimised at the cost of write amplification.
Rebuilding the suggestion index hourly from aggregated logs is simple and lags trends; streaming updates catch breaking events and cost a live pipeline.
Client-side debouncing and prefix caching cut backend traffic by an order of magnitude and add a small perceived delay.

Click or drag a component onto the canvas, then connect the handles to draw the data flow.

3 nodes · 2 edges

Components · 35

Client & Edge4

Compute & Gateway7

Storage & Caching11

Messaging & Streaming6

Coordination & Ops5

Intelligence2

React Flow