Search Typeahead
IntermediateOverview
A search typeahead (autocomplete) service returns the top-ranked query suggestions for whatever prefix a user has typed so far, updating on each keystroke. Because it fires on nearly every character, it must answer in tens of milliseconds at very high read volume.
Functional Requirements
- Return the top-k suggestions for a given prefix, ranked by popularity.
- Update suggestions as the user types each additional character.
- Reflect trending and newly popular queries as the corpus evolves over time.
- Filter out disallowed or unsafe terms from suggestions.
Non-Functional Requirements
- Very low latency: a suggestion response should return in well under 100 ms, ideally under 50 ms, per keystroke.
- High availability and scalability: sustain massive, read-dominated traffic with no user-visible downtime.
- Freshness: the suggestion corpus reflects recent query activity within an acceptable delay (minutes to hours).
Capacity Estimation
Assume 100 million daily active users, each issuing 10 searches/day, and (after client-side debouncing) ~4 typeahead requests per search.
- QPS: 100e6 x 10 x 4 = 4e9 requests/day. 4e9 / 86,400 s ~ ~46,000 requests/sec average; a 5x peak gives ~230,000/sec. This is overwhelmingly read traffic.
- Bandwidth: a response of ~10 suggestions is about 1 KB. 46,000/sec x 1 KB ~ ~46 MB/s ~ 370 Mbps average, approaching ~1.8 Gbps at peak.
- Storage: the served index is a compact prefix structure over the most popular phrases. Roughly 10 million top phrases x (~20 chars + a precomputed top-k list) ~ a few GB, small enough to hold in memory; the full raw query log used to build it is far larger and lives in bulk storage.
High-Level Architecture
The system splits into a Data Gathering Service (which logs queries and aggregates them) and a Query Service (which serves suggestions). The Query Service relies on an in-memory Trie data structure that is periodically rebuilt by the Data Gathering pipeline. A Redis cache sits in front to serve the most common prefixes instantly.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| Suggestion entry | prefix, top_k (ordered phrase + score list) | In-memory cache backed by a prefix index (trie) |
| Query aggregate | query, count, window | Analytics / bulk store, updated by the pipeline |
| Raw query log | query, timestamp, user_bucket | Append-only log / object storage |
Detailed Design
The Trie Data Structure
The core trick is to precompute the answer using a Trie (Prefix Tree). Each node in the Trie represents a character. To avoid traversing the whole tree to find the top 5 suggestions for a prefix, we cache the top-k most popular completions directly on every node. The result is a prefix index where a lookup is a direct read of the node, not a search-and-sort.
Data Gathering Pipeline
Rather than updating the Trie in real-time (which would cause massive lock contention), an offline pipeline (e.g., Spark or Flink) periodically aggregates the raw query log into per-phrase popularity counts. It builds a completely new Trie in the background. Once built, the Query Service swaps its pointer to the new Trie in a single atomic operation, so readers never see a half-built index.
Caching & The Read Path
At request time the prefix cache does the heavy lifting. Popular prefixes are short and few ("a", "ap", "app"), so a Redis cache of prefix -> top-k absorbs the vast majority of keystrokes with an in-memory hit; only cold prefixes fall through to the Trie. Serving is further pushed toward the user with edge caching (CDN) for the hottest prefixes and browser-level caching (local storage), cutting round-trip latency to zero for repeated queries.
Bottlenecks & Solutions
The offline pipeline can take hours to process billions of logs, meaning the suggestions are not perfectly real-time. If a major news event breaks, it won't show up in typeahead immediately. To fix this, a secondary "Trending Stream" can ingest real-time queries via Kafka, detect sudden spikes, and inject them into a smaller, real-time cache that the API queries alongside the main Trie.