137Design an autocomplete system serving millions of users with caching and request cancellation

Functional

• Show up to 8–10 suggestions as the user types; highlight the matching part.
• Keyboard: arrows to move, Enter to select, Escape to close, Tab to accept; mouse and touch selection.
• Mixed groups: recent searches (local), popular queries, products with thumbnails.
• Submitting the query (not a suggestion) goes to the results page.

Non-functional

• p95 time from keystroke to suggestions under ~150 ms for cached prefixes, ~300 ms otherwise.
• No more than one in-flight request per input; no stale results displayed.
• Backend load bounded: aim for well under one request per keystroke on average.
• WCAG-compliant combobox; works on low-end phones.

┌──────────────────────── Browser ─────────────────────────┐
│ <SearchBox>                                               │
│  input (role=combobox) ─ onChange ─┐                      │
│                                    ▼                      │
│  Suggestion controller                                    │
│   1. normalise query ("  iPhone " → "iphone")             │
│   2. local results now: recent searches, LRU cache hit    │
│   3. debounce 100–150 ms                                   │
│   4. abort previous request, fetch with AbortSignal        │
│   5. accept response only if query === latestQuery          │
│   6. store in LRU, render                                   │
│  listbox (role=listbox) ─ options (role=option)            │
└──────────────────┬───────────────────────────────────────┘
                   ▼ GET /suggest?q=iph&locale=en-IN  (Cache-Control: public, max-age=300)
        CDN edge cache (popular prefixes) ──▶ Suggest service ──▶ prefix index (trie / FST)

• Controller is framework-agnostic: it holds the latest query, the cache, the in-flight AbortController, and emits states (idle, loading, results, error).
• Client cache: an LRU (for example 100 entries) keyed by normalised query. A longer query can also be answered locally by filtering a cached shorter prefix when the server marked that result as complete.
• Server: a precomputed prefix index (trie or finite-state transducer) of popular queries with scores, so lookups are O(length of prefix); results for popular prefixes are cacheable at the CDN because they are not personalised. Personal suggestions (recent searches) are merged on the client.

type Suggestion =
  | { type: "query"; text: string }
  | { type: "recent"; text: string }
  | { type: "product"; id: string; title: string; imageUrl: string; price: string };

type SuggestState = {
  query: string;               // what the input shows
  latestRequested: string;     // the normalised query the UI waits for
  status: "idle" | "loading" | "results" | "error";
  items: Suggestion[];
  activeIndex: number;         // keyboard highlight, -1 for none
};

type Cache = LRU<string /* normalised query */, { items: Suggestion[]; complete: boolean; fetchedAt: number }>;

Recent searches live in localStorage (capped, de-duplicated, removable by the user); they are shown immediately on focus with an empty input.

Typing "iph"

1. i: show recent searches matching "i" instantly; start the debounce timer.
2. ip: restart the timer.
3. iph: the timer fires 120 ms after the last key; cache miss, so abort nothing (none in flight) and send GET /suggest?q=iph.
4. The user types o while it is in flight: abort it (saving bandwidth), start the timer for "ipho".
5. A response is applied only if its query equals latestRequested; otherwise it is cached but not shown.

Backspacing to "iph" hits the LRU and renders instantly with no request.

Request reduction math: with a 120 ms debounce, typical typists (5–8 keys/s) trigger requests mostly on pauses; client caching removes repeats; CDN caching absorbs the head of the distribution (a few thousand popular prefixes cover most traffic).

Trade-offs

• Fast first suggestion: preconnect to the suggest endpoint on focus; prefetch suggestions for the empty query (trending) on focus.
• Payload size: short JSON with only displayed fields; compressed; thumbnails small and lazy.
• Main thread: keep rendering cheap; highlight matches with string slicing, not innerHTML; avoid layout thrash in the dropdown.
• Slow networks: show local results immediately, a subtle loading indicator after ~300 ms, and keep showing the last results while new ones load to avoid flicker.
• Failures: on errors, keep local and cached suggestions; never block typing or form submission.
• Backend protection: minimum query length (1–2 characters), server-side rate limits per user, and CDN caching; the client respects Retry-After.
• Metrics: keystroke-to-render latency, requests per search session, cache hit rate, suggestion click-through rate, and zero-result rate.