Design Search Autocomplete

Requirements

Search autocomplete (typeahead) shows a short list of suggested queries as the user types. Typing sys might show "system design", "system of a down", "sysco". The key constraint is time: suggestions must appear faster than the user types the next character.

Functional

• Given a prefix, return the top k (say 5-10) most popular completions.
• Suggestions reflect query popularity, updated regularly (hourly or daily), with optional trending boost.
• Filter offensive, unsafe or legally blocked suggestions.
• Optional: personalization (your recent searches), localization per language/region, typo tolerance.

Non-functional

• Very low latency: p99 under ~100 ms end to end; server-side well under 20 ms.
• Highly available: if autocomplete fails, search still works, but the experience degrades visibly.
• Read-heavy: every keystroke is a read; writes are batch updates from logs.
• Eventual consistency is fine: a new popular query can take minutes to hours to appear.

Capacity Estimates

Assume 10 M DAU, 10 searches per user per day, and an average of 20 characters typed per search, with the client debouncing so roughly one request every 2 characters.

Every request is a tiny read, so the design is about keeping the index in memory, close to the user, and cacheable.

API Design

GET /api/v1/suggestions?q=sys&limit=8&locale=en-US
  200: {
    "prefix": "sys",
    "suggestions": [
      { "text": "system design", "score": 98213 },
      { "text": "system of a down", "score": 55102 },
      { "text": "sysco", "score": 21877 }
    ]
  }
  Cache-Control: public, max-age=3600

• Lowercase and trim the prefix on the client so equivalent requests hit the same cache entry.
• The client debounces (waits ~100-150 ms after the last keystroke), cancels in-flight requests when a newer prefix is typed, and caches responses locally so backspacing is free.
• Search submissions are logged separately (POST /search or the search service's own logs); autocomplete reads never write.

Data Model

An alternative to a trie is a flat key-value table of prefix → top-k list (precomputed for every prefix up to, say, 20 characters). It is simple to shard and serve from Redis or Cassandra at the cost of more storage.

High-Level Design

flowchart LR
  U[Browser or App] --> CDN[CDN and Edge Cache]
  CDN --> LB[Load Balancer]
  LB --> AS[Autocomplete Service]
  AS --> RC[(Prefix Cache)]
  AS --> TS[Trie Servers in memory]
  U -->|search submitted| SS[Search Service]
  SS --> L[[Query Log Stream]]
  L --> AGG[Aggregator batch or streaming]
  AGG --> F[(Frequency Table)]
  F --> TB[Trie Builder]
  BL[(Blocklist)] --> TB
  TB --> SNAP[(Trie Snapshots)]
  SNAP --> TS

The system splits into two independent paths:

• Query (read) path: client → CDN/edge cache → autocomplete service → in-memory trie shard → top-k list. Most popular prefixes never reach the origin.
• Data (write) path: search logs → aggregation (counts per query per time window) → trie builder (applies filtering, computes top-k) → versioned snapshot → trie servers hot-swap the new version.

Deep Dives

Trie with precomputed top-k

A plain trie answers "which queries start with sys?" by walking to the s → y → s node and then traversing the whole subtree to find the most frequent completions. For short prefixes like s, that subtree has millions of entries, far too slow per keystroke.

Two optimizations make lookups effectively O(prefix length):

1. Cap the prefix length (for example 50 characters); longer prefixes rarely matter.
2. Store the top-k completions at every node. The trie builder computes them bottom-up: each node's list is the best k among its own terminal query and its children's lists. A lookup then walks at most p nodes and returns the stored list.

root
 └─ s
     └─ y
         └─ s   top5: [system design, system of a down, sysco, sysadmin, systemd]
             └─ t ...

Storage grows by k references per node, which is why the builder prunes queries below a frequency threshold and stores pointers or IDs rather than full strings.

Building and updating the data

• Aggregation: a periodic job (Spark/MapReduce) counts queries per time bucket. A weighted score such as sum(count × decay^age) lets recent popularity outweigh old popularity, which gives a basic trending effect.
• Filtering: remove rare queries (privacy and noise), personally identifying strings, and blocklisted terms before building.
• Snapshot and swap: build the new trie offline, write it to object storage with a version number, and have each server load it into memory and atomically switch a pointer. Never update a live trie node-by-node under traffic.
• Real-time trends: for breaking news, a streaming job (Flink/Kafka Streams) maintains a small "trending" top-k per prefix that is merged with the batch results at query time.

Caching at every layer

Prefix popularity is extremely skewed: one- and two-character prefixes account for a large share of requests, and their answers barely change between rebuilds.

• Browser cache: responses carry Cache-Control headers; repeated prefixes and backspaces cost nothing.
• CDN/edge: cache GET /suggestions?q=... responses keyed by normalized prefix and locale, with TTL aligned to the rebuild interval.
• Service cache: a Redis or in-process LRU of hot prefixes in front of the trie.
• Personalized results cannot be shared; return a cacheable global list and merge personal history on the client.

Sharding the trie

If the trie does not fit on one machine, or for throughput and isolation:

• By first character(s): shard a-c, d-f, ... Simple, but uneven: far more English queries start with s than with x.
• By measured load: use historical traffic to split ranges so each shard gets similar QPS (for example s alone may be split into sa-sh and si-sz). A small shard map in each service instance routes requests.
• By hash of the prefix for the flat prefix → top-k table: even distribution, but no range locality.
• Replicate each shard several times; trie servers are read-only between rebuilds, so replicas never diverge.

Client-side behaviour

Much of the perceived speed comes from the client: debouncing, cancelling stale requests, rendering only the response that matches the current input (responses can arrive out of order), and prefetching the top suggestion's results. Mobile clients may ship a small on-device list of the most common prefixes for instant first-character suggestions.

Scaling & Reliability

• Stateless service tier in front of in-memory trie replicas; scale replicas with QPS.
• Multi-region deployment with region-specific tries (language and local trends differ) and edge caching close to users.
• Graceful degradation: if a trie shard is unavailable, return cached or empty suggestions quickly; never block the search box.
• Timeouts: autocomplete answers that arrive late are useless, so use tight server timeouts (tens of milliseconds) and drop rather than queue.
• Pipeline safety: validate each new snapshot (size, sample queries, blocklist checks) before rollout, roll out gradually, and keep the previous version for instant rollback.
• Monitoring: p50/p99 latency, cache hit ratio per layer, suggestion click-through rate, and snapshot age.

Trade-offs

Interview Tips

• Lead with latency: a suggestion that arrives after the next keystroke is wasted, which drives every decision.
• Separate the read path from the data-collection path early; interviewers want to see that the trie is rebuilt offline.
• Explain why a naive trie is slow for short prefixes and how top-k caching per node fixes it.
• Cover caching in the browser, CDN and service layers, and why autocomplete responses cache so well.
• Discuss uneven sharding by first letter and a load-aware fix.
• Mention filtering, abuse and emergency removal; it shows product awareness.

References

• System Design Primer: Cache
• System Design Primer: Sharding
• Trie (Wikipedia)
• ByteByteGo: System Design 101
• Awesome Scalability