Stackbook Logo
← Back to System Architectures

Designing Search Autocomplete and Typeahead

Design a typeahead system returning top suggestions in under 100 ms for 5B queries a day using tries, offline aggregation, caching and freshness updates.

5 min read

Autocomplete suggests completions as the user types. It must answer in tens of milliseconds, handle a request per keystroke, and balance popularity, freshness and personalisation. It is a read-dominated system built on precomputed data.

Requirements

Functional

  • Return the top 5 to 10 suggestions for a typed prefix.
  • Rank by popularity, with optional personalisation and locale.
  • Reflect trending queries within minutes.
  • Filter offensive or blocked suggestions.

Non-functional

  • 5B searches per day; every keystroke can fire a request.
  • Latency p99 under 100 ms end to end, ideally under 20 ms server side.
  • High availability; suggestions are optional, so degrade gracefully.
  • Eventual consistency is fine; hour-old rankings are acceptable, trending data should be minutes old.

Capacity estimation

  • 5B searches per day, average 20 characters, but clients debounce and cache, so say 10 requests per search: 50B requests per day, roughly 580,000 per second, peak 1.5M.
  • Distinct queries worth indexing: say 500M unique, average 25 bytes, giving about 12 GB of text. With counts and trie overhead, a few tens of GB. This fits in memory on each serving shard.
  • Log volume: 5B query log lines per day at 200 bytes is 1 TB per day to aggregate.

High-level design

Client (debounce, local cache) -> CDN / Edge cache -> Suggestion Service
                                                         |
                                       prefix cache (Redis) -> Trie shards (in memory)

Query logs -> Kafka -> Batch aggregation (hourly/daily) -> Trie builder -> Snapshot store
                    \-> Stream aggregation (minutes) -> Trending store -> merged at read

Data model

The serving structure is a trie where each node stores its top K completions precomputed:

node(prefix) -> [ (query, score) x K ]   -- K = 10

Storing top K at every node makes a lookup a single traversal of at most the prefix length, with no subtree scan. Memory grows, but only prefixes of popular queries are kept; long-tail prefixes are pruned. Alternatively, a key-value table maps each prefix directly to its top-K list, which is simpler to shard and cache.

Deep dives

Building the index offline. Aggregate query logs into counts per query over a window, apply time decay so recent queries matter more, drop queries below a frequency threshold (also a privacy safeguard), filter blocked terms, then build the trie or prefix table. Publish as a versioned snapshot to object storage. Serving nodes load the new snapshot and swap atomically; rollback is switching the pointer back.

Sharding. Partition by prefix range (for example first one or two characters), with balancing for skewed letters, or hash the prefix. Replicate each shard for throughput and availability. Short prefixes such as one letter are enormously hot, so serve them from cache or a very small precomputed table.

Caching. Layers: browser cache for repeated prefixes within a session, CDN with a short TTL for common prefixes (the response is the same for all users), and a Redis prefix cache. Cache hit rates above 90 percent are typical because prefixes repeat heavily.

Freshness. A stream job counts queries over sliding windows of a few minutes and detects spikes relative to baseline. The trending list is small and merged with the static top K at query time, with a boosted score. This covers breaking news without rebuilding the trie.

Personalisation. Blend global suggestions with a small per-user or per-locale list, such as recent searches stored on the client or in a fast store. Keep the personalised part small to avoid destroying cache hit rates.

Client behaviour. Debounce by 50 to 150 ms, cancel in-flight requests when the user types further, and ignore stale responses. These cut server load by a large factor.

Safety. Run suggestions through a blocklist and a classifier at build time. Support an emergency suppression list applied at read time for urgent takedowns.

Failure modes and trade-offs

  • Bad snapshot: validate size and sample queries before publish, canary a few nodes, and keep the previous version for instant rollback.
  • Hot prefixes: replicate and cache; avoid a single shard serving the letter a.
  • Trending abuse: bots can manipulate counts. Deduplicate by user and IP, and require minimum distinct users before a query trends.
  • Freshness versus cost: more frequent rebuilds improve relevance but cost compute; the trending overlay gives most of the benefit cheaply.
  • Typos: exact-prefix tries do not handle misspellings. Add fuzzy matching only as a fallback because it is slower.

Key takeaways

  • Precompute top K per prefix so serving is a lookup, not a computation.
  • Build offline from query logs with decay and thresholds, and swap versioned snapshots atomically.
  • Cache aggressively at client, CDN and server, and debounce on the client.
  • A small streaming trending overlay delivers freshness without rebuilding everything.
  • Treat suggestions as optional: degrade silently rather than block search.