Fundamentals · Intermediate

Search autocomplete

Instant typeahead from a precomputed top-k trie, rebuilt offline from query logs.

Every part, and why it is there

Search box

Sends a request as the user types, usually after a short pause (debounce) so “pizza” is not five requests. Suggestions must appear in under ~100 ms to feel instant.

Edge cache

Short prefixes like “a” or “we” are typed by millions of people and have the same answer for everyone, so they can be cached at the edge for a few minutes.

Suggestion service

Looks up the prefix and returns the best 5–10 completions. It does no ranking work at request time; the ranking was done when the trie was built.

Prefix → top-k (trie shards)

Every prefix stores its top completions already sorted, so a lookup is one read. Sharded by prefix range so it fits in memory.

API gateway

Routes full searches (when the user presses enter) to the search service.

Search service

Runs the actual search and records the query. Those records are the raw material for future suggestions.

Search index

The full-text index for real results. Autocomplete deliberately does not query it per keystroke; that would be too slow and too costly.

Query log

Every submitted query as an event. Buffering it means the search path never waits on analytics.

Query aggregator

Counts queries over time windows and filters out spam or offensive terms before they can become suggestions.

Query counts

Historical frequency per query, with recent queries weighted higher so trending searches rise quickly.

Trie builder

Periodically (e.g. hourly) reads the counts and builds a fresh trie with top-k lists. Building offline keeps the serving path read-only and simple.

Trie snapshots

Versioned snapshots of each build. Suggestion servers load the latest one, and a bad build can be rolled back.

Asked in interviews at

  • meta
  • databricks
  • linkedin
  • amazon

Learn more

All system design examples