Engineering Atlas › System Design Interviews

Design a search suggestion service

18 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional

Non-functional

Out of scope

Back-of-envelope

API

GET /v1/suggest?q=how+to+ma&locale=en-US&k=10
-> 200 {
     "prefix": "how to ma",
     "suggestions": [ {"text": "how to make pancakes"}, {"text": "how to make money"} ],
     "snapshot": "en-US/2026-10-16T09:00Z"
   }
   Cache-Control: public, max-age=300     (only for prefixes of 3 characters or fewer)

POST /v1/search-events
{ "query": "how to make pancakes", "locale": "en-US",
  "session_id": "s-81f2", "typed_prefix": "how to ma", "picked_rank": 1, "ts": 1760605200 }
-> 202

Internal RPC (suggest frontend to shard):
TopK(locale, prefix, k, snapshot) -> [ {phrase_id, score} ]

Admin:
POST /v1/blocklist { "pattern": "exact phrase or rule", "reason": "legal", "ticket": "T-1234" } -> 201

Scores stay internal because they change with every build. picked_rank in the search event lets the pipeline learn which suggestions people actually click.

Data model

The partition key for serving is (locale, prefix range). Locale comes first because rankings differ completely between en-US and pt-BR, and a locale is the natural unit to build and roll back.

High-level design

flowchart LR
  U["Client: debounce, cache"] --> CDN["CDN edge cache"]
  CDN --> FE["Suggest frontend"]
  FE --> RT["Prefix-range router"]
  RT --> S1["Shard a..f"]
  RT --> S2["Shard f..p"]
  RT --> S3["Shard p..z"]
  U -->|"completed search"| EV["Event collector"]
  EV --> K["Kafka: search-events"]
  K --> TR["Trending counters on shards"]
  K --> ARC["Object storage archive"]
  ARC --> B["Hourly batch: score, filter, build"]
  BL["Blocklist"] --> B
  BL --> FE
  B --> SN["Snapshot files and manifest"]
  SN --> S1
  SN --> S2
  SN --> S3

Read path. The client debounces about 50 ms, cancels any in-flight request and checks its own cache; on a miss the CDN answers short prefixes. The frontend normalises the prefix (lowercase, Unicode NFC, collapse spaces), finds the shards owning that prefix in the current manifest (usually one), and calls them in parallel. Each shard walks its compact trie to the prefix node, reads the stored top-k phrase IDs, merges in its trending counters, drops anything on the blocklist, and returns its best k. The frontend merges the lists, deduplicates, takes the top k and returns text.

Write path. A completed search becomes an event, validated, normalised and written to Kafka. Each shard's trending consumer updates decayed counters for phrases in its range; an archiver writes hourly files. Every hour, a batch job reads the last 30 days of aggregates plus the new hour, recomputes decayed scores, applies thresholds and the blocklist, chooses split points from traffic, builds one snapshot file per shard, and publishes a new manifest. Shards download the new files, build the in-memory structure off the request path, and swap a pointer.

Deep dives

1. The serving structure

Options: edge n-grams in an existing search cluster, a pointer trie with a top-k list per node (covered in Search and Typeahead), or a compact trie or finite state transducer built offline. Edge n-grams make every prefix an indexed term and every keystroke a scored search, costing milliseconds, not microseconds. Facebook's people typeahead worked this way at scale, with a posting list for every name prefix up to a fixed length, but it ranked by social graph, not by a global top k (Unicorn, VLDB 2013). A pointer trie wastes memory on a heap object per node and a pointer per child.

I would build a compact trie offline. Nodes are laid out breadth-first in flat arrays: a first_child index, a label byte per edge, and a topk_offset into a shared array of phrase IDs. Single-child chains are collapsed into one edge with a multi-byte label (a radix tree), which removes most nodes in natural language because phrases share long middles. Top-k lists are stored only where they help: at a node whose subtree contains more than k phrases. Below that, the subtree is small enough to enumerate at query time in a few hundred nanoseconds. Lucene's completion suggester makes a similar choice with a weighted FST, and Elasticsearch exposes it as a completion field that is costly to build and held in memory (Elasticsearch suggesters). An FST beats a trie on memory because it shares suffixes as well as prefixes: one public build packed 1.6 billion Common Crawl URLs into 27 GB, about a fifth of the sorted input (Andrew Gallant). Either way, building offline into an immutable result is what allows the compact layout.

One catch with filtering at query time: if a node stores exactly k phrases and the blocklist removes three of them, the shard can only return seven. Store a margin, say 2k, at each node so filtering still fills the list. Lucene's suggester documents the same hazard, warning that many deletions or a restrictive filter make its pruned top-N search miss results (Lucene NRTSuggester).

2. Freshness and ranking with decayed frequency

Raw 30-day counts rank "world cup schedule" above "election results" on election night. Exponential decay needs two numbers per phrase: score and updated_at. Reading at time now gives score × 2^(-(now - updated_at) / half_life). Recording a search applies the decay and adds 1. Since all scores decay by the same factor, a stored ranking stays valid until new events arrive.

I use two half-lives. The batch layer uses 7 days for durable popularity; the trending layer uses 30 minutes for spikes. The shard blends them, for example batch + 3 × trending tuned against click-through, so a new phrase can appear within 15 minutes without a rebuild.

Counting is also the attack surface. Ranking by distinct users rather than raw events, requiring a minimum number of distinct users before a phrase is eligible, and capping one session's contribution stop a script from pushing a phrase into everyone's suggestion list. Recent personal searches are merged on the client, so personalisation never pollutes shared caches.

3. Partitioning, routing and merging

Hashing the full phrase spreads load evenly but sends every prefix query to every shard, since completions of "how" are scattered. Hashing the first two characters keeps prefixes together but cannot be rebalanced: "th" and "s" are enormous, "qz" is empty. Prefix ranges, as in Bigtable's tablets, which are contiguous row ranges split as they grow (Bigtable, OSDI 2006), keep neighbours together and can be rebalanced by moving split points. Azure's sharding guidance names the price: range sharding does not balance load on its own, and rebalancing may not help when activity piles up on adjacent keys (Azure Sharding pattern). That is why the split points below follow traffic, not phrase counts.

The batch job picks split points so each shard carries a similar share of expected request traffic, not of phrases. That pushes split points deep in busy areas, such as [ca, cat) then [cat, d), so "c" spans several shards. The routing rule is simple because strings with a common prefix are contiguous in sorted order: start at the shard owning the prefix itself, then include one more shard for every split point that begins with the prefix. Multi-shard prefixes are short, and short prefixes are what the caches absorb.

Merging must deduplicate, because during a rebalance a phrase can briefly exist on both the old and the new owner, and each shard must return its own top k (not fewer) so the global top k is guaranteed to be in the union. All shards of one request use the same pinned manifest version.

Down the stack

Layer 1The contract

For a normalised prefix, return up to k phrases starting with it, ordered by blended score from one snapshot version plus trending state, excluding anything blocklisted when the request arrived. The long tail may be one build interval stale, trending a few minutes. If a shard misses its 15 ms budget, the frontend returns a partial answer, marked uncacheable, rather than an error.

Layer 2The mechanism

The compact trie is three arrays per shard: edges sorted by label within each node so a child lookup is a binary search over a few bytes, a node array of (first_edge, edge_count, topk_offset, topk_len) packed in 16 bytes, and a phrase-ID array. Lucene's equivalent, CompletionPostingsFormat (versioned per codec, Completion101PostingsFormat in Lucene 10), stores an FST per segment whose outputs carry a weight, surface form and document ID, and NRTSuggester runs a top-N search over it (Lucene NRTSuggester). The trending layer is a hash map plus a min-heap per hot prefix, updated by the Kafka consumer thread and read by request threads through a read-copy-update swap every second, so readers never take a lock. Snapshot loading verifies the SHA-256 from the manifest before swapping.

Layer 3The machine

An 8-character prefix touches about 8 nodes. In a pointer trie each is a separate heap object and likely a cache miss at 80 to 100 ns, close to 1 µs per lookup. In the flat layout, root-level nodes stay hot in L1 and L2 and breadth-first order packs siblings into one 64-byte line, so a lookup is well under 1 µs. A 12 GB snapshot is loaded with mmap, outside the garbage-collected heap; 12 GB of small heap objects could cost GC pauses of tens of milliseconds, the whole budget. The network still dominates: a mobile round trip is 50 to 150 ms and a fresh TLS 1.3 handshake adds one more (RFC 8446), so clients keep one HTTP/2 connection open while the box is focused and multiplex keystroke requests over it (RFC 9113).

Why it's built this way

  1. Users type faster than a search engine can rank, so answers per prefix must be precomputed and looked up.
  2. Precomputed answers for a billion prefixes are large, so they are built offline into a compact, immutable layout that the CPU cache likes.
  3. Immutable snapshots are stale between builds, so a small, mutable trending layer with fast decay covers the gap.
  4. The snapshot no longer fits one machine, so it is split by prefix range, because range splitting keeps one prefix's answer on one shard.
  5. Even a microsecond lookup sits behind a 100 ms mobile round trip, so caching at the client and edge saves more than any server optimisation.

Failure modes

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Compact trie or FST, offline buildSub-microsecond lookup, small memoryStale between builds, build pipeline to runLarge query-log autocomplete
Edge n-grams in a search clusterReuses existing cluster, flexible filtersLarger index, millisecond queriesProduct or entity search at moderate scale
Prefix-range shardingOne shard per typical prefix, rebalanceableShort prefixes scatter, split points to manageCorpus too big for one node
Hash shardingEven load, no split managementEvery query scatters to all shardsRarely, for autocomplete
Decayed scoreO(1) update, two numbers per phraseOne fixed half-life per scorePopularity with recency
Sliding window countsExact "last N hours" semanticsMemory per bucket, slow expiryCompliance or reporting views

Leadership lens

Check yourself

  1. Why shard by prefix range instead of hashing the full phrase or its first two characters?

    Show answer

    Hashing the full phrase sends every prefix query to every shard, and hashing the first two characters keeps prefixes together but cannot be rebalanced because "th" is enormous and "qz" is empty. Prefix ranges keep neighbours together and rebalance by moving split points, so most prefixes hit one shard.

  2. Why rank by decayed frequency rather than raw 30-day counts, and what does it cost to store?

    Show answer

    Raw counts let old fads outrank what people are searching for now, such as on election night. Exponential decay needs only score and updated_at per phrase with an O(1) update, and since all scores decay by the same factor a stored ranking stays valid until new events arrive.

  3. A build bug produces a snapshot that ranks spam first. How is the damage limited?

    Show answer

    Snapshots are validated against golden prefixes and the manifest is canaried on one replica group before rollout. If it still gets through, rollback is reverting the manifest pointer to the last good version.

  4. How does about 56k QPS average become a much smaller origin load, and why does that matter for sharding?

    Show answer

    Prefixes of one to three characters are perhaps 40% of requests and are cached at the CDN with a 5-minute TTL, cutting origin peak from about 140k to around 85k QPS. Those short prefixes are also the ones that span several shards, so caching absorbs most scatter-gather queries.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →