Design: search autocomplete

The prompt

"Design search autocomplete" (Google's search box, a shop's search bar) is mostly a data pipeline question. The serving path is a lookup; the real design is how suggestions are counted, ranked, filtered and shipped to the servers that answer.

1. Requirements

Functional: return the top 5 suggestions for a prefix, ranked by popularity; reflect trending searches within minutes; never suggest offensive or private queries.

Non-functional: under 100 ms end to end, so a few milliseconds at the server; very high availability (a broken autocomplete is noticed immediately, though search still works without it).

2. Estimates

• Requests: 10 million × 5 searches × about 6 requests per search after debouncing ≈ 300 million a day, about 3,500 a second and 15,000 at peak. Several times the search traffic itself.
• Table size: suppose 10 million distinct queries clear the popularity threshold. Prefixes up to 10 characters, heavily shared, come to perhaps 50 million; × 5 suggestions × about 30 bytes ≈ 7.5 GB. That fits in memory on each serving node.
• Logs: 50 million searches a day is a few GB a day: an ordinary batch job.

3. Entities and API

SearchLog    { query, user_id_hash, at, country }               raw, kept 30 days (14.11)
QueryScore   { query, score }                                    rebuilt weekly with decay
PrefixTable  { prefix → [(query, score)] × 5 }                   versioned snapshot

GET /suggest?q=su&locale=en-GB        →  200 ["summer sale", "summer shoes", ...]   Cache-Control: max-age=300

4. High-level design

5. Deep dives

export function buildPrefixTable(counts: Map<string, number>, k = 5, maxPrefix = 10) {
  const table = new Map<string, [string, number][]>();
  for (const [query, n] of counts) {
    for (let len = 1; len <= Math.min(query.length, maxPrefix); len++) {
      const prefix = query.slice(0, len);
      const top = table.get(prefix) ?? [];
      top.push([query, n]);
      top.sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
      if (top.length > k) top.pop();
      table.set(prefix, top);
    }
  }
  return table; // written to a snapshot: prefix -> top k
}

/** Blend this week into the running score so old spikes fade: halve the past every week. */
export function decay(previous: Map<string, number>, thisWeek: Map<string, number>, keep = 0.5) {
  const out = new Map<string, number>();
  for (const [q, n] of previous) out.set(q, n * keep);
  for (const [q, n] of thisWeek) out.set(q, (out.get(q) ?? 0) + n);
  return out;
}

Tested with six queries over three weeks, k = 3. In week 1, su suggested "super bowl" (2,000), "summer sale" and "summer shoes". In week 2, "super bowl" fell to 30 searches; its decayed score of 1,030 dropped it below "summer sale" (1,400). By week 3, "sun cream", rising from 120 to 500 searches a week, had overtaken it as well: su showed "summer sale", "sun cream", "summer shoes". The six queries produced 42 prefix entries.

Filtering. Before a query enters the table: drop anything on a blocklist (offensive, defamatory, or names a creator has asked to remove), and drop queries searched by fewer than, say, 50 distinct users, so nothing someone typed privately (a phone number, a name) is ever suggested to others. These are rules in the build, run before anything is served.

The client. Debounce about 100 ms, cancel requests for stale prefixes, cache by prefix in the browser, and filter already-fetched suggestions locally as the user keeps typing (10.06 Autocomplete). With a few minutes of caching at the CDN, most one- and two-letter prefixes never reach the servers.

6. Wrap-up

What breaks first: build time and memory as distinct queries grow, handled by the popularity threshold and by limiting prefixes to 10 characters; then regional differences, handled by building one table per locale.

Recap

Interview questions