Design a typeahead service

01Problem and scope

A typeahead service returns a small ranked set of completions for a partially typed query before the user submits a search. It must find and rank prefix matches quickly, limit the work each request creates, protect private history and remove blocked terms under a stated deadline. For example, prefix ca matches cap, capital, captain, caption and cat. A trie is a tree whose edges consume characters: traversing c, then a, locates the subtree containing those terms. A terminal marker distinguishes a completed term such as cap from an intermediate path.

Assume exact prefix matching ranked by popularity, with locale and optional personal history, and results displayed within 200 ms. Start with a public approved vocabulary and consistent normalization. Typo correction, arbitrary substring matching and semantic retrieval require additional candidate-generation algorithms and are excluded from the initial path.

An index snapshot is a read-only copy of the vocabulary index and its scores, built together. Build the next copy separately so queries keep reading the previous complete ranking until the replacement is ready.

The design covers trie compression, ranking, snapshots, partitioning and client behavior. The central tradeoff is moving work from every query into periodic index construction. The write and read paths use requests 12 (ca) and 13 (cap), plus a popularity event that changes snapshot 84 into 85. The client assigns a new input-generation number whenever the typed query changes. Comparing that number with each response prevents an older response from replacing newer suggestions, independently of how recently the index was built.

02Functional requirements

1. Suggest for prefix: Every returned public candidate matches the normalized prefix and locale.
2. Type another character: Older responses cannot replace suggestions for newer input.
3. Submit/select search: Emit an identifiable popularity event under the logging policy.
4. Rebuild rankings: One query observes a coherent approved index version.
5. Remove blocked terms: A separate policy filter removes blocked terms within its stated bound.
6. Use private history: Only the authenticated user's data affects their private response.

Matching and normalization

Return at most ten approved matching terms, with stable display strings and deterministic score/ID tie-breaking. Indexing and requests use the same normalization version: Unicode normalization resolves defined equivalent sequences, and an explicit locale-aware case policy handles case-insensitive matching. Preserve original display spelling. A case-folding rule is not automatically correct for every language, and visually similar characters are not necessarily equivalent.

Input bounds, freshness and private history

Empty or too-short prefixes follow a documented policy, initially requiring two characters. Long prefixes and result limits are bounded to control abuse. The service may return fewer than ten results after policy filtering; filling the list must not trigger an unbounded subtree scan. Normal popularity freshness may be hourly, while urgent safety removal is faster. Personal history may rerank eligible candidates but does not automatically outrank all public suggestions, and private suggestions never enter a shared public response cache.

03Non-functional requirements

1. Latency: End-to-end suggestion p95 below 200 ms: 50 ms waiting for a pause in typing (client debounce), up to 80 ms network allowance, roughly 50 ms service work, plus reserve. These illustrative budgets vary by geography.
2. Availability: 99.95% eligible suggestion availability. A missing suggestion box must not prevent submitting a search.
3. Popularity freshness: Use hourly ranking snapshots; recent popularity may lag by roughly a build/distribution interval, which is measured and exposed operationally.
4. Urgent removal: Blocked terms stop being served within 60 seconds. The policy service issues versioned blocklists with absolute expiry times, called freshness leases. Servers and clients stop displaying suggestions when the lease expires; its duration reserves time for measured clock and transport uncertainty.
5. Zone resilience: Serving replicas tolerate one node or zone failure when spare capacity exists.
6. Regional recovery: Back up durable vocabulary, aggregate inputs and approved snapshots; specify a separate restore/reroute target for a full-region outage.

Version, privacy and fail-closed rules

The main ranking index may remain older while fresh policy filtering enforces removals. A policy outage therefore has different consequences from a ranking-build outage. The in-memory trie is rebuildable, but recovery depends on snapshot size, load bandwidth and validation—not merely starting a process.

04Capacity estimates

Workload assumptions and arithmetic

Assume five billion submitted searches/day: 5B / 86,400 = 57,870 searches/s. If each submission produces four suggestion requests after client debounce and cancellation, average serving load is 231,481/s; fivefold peak is about 1.16 million/s. The submitted-search rate alone therefore understates autocomplete traffic when each search produces several suggestion calls.

Count the vocabulary and the lookup structure separately. The vocabulary stores each complete term; trie nodes represent prefixes and may store precomputed shortlists for faster queries. A top-k shortlist contains the k highest-ranked candidates, so increasing either the number of prefix nodes or k increases its memory cost.

One hundred million distinct terms averaging 30 encoded bytes use 3 GB of strings. That is not the in-memory index size. Suppose a measured representative construction extrapolates to 300 million nodes and each node retains ten 8-byte term-ID/score references. Shortlists alone use 300M × 10 × 8 = 24 GB, before transitions, node headers, strings and allocator overhead. A compressed trie reduces single-child chains, while compact arrays/finite-state representations can avoid pointer overhead.

Worked estimates

Capacity implications and limits

An estimate of 24.9 GB after one year assumes linear growth of 2% of the original 3 GB each day: 3 GB + 365 × 0.02 × 3 GB = 24.9 GB. If ‘2% daily growth’ means compounding on the current size, it is instead 3 GB × 1.02^365 ≈ 4.13 TB. These are very different assumptions; state which population changes and whether retention removes old terms. Real unique-term retention and churn determine growth; neither total events nor sampled events directly determines distinct vocabulary size. Benchmark node count and load-time peak memory before saying the index “fits on one server.”

05APIs and contracts

Request and response example

The user requests GET /v1/suggest?prefix=ca&locale=en-US&limit=10&requestSeq=12. The response includes requestSeq:12, normalizedPrefix:"ca", indexVersion:84, policyVersion:9 and a list of {termId,displayText}. Scores may be internal; exposing them is not necessary for the user. The next input issues sequence 13 for cap, and only a response matching the current input generation may update the UI.

Interface contracts

Validation and response semantics

An event e91 might record the user selecting term t17=capital; ingestion deduplicates e91 within the defined event-retention window. A suggestion impression and an actual search submission are different signals. Logging every prefix as a successful search would bias popularity toward partial strings. Reject oversized/malformed queries with 400, bound result count, and rate-limit abusive traffic. A serving overload can return an empty suggestion set or explicit retryable status while the search box continues to work; that fallback must not appear as a completed search response.

06Data model and access patterns

The durable records supply vocabulary, popularity evidence and published index versions. Term preserves a term's identity and display form; CountBucket groups its observed events by time; Snapshot records which built artifact serving nodes should load. The in-memory trie is generated from these records rather than being the only recoverable copy of them.

Each trie node stores transitions, an optional terminal term identity and a bounded ordered list of term IDs/scores. Store display text once in the term table rather than at every prefix node.

For the sample, cap is a terminal and a parent of capital, captain and caption. A compressed edge may consume a whole substring when intermediate nodes have only one child. The lookup must handle a query ending in the middle of such an edge; its candidate set is still the terms under that compressed subtree if the consumed characters match. Compression saves topology bytes without changing prefix semantics.

Persist arrays with stable offsets or IDs, not raw process pointers. A breadth-first encoding containing edge labels and child counts can reconstruct topology; top-k IDs/counts must be serialized explicitly or recomputed bottom-up. Keep score definition, locale and normalization version in the artifact so serving code cannot mix incompatible assumptions. Private UserHistory(userId,termId,lastUsed,weight) is stored separately and accessed only after authentication. Query-result cache keys include normalized prefix, locale, index/ranking version and public policy scope; private reranked results are not stored under that shared key.

07Basic working design

Small trie lookup

Build the small trie in memory from a durable vocabulary file. When the user asks for ca, traverse the two edges, enumerate descendant terminal terms, read their popularity counts, sort by score and return up to ten. For five words this is easy to test by hand. Suppose counts are cat 900, capital 700, captain 500, caption 400 and cap 100; that is the returned ordering under one deterministic score policy.

Indexed database alternative

A simple database prefix range query with a suitable index could also be a valid small baseline. Choose a specialized in-memory index when measurements show a latency or throughput benefit over that database baseline for the expected workload. The vocabulary and counts remain durable outside the serving process so a crash can rebuild them.

Debounce and input-generation checks

On the client, a 50 ms quiet period debounces typing, and a new input cancels the previous request where possible. Cancellation is an efficiency hint, not a correctness guarantee: the server or network may already have completed the old response. The client compares requestSeq with its latest input before rendering. This baseline therefore teaches both index semantics and interaction semantics before adding snapshots, distributed shards or personalized ranking.

08Find the baseline flaws

09Improve the design, step by step

1. Store bounded top-k candidates at prefix nodes. The trigger is unbounded descendant enumeration. Build each node's best terms from its own terminal and its children's best lists, then return the stored shortlist after prefix traversal. Query work becomes approximately prefix length plus returned candidates. The cost is substantial memory and update work; a scan remains simpler for tiny vocabularies or rarely queried branches. Store IDs/scores rather than full repeated strings.

2. Build immutable ranked snapshots from aggregated events. When score updates make queries wait, aggregate events and build validated snapshots hourly or at another chosen interval. Each query keeps using one read-only version while the next is built. Queries take more predictable time, and a failed rollout can return to the old version. The costs are delayed rankings, retained events and twice the memory during replacement. Incremental live mutation is an alternative when very fresh scores justify more complex synchronization; a small bounded overlay can cover urgent trends without rebuilding everything.

3. Partition by measured prefix ranges and replicate hot ranges. Memory/throughput triggers variable-size lexical subtrees rather than one equal shard per letter. The router records which ranges intersect a prefix, and an aggregator merges shard results. This spreads distinct data but adds cross-shard work for short prefixes and rollout coordination. Hashing complete terms balances storage while forcing broad prefix fanout; choose it only with an additional index or acceptable all-shard query cost.

4. Separate policy filtering and private reranking from public caching. After retrieving public candidates, add only the authenticated user’s private history and rank the combined list using the chosen scoring rule. Check every result against the current blocklist so blocked terms disappear without waiting for a snapshot rebuild. Keep private results out of shared caches. The costs are a fresh-policy dependency and possibly fewer than ten results. A purely global public service is simpler if personalization has little measured value.

Client connection reuse, bounded prefetching and recent local caching reduce perceived latency, but they must preserve the same policy and input-generation rules.

10Detailed architecture

Bounded online suggestion path

The online path has an edge/API, prefix router/aggregator, replicated read-only index shards, a public candidate cache, a current policy filter and optional authenticated history reranker. The router fixes one snapshot version for the request and chooses its shard ranges for the normalized prefix. Shards return short candidate lists. The aggregator combines them, removes duplicates, adds the authenticated user’s private history and reranks. The policy filter then removes blocked terms from that complete list. Cache only public candidates in the shared cache.

Offline scoring and snapshot construction

The offline path ingests submitted-search/selection events into a durable log, aggregates score buckets, and builds snapshots from approved vocabulary plus counts. A validator checks checksums, schema, representative prefix answers, ranking quality and memory size. Approved artifacts are stored durably and distributed to serving replicas. A control manifest advertises a version only after the necessary shard replicas have loaded and passed readiness checks.

Version-coherent rollout

Shards hold both old and new versions during a bounded transition or use replacement hosts when memory is insufficient. A request for version 84 cannot be silently routed to a shard that serves only incompatible 85 data. Health-aware routing removes unready replicas and preserves spare capacity for a hot range. Snapshots and policy have separate revision timelines: a main index can be hours old while urgent blocked-term filtering remains fresh.

Strongest consistency boundaries

Most requests read a prepared index rather than update a database. Each query must use compatible index data, obey the policy expiry and keep private history private. Popularity scores may be older because hourly refresh is acceptable here.

11Write path and acknowledgement

The write path turns submitted-search events into a validated serving artifact; it does not mutate the query index on every keystroke. Event e91 increments the score input for term t17 (capital) and contributes to snapshot 85.

Popularity needs a time policy as well as an event count. A sliding window stops counting an event when it leaves the window; exponential decay reduces older events' weight gradually. Either can make a formerly popular term's score fall, which is why the builder must retain enough candidates to recompute the shortlist.

1. The user selects capital. The client emits event e91 with term t17, locale and the declared event type. Before saving the event durably, ingestion checks its identity for repeats, limits retained personal data and applies abuse controls.
2. Aggregation updates the appropriate term/time bucket. If aggregation increments a count and crashes before saving progress, retrying would count the same event twice. Save the count and processed-event identity or log position in one transaction, or recompute the bucket from the same fixed log range on every retry. A sliding ten-day window sums its included buckets and subtracts the expired bucket; an exponentially decayed score instead applies a decay rule. Choose one definition rather than treating the formulas as interchangeable.
3. The builder reads a consistent vocabulary/count cutoff, updates terminal scores and recomputes affected ancestor shortlists. A full bottom-up rebuild is simpler to validate; incremental work still needs enough information to recover candidates after score decreases.
4. It writes immutable snapshot 85 with topology, term table, shortlist arrays, schema/normalization version and checksums. An incomplete artifact has no approved serving pointer.
5. Validation compares known queries, held-out quality metrics and prohibited-term handling, then stages 85 onto replicas. Nodes verify checksums and load memory before reporting ready.
6. The control plane makes 85 available for new request routing only when every required range has adequate ready replicas. Existing version-84 requests finish against their pinned data.
7. After a rollback/grace interval and no active readers, retire 84. If build or loading fails, continue serving 84 with current policy rather than publishing a half-indexed 85.

Sampling events is optional, but one-in-a-thousand sampling gives noisy rare-term estimates. It does not guarantee that every term searched a thousand times is represented, nor divide vocabulary size by exactly a thousand.

12Read and delivery path

A suggestion request must use one compatible index version and remain associated with the latest browser input. The bounded example sends sequence 12 for ca, then sequence 13 for cap.

1. The user types ca. After the chosen debounce, the browser sends requestSeq 12 and normalized locale information. Connection reuse avoids paying a new handshake for each keystroke.
2. The API validates raw-input limits, pins index manifest 84, then normalizes with that manifest’s normalization version. It must not normalize under a new policy and then query an older incompatible snapshot. A public candidate cache lookup uses (ca,en-US,84,rankingVersion).
3. On a miss, the prefix router finds all intersecting ranges. Shards traverse their compressed index and return bounded best IDs/scores. The aggregator merges using the same score and tie-breaker and stores only public candidates in the shared cache.
4. If the user opted into private history, fetch only user-scoped candidates matching the same normalized prefix and locale, merge them with public candidates and rerank the bounded union. A private-history source is not exempt from blocked-term policy.
5. Apply the current allowed-term filter to that final union, after every candidate source. If its freshness lease is invalid, return no suggestions or an explicit temporary-unavailable result. Return up to ten allowed display strings with requestSeq 12 and version metadata; never refill the list afterward from an unfiltered source.
6. The user has already typed cap and sent requestSeq 13. Even if 12 arrives later, the browser discards it because it no longer matches the latest input generation. Canceling 12 alone would not prove this behavior.
7. Render accepted suggestions as text, with safe highlighting boundaries. Submission of the actual search remains functional even if suggestions fail.

13Correctness deep dive

Why child top-k lists are sufficient

Score decrease exposes a missing candidate

Consider k=2 under cap: capital=700, captain=500, caption=400, cap=100. Store capital/captain. When capital falls to 50 after window expiration, retaining only its old top-two pair would miss caption. Recompute from child lists/counts to obtain captain/caption. The full subtree counts remain available in the build inputs; the serving shortlist is not the only record of candidates.

build(node):
    candidates = [node.terminal] if node.has_terminal else []
    for child in node.children:
        candidates += build(child).topK
    node.topK = bestK(unique(candidates), score_then_id)
    return node

Pin before swapping local versions

During replacement, reader R pins snapshot 84, then loader L finishes and validates 85. L atomically changes the active pointer for new requests. R continues with 84 until it finishes; memory for 84 is freed only after all pinned readers release it. A pointer swap followed by immediate free would cause use-after-free despite an apparently atomic update.

Pin one manifest across shards

14Failure and recovery

15Operations, security, and cost

Latency, version and policy signals

Measure end-to-end p95/p99, normalized prefix length, shard fanout count, cache hit ratio, empty-result rate, query cancellation rate and stale-response discard rate. Monitor snapshot age, build duration, load-time peak RAM, readiness failures and policy age/blocked-term leakage. Quality evaluation uses test prefixes kept separate from ranking development (held-out prefixes) and user engagement metrics with safeguards against rewarding misleading or harmful suggestions. A low-latency trie returning irrelevant terms is not a successful product.

Top-k memory and rollout cost

Memory/cost decisions can be expressed in units. Precomputing ten 8-byte references at 300 million nodes costs 24 GB; increasing to twenty candidates for better policy/personalization recall adds another 24 GB before copies. At three replicas and simultaneous old/new snapshots, those shortlist arrays alone could occupy 144 GB for k=10 or 288 GB for k=20. Larger candidate pools may improve filtered results, but they are not free. Compare this with measured latency from on-demand deeper expansion.

Prefix privacy and private history

Prefixes can contain names, secrets or pasted identifiers. Minimize raw logging, restrict access, use retention limits, and keep private history separate with deletion propagation. Do not place personal suggestions in public CDN keys. Render display strings safely and normalize consistently to avoid policy bypass through alternate code-point forms; normalization is not a complete anti-confusable solution.

Normalization rollout and edge-case tests

Roll out normalization changes as new incompatible index versions with shadow queries and explicit client/server compatibility. Test score decreases, terminal-prefix terms, compressed-edge midpoints, cross-shard top-k merging, delayed request 12, corrupt snapshots and blocked-term removal during cache hits. Recovery tests should include load time under node failure, not merely whether the artifact can be parsed offline.

16Decision ledger and limitations

The lookup strategy determines both memory use and which machines a query must contact. Lexical range partitioning groups terms by their ordering, helping route a prefix to relevant ranges; hashing complete terms scatters them more evenly but loses that prefix locality. Compare these placement choices separately from how candidates are ranked and refreshed.

Equal first-letter partitioning is easy to explain but uneven in both vocabulary size and traffic. Capacity-based half-open ranges such as [a,aabd) and [aabd,bxb) adapt memory without leaving gaps: the lower boundary is included and the upper boundary is excluded. Prefix a intersects both ranges and needs aggregation. The server-side aggregator provides one stable API and policy boundary; making clients merge shards exposes topology and duplicates logic.

Personal history, locale, freshness and location can improve relevance under a defined policy. They should not automatically outrank every global candidate, and public global top ten is not guaranteed to contain a user's best personal term. Use a separate bounded personal candidate source or a larger approved pool and measure recall. Sampling and exponential decay are distinct engineering choices, not shortcuts that preserve every exact count. The index may be served by a specialized completion engine rather than handwritten trie nodes, but its memory and update guarantees still require measurement.

Elasticsearch’s completion suggester is one concrete alternative to a hand-built trie: it uses an in-memory completion structure and supports weighted inputs. Its own analysis, refresh, shard coordination and memory behavior must be measured; it does not automatically implement this chapter’s immutable snapshot rollout, private-history isolation or 60-second policy lease. A suitable indexed SQL prefix query remains reasonable for a smaller approved vocabulary. Choose the simplest implementation that meets the measured prefix latency and update budget.

17Interview closing

“I began with a five-word trie: follow the prefix, enumerate descendants and sort. At our assumed four suggestion requests per submitted search, traffic reaches about 231,000 average requests per second, so scanning broad subtrees is too expensive. I precompute bounded candidate IDs at prefix nodes and build immutable ranked snapshots from aggregated events. The three-gigabyte string corpus is only one part of a much larger index, especially during version swaps.

“The user's request pins one snapshot and locale policy, merges relevant shard candidates and authorized private history, then applies a fresh removal filter to the final union. The browser discards responses that do not match the latest input generation. Snapshot publication is atomic for new readers while old readers retain their version, and shard routing does not mix incompatible snapshots.

“I accept hourly popularity freshness for predictable serving latency, with a separate sixty-second urgent-removal contract. My next measurements are load-time peak memory, hot-prefix fanout and suggestion quality on held-out inputs.”

If the interviewer adds typo tolerance, clarify edit distance, language and latency limits. Add a bounded fuzzy candidate generator or a completion engine with that capability, then evaluate quality and additional work. A plain prefix trie does not acquire semantic or spelling correction merely by adding more replicas.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.