Design typeahead suggestions

01Functional requirements

A typeahead service suggests complete queries while someone types. The prefix is the text already entered: for ca, possible completions include car and camera.

1. FR1: Prefix suggestions. Return up to ten completions matching the submitted prefix and language. Normalize stored terms and queries in the same way, such as applying the same case and Unicode rules, so equivalent text matches consistently. A popular term that does not match the prefix is not a valid completion.

2. FR2: Popularity ranking. Order matching terms by recent completed-search popularity within the requested language. Use a declared popularity window rather than assuming lifetime counts represent current interest.

3. FR3: Phrase suppression. Remove disallowed phrases from every returned list, including lists obtained from a cache or an older popularity index.

4. FR4: Completed-search collection. Accept completed-search events so future rankings can improve. Count a repeated event ID only once, and apply authentication or abuse controls. Recording a private query does not automatically authorize publishing it as a suggestion.

Out of scope

• The search-results page and document retrieval.
• Personal recommendations and spelling correction. Explain their additional inputs and integration if asked; prefix matching alone supplies neither.

Example. Completed-search counts are car:50, cat:30, camera:20, cart:10, and dog:40. For ca, the first three suggestions are car, cat, camera. dog fails the prefix requirement even though it is popular.

02Nonfunctional requirements

These are independently chosen exercise assumptions to validate, not measured production guarantees.

1. NFR1: Lookup latency. At least 95% of measured requests must finish within 100 ms, from service receipt to completed response; this is the p95 latency target. The client can also wait briefly for a typing pause before sending a request, a technique called debouncing. Measure that extra wait separately because the user experiences it too.

2. NFR2: Peak lookup capacity. Plan for about 2,310 prefix requests/second at the assumed peak derived below. Load-test by locale and prefix length, since hot one-character prefixes can be slower than the overall average.

3. NFR3: Popularity freshness. Ordinary completed searches must affect the suggested ranking within one minute. Measure from saving the completed-search event to serving a validated index build containing its updated count.

4. NFR4: Suppression correctness. Once current policy blocks a phrase, no returned list may include it. Check that policy after retrieving candidates, including cached candidates. If the check is unavailable, omit unchecked suggestions rather than reuse an older allowed list.

5. NFR5: Version-swap memory. For a measured 500 MB index, budget at least 1 GB per replica for overlapping old and new versions, plus process and cache overhead. Measure peak memory during validation and installation, not only steady-state index size.

03Back-of-the-envelope Estimates

Estimate the two kinds of work separately: the browser asks for suggestions while typing, but popularity changes only when someone completes a search. All sizes below use decimal bytes.

1. Suggestion requests. Assume one million daily users, four completed searches each and five suggestion calls per search. 1,000,000 × 4 × 5 = 20 million calls/day. Divide by 86,400 to get about 231 calls/second; assume a tenfold peak of 2,310/second. Test the suggestion handler at that rate before deciding how many copies to run.
2. Response bytes. Ten suggestions at 40 bytes each make about 400 bytes per list. 20 million × 400 = 8 GB/day, before JSON and protocol overhead. The service needs fast small lookups rather than a large-file delivery system.
3. Term text. At 500,000 terms averaging 30 bytes, text alone uses 500,000 × 30 = 15 MB. If a term contributes to at most 20 prefixes, there are at most ten million prefix contributions. Shared prefixes reduce the number of distinct trie nodes. Candidate IDs, scores and pointers can cost more than the text; measure the whole structure, including the proposed 20 candidates at 16 bytes each per distinct prefix.
4. Installing an index. Suppose the measured structure is 500 MB. A server holding the old and new copy during replacement needs at least 500 + 500 = 1,000 MB, or 1 GB, before process, cache and loading buffers. Measure that peak, not only steady-state memory.
5. Popularity updates. Four million completed searches/day are about 4,000,000 ÷ 86,400 ≈ 46 events/second. Count each completed search once. Counting the five typing requests as five searches would change the meaning of popularity.

04API Design and Retry Contracts

The browser’s suggestion code sends the text currently in its input box. The server’s suggestion handler returns possible completions; it does not run the final document search.

GET /suggest?q=ca&locale=en&limit=3

{"prefix":"ca","indexVersion":42,"suggestions":[{"term":"car","score":50},{"term":"cat","score":30},{"term":"camera","score":20}]}

1. Read the inputs. The handler reads q, locale and limit. Here ca is the typed prefix, en chooses English and 3 is the requested result count. Apply the same case and Unicode rules used to store terms.
2. Return a recognizable answer. Return 200 with matching terms, including an empty list when nothing matches. Echo ca so the browser can recognize a reply to an older input. indexVersion:42 identifies the installed index build; it is not a permission decision.
3. Reject invalid or excessive work. Return 400 for an invalid limit and 429 for throttled callers. Cap prefix length and result count so one call cannot demand an unlimited search.
4. Collect completed searches separately. After a user actually searches, the completed-search endpoint receives an event ID, normalized term, language and time. The client keeps the same event ID if it retries after losing the reply. The collector authenticates or applies abuse controls. A private query is not automatically safe to publish as a suggestion.

05Data Model and Access Paths

Keep the text, its popularity and the block decision separate. A term ID identifies one stored phrase; a build number identifies one prepared ranking. The suggestion handler uses those IDs to look up data, rather than treating every saved copy as current policy.

• The count worker counts completed searches within a stated interval, such as the last hour, with a longer-term fallback. Otherwise old lifetime popularity could dominate forever.
• The count store also retains processed event IDs for as long as those events can be retried or replayed. The worker saves “event counted” and the count change together, so a retry cannot add the same completed search twice.
• The index builder reads those counts and prepares the prefix records. A prefix record stores several possible answers, called candidates, not just the number the browser displays.
• The policy store records which term IDs are currently blocked. The suggestion handler checks it after loading candidates from either memory or a cache.

06Baseline: Start with a prefix index

First make one server answer ca correctly. A small vocabulary can begin as a database table: select terms starting with ca, sort them by popularity and take the first results. A limit of three bounds the answer size, but the database may still inspect and sort many matches.

A trie stores characters along branching paths. Following the c branch and then a reaches the node for ca. Prepare a short ranked list there so the handler does not search every descendant on each keystroke.

Prepare the server

1. The builder reads the saved terms and counts: car 50, cat 30, camera 20, cart 10 and dog 40.
2. It places car, cat, camera and cart under ca, ordered by score. Dog is absent because it does not start with ca.
3. Before publishing the prepared index, the builder checks known prefix queries, score order, expected vocabulary coverage and memory size. The server loads that completed build into memory. Requests only read it; they do not change its branches or scores. This is an immutable index.

Handle one browser lookup

1. The suggestion handler reads ca from the browser’s request and follows c, then a in memory.
2. It loads [car:50, cat:30, camera:20, cart:10] from that node.
3. It asks the current block policy which of those term IDs may be returned. If car is blocked, it removes car.
4. It returns cat, camera and cart, plus the prefix ca. Keeping cart as a reserve lets filtering still produce three answers.
5. The browser compares the response prefix with its current input. It displays the list only if the input is still ca.

If the node stored only three candidates, removing car would leave only cat and camera. The handler must return two or consult another candidate source; it cannot guess that cart is fourth. A compressed trie can combine nonbranching character paths to save memory, but needs more involved construction.

07Evolution: Split updates from serving

Change the part that reaches its measured limit. A larger machine may hold more index data and serve more lookups, but still needs an independent recovery copy.

When one server cannot serve enough lookups

1. Run several suggestion servers behind a load balancer. Give each the complete small index, so one browser lookup reaches one server rather than contacting many data partitions.
2. Run the builder separately from those handlers. To add camera’s 50 new searches, it reads updated counts, computes 20 + 50 = 70 and prepares a replacement build.
3. Validate the replacement and save it in version storage. Each serving process switches from build 41 to 42 only after the new copy is ready; reads already using 41 finish there. Keep the previous valid build for rollback and budget both copies in memory.

When update collection or repeated prefixes add unnecessary work

1. The completed-search collector saves events in a durable log: a retained sequence of records the count worker can read again after a crash. This lets collection and counting run at different speeds without losing accepted updates.
2. For each event, the count worker checks its stored processed-event ID. A matching retry is skipped; a new ID updates the window’s count and is marked processed in the same transaction. This is deduplication: recognize repeated delivery before repeating its effect.
3. The builder uses those counts for the next ranking. Camera can move ahead of car and cat when that build is installed; current blocking still happens on every lookup, independently of the build.
4. Cache frequent candidate lists under (locale,prefix,version). A cache hit saves index work, but the handler must still run the current block check.

Do not assume c and z receive equal traffic. Replicate very popular short prefixes when useful. Personalization would need additional user data and a bounded scoring step; the shared popularity index alone does not supply it.

08Failure and Recovery Scenarios

Test the basic lookup before adding these failures:

1. The browser receives replies in the wrong order. It sent ca, then cat, but the ca reply arrives last. Browser code checks the echoed prefix and ignores that reply; arrival time does not make it the newest input.
2. The builder fails. Serving processes continue reading the last validated build. Operators measure its age and alert when the minute freshness target is missed. For example, a build that unexpectedly loses the saved vocabulary must fail the coverage check even if its file format is readable.
3. An older build arrives late. A serving process already using 43 rejects installation of 42. Compare build numbers before changing the active index, so delayed work cannot reverse a newer publication.
4. The block check is unavailable. The handler cannot prove which candidates are permitted. It omits unchecked suggestions instead of returning a previously allowed list. This protects the removal rule at the cost of some availability.
5. A deletion must remove stored history. Blocking a response does not erase saved events or old index builds. The retention process must remove the required copies as well and verify that it did so.

09Trade-offs and Validation

The design spends memory and build work before a request, so the suggestion handler reads a short list after each typing pause. That fits a shared popularity ranking. Arbitrary filters or a unique ranking over millions of terms would require a different candidate plan.

• Check response speed: measure service p95/p99 and the extra wait the browser adds before sending. Break results down by language and prefix length; one-character prefixes can be much busier.
• Check update progress: record the installed build number, build age, completed-search delay and memory during replacement.
• Check correctness: count blocked terms returned, prefix mismatches and answers shortened by filtering. A high cache hit rate cannot excuse a forbidden term.
• Check usefulness: measure accepted suggestions with controlled ranking experiments. Higher positions receive more clicks even without better relevance.

Close by explaining the ca lookup, the blocked car and the late browser reply. Spelling correction needs a way to generate nearby words; document retrieval needs a separate result index. A trie supplies neither automatically.