Sweaty Imposter

Design a Web Search Autocomplete

System DesignLow LatencyRead HeavySenior3 min readUpdated

Every keystroke is a query, and the answer has to come back before the next one. The design precomputes the top completions for every prefix offline, so the online path is a lookup.

1 · Requirements

The Prompt

Suggest top-k completions for a partial query in <100ms for global traffic.

Functional

  • Suggest the top completions for a partial query
  • Rank completions by popularity and recency
  • Show trending queries by region

Non-Functional

  • Suggestions return in under 100 ms at p99, worldwide
  • The service handles about 150,000 prefix lookups a second at peak
  • New queries show up within a day, and trending lists within minutes

2 · Estimates

Drill This Phase First

Show the Answer and Estimates

Answer

About 60,000 a second

1B divided by 86,400 seconds is about 12,000 searches a second. Five lookups each gives about 60,000 a second, and about 150,000 at peak.

Lookups
1B searches a day is about 12,000 a second; 5 keystroke lookups each makes about 60,000 a second and 150,000 at peak
Latency
Under 100 ms at p99: about 5 ms for the trie lookup and 2 ms on a cache hit, leaving the rest for the network
Trie
About 50M prefixes with the top 5 completions at 50 bytes each: about 12 GB in memory per node
Logs
1B queries at about 100 bytes: about 100 GB a day of query logs for the rebuild
CDN
About 10,000 hot prefixes serve half the traffic, so edge caching cuts origin load to about 30,000 lookups a second
Rebuild
A nightly Spark job over 30 days of logs ranks the top completions and ships a new trie snapshot

3 · API

GET /autocomplete?q=prefix&limit=10 → { suggestions: [{ text, score }] }
POST /events/search { query, user_id?, ts } → 202 (logs to Kafka)
GET /trending?region=US → { queries[] } (refreshed every minute)
Admin: POST /index/rebuild → { job_id, eta }

Data Model

trie_node (in-memory + S3 snapshot):
  prefix (PK)     : string
  top_k           : list<{ completion, score }> (k=10)
  child_offsets   : map<char, node_offset>

query_log (Kafka → S3 partitioned by hour):
  query           : string
  user_id         : uuid?
  region          : string
  ts              : timestamp
  clicked_result  : string?

trending (Redis, key = "trend:{region}"):
  sorted_set of query → recency-weighted count

4 · High-Level Design

The read path is a lookup at every step: the edge cache, then Redis, then the in-memory trie node, which already stores its top completions. The write path is offline: query logs feed a nightly rebuild that ships a fresh trie snapshot.

5 · Deep Dives

Top K at Every Node

Walking the subtree under a prefix at query time is too slow for short, popular prefixes. Store the top 10 completions directly on each trie node during the rebuild, and a lookup becomes one node read.

Sharding the Trie

Sharding by first letter overloads the shards for common letters. Shard by a hash of the first two or three characters, and replicate the hottest shards, so load spreads evenly.

Fresh Trends

A nightly rebuild misses breaking news. Keep a small trending layer in Redis, updated every minute from the Kafka stream with recency-weighted counts, and merge it with the trie's results before ranking.

6 · Wrap Up

Close on what you would add next: personalization from a user's own history, a blocklist for offensive completions, and a trie per language.

The Short Version

Trie of prefixes with top-k cached at each node. Refresh from query logs nightly. Edge CDN cache for hot prefixes.

Building Blocks