Design exercise: search autocomplete

Generated by Claude (Fable 5.1) by hand, Scout learning center M4a on 2026-10-12, reviewed by a second reader (Claude Fable 5.1), Scout learning center M4b on 2026-10-12.

Concept: System design and architecture · also covers Relational and non-relational data stores, Scaling, Low latency · Part C (Design exercises) of the system design module · design exercise · version 2

A classic design exercise: search-box suggestions within a 100 ms budget at tens of thousands of requests per second. The reference answer precomputes the top ten completions per prefix from an hourly, decayed aggregation of the query log, serves them from in-memory shards by first letters behind a short-TTL edge cache, re-ranks with the user's own recent queries, and treats freshness as a cost dial on the build pipeline.

Attempt the design from the prompt, the constraints and the questions before reading the reference answer.

The prompt

Design the search box suggestions for a large consumer site: as the user types, show the ten most likely completions within the time it takes to type the next character. Suggestions should reflect what people are searching for now, not last year.

Constraints and numbers

Functional

Return the top 10 completions for a prefix of 1 to 20 characters; rank by popularity with recency; exclude blocked terms; optionally re-rank by the user's own recent queries; update suggestions from the query log within an hour.

Scale (assumption)

100 million searches per day; each search session sends about 5 prefix requests, so 500 million autocomplete requests per day; peak 10x the daily average; a vocabulary of the top 10 million distinct queries worth suggesting. Chosen for the exercise; derive the request rate, the index size and the memory per shard yourself.

Targets (assumption)

p99 under 100 ms end to end at the client, which leaves about 20 ms inside the service after network time (assumption); 99.9 percent availability; the box must never block search itself.

Non-goals

Full search, spell correction beyond a fallback, query understanding, ads in suggestions.

Clarifying questions worth asking

• Are suggestions whole queries or next words? Whole queries that start with the prefix; mid-word matches are out of scope.
• How fresh is fresh? A query trending now should appear within an hour; a query that stopped being popular should fade over days, not vanish at once.
• Personalised? Lightly: the user's own recent queries are boosted among the global candidates; no per-user index.
• Case and language? Case-folded; one language per site locale, each with its own index; typo tolerance only as a fallback when the prefix has no completions.
• Is exactness of popularity counts needed? No; approximate counts with hourly refresh are fine.
• What must never be suggested? Blocked terms (a curated list), personal data that appears in queries, and anything seen fewer than a minimum number of times (assumption: 10 in the window).

Reference answer

Requirements and estimates

Derived numbers

500 million requests per day is about 5,800 per second average and 58,000 at peak. Client debouncing (wait about 100 ms after a keystroke before sending) removes most intermediate prefixes and is the single cheapest optimisation; the numbers above assume it. The index: 10 million queries of about 20 characters produce about 10 distinct prefixes each (assumption; short prefixes are shared between queries), 100 million prefixes; storing the top 10 completions per prefix as references to a query table (10 ids times 4 bytes plus the key) is about 100 bytes per prefix, so about 10 GB; as a trie with top-10 lists at every node it is of the same order. One memory lookup is 100 ns and a trie walk of 20 characters a few microseconds, so the service time is dominated by serialisation and the network, not the lookup.

Shard arithmetic

A sharded index by the first one or two characters is unbalanced: common first letters carry far more prefixes and far more traffic. 58,000 requests per second with the busiest letter at 10 percent (assumption) is 5,800 per second on one shard, which one in-memory node serves easily; the imbalance is handled with replicas per shard, not with finer sharding.

High-level design

Container view

Two halves. Serving: an edge cache keyed by prefix (the same prefixes repeat constantly, so a short TTL cache absorbs most traffic), an autocomplete service that reads a precomputed top-10 list for the prefix from an in-memory shard and optionally re-ranks it with the user's recent queries. Build: an hourly aggregation of the query log into decayed counts, filtering, and a versioned rebuild of the per-prefix top-10 lists that shards load atomically. The serving side never computes popularity; it only looks up.

flowchart TB
  subgraph Serving
    U[Clients, debounced keystrokes] --> E[Edge cache: prefix to top-10, 60 s TTL]
    E --> AS[Autocomplete service]
    AS --> SH[(Prefix index shards, in memory, by first letters)]
    AS --> PR[Personalisation re-rank]
    PR --> UH[(Recent queries per user)]
    AS -.->|no entry for the prefix| FB[Fallback suggester: term or phrase, 10 ms deadline]
  end
  subgraph Build
    QL[[query log]] --> AG[Aggregator: counts with decay, every hour]
    AG --> FL[Filter: block list, min count, dedupe]
    FL --> BU[Index builder: top-10 per prefix, versioned]
    BU --> OS[(Index versions: object storage)]
    OS -->|load and switch| SH
  end

flowchart TB
  subgraph Serving
    U[Clients, debounced keystrokes] --> E[Edge cache: prefix to top-10, 60 s TTL]
    E --> AS[Autocomplete service]
    AS --> SH[(Prefix index shards, in memory, by first letters)]
    AS --> PR[Personalisation re-rank]
    PR --> UH[(Recent queries per user)]
    AS -.->|no entry for the prefix| FB[Fallback suggester: term or phrase, 10 ms deadline]
  end
  subgraph Build
    QL[[query log]] --> AG[Aggregator: counts with decay, every hour]
    AG --> FL[Filter: block list, min count, dedupe]
    FL --> BU[Index builder: top-10 per prefix, versioned]
    BU --> OS[(Index versions: object storage)]
    OS -->|load and switch| SH
  end

Boxes are containers; the two frames are the serving and build halves; cylinders are stores; double brackets are logs; the dotted edge is the fallback path taken only when the prefix has no entry.

The data model

Entities

Query {query_id, text (case-folded), locale, score (decayed count), first_seen, blocked}. PrefixEntry {prefix, locale, top[] of (query_id, score)} capped at 10. UserRecent {user_id, queries[] of (text, time)} capped at 50 with a 30-day TTL (assumption). IndexVersion {locale, version, built_at, shard files}.

Index structures

Three ways to hold PrefixEntry, all cited for comparison. A trie: one node per character, each node carrying its top-10 list; lookup cost is proportional to the prefix length. Sorted sets with lexicographic ranges, the minimal in-memory approach antirez describes: every prefix of every query is a member, and a range query from the prefix returns completions, with a score for ranking. A completion suggester, which Elasticsearch documents as optimised for speed: data structures that give fast prefix lookups, are held in memory and are costly to build, which fits a rebuild-and-swap model (the structure underneath is a finite state transducer, FST). The answer precomputes top-10 lists per prefix into a hash map per shard (the trie's data without the trie's pointers), because the lists are small and the build is offline.

API

GET /suggest?q=prefix&locale=en&limit=10 returns {suggestions[] of (text, score)}; the response carries Cache-Control: public, max-age=60 so edge and browser caches share it. POST /blocklist is an operator endpoint. The query log is written by the search service, not by this one.

The core flow, step by step

One keystroke, and one hourly build.

1. The client waits 100 ms after the keystroke, then requests the prefix; the edge cache answers if it has seen the prefix within 60 s (for the top few thousand prefixes this is nearly always).
2. On a miss, the service hashes the prefix's first characters to a shard, reads the PrefixEntry from the shard's in-memory map (replicas chosen round robin), and gets up to 10 query ids with scores.
3. If the user is known, the service merges the user's recent queries that start with the prefix, boosting them ahead of global results; it never shows another user's queries.
4. If the prefix has no entry (a rare or misspelled prefix), the service falls back to a term or phrase suggester over the query vocabulary for a correction, bounded by a 10 ms deadline, else returns an empty list.
5. Build, every hour: the aggregator reads the last hour of the query log, adds counts to a decayed score (yesterday's count weighs half, assumption), drops queries below the minimum count or on the block list, recomputes the top 10 for every affected prefix, writes a new index version to object storage, and tells shards to load it. Shards load the new version beside the old and switch pointers, so no request sees a partial index.

Scaling and the bottleneck

Freshness versus build cost

The serving path is a cache in front of a memory lookup; it scales by replicas, and its only risk is a cold start after a deploy, which is why shards load the index from a prebuilt file rather than computing it. The real bottleneck is the build: recomputing top-10 for 100 million prefixes every hour is a batch job over the query log, parallel by prefix range, and its runtime bounds freshness. A trending query reaches suggestions within one build interval plus the edge TTL, which meets the one-hour target; a faster lane for the top few thousand trending queries (a streaming count with a five-minute window merged at serve time) is the usual next step when product asks for minutes.

Hot prefixes and replicas

Hot shards (common first letters) get more replicas than cold ones, assigned from measured traffic per shard rather than evenly; the edge cache already removes most of the skew because popular prefixes are exactly the cached ones. Discord's message search write-up is the reference for the opposite shape, sharding a search index by owning entity and indexing lazily on first use; it does not fit here because autocomplete has one global vocabulary per locale, but the lesson that index layout follows the query pattern does.

Failure modes and what degrades

Each row names the failure, what the user sees, and the mitigation.

Trade-offs and the alternative not taken

The decisions a reviewer reads first.

What changes at 10x

At 5 billion requests per day the edge cache is the system and the service is its origin; the index moves closer to users (regional replicas of the versioned files). The vocabulary grows to 100 million queries and the hourly build becomes incremental: only prefixes whose counts changed are recomputed, with a streaming lane for trending terms. Multilingual sites get an index per locale with locale-specific folding and tokenisation; mixed-script prefixes are the hard case and get a product decision rather than an engineering one. Abuse becomes a feed: coordinated query spam to plant a suggestion is countered by per-source rate limits on the log and anomaly checks in the aggregator, and the block list gets an owner.

Self-check rubric

Read, not scored: find the level your answer reached.

L1, mid-level: applies

• A prefix index served from memory with precomputed top-10 per prefix, and the request rate derived from the assumptions.
• Client debouncing and an edge cache with a short TTL in front of the service.
• A block list and a minimum count applied before anything is suggested.

L2, senior: chooses with numbers and defends

• Offline aggregation of the query log with decayed counts and a versioned, atomically swapped index.
• Prefix sharding by first letters with replicas sized to traffic, and the hot-letter arithmetic.
• Personalisation as a re-rank of global candidates, and typo tolerance as a deadline-bounded fallback.
• The latency budget split (network, serialisation, lookup) that shows why p99 under 100 ms holds.

L3, staff: sets the constraint and judges

• Freshness as a cost: the build interval, the trending lane, and when minutes are worth it.
• Abuse of the query log as a design input, with ownership of the block list.
• Multilingual and mixed-script trade-offs stated as product decisions with engineering consequences.

The 45-minute interview frame

• 0:00 to 0:05 Requirements: whole-query completions, freshness within an hour, light personalisation, case folding and locales, what must never be suggested. Say the numbers aloud: 58,000 requests per second at peak after debouncing, 100 million prefixes, about 10 GB of index, a 20 ms service budget inside a 100 ms client target.
• 0:05 to 0:10 Entities and API: Query with a decayed score, PrefixEntry with a top-10 list, UserRecent, IndexVersion; the suggest endpoint with public caching headers.
• 0:10 to 0:20 High-level design with the diagram: the serving half (edge cache, service, in-memory shards, re-rank) and the build half (log, aggregator, filter, versioned builder). Name the three index structures and why precomputed lists make the choice unimportant.
• 0:20 to 0:40 Two deep dives: the build pipeline (decay, minimum counts, block list, atomic version swap, freshness bound), then serving under skew (sharding by first letters, replicas by traffic, the edge cache removing the hot prefixes, the fallback deadline).
• 0:40 to 0:45 Failure modes from the table, the 10x plan (regional index files, incremental builds, trending lane, abuse controls), and the L3 sentence: the serving path is trivial on purpose; the design is the build pipeline and its freshness-versus-cost dial.

The design-doc frame

• Context and scope. The search product, the existing query log and its retention, the locales served, and the latency complaints or stale suggestions that motivate the work.
• Goals and non-goals. Top-10 completions under 100 ms at p99, freshness within an hour, light personalisation; no full search, no spell correction beyond a fallback, no ads.
• Design. This answer fills it: the serving path, the index layout, the hourly build with versioned swap, the fallback.
• Alternatives considered. Ranking at request time, trie versus sorted sets versus FST suggester, prefix-hash sharding, a per-user index, with the trade-off table.
• Cross-cutting concerns. Privacy (no personal data in suggestions, per-user recents with a TTL and never shared), abuse (block list ownership, log rate limits), observability (edge hit ratio, index age, empty-result rate, fallback rate), cost (memory per replica, build compute per hour), rollout by locale with the index version pinned.
• Review questions the doc must answer. How a blocked term is removed from every cache within minutes, and what the service returns when the index is older than its freshness target.

Depth notes

• L1. A prefix index served from memory with top-k per prefix.
• L2. Offline aggregation of query logs, prefix sharding, personalisation as a re-rank, p99 under 100 ms.
• L3. Freshness versus cost, abuse filtering, multilingual and typo tolerance trade-offs.

Sources

• docElasticsearch reference: Suggesters (completion suggester) (www.elastic.co)
• blogantirez: Autocomplete with Redis (oldblog.antirez.com)
• docWikipedia: Trie (en.wikipedia.org)
• blogDiscord: How Discord indexes billions of messages (discord.com)
• docLatency numbers every programmer should know (gist.github.com)
• specRFC 9111: HTTP Caching (www.rfc-editor.org)

Related lessons

• Caching sd-caching planned
• Data modelling across stores sd-data-modelling planned
• Queues, streams and delivery guarantees sd-queues-streams planned
• Replication and partitioning sd-replication-partitioning planned
• Latency, throughput and back-of-envelope numbers sd-numbers planned