Engineering Atlas › System Design Interviews

Building search and typeahead

13 min read · last reviewed 2026-10-17

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

In one minute

How it works

When the pattern shows up in interviews

"Search tweets by keyword", "search products with filters", "find users by name", "search Slack messages", "Google-style autocomplete", and "Design Yelp" (text plus location). The interviewer wants to hear why LIKE '%term%' on the primary database does not scale, what the index looks like, how it is sharded, how fresh it is, and for typeahead, how suggestions are ranked and served within a keystroke budget.

The inverted index

At index time, an analyzer turns text into terms: tokenize, lowercase, remove or keep stop words, and optionally stem ("running" to "run") or add synonyms. For each term the index keeps a postings list: the sorted IDs of documents containing it, often with term frequency and positions for phrase queries. A query for red shoes looks up both postings lists, intersects them (for AND) by walking both in order, and scores each match. BM25 scores a document higher when the query terms are frequent in it, rare across the corpus, and the document is not unusually long (Manning, Raghavan and Schütze, 11.4.3). Production ranking blends this text score with signals such as popularity, recency, personalisation or a learned model, often as a second-stage re-rank on the top few hundred hits.

Segments, refresh and merges

Updating a compressed, sorted postings list in place for every new document would be ruinous, so Lucene buffers new documents in memory and periodically writes them out as a new, immutable segment: a self-contained mini-index. A search consults all segments and merges results. Deletes and updates mark the old document as deleted in a bitmap; the space is reclaimed when a background merge combines small segments into larger ones. Making buffered documents visible is a refresh, every second by default in Elasticsearch (five seconds on its Serverless offering), which is why it is called near-real-time. One catch: a shard that has seen no search for 30 seconds is "search idle" and skips background refreshes until the next search arrives, which then waits for one, unless you set the interval explicitly (Elasticsearch docs).

Sharding and scatter-gather

A large corpus is sharded by document (hash of ID, or by tenant). A query goes to every shard, each returns its local top k, and a coordinator merges them. Writes stay local, but every query touches every shard, so the slowest shard sets tail latency. Replicas add read capacity. Term-partitioned sharding is rare because multi-term queries must then join across machines. Waiting on the slowest of many machines is the general "tail at scale" problem: rare slow responses come to dominate as fan-out grows (Dean and Barroso). Shard size has a hard ceiling too: a Lucene index tops out at about 2 billion documents, after which indexing simply fails, which is one reason Discord moved to many smaller indexes capped at 200 million messages (Discord).

Typeahead

Typeahead suggests whole queries, not documents. Mine the query logs for completed searches, count them over a window (with decay so last week matters more than last year), filter out unsafe or low-quality phrases, and build a trie in which every node stores its precomputed top k completions. A lookup walks the prefix (a few characters) and returns the stored list: no traversal of the subtree at query time. Rebuild offline (hourly or daily) and swap atomically; layer a small real-time "trending" index on top if freshness matters. Storing top k in every node fixes k in advance and costs space that grows with k; compressed trie variants keep only scores and still return a completion in about a microsecond, at close to gzip size (Hsu and Ottaviano, WWW 2013). Elasticsearch offers the same idea as the completion suggester, whose finite-state structure is entirely heap resident (Elasticsearch docs), or as edge n-gram fields that index every prefix of each word.

Shaving the keystroke budget

Debounce on the client, cancel in-flight requests as the user keeps typing, and cache responses in the browser and at the CDN for short, popular prefixes. Merge personalisation (recent searches) on the client from a small per-user list.

Down the stack

Layer 1The contract

Search returns the top k documents by a defined ranking for a query over the indexed snapshot, which lags the source of truth by the pipeline delay plus the refresh interval. Results are not strongly consistent: two shards may be at slightly different points, and replicas can differ until they refresh. Typeahead returns up to k suggestions for a prefix, ranked by a popularity score as of the last build, with a latency target small enough to keep up with typing, typically well under 100 ms end to end.

Layer 2The mechanism

A Lucene segment stores a term dictionary (terms sorted, with an FST-based terms index that maps prefixes to blocks on disk), postings (doc IDs delta-encoded and bit-packed in fixed-size blocks, with skip data so intersection can jump ahead), positions for phrases, stored fields (the original document, compressed), and doc values (column-oriented values used for sorting and aggregations). A .liv file holds the live-docs bitmap for deletions. Durability between Lucene commits comes from Elasticsearch's translog, which records each operation and by default is fsynced on the primary and every replica before the write is acknowledged; the async setting fsyncs every 5 seconds instead and can lose writes acknowledged in that window (Elasticsearch docs). BM25's free parameters default to k1 = 1.2 (term frequency saturation) and b = 0.75 (length normalisation) (Elasticsearch docs). The tiered merge policy groups segments of similar size and merges them to keep the count per shard bounded. For typeahead, a trie node holds child pointers and a top-k array; inserting a term with new weight updates the top-k array of every node on its path, which is O(length times k).

Layer 3The machine

Lucene opens segment files with mmap, so postings and term blocks are read through the OS page cache; a hot index whose working set fits in RAM serves queries at memory speed, while cold reads cost an SSD random read of roughly 100 microseconds each. This is why Elastic tells you to give the JVM heap no more than half of a node's memory, and to stay under the compressed-pointer limit (about 26 GB is safe), leaving the rest to the page cache (Elasticsearch docs). Bit-packed postings let the CPU decode many document IDs per instruction with good cache-line locality. Merges are sequential I/O that compete with queries, so they are throttled. For typeahead, the whole trie lives in process memory, and the request cost is dominated by the network: a round trip from a phone over mobile networks can be 50 to 100 ms, so caching at the edge and in the browser often matters more than server time.

Why it's built this way

  1. Scanning all text per query is linear in the corpus, so invert it once at index time and look up terms.
  2. Sorted, compressed postings are expensive to edit, so write immutable segments and merge later.
  3. Writing a segment per document would create millions of tiny files, so buffer and refresh periodically, accepting a freshness lag.
  4. One machine cannot hold or serve the whole index, so shard by document and scatter-gather, which makes tail latency the slowest shard's latency.
  5. Keystrokes arrive faster than any search can rank, so typeahead precomputes per-prefix answers and pushes them close to the user.

Diagram

flowchart LR
    U["User types 'iph'"] --> C["Browser cache / debounce"]
    C --> E["CDN edge cache"]
    E --> TS["Typeahead service (in-memory trie)"]
    TS --> R["top-k for prefix"]
    LOG["Query logs"] --> AGG["Batch counts with decay"]
    AGG --> B["Build trie with top-k per node"]
    B -->|"atomic swap"| TS
    Q["Full query 'iphone case'"] --> CO["Search coordinator"]
    CO --> S1["Shard 1: segments"]
    CO --> S2["Shard 2: segments"]
    S1 --> CO
    S2 --> CO

Worked example

An online store wants autocomplete for 40 million daily users. Each search averages about 6 keystrokes after debounce, and with roughly 1.5 searches per user per day that is around 360 million suggestion requests per day, about 4,000 per second on average and perhaps 15,000 at peak.

The query logs contain about 8 million distinct queries over 30 days. After dropping those seen fewer than 5 times and filtering unsafe terms, 2 million remain, averaging 18 characters. A trie of that size has on the order of tens of millions of nodes; storing a top-10 list of 4-byte phrase IDs per node plus child pointers lands in the low single-digit gigabytes, which fits comfortably in memory on one server. The team runs 12 replicas across regions for capacity and locality rather than for size.

The CDN caches prefixes of up to 3 characters for 5 minutes; there are only tens of thousands of them and they carry a large share of requests. Server lookup takes well under a millisecond; users see 30 to 80 ms, almost all network. The trie is rebuilt hourly from a streaming count with a 7-day half-life, so "black friday deals" climbs within an hour of the campaign starting.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
LIKE / database full-textNo new systemPoor ranking, scans or limited index, loads primarySmall data, admin tools
Elasticsearch / OpenSearchRich queries, ranking, facets, matureCluster ops, eventual consistency, memory hungryProduct search, logs, most text search
Trie with precomputed top-kSub-millisecond lookups, simple to cacheOffline build, memory per node, stale between buildsQuery autocomplete
Edge n-gram indexUses existing search cluster, matches mid-phrase wordsIndex size grows a lot, slower than a trieModerate scale, word-prefix matching

Pitfalls in production

Leadership lens

Check yourself

  1. Why are new documents in Elasticsearch not visible immediately after indexing?

    Show answer

    They sit in an in-memory buffer until a refresh writes a new segment and opens it for search, which happens on an interval rather than per document.

  2. Why does each trie node store its own top-k list rather than computing it at query time?

    Show answer

    Computing it would traverse the whole subtree under a short prefix, which can hold millions of phrases; storing it makes lookup proportional to the prefix length.

  3. What limits tail latency in a document-sharded search cluster?

    Show answer

    Each query waits for every shard, so the slowest shard (GC pause, merge, cold cache) sets the response time.

  4. What does BM25's length normalisation protect against?

    Show answer

    Long documents matching terms simply because they contain many words; it discounts term frequency in documents longer than average.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

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