System Design: [Search autocomplete name]

Reference design for search typeahead (autocomplete): as the user types, the service returns the most useful completions for the prefix within tens of milliseconds. It covers prefix indexes (trie, finite state transducer, edge n-grams), ranking by popularity and recency, the data pipeline from query logs, edge caching, the latency budget, personalisation and abuse filtering. It follows the structure of the System Design Document template and is pre-filled with a worked design to adapt. Values marked Example are assumptions: replace them and recompute.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Today suggestions come from a LIKE 'prefix%' query on the product database. p99 is 380 ms, suggestions are alphabetical rather than useful, breaking news terms take a day to appear, and last month an offensive suggestion was screenshotted and shared widely.]

1.2 Proposed solution

[Example: An offline pipeline aggregates anonymised query logs hourly into scored suggestions, filters them against policy lists, and builds an immutable in-memory prefix index (a trie with the top completions cached at each node). Suggest servers load the index and answer prefix requests in under 5 ms. A streaming layer adds trending queries within minutes. Responses for short, popular prefixes are cached at the CDN edge for 5 minutes. Personal recent searches are blended in on the client from local history.]

1.3 Decisions requested from reviewers

2. Requirements

2.1 Functional requirements

2.2 Non-functional requirements

2.3 Out of scope

• [Example: the search results page itself]
• [Example: rich entity cards in the dropdown]
• [Example: voice query suggestions]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Request rate

Origin load after the edge cache:

3.3 Index size

Prefix nodes:

With a top-10 list of 4-byte suggestion IDs (40 B) plus about 24 B of node structure:

plus suggestion strings and scores ($2 \times 10^{7} \times 32$ B $\approx 0.64$ GB), about 8.3 GB per replica. Each suggest server holds a full replica, so no cross-node calls are needed on the request path.

3.4 Pipeline volume

3.5 Summary

4. API design

4.1 Endpoints

4.2 Request and response examples

The prefix is normalised (case-folded, whitespace collapsed) on the client and the server so cache keys match:

GET /v1/suggest?q=wint&locale=en-GB&n=8 HTTP/1.1

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: public, max-age=300
Vary: Accept-Encoding

{"q": "wint", "indexVersion": "2026-03-14T09", "suggestions": [{"text": "winter coats", "kind": "query"}, {"text": "winter tyres", "kind": "query"}, {"text": "winter olympics schedule", "kind": "trending"}]}

4.3 Errors and limits

Clients treat any error or a response slower than 300 ms as "no suggestions"; typing is never blocked.

5. Data model

5.1 Entities

The pipeline turns raw query events into scored suggestions; an index build packages them for serving.

5.2 Storage choices

6. High-level design

The serving path is read-only and in memory; all heavy work happens in the pipeline.

7. Detailed design

7.1 Prefix index options

The trie stores, at each node, the IDs of the 10 highest-scoring suggestions in its subtree, computed bottom-up during the build. A lookup walks the prefix and returns that list without exploring the subtree.

7.2 Ranking

Base score for query $x$ in locale $\ell$ uses exponentially decayed daily counts with half-life $h$ (Example: 7 days):

At serve time, the trending layer adds a boost when the last window greatly exceeds the expected rate:

where $\mu$ is the average 5-minute count over the last 7 days. A query seen 16 times more than usual gets a boost of about 4 score units; the weight of the boost against $S$ is tuned with online experiments. Final order also applies diversity (no more than 3 suggestions sharing the same first two words).

7.3 Data pipeline

Servers keep the previous version in memory until the new one passes a self-test, so a bad build never serves.

7.4 Suggest request (critical path) and caching

Short prefixes are the most requested and the least personal, so they are cached at the edge; longer prefixes go to origin.

Clients also keep a small in-memory cache: if "win" returned 10 results and the user types "wint", the client can filter locally while the request is in flight.

7.5 Personalisation

Personal recent searches stay on the device (local storage, last 50 entries, user-clearable) and are blended on the client by prefix match, which keeps edge responses cacheable and avoids server-side profiles. Signed-in users may opt in to sync history; synced history is encrypted at rest, deletable, and never used to train global suggestions.

7.6 Abuse and safety filtering

• Block rules: exact terms, patterns and entity lists maintained by the policy team; applied in the pipeline and again at serve time so a new rule takes effect within the 10-minute rule-sync interval without a rebuild.
• Manipulation: coordinated query injection is limited by the distinct-user threshold, bot filtering and caps on the trending boost per source network.
• Privacy: the threshold and PII detectors prevent rare personal queries (names with addresses, account numbers) from becoming suggestions.

7.7 Consistency model

All servers converge on the same index version within one publish cycle; during rollout two versions may serve for up to 10 minutes, which users cannot notice. Block-rule removals are the only change with a hard deadline (FR-07) and are pushed separately from index builds.

8. Scalability and performance

Latency budget, keystroke to rendered suggestions (target p95 100 ms):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security, privacy and abuse

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: A/B test against the old endpoint for 2 weeks per locale. Rollback flips the client config back to the old endpoint; index rollback pins servers to a previous version.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on common industry practice for search autocomplete design and on the HTTP specifications cited in 12.3. This is a reference design to adapt, with illustrative numbers. Original text written for this collection. Template licence: MIT.